轻松掌握甘特图制作技巧,助力项目管理高效运作
759
2022-10-10
numbers甘特图(numbers甘特图制作教程)
本文目录一览:
基于动态双种群粒子群
算法的柔性工作车间调度
摘 要: 针对标准粒子群优化算法存在易陷入局部最优点的缺点,提出了一种基于动态双种群的粒子群
优化算法(DPSO) ·DPSO 算法将种群划分成两个种群规模随进化过程不断变化的子种群,两个子种群分别采
用不同的学习策略进行进化,并在进化过程中相互交换信息·该算法提高了全局寻优能力,有效地避免了早熟
收敛的发生·将以DPSO 算法为基础的排序算法和启发式分配算法(HA) 相结合形成了解决柔性工作车间调
度问题的新方法(DPSO2HA) ·通过对算例的研究和与其他方法的比较表明,该方法是有效可行的·
A Dynamic Double2Population Particle Swarm Optimization
Algorithm for Flexible Job2Shop Scheduling
L I Dan , GA O L i2qun , MA Jia , L I Yang
( School of Information Science Engineering , Northeastern University , Shenyang 110004 , China.
Correspondent : L I Dan , E2mail : lidanneu @163. com)
Abstract : A dynamic double2population particle swarm optimization ( DPSO) algorithm is
presented to solve the problem that the standard PSO algorithm is easy to fall into a locally
optimized point , where the population is divided into two sub2populations varying with their own
evolutionary learning st rategies and the information exchange between them. The algorithm thus
improves it s solvability for global optimization to avoid effectively the precocious convergence.
Then , an ordering algorithm based on DPSO is integrated with the heuristic assignation ( HA)
algorithm to form a new algorithm DPSO2HA so as to solve the flexible job2shop scheduling
problem (FJ SP) . The new algorithm is applied to a set of benchmark problems as instances , and
the simulation result s show the effectiveness and feasibility of DPSO2HA algorithm for the flexible
job2shop scheduling.
Key words : double population ; PSO(particle swarm optimization) ; learning st rategy ; DPSO2HA
algorithm; flexible job2shop scheduling
柔性工作车间调度问题( flexible job2shop
scheduling problem , FJ SP) 是经典工作车间调度
问题的一个延伸,它允许工件被给定的有处理能
力的任何机器处理·柔性工作车间调度问题由于
减少了机器约束,扩大了可行解的搜索范围,提高
了问题的复杂性,所以与传统工作车间调度问题
相比更加接近实际生产环境的模拟·
相对于传统工作车间调度,关于柔性工作车
间调度问题的文献还比较少·目前所采用的方法
主要有分枝定界法[1 ] 、多项式算法、分等级法和
传统进化算法( EA) [2 ]等,在近几年中,很多研究
者使用禁忌搜索和遗传算法对FJ SP 进行求
解[3 - 4 ]
·
本文提出一个新的求解柔性工作车间调度问
题的方法———基于动态双种群粒子群优化的分阶
段方法·本方法的主要思想是:将柔性工作车间调
度问题分解成两个有时间顺序的子问题来考虑,
首先考虑工序排序子问题,在获得可行的排序后
再考虑机器分配子问题·本文首先利用动态双种
群粒子群优化算法为工序进行排序,使其满足约
束条件从而获得一个可行解,然后利用文中所提
出的分配算法为每道工序分配合适的机器,形成
可行的调度方案·本文所考虑的优化目标是最小
化最大完工时间(makespan) ·
1 柔性工作车间调度问题描述
柔性工作车间调度问题可描述为将n 个加工
顺序不同的工件在m 台机器上加工完成·每个工
件使用同一台机器可以多于一次,每道工序的加工
过程不允许中断·机器的集合用U 来表示,每个工
件J 包含nj 道工序,各工序之间的顺序不允许改
变·Oij表示工件J 的第i 道工序,它可以在有处理
能力的任何一台机器上被加工·Ti , j , k表示工序Oij
用机器Mk 来加工所需要的时间, 可用集合T =
{ Ti , j , k| 1 ≤j ≤N ;1 ≤i ≤nj ;1 ≤k ≤M}表示, N 为
工件的数量, M 为机器的数量·例如表1 即是一个
实际的柔性工作车间调度加工时间表·
表1 柔性工作车间调度加工时间表
Table 1 Proce ssing schedule for FJ SP
工件工序M1 M2 M3 M4
J1
O1 ,1 1 3 4 1
O2 ,1 3 8 2 1
O3 ,1 3 5 4 7
J2
O1 ,2 4 1 1 4
O2 ,2 2 3 9 3
O3 ,2 9 1 2 2
J3
O1 ,3 8 6 3 5
O2 ,3 4 5 8 1
在柔性工作车间调度问题中, 应满足以下假
设:
(1) 所有的机器在时间t = 0 时都是可以使
用的,每个工件都可以在t = 0 时开始加工;
(2) 在给定的时间内, 一台机器只能加工一
道工序,直到加工完此工序后方可加工其他工序,
这就是所谓的资源约束;
(3) 对于每个工件的各道工序只能按照事先
给定的顺序加工,这就是所谓的优先约束·
对于每一道工序Oi , j , 本文用ri , j来表示其
最早开始加工时间, 对不同的工序分别用下式进
行计算:
ri , j =
0 , 1 ≤ j ≤ N ;
ri - 1 , j +γi , j , 2 ≤ i ≤ nj ,1 ≤ j ≤ N ·
式中,γi , j = mink ( Ti , j , k) ,1 ≤i ≤nj ;1 ≤j ≤N·
对于FJ SP 来说一般存在两个难题:第一个
是如何为每道工序选择合适的机器;第二个是如
何计算每道工序的开始加工时间t i , j和结束加工
时间tf i , j·
本文所要研究的FJ SP 的优化目标是,在满
足上述优先约束和资源约束的条件下寻找最优调
度方案,使全部工件的最大完工时间(Makespan)
最短·
2 排序算法———动态双种群粒子群
优化算法
2. 1 标准粒子群优化算法
粒子群优化(particle swarm optimization ,简
称PSO) 算法是由Kennedy 和Eberhart 在1995
年提出·在PSO 系统中,每个潜在解被称为一个
粒子,多个粒子共存、合作寻优,每个粒子根据它
自身的经验在目标搜索空间中向更好的位置飞
行,搜索最优解·由文献[ 5 ]可知,每个粒子根据如
下的公式来更新自己的速度和在解空间的位置·
v ( t +1)
id = w v ( t)
id + c1 r1 p ( t)
id - x ( t)
id +
c2 r2 p ( t)
gd - x ( t)
id , (1)
x ( t +1)
id = x ( t)
id + v ( t +1)
id · (2)
其中, d = 1 ,2 , ⋯, n , i = 1 ,2 , ⋯, m , m 为种群规
模; t 为当前进化代数; r1 和r2 为均匀分布于[0 ,
1]的随机数; w 为惯性权重, 其值由下式来确
定[6 ] :
w = w max -
w max - w min
itermax
×iter · (3)
式中, w max , w min分别是w 的最大值和最小值;
iter ,itermax分别是当前迭代次数和最大迭代次数·
2. 2 粒子群优化算法的学习策略
由标准粒子群优化算法可知,粒子通过跟踪
自己迄今为止所找到的最优解和种群迄今为止所
找到最优解这两个极值来更新自己的速度,从而
更新自己的位置·这种行为也可以理解为,粒子在
借鉴自身和整个群体所取得的成功经验,通过对
以往的成功经验的学习获得有用的信息,指导自
己下一步的行动策略·但人们也常说“失败乃成功
之母”“, 吃一堑,长一智”,可见从一些失败的尝试
中也可以获得有用的信息,基于这一点,提出了新
的粒子群优化算法学习策略,这就是从以往的失
败中获得有价值的信息,使粒子远离粒子本身和
整个群体所找到的最差的位置,从而更新粒子的
速度和位置·粒子在搜索过程中的失败可以表现
为搜索到的具有较差适应值的位置,记第i 个粒
子迄今为止搜索到的最差位置为si = ( si1 , si2 ,
⋯, sin) ,整个粒子群迄今为止搜索到的最差位置
为sg = ( sg1 , sg2 , ⋯, sg n) ,则第i 个粒子的速度和
位置更新公式如下:
v ( t +1)
id = w v ( t)
id + c1 r1 x ( t)
id - s ( t)
id +
c2 r2 x ( t)
id - s ( t)
gd , (4)
x ( t +1)
id = x ( t)
id + v ( t +1)
id · (5)
如果只是利用上述的位置和速度更新公式更
新粒子,也就是说只是从失败中获取经验,这与实
际经验不符·一般来说,还是更多地从成功的经历
中获取信息,而从失败的经历中获得相对少的信
息,基于这一点本文的算法同时从成功和失败的
经历中获取信息来更新粒子·
2. 3 动态双种群粒子群优化算法
由上面的叙述可以知道粒子群中的粒子可以
按照不同的学习策略进行学习,对速度和位置作
出更新·所以本文将一个种群分成两个子种群,每
个子种群选用不同的学习策略,即第一个子种群
中的粒子选用从成功经历中获得学习信息的策
略,更新自己;第二个子种群中的粒子选用从失败
的经历中获得学习信息的策略进行进化·本文可
以设置一个比例系数ρ来控制两个子种群中粒
子的个数·
ρ =
m1
m2
, m1 + m2 = m · (6)
式中, m 为粒子群中的粒子总数; m1 为第一个子
种群中的粒子个数; m2 为第二个子种群中的粒
子个数·
为了使每个粒子都能从自身和群体的经历中
获得充分的学习, 本文规定两个子种群中的粒子
是不断变化的, 即每隔一定的代数后将整个种群
按照比例系数ρ重新随机划分成两个子种群·从
粒子群优化算法的进化过程中知道在优化的初期
粒子的位置比较分散, 得到较优值和较差值的机
会相差不多,所以此时采用上述两种不同学习策
略的粒子的个数应大致相等·在优化搜索的后期
粒子将聚集在最优值的附近,这时将很难出现比
历史最差值更差的值了,第二个子种群将从失败
经历中得不到太多的有价值的信息·此时第二个
子种群中的粒子数应该远远小于第一个子种群中
的粒子个数,直至完全采用跟踪最优值来更新粒
子,即第二个子种群消亡·基于上述原因将ρ设
为一个线性变化的量,其值由下式确定:
ρ = ρmax -
ρmax - ρmin
018 ×itermax
×iterc · (7)
式中,ρmax和ρmin分别是ρ的最大值和最小值;
iterc 和itermax分别是种群重新划分时的进化代数
和最大进化代数·
动态双种群粒子群优化算法的实现步骤如
下:
(1) 设PSO 种群规模为m , 加速常数为c1
和c2 ,惯性权重的最大值和最小值为w max , w min ,
比例系数ρ的最大值和最小值为ρmax ,ρmin ,种群
重新划分代数iterc ,最大进化代数为Tmax·将当前
进化代数置为t = 1 ;
(2) 在解空间中初始化粒子的速度和位置;
(3) 将种群按照比例系数ρ划分为两个子种
群;
(4) 按式(3) 更新惯性权重w , 按式(7) 更新
比例系数ρ, 第一个子种群按式(1) 和(2) 更新粒
子速度和位置,第二个子种群按式(4) 和(5) 更新
子种群中的粒子,从而产生新种群Xt ;
(5) 评价种群Xt·将第i 个粒子当前点适应
值与该粒子迄今找到的最优位置pi (最差位置
si) 的适应值进行比较, 若更优(差) , 则更新pi
( si) ,否则保持pi ( si) 不变,再与种群迄今找到的
最优位置pg (最差位置sg) 的适应值进行比较,若
更优(差) ,则更新pg ( sg) ;否则保持pg ( sg) 不变;
(6) 检查是否满足寻优结束条件, 若满足则
结束寻优, 求出最优解; 否则, 置t = t + 1 , 转至
(3) ;结束条件为寻优达到最大进化代数Tmax·
2. 4 基于动态双种群粒子群优化算法的工序排序
2. 4. 1 粒子的编码和解码
根据第1 节对柔性工作车间调度问题的描
述,本文定义所有工件的总工序数L = 6n
j =1
nj ,把
一个粒子表示为一个L 维的向量·对所有工序进
行连续编号,即为每道工序指定一个固定的编号·
例如可以对表1 所给出的例子中的工序进行编
号,如表2 所示,则粒子的位置向量x [ L ]就是由
一组连续的自然数组成的L 维的向量,自然数的
顺序决定了工序调度的顺序·xi = [1 ,7 ,2 ,4 ,8 ,3 ,
5 ,6 ]就表示了一个满足优先约束的可行的工序排
序·
表2 工序编号
Table 2 Serial numbers of operations
工序O1 ,1 O2 ,1 O3 ,1 O1 ,2 O2 ,2 O3 ,2 O1 ,3 O2 ,3
编号1 2 3 4 5 6 7 8
2. 4. 2 位置向量和速度向量的更新
对每个粒子, 粒子的速度向量可以用v [ L ]
表示·按照上面所述的更新公式对x [ L ] , v [ L ]
进行更新·由于粒子群优化算法经常用在连续空
间上,而柔性工作车间调度问题为整数规划问题
而且有工序先后顺序约束,所以将粒子群算法用
于柔性工作车间调度问题时,在速度和位置更新
方式上要做如下的修改:令粒子i 的当前的位置
为xi = [1 , 7 , 2 , 4 , 8 , 3 , 5 , 6 ] , 在经过一次迭代以
后位置向量变为xi = [ 2. 5 , 6. 7 , 3. 6 , 5. 9 , 8. 5 ,
112 ,4. 1 ,7. 6 ]·位置向量里存放的是工序的编号,
很明显不能为小数, 本文对迭代后的位置向量进
行如下的处理:将更新后的位置向量中各分量的
值按照由小到大的顺序进行排列, 并为其进行重
新编号:1. 2 (1) 2. 5 (2) 3. 6 (3) 4. 1 (4) 5. 9
(5) 6. 7 (6) 7. 6 (7) 8. 5 (8) ,式中括号内的数
字为该分量的编号, 然后位置向量中各分量用其
获得的相应的编号代替·例如,第一个分量2. 5 用
编号2 代替,第二个分量6. 7 用编号6 代替等等,
此时位置向量变为xi = [2 , 6 , 3 , 5 , 8 , 1 , 4 , 7 ]·但
是这个工序排序不满足优先约束,还要对其进行
调整,使其满足约束条件·例如第一个分量2 代表
的是工序O21 ,第6 个分量1 代表的是工序O11 ,
工序O21应在工序O11之后进行加工, 所以要对
其进行调整·调整的方法为:对属于同一个工件的
工序调换其相应先后位置使其满足约束, 对每个
工件都做相似的处理, 则可以得到满足优先级约
束的位置向量: xi = [1 ,4 ,2 ,5 ,7 ,3 ,6 ,8 ]·
3 启发式分配算法
通过上一节介绍的排序算法本文可以获得一
个满足工序优先约束的可行的工序序列·这一节
通过一个启发式算法为这一工序序列中的每一工
序分配一台合适的机器对其进行加工·
本文所采用的分配算法的主要思想是:选择
一台能使本道工序获得最小完工时间的机器分配
给待加工的工序·可以用如下公式表示选择机器
Mk 分配给待加工的工序以使本道工序的完工时
间最短:
tf i , j = min k ( ri , j + Ti , j , k) ,
ri , j = max ( rpfk , ropf) ·
式中, tf i , j 为工序Oi , j 的完工时间; ri , j 为工序的
开始加工时间; Ti , j , k为工序用机器k 加工消耗的
时间; rpfk为机器Mk 当前状态下所加工的最后一
个工件的完工时间; ropf为待加工工序紧前工序的
完工时间·
利用排序算法和分配算法就可以获得一个满
足优先约束和资源约束的可行的调度方案, 并且
利用分配算法还可以得到目标函数———全部工件
的最大完工时间的值·
将前面介绍的排序算法和分配算法综合起来
便形成本文所采用的处理柔性工作车间调度优化
问题的方法,记为DPSO2HA·该方法将柔性工作
车间调度问题分解为两个子问题———排序问题和
分配问题,在每一次迭代中首先通过动态双种群
粒子群算法获得一个可行的工序序列, 然后利用
分配算法给该序列分配合适的机器并计算目标函
数值,直至达到最大进化代数·
4 算例仿真
4. 1 仿真研究1
本文选用文献[ 7 ]中的一个10 ×10 (10 个工
件,10 台机器) ,30 道工序的柔性工作车间调度问
题来计算最大完工时间·实验参数如下:粒子群的
种群规模为m = 30 , c1 = c2 = 2 ,ρmax = 015 ,ρmin =
0 ,每隔5 代重新划分种群,最大迭代次数Tmax =
150·
实验中采用本文所提出的算法运行10 次,和
传统的GA 方法、文献[8 ]中采用的MSA 算法相
比较,比较结果如表3 所示·
表3 实验结果比较
Table 3 Comparison of te sting re sults
方 法最优值平均值标准偏差
GA 8 11. 5 2. 67
MSA 7 7. 9 0. 97
DPSO2HA 7 7. 1 0. 32
从表3 中可以看出DPSO2HA 求得的平均值
和标准偏差都明显优于GA 和VEGA , 这说明
DPSO2HA 的精度与稳定性明显优于GA 和
VEGA 算法·实验中所获得的一个较优的调度方
案的甘特图如图1 所示·图中方框内的数字“i . j”
表示第j 个工件的第i 道工序·,
(不好意思,图粘贴不下来,要不你告我邮箱)
图1 柔性工作车间调度优化结果
Fig. 1 Optimization solution to the problem
10 ×10 with 30 operations
4. 2 仿真研究2
为了进一步对本文提出的算法的性能加以验
证,选用文献[ 9 ]中所给出的实验数据,利用本文
提出的算法进行求解,并将调度结果与文献[ 9 ]及
文献[ 10 ]中所提算法的调度结果加以比较·比较
结果如表4 所示·
表4 不同方法的调度结果比较
Table 4 Comparison of different scheduling re sults
算例描述Brandimarte GENACE DPSO2HA
MK1 10 ×6 42 41 40
MK2 10 ×6 32 29 28
MK4 15 ×8 81 67 61
MK5 15 ×4 186 176 173
MK6 10 ×15 86 68 62
MK7 20 ×5 157 148 141
MK8 20 ×10 523 523 523
MK9 20 ×10 369 328 307
MK10 20 ×15 296 231 207
由上述的比较结果可以看出,本文所提出的
DPSO2HA 方法对上述算例的求解结果较另外两
种方法有了较大的提高·
5 结 论
本文提出了一种动态双种群粒子群优化算法
(DPSO) ·DPSO 将种群划分成两个种群规模随进
化过程不断变化的子种群,两个子种群分别采用
不同的学习策略进行进化,并在进化过程中相互
交换信息·该算法在保持PSO 算法高效简单的基
础上提高了全局寻优能力·将以DPSO 算法为基
础的排序算法和启发式分配算法相结合形成了解
决柔性工作车间调度问题的新方法·通过对算例
的研究和与其他方法的比较表明,该方法是有效
可行的·
参考文献:
[ 1 ] Carlier J , Pinson E. An algorithm for solving the job2shop
problem[J ] . Management Science , 1989 ,35 (2) :164 - 176.
[ 2 ] Reynolds R G. An introduction to cultural algorithms[ C] ‖
Proceedings of the Third Annual Conference on Evolutionary
Programming. River Edge : World Scientific , 1994 : 131 -
139.
[ 3 ] Mastrolilli M , Gambardella L M. Effective neighborhood
functions for the flexible job shop problem[ J ] . Journal of
Scheduling , 2002 ,3 (1) :3 - 20.
[ 4 ] Kacem I , Hammadi S , Borne P. Pareto2optimality approach
for flexible job2shop scheduling problems : hybridization of
evolutionary algorithms and fuzzy logic[J ] . Mathematics and
Computers in Simulation , 2002 ,60 (3) :245 - 276.
[ 5 ] Kennedy J , Eberhart R. Particle swarm optimization [ C] ‖
Proceedings of IEEE International Conference on Neural
Networks. Perth : IEEE Press , 1995 :1942 - 1948.
[ 6 ] Shi Y, Eberhart R C. Empirical study of particle swarm
optimization [ C ] ‖Proceedings of the 1999 Congress on
Evolutionary Computation. Washington , 1999 : 1945 -
1950.
[ 7 ] Xia WJ , Wu Z M. An effective hybrid optimization approach
for multi2objective flexible job2shop scheduling problems[J ] .
Computers Indust rial Engineering , 2005 ,48 (2) :409 -
425.
[ 8 ] Najid N M , Stephane D P , Zaidat A. A modified simulated
annealing method for flexible job shop scheduling problem[C]
‖Proceedings of the IEEE International Conference on
Systems , Man and Cybernetics. Hammamet : IEEE Press ,
2002 :89 - 94.
[ 9 ] Brandimarte P. Routing and scheduling in a flexible job shop
by tabu search[J ] . A nnals of Operations Research , 1993 ,41
(3) :158 - 183.
[ 10 ] Ho N B , Tay J C. GENACE: an efficient cultural algorithm
for solving the flexible job2shop problem[C] ‖Proceedings of
the IEEE Congress on Evolutionary Computation. Portland :
IEEE Press , 2004 :1759 - 1766.
(do you know)
OpenProj
OpenProj是一个款免费的、可替代MSProject的桌面项目管理工具,其使用方式应于Project相似,可以轻松上手。它拥有与MS Project同等的功能,一个友好的用户界面并且能够打开现有的MSProject文件。OpenProj做的较为出色的是它是跨平台的,Windows、 Linux、Unix和Mac下都能使用。
GanttProject
GanntProject是一款以Java编写的开源甘特图绘制软件,提供了基本的项目管理能力,如创建工作分解、确定主要里程碑、持续时间、相依性、进度、备注以及资源分配等等。GanntProject可以导入导出CSV和Microsoft Project文件。它可以在Windows、Linux、Mac OS及其它操作系统上执行。
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。