资源受限项目调度问题的改进文化微粒群算法求解何立华

格式：pdf
大小：583.30 KB
文档页数：4

下载文档原格式

并行机调度问题粒子群优化研究

：ｓｕ凡ｓｅｅＰｒａｃｅｅｃｈｔｒｅｍｎ．ｑｅａｂｔｅ
：
ｊ
ｎ… … …
：
！
ＫｙｗｒｓＰｒｃａｍｏｔｚｔｎａｏｉｍ；ａａｅｍａｈｅｃｅｕｎ；ａｔｌｐｓｊｅｏｄ：ａｔｌｓｒｐｉａｉｌｒｈＰｒｌｌｃｉｈｄｌｇＰｒｃｏｉｉｅｗｍｉｏｇｔｌｎｓｉｉｅ－；
时间，如果不考虑工件的准备时间，么，那所有工件的最大完工时对于并行机调度问题，其可行解的前提条件是必须保证每间的计算方法为：首先分别计算分配在各机器上的工件的加工时
台机器都被分配工件进行加工，此基础上，所有工件的任意间的总和，在对然后取各机器上加工时间总和最大者即为所有工件的分配都可行形成一个可行调度解。最大完工时间，Ｍｋｓａ。即ａｅｐｎ
粒子群算法（ａｉｅｗｒｐｉｚｔｎ简称ＰＯ）ＰｒｃａｍＯｔａｉ，ｔｌＳｍｉｏＳ是一种
台机器上加工各工件之间的准备时间，ｔ用，表示工件ｉ的加工
Ｇ表示该工件基于群体智能的进化类算法一经提出便得到较为广泛的应用，时问，表示加工过程中该工件等待加工的时间，，
ＬＩＺｈ－ｉｎｇ’ Ｕｉｘｏ ’ ：
（ＣｌｇｆＭａｈｎｒｎｕｏｔｎＷｕａｉｅｓｔｆｃｅｃｎｅｈｏｏｙ，ｈｎ４０８，ｈｎ）ｏｌｅｏｃｉｅａｄＡｔｍａｉ，ｈｎＵｎｖｒｉｏｉｎｅａｄＴｃｎｌｇＷｕａ３０ＣｉａｅｙｏｙＳ１

基于非线性规划的微粒群算法研究

第２卷第９７期
文章编号：０６— ３８２１）９— ２２— ３１０９４（００００１０
计
算Leabharlann 机仿真２０月０年９１
基于非线性规划的微粒群算法研究
何志华
（成都大学信息科学与技术学院，四川成都６００）１１６
摘要：在工程中，寻求复杂的带约束条件的非线形规划的最优解一直是一个难点，需要一种功能强大的算法，而微粒群算法
（Ｓ）ＰＯ有这样的特点。ＰＯ的代码和参数很少，Ｓ概念简单，实现容易，随机简便，收敛性良好。目前，ＳＰＯ的参数的控制和调整主要依赖于经验确定，不同参数的选择可能导致算法收敛加快或变慢，甚至不收敛；另外，需要对ＰＯ不断进行改进以得Ｓ到良好的收敛性。为此，ＰＯ来求解带约束条件的非线形规划问题，用Ｓ通过仿真实验对参数进行适当调整和算法分析，并引入收缩因子对算法改进，研究其对收敛速度的影响。计算机仿真实验表明对参数进行合理的调整，可使收敛速度明显加快，
ＮｏｌｎｒＰｒｇａｍｉｇＰｒｂｅｎｉｅｏｒｍｎｏｌｍ
ＨＥＺｈ —ｈａｉｕ
（ｅａｔｅｔｆｏｕｅＳｉｃｎｅｈｎｇ．ＣｅｇｕＵｉｅｉ，ｈｎｄｉｕｎ６００，Ｃｉａ）ＤｐｒｎｏＣｍｐｔｒｃｎｅａｄＴｃｏｌｙｈｎｄｎｖｒｔＣｅｇｕＳｈａ１１６ｈｎｍｅｏｓｙｃ
ＩｅｔｏｆｔｅｐａｒｉｏａｐｌＯｏｎｎｉａｏａｎｔｎｉｎｏｈｐｅｓｔｐｙＰＳｔｏｌｎｅｒｐｒｇｍｍｉｇｐｏｌｍｔｅｔｃｉｎｎｎｔｏｕｃｈｏｒｃｉｇｒｎｒｂｅｗｉｈｒｓｒｔｏａｄｉｒｄｅｔｅｃｎｔａｔｎｉ

基于云多目标微粒群算法的多项目调度方法

N
)
(2)
目标函数 2：
N pinum E
∑ ∑ ∑ min PC =
esalary k
⋅yijk
⋅
a dur ij
(3)
i =1 j =1 k =1
此外，在求解该问题的过程中，还需考虑以下这些约束条
件：
约束条件 1：每项任务至少需分配 1 名员工。
E
∑ uijk
≥1
∀i ∈ (i = 1,.., N ),
pi (i
= 1, 2..., N )
需并行执行，
p num i
表示项目
N
∑ pi 的任务总数，则 N 个项目的任务总数 M =
p num i
， aij
表示
i =1
第 i 个项目中的第 j 项任务，每项任务有不同的技能
基金项目：国家自然科学基金(the National Natural Science Foundation of China under Grant No.70871111) 作者简介：郭研，男（汉），浙江宁波人，博士研究生，讲师，研究方向：工程与项目管理；李南，女（汉），教授，博士生导师，研究方向：管理科学与工程、项目管理；李兴森，男（汉），山东沂水人，博士，教授，研究方向：知识管理与数据挖掘
本文在深入研究多技能员工受限的多项目调度问题的基础上，建立了以项目群的总工期和总费用最小为目标的调度模型。在算法设计上，我们云模型[9]嵌入到 VEPSO-BP [10]中，提出了
一种新的云多目标微粒群算法(CMOPSO)。CMOPSO 将只适用于单目标优化问题的云自适应微粒群算法[9]扩展到多目标优化
CMOPSO 的性能，并与 VEPSO-BP 进行了对比；实验结果表明 CMOPSO 能取得更为丰富且优化效果更好的 Pareto 非支配解。

不确定资源约束下项目鲁棒性调度算法

不确定资源约束下项目鲁棒性调度算法
张宏国;徐晓飞;战德臣
【期刊名称】《计算机应用研究》
【年(卷),期】2009(026)006
【摘要】在跨企业项目中,由于资源可用时间具有不确定性,从而使得项目计划具有易变性.针对这一问题,首先采用模糊集对项目的不精确时间参数和资源不确定性进行了表示,并在同时考虑调度的质量鲁棒性和解的鲁棒性情况下,定义了调度的鲁棒性度量,进而开发了遗传算法来求解不确定资源约束下的项目鲁棒性调度问题.最后,给出了应用实例,并通过仿真分析说明算法的有效性.该算法已被应用到跨企业项目管理系统中,获得了良好的效果.
【总页数】5页(P2079-2082,2089)
【作者】张宏国;徐晓飞;战德臣
【作者单位】哈尔滨工业大学,计算机科学与技术学院,哈尔滨,150001;哈尔滨工业大学,计算机科学与技术学院,哈尔滨,150001;哈尔滨工业大学,计算机科学与技术学院,哈尔滨,150001
【正文语种】中文
【中图分类】TP391
【相关文献】
1.求解不确定资源约束下的模糊调度算法 [J], 陈志强;张宏国
2.资源约束下多项目再调度算法 [J], 李丹;张宏国
3.随机工期下基于可更新资源约束的Max-npv项目鲁棒性调度优化 [J], 郑维博;何正文;刘人境
4.不确定周期约束下项目调度算法 [J], 张宏国;杜雷;谢璟琦
5.资源不确定环境下模具多项目预测-反应式调度算法 [J], 张沙清;陈新度;陈庆新;陈新
因版权原因，仅展示原文概要，查看原文内容请购买。

港口泊位调度问题的粒子群优化研究

对该粒子中的粒子位置进行取整操作，可以得到各船舶的泊位分配情况，如表 3 所示。
船舶泊位
表 3 解码后每艘船舶的泊位分配 12345678 13221332
9 10 21
于是，就可以得到每个泊位上的船舶作业顺序，即如表 4 所示。
泊位 1 2 3
表 4 泊位分配结果
船舶 1，5，10 3，4，8，9 2，6，7
保证所生成的泊位调度解的可行性，提出了一种针对粒子编码的修正方法。针对港口船舶作业实际数据，采用粒子群
算法进行了计算，并与实际泊位调度结果进行了比较。计算结果说明粒子群算法能够有效地优化港口泊位调度问题。
【关键词】港口；泊位调度；建模；粒子群算法；粒子编码
【中图分类号】 TP39； U692
3 粒子群算法设计
3． 1 粒子群算法
在粒子群算法中，所有粒子都有一个由被优化的函数决
定的适应值，每个粒子还有一个速度决定它们搜索的方向和
距离，所有粒子通过追随当前的最优粒子（个体最优粒子和全
局最优粒子）在解空间中进行搜索。假设粒子群中的第 i 个
粒子在 n 维空间中的位置表示为一个 n 维向量 xi = （ xi1 ，xi2 ， …，xij ，…xin ），速度 vi = （ vi1 ，vi2 ，…，vij ，…vin ）决定了粒子在搜索空间单次迭代的位移。当前粒子群中的个体最优粒子表
2． Tianjin Port （ Group） Co．，LTD Postdoctoral Research Center，Tianjin 300461，China）
【Abstract】Berth planning and scheduling has an important effect on making harbor of the vessels and particle swarm optimization algorithm is employed to optimize the berth scheduling problem． The model of berth scheduling problem is made and the two － dimension particle encoding method based on the vessel and the particle position rounding is introduced according to the character of the berth scheduling problem． To assure that the generated berth schedule solution after decoding is feasible，a kind of revising approach for the particle encoding is presented． Particle swarm optimization algorithm is applied to the practical data of the port operation and compared with the practical berth schedule solution． Computational results show that particle swarm optimization algorithm can effectively optimize the berth scheduling problem．

融合粒子群与改进蚁群算法的AUV路径规划算法

2021576海洋资源已经成为人类开发的重点，但复杂的海洋环境对人类水下作业有着极大的限制，水下机器人正在成为海洋作业的主角，自主式水下机器人（Autono-mous Underwater Vehicle，AUV）依靠自身携带的能源进行水下作业。

由于在整个过程中无法补充能源，因此利用路径规划与安全避障技术对AUV导航控制，是其能否精确、安全和完整地完成水下作业的关键。

AUV 路径规划问题已经成为了一个研究热点[1]，主要涉及两方面问题：一是对海洋环境进行三维建模；二是选取合适的算法进行全局路径规划。

海洋环境建模主要有两类方法：一类是规则地形模型，主要利用正方形、矩形等规则形状进行组合来表示海底表面；另一类是不规则地形模型，将三角形、多边形等不规则形状作为模型单元的基础[2]。

文献[3]使用Voronoi图法简化三维水下环境，生成全局路线图；文献[4]将Delaunay三角模型应用于被测地标，建立拓扑模型。

文献[5]利用八叉树模型来反映AUV工作环境，但主要应用于较大障碍物之间的路径规划，不适合存在许多小障碍物的环境；文献[6-7]不考虑水深，将三维空间简化为二维栅格模型，节省了空间，但却丢失了环境信息；文献[8-9]将三维空间划分为若干平面，然后利用二维栅格模型将每个平面栅格化，有效实现三维栅格建融合粒子群与改进蚁群算法的AUV路径规划算法朱佳莹，高茂庭上海海事大学信息工程学院，上海201306摘要：针对传统蚁群算法在处理自主式水下机器人AUV（Autonomous Underwater Vehicle）三维路径规划问题时存在初期寻径能力弱、算法收敛速度慢等问题，提出一种融合粒子群与改进蚁群算法的AUV路径规划算法PSO-ACO（Particle Swarm Optimization-improved Ant Colony Optimization）。

基于空间分层思想建立三维栅格模型实现水下环境建模；综合考虑路径长度、崎岖性、危险性等因素建立路径评价模型；先使用粒子群算法预搜索路径来优化蚁群算法的初始信息素；再对蚁群算法改进状态转移规则、信息素更新方式并加入奖惩机制实现全局路径规划。

应用改进蚁群算法求解柔性作业车间调度问题

应用改进蚁群算法求解柔性作业车间调度问题
刘志勇，吕文阁，谢庆华，明玉，何杰，刘雄辉
（东工业大学机电工程学院，东州５００）广广１０６
摘要：将蚁群算法信息素更新规则进行改进，规定只有产生至今最优解的蚂蚁才能释放信息素，只更新全局信息素，少了传统蚁群算法的时间复杂度，高了问题的求解效率。分析了柔且减提性作业车间调度的特点，选取三个性能指标作为求解目标，定其求解优先级，设并建立相应的调度
ｃａａｔｒｓｉｏｅｉｌｏ — ｈｐＳｈｄｌｇＰｒｂｅｈｒｃｅｉｔｃｆＦｌｘｂｅＪｂｓｏｃｅｕｉｏｌｍｓ（ＪＰ）ｈｐｉｒｔｆｔｒｅｏｊｃｎＦＳ，ｔｅｒｏｉｏｈｅｂｅｔｙ
中图分类号：０２；３１６２４ＴＰ０．文献标识码：Ａ
ＳｌｉｇＦｅｉｌｏ —ｈｐＳｈｄｌｎｒｂｅＢａｅｎａｏｖｎｌｘｂｅＪｂｓｏｃｅｕｉｇＰｏｌｍｓｄｏｎ
Ｉｐ杨ｖｄＡｎｔＣｏｏｙＯｐｉｉａｉｎＡｌｏｉｈｍｒ广ｏｅｌｎｔｍｚｔｏｇｒｔｍ
．
ｔｏｐｅｉｙｅｓｎｄｉｍｅｃｍｌｘｔｌｓｅｅｍａｋｄｙｎｓａｃｅｆｉｎｙｎａｃｄｂｉｕｌ．Ｂａｅｏｔｅｒｅｌａｄｅｒｈｆｉｅｃｅｈｎｅｏｖｏｓｙｃｓｄｎｈ

应急资源调度问题的改进进化规划算法研究

ＡｂｔａｔＡｍｕｔ—ｅｏｃｔｍｅｃｓｍｏｅｉｐｏｏｅｏｈｐｏｌｍｏｍｅｇｎｙｅｏｒｅｓｈｄｌｎ．ｓｒｃ：ｌｒｓｕｒｅｉ — ｏｔｉｄｌｓｒｐｓｄｆｒｔｅｒｂｅｆｅｒｅｃｒｓｕｃｓｃｅｕｉｇ
ｓａｅｙｏｏｕａｉｖｌｔｎｏｉｒｖｄｅｏｕｉａｙｐｏｒｍｍｎＥ）ＡｘｅｉｅｔａｅｎｄｎｒｔｔｇｆｐｌｔｎｅｏｉｆｍｐｏｅｖｌｔｎｒｒｇａｉｇＰ．ｎｅｐｒｎｈｓｂｅｏｅｆｒｐｏｕｏｏｆＩｍｏａ
汪勇，金菲
（汉科技大学管理学院，湖北武汉４０８）武３０１
摘
要：对应急资源调度问题，立一种多资源时间一本调度模型。设计了进化规划算法的全局变异算子和针建成
局部变异算子，据全局变异前后个体适应度值和分量值的变化趋势，现定向变异。构建了具有惩罚系数的根实适应度函数，出了改进的进化规划算法种群进化策略。计算实验表明，进的进化规划算法具有较强的局部给改
ｓｔｏａａｉａｌｂ，ａｄｔｅｒｓｌｓｓｏｔｔｔｅｍｏｅｓｅｓｏｃｌｕａｅ，ａｄＩｓｐｏｉｅｔｔｏｇｒｅｆｄｔｎＭｔａｎｈｅｕｔｈｗｈａｈｄｌｉａｙｔａｃｌｔｎＥＰｉｒｖｄｄｗｉｈｓａｏｎｏａｔｔｎｏｅａｏｆｅｏｕｉｎｒｒｇａｍｉｇａｅｄｓｇｅｏａｔｔｏｐｒｔｒａｄｌｃｌｍｕａｉｐｒｔｒｏｖｌｔａｙｐｏｒｍｏｏｎｒｅｉｎｄ，ａｄｌｃｌｍｕａｎｏａｔ —

基于文化粒子群算法的水库发电调度图绘制

Ａｂｓｒｔｔａｃ：Ｔｈｅｄｒｗｉｇｏｏｎｅｔｏｌｇｎｒｔｏｃｅｌｎｇｃｒｓｃｎｓｒｉｄｙｉｔｄｈｒｌｇａｐｅｄｔｉｌａｎｆｃｖｎｉｎａｅｅａｉｎｓｈｄｕｉｈａｔｉｏｔａｎｅｂｌｍｉｅｙｄｏｏｙｓｍｌｓａｎｙｐｃａ
Ｕｉｒｉｅｉｇ１２０；．ｅｉｇＨｕｄａｉｄｃｎｅａｋＣ．Ｌｄ，ｅｉｇ１２０）ｎｖｓｙＢｉｎ０２６２ＢｉｎａｉＴａｅＳｉｃｒｏｔ．Ｂｉｎ０２６ｅｔｊｊｎｎｅＰ，ｊ
第３６卷第１期
２１００年１月
水力发电
基于文化粒子群算法的水库
发电调度图绘制
杨子俊，王丽萍，谢维，方婧，喻杉
（．１华北电力大学水资源与水利水电工程研究所，北京１２０；０２６
２北京华电天德科技园有限公司．北京．
的思想中孕育而生Ｉ文化算法包含微观层面上的由７ｌ
直倍受关注＿３具有年和季调节性能的水电站，其ｌ１＿
发电调度图绘制的常规方法是基于满足设计保证率
具体个体组成的种群空间和宏观层面上的由进化过程中获取的知识及经验组成的信仰空间咧这两个空间
ｃｎｅｔｎｌｔｏｎａｅｕｅｒｍｅｉｍｎｏｇｔｒｏｅａｉｎｏｔｚｔｎｏｙｒｐｗｒｓａｉｎｏｖｎｉａｈｄａｄｃｎｂｓｄｆｄｕａｄｌｎ — ｅｍｐｒｔｐｉａｉｆｄｏｏｅｔｔ．ｏｍｅｏｏｍｉｏｈｏ

不确定多项目选址问题的微粒群优化算法

∑
J j =1 ij
x = 1. ,K
(3)
s.t
μc ( X ) = ∑ m =1, m ≠ p β m μc , m ( X ) = 1
K
(5)
p − 1, p + 1,
∑
I i =1
xij ≤ 1,
∑
K
J j =1
xij = 1,
其中， bm 为对于指标 f m 所选方案应得到的最低效益值。
0 ≤ β m ≤ 1,
intervalconstraint引言1多目标选址问题是实际工程中普遍存在的一类组合优化问题其目的是在保证某些评价指标同时最优的基础上为多个服务设施或工厂在指定区域内选定它们的位置如废弃物回收设施选择问题1无线通讯网基站的选址2等
第 21 卷第 23 期 2009 年 12 月
系统仿真学报© Journal of System Simulation
• 7464 •
第 21 卷第 23 期 2009 年 12 月
张勇，等：不确定多项目选址问题的微粒群优化算法
Vol. 21 No. 23 Dec., 2009
置 s j 时 f k 所对应指标 ( 或收益 ) 值的范围已知，为区间数
k k k 关于指标 f k 的收益矩阵为 Ak = ( aij aij = [ aij , aijk ] ； ) I ×J 。决策
Abstract: Aiming at a multi-project location problem with uncertainty that the benefit values are intervals, firstly the multi-objective optimization model with interval parameters was converted into a certain single optimization proposition by defining a satisfaction metric and a solving method for constraints. Secondly, the particle swarm optimization algorithm was applied to solve the above model, based on that such continuity of discrete variables, normalization and decoding of particle positions as key problems were solved successfully. Finally, the feasibility of the deterministic model and the efficiency of the proposed algorithm were validated by optimizing an eight-project and ten-site location problem. Key words: multi-project location problems; uncertainty; particle swarm optimization; interval constraint

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

群算法。该算法框架基于微粒群算法的主群体空间和文化算法的知识空间，两种空间具有各自的群体并可独立并行演化，形成双演化双促进机制，提高了算法的全局搜索能力和运行效率。同时为了避免文化算法知识空间引入遗传算法的演化机制来改进知识空间的演化操作。通过具体的算例比较，验证了提出的改自我演化限制，进文化微粒群算法在求解资源受限项目问题时的有效性。关键词：文化微粒群算法；资源受限项目调度问题；知识空间；主群体空间中图分类号： TP18 ； TP301. 6 文献标志码： A 文章编号： 1001-3695 （ 2013 ） 01-0090-04 doi： 10． 3969 / j． issn． 1001-3695． 2013． 01． 021
Improved cultural particle swarm optimization algorithm for solving resourceconstrained project scheduling problem
2 HE Lihua1，，SUN Xiaosen2 ，ZHANG Lianying1
第 30 卷第 1 期 2013 年 1 月
计算机应用研究 Application Research of Computers
Vol. 30 No. 1 Jan． 2013
资源受限项目调度问题的改进文化微粒群算法求解
1， 2 2 1 何立华，孙晓森，张连营
*
（ 1．天津大学管理与经济学部，天津 300072 ； 2．中国石油大学（华东）经济管理学院，山东青岛 266580 ）摘要：为了克服标准微粒群算法在求解资源受限项目调度问题上存在的早熟现象，提出一种改进的文化微粒
［7 ， 8 ］［9 ］、、微粒群算法蚁群算法等。在以上算微粒群算法是一种应用在 RCPSP 上比较成功的群智能法中，算法。传统的微粒群算法在求解 RCPSP 时，由于算法自身的［5 ， 6 ］
遗传算法的种群演化机制来改进知识空间的自我演化机制，使其在求解 RCPSP 时可以减少粒子过早陷入局部最优的概率，能较好地解决 RCPSP。
（ 1 ． School of Management ＆ Economics，Tianjin University，Tianjin 300072 ，China； 2 ． School of Economics ＆ Management，China University of Petroleum （ East China），Qingdao Shandong 266580 ，China）
Abstract： In order to overcome the premature phenomen of standard particle swarm optimization （ PSO ） for solving RCPSP， this paper proposed an improved cultural particle swarm optimization （ ICPSO ） algorithm． The framework of the proposed algorithm was based on the main population space of the PSO and the knowledge space of the cultural algorithm（ CA），where two spaces having respective groups as well as evolving independently，and formed the mechanism of “double evolution，double ． At the same time， in order to avoid the restriction of selfevolving by the knowledge space of the CA， it introduced promotion ” the evolutinary mechanism of the genetic algorithm （ GA ） into the knowledge space to improve its evolutionary operations． A specific comparing example verifies the validity of the ICPSO for solving the RCPSP． Key words： cultural particle swarm optimization（ CPSO） algorithm； resourceconstrained project scheduling problem （ RCPSP）； knowledge space； main population space
1
经典资源受限项目调度问题
经典资源受限项目调度问题可以描述为
［11 ］
：项目中有一
系列的工作，它们之间存在着时序约束，每个工作都对应一组确定已知的持续时间和资源需求量，该问题的求解是在满足工作的紧前关系约束和资源约束条件下生成一种使项目工期最短的最优调度方案。经典 RCPSP 的模型一般基于以下几个假设条件： a）项目中的工作数目 J 确定； b ）各工作只允许有一种且该执行模式不具有抢先权； c ）工作间的紧前、紧执行模式，后约束关系确定； d）各工作执行过程中需多种可更新资源，且每种资源在各阶段的需求量和供应量确定； e ）各工作的执行只受可更新资源约束。基于以上假设，设单项目中共含有 J 个工作，设 ST j 为工 2， …， J）， d j 表示工作 j 的执行时间（ j = 作 j 的开始时间（ j = 1 ，
资源受限项目调度（ RCPSP ）是在满足项目紧前约束与资通过安排项目所有任务的开工时间达到最小源约束的前提下， hard 问题［1］，化项目总工期的目的。RCPSP 是一个典型的 NP自 20 世纪 50 年代以来，一直都备受学者的关注，他们对 RCPSP 进行了大量的研究并取得了很多成果。在 RCPSP 的求解从精确解法到满意解，从线性规划、非线性规包括遗传算法到分支定界法直至现在的启发式算法，模拟退火算法