numbers甘特图

本文目录一览：

• 1、高分急求！ 关于 粒子群解决车间调度的英文文献 ！ ！先50 满意再加50
• 2、苹果笔记本制作甘特图

高分急求！ 关于 粒子群解决车间调度的英文文献 ！ ！先50 满意再加50

基于动态双种群粒子群

算法的柔性工作车间调度

摘 要: 针对标准粒子群优化算法存在易陷入局部最优点的缺点,提出了一种基于动态双种群的粒子群

优化算法(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及其它操作系统上执行。