第39卷第1期2017年2月
武汉理工大学学报（信息与管理工程版）
JOURNAL OF WUT( INFORMATION & MANAGEMENT ENGINEERING)
Vol.39 No.1
Feb.2017
文章编号:2095 -3852(2017)01 -0104 -06文献标志码:A
杨立熙，余慧慧
(福州大学经济与管理学院，福建福州35〇1〇8)
摘要：在实际加工生产中，工序间的运输时间占整个加工时间的比例很大。为了更合理地研究柔性作 业车间调度问题，将运输时间作为独立影响因子考虑到模型中。针对模型的特殊性与传统遗传算法易早熟的 缺陷，运用小生境的思想和自适应距离变量划分种并协同进化，进而平衡种选择压力，避免算法 过早收敛 至局部最优。同时提出最短工作时间方法优化初始种，改善算法的求解效率。运用M atlab对国际上通用 的算例进行实验并与经典遗传算法对比，结果表明，新提出的算法能够获得更优的调度方案。
关键词：柔性作业车间调度；运输时间；遗传算法；小生境；选择压力
中图分类号:TP29
随着自动化技术的发展和柔性制造系统的出 现，近年来柔性作业车间调度问题（flexible job - shop scheduling problem,FJSP)成为研究重点。
FJSP已经被证明是NP - Hard问题，求解方法主
要是体智能优化算法，如遗传算法（genetic algorithm,GA)[1]、蚁 算法 （ant colony algorithm, AC0) [2]、粒子算法(particle swarm optimization, PS0)[3]等。但大多数关于FJSP的研究忽略了工 序之间的运输时间，而运输时间却是实际生产中 客观存在的，若放宽过多的假设条件会导致理论 研究缺乏指导性，而且在一些特定的生产领域，其 运输时间过长会直接影响产品的质量。
目前，考虑运输时间的FJSP的研究相对较 少。HURINK等[4_5]假定物料处理系统间存在运 输时间，以最小化完工时间为优化目标，运用禁忌 搜索算法寻求局部最优解；李峥峰[6]利用传统遗 传算法求解
了考虑运输时间因素影响的柔性车间 调度问题，测试结果表明考虑运输时间的柔性车 间调度模型具有极强的优化性能，其平均改进结 果达到33.6%；王永峰[7]在传统遗传算法的基础 上，设计了一种机器选择的启发式算法作为初始 解改进算法加以求解;ZHANG等[8]借助遗传算法 和禁忌搜索算法解决了考虑运输时间的柔性调度 问题；赵宁等[9]在研究考虑运输时间的柔性作业 车间调度过程中，建立了两阶段求解方法。遗传
D0I：10. 3963/j.issn.2095 - 3852.2017. 01.022
算法是求解此类组合优化问题的有效方法，但上 述文献未考虑到算法易早熟、容易陷入局部最优 的弊端。笔者研究考虑运输时间的FJSP，提出一 种小生境遗传算法。在遗传算法的框架下，结合 小生境的思想划分种进行局部寻优，平衡种 选择压力以克服G A易过早陷入局部最优的缺 点。并针对优化目标提出新的初始化方法，以期 改善考虑运输时间的FJSP的求解速度和求解质量。
1问题描述
考虑运输时间的FJSP的描述如下个工件{■^■^，…，人丨要在肌台机器丨札^^…^^上
加工。每个工件包含一道或者多道工序，工序的 顺序是预先确定的，每道工序有一台或者多台加 工机器可供选择，选择不同的加工机器对应的加 工时间和运输时间也不同。调度需要为每道工序 选择合适
的加工机器、确定每台机器上各工序的 最佳加工顺序和开工时间，使整个系统的性能指 标达到最优。此外，在加工过程中不仅要考虑工 序顺序和设备资源的约束，还要考虑工序间的运 输时间约束，笔者作出如下假设:①每个工件的加 工一旦开始不能中断，即加工过程为非抢占式;② 同一台机器同一时刻只能加工一个工件;③设备 在零时刻可用，所有工件的第一道工序在零时刻
收稿日期=2016 -09 -18.
作者简介：杨立熙（1970 -)，男，福建福安人，福州大学经济与管理学院副教授；博士.
第39卷第1期杨立熙，等：考虑运输时间的柔性作业车间调度问题研究105
都可以被加工;④所有工序按先后顺序加工，每一*
道工序加工完毕后立即运输到下一加工工序的设
备，下一道工序方可加工；⑤工序加工时间因所
选的加工设备不同而不同，加工时间是给定的;⑥
同一工件的相邻工序之间存在加工运输时间，运
输时间因相邻两道工序选择的加工机器的不同而
不同，且机器间的运输时间是给定的。
数学模型描述及定义为：工件集/=I人，厶，
…，Jk，…丄丨，Jk为第k个工件（k = l，2,…，n);
机器集，焉，…，軋，…，风J，軋为第€台
机器(i= 1，2,…，m)；心为第j'个工件的第A道
工序，并定义表示第〜的前一道工序，
表示〜当前所在机器的前一道工序；为第7_个
工件的第&道工序在机器纟上加工所需时间;
为第y个工件的第&道工序在机器纟上的开始加
工时间；为第y个工件的第&道工序在机器€
上的结束加工时间；为机器軋和机器
之间的运输时间；q为第个工件的完工时
间…m a x为最大完工时间。考虑最小化最大完工
时间（makespan)，目标函数及其约束条件分
别为：
Cm a x=m in(max(C J))(1)
:=Sijh + P ijh(2)
^ijh ~^Pijh(3)
Ce](h-i) Cifh'+ Transtime i e Cr f h'< Cej(h-i)+ Transtimei e
Clfh'> Cej(h-i) + Transtimeu⑷
式(2)表示工序的完工时间等于开始时间与 加工时间之和，S卩加工为非抢占式；式（3 )表示机 器资源
约束，即假设2；式(4)表示若工序所在机 器的可开始加工时间小于前一道工序运输结束时 间，则受运输时间约束；否则，工序受当前加工机 器的资源约束。因此，对于同一机器的相邻工序 而言，仅受机器资源约束；对于同一工件内的相邻 工序而言，考虑了运输时间，替代了传统模型中的 工序顺序约束。用工件号表示，其中每个工件号出现的次数代表 该工件的工序数。如一个可行基因串1 -1 - 2 - 2 _ 1，对应的工序)幡序是_ 012 _ 021 _ 022 _ 〇13。②机器选择部分：采用基于机器分配的编码。基因串长度为总工序数，从左到右依次按工 件工序顺序排列，基因位置代表工序对应加工机 器。例如一个可行基因串1 -3 -1 -1 -2，表示 工序^^在可选机器的第1台机器軌加工，工序 〇12在可选机器的第3台机器M4加工，依次类推。具体编码如图1所7K。
染体|
编码I
初始解|
码丨
工序排序部分一►_—机器选择部^—«
〇n〇n〇：3〇2：〇22
112 2 113112
丨丨i j i--1-
,I M x|M2\M41M5\
〇n〇n〇2l〇22 〇u\
工序顺序丨
|M|M3\_____
机器选择
图1染体编码
解码时需要考虑两个问题:①工序顺序和机 器资源约束，插入式主动调度如图2所示，以工序 〇13为例，其前一道工序〇12的运输完成时间大于 当前机器可加工时间，此时受机器资源约束;②文 献[10]已证明正规性指标的最优调度存在于主 动调度集中，因此在图1的初始解码的基础上，判 断当前机器是否存在空闲时间。若存在空闲时间 且大于该工序的加工时间，则将当前工序插入到 间隔时间段中，确保生成主动调度集，以图2工序 为例。
图2插入式主动调度
2改进遗传算法
2.1染体编码和解码
编码和解码是遗传算法首要解决的问题，用 于将问题解和染体相互转换。FJSP包括工序 排序和机器选择两个子问题，将两个子问题融合 成一条染体，S卩表示为柔性作业车间调度的一 个可行解。①工序排序部分：采用基于工序的实 数编码。基因串长度为总工序数，每个基因位置2.2初始化方法
初始解的优劣影响算法的求解质量和收敛速 度。目前使用较多的是随机初始化，这种方法操 作简单，但是初始解参差不一，需要增加迭代次数 或者种规模来寻求较优解。由于模型中考虑了 运输时间，使得可行解的搜索范围扩大进而问题 求解更为困难。故笔者提出考虑工序加工时间和 运输时间因子影响的最短工作时间法（short working machine，SWM)，
赋予各个工序选择近似
106武汉理工大学学报(信息与管理工程版)2017年2月
较优的机器来获得较优的初始解，缩短算法收敛 寻优的收敛时间。同时为保持初始种多样性，初 始化采用一半SWM，一半随机初始化方法生成。
SW M执行步骤为：①获取工件集总数/_0_ 丽每个工件^对应的工序数，6〇 ;
②设置一个整型数组/办，用于记录机器索引号；设置一个整型数组长度等于总工序数，用于记录SM W算法的机器选择部分，初始化数 组元素值为〇;③随机选择一个工件，并选择当前 工件的第一道加工工序;④寻当前工序的可选 择加工机器及加工时间，选择时间最小的那台机 器作为当前工序的加工机器，更新和^om_M，并以此作为下一次选择依据;⑤选择当前工件的 下一道工序，并记录工序的可选机器及对应加工 时间，从中获取上一道工序加工机器索引号，计算相邻工序间的运输时间，不更新数组;⑥将加 工时间与运输时间相加，选择相加和最小的那台 机器作为当前加工机器，更新1心和⑦
重复步骤⑤和步骤⑥，直至当前工件所有工序的 加工机器选择完毕;⑧从工件集中选择下一个工 件，同时选择工件的第一道工序，重复步骤④〜步 骤⑦，直至工件集中所有工件被选择完毕。
即表示最短工作时间法产生的机器选择 初始化，以义为例，SW M计算逻辑如图3所示。
图3 S W M计算逻辑
2.3交叉算子
交叉的目的是通过父代个体的信息交换，保 留父代中优良信息，产生新的子代。染体有 两部分组成，分别采取不同的操作方式。①工 序染体：该部分是基于工序编码，传统的随机 选择交叉简单易操作，但是容易产生不可行解，因此该部分采用文献[11 ]提出的P O X交叉法，继承父代染体工序排序部分的优良基因。首 先，将工件集/随机划分成两个非空子集，Jo62；其次，将父代染体P1/P2中包含/〇M/的工件复制到子代C1/C2中，并保持其位 置和顺序不变；最后，将父代染体P1/P2中包 含M2//o61的工件复制到子代C2/C1中，并保 持其顺序不变。②机器染体：为保证此部分交叉后产生的仍是可行解，采用多点交叉(MPX)方式，即随机选取多个交叉点，两父代进 行基因块交换。
2.4变异算子
变异是通过随机改变染体的某些基因，产 生新的染体，从而增加种的多样性，改善GA 的局部搜索能力。①对于工序排序部分，采用互 换操作，即随机选择两个不同位置的基因进行交 换。②对于机器选择部分，随机选择一个基因位，在该位置的可选机器上随机选择一个加工机器代 替当前染体中的加工机器。2.5小生境进化策略
选择压力过大是导致G A早熟收敛至局部极 值的一个重要原因。随着进化的进行，优秀个体 的重抽样机会增多，使得靠近局部最优解而非全 局最优解的个体更容易被选择，导致种过早陷 入局部最优。因此，笔者借鉴小生境的概念，通过 设定一个自适应距离隔离小生境，将种划分成 两个子种，分
别按适应度值排序保留较优解于 精英库，结合遗传算法的交叉变异规则更新，最后 合并得到新一代种，进化策略如图4所示。
从概率上讲，与最优解有较大相似度的个体 也有较高的适应度[12]，小生境隔离策略以当前最 优点为中心，将种划分成两部分。小于阈值^ 表明与最优解有较高的相似度，划分到优质子种 /；其余个体划分到次优子种/>即2。其中 子种M p l为提高整体适应度；子种为保持种多样性。由于遗传算法是按照染体编 码的方式计算，因此在种划分中引入海明距离 的概念：
n
= I〇Pl(i) ®0P2(i) +
j = l
m
^Mc l(j)®Mc2(j)
j =1
式中:q和C2表示两条染体；办1和
表示Q和C2工序排序的编码部分；办1(〇
、
第39卷第1期杨立熙，等：考虑运输时间的柔性作业车间调度问题研究107
图4
小生境进化策略
Op2(〇表示第€位基因；她1和表示和(：2
机器分配编码部分;MC 1 (y )、Mc2(y )表示第y 位基 因;〃和m 分别表示工序排序部分和机器分配部 分的染体长度。㊉为异或运算符，其定义为：
A @B
=
I 1 A ^B
VQ
A
=
B
按照海明距离定义小生境，以期在子种
p o p l 中寻求一个局部最优值即为当前全部最优。 初期无法界定两个局部最优值的距离，故采用固 定阈值^是不准确的。笔者采用自适应的阈值， 即随着进化的进行，^会逐渐缩小，直至剩余个体 都集中于一个局部极小值附近。阈值^和种划 分规则定义如下：
\p o p \ ：H (x ,x m )
^ d
lp o p 2:H (x ，x m ) > d
其中，4 =0. 5min (max )，表7K 每 A :
代随种变化的划分阈值。随着迭代次数的增 加，当^足够小时，表明种个体趋于近优解，定义
評2为空集，S 卩个体全部集中于优质子种p opl 。 2.6改进
GA 的执行步骤
单一的遗传算法存在局部搜索能力差的缺
陷，笔者综合考虑带运输时间的H S P ，利用遗传 算法实现全局搜索，小生境划分实现局部搜索，两 者结合发挥各自的算法优势。改进遗传算法具体
执行步骤为:①确定种规模、迭代次数交 叉概率'、变异概率Pm 等参数;②种初始化。
采用一半SWM ，一半随机初始化法;③利用小生 境进化策略将种划分成两个子种;④ 分别评价种中每个染体适应值，并按大小 排序，如果满足条件输出近优解；否则执行步骤⑤;⑤ 精英库中的个体直接保留至下一代，其余执行 锦标赛选择策略;⑥对满足交叉概率的染体个
体按照交叉策略进行交叉;⑦对交叉后得到的种 满足变异概率的染体按照变异策略进行变 异，得到新一代种;⑧按照精英策略对精英库进 行更新;⑨合并子种，/>即2;⑩返回步骤③。
3
计算结果与比较
菱镁材料
为验证该改进遗传算法的有效性，采用Mat -
la b 编写运行代码，程序在处理器为P 4 CPU ，主频
为2. 13 GHz ，内存2 G B 的个人计算机上运行。 设置种规模为1〇〇，最大迭代次数=200, ' =0.8，变异概率匕=0. 1，一半最短工作时间 法初始化
，一
半随机初始化。对每组算例运行10
次，取其最优解。从两方面展开对比实验:①与传
双接头统G A 对比算法的质量效率;②与不考虑运输时 间的最优调度方案对比最优结果。
测试算例选择国际上通用K A C E M 等[13_14]
提出的3个标准算例进行测试，包含8 x 8的？-
FJSP 、10 x 10 的 T - FJSP 和 15 x 10 的 T - FJSP ，
这些数据是FJSP 问题中普遍采用的。考虑到现 实问题中存在不同程度的设备运输情况，将运输 时间按照平均加工时间、最大加工时间分成〇〜
1，1〜5,5〜10这3个等级（KAC EM 算例中最长 加工时长为10)，参考文献[9]采用的随机函数法 生成。
1〜5之间分布和相关实验结果对比分别 如表1和表2所示。
表1
在1〜5之间分布的设备间运输时间
设备
M l
M 2
M 3
m
M 5
M 6M l
M 8
M 9
M 10零时刻
Ml
0. 000 02. 052 83. 158 4 3.714 9 1.297 2 4.312 1 4.016 12. 864 6 1.725 31. 095 0M 22. 052 80. 000 03. 493 61. 297 3 1.772 94. 670 23. 652 64. 655 13. 007 84. 480 9M 3
3. 158 43. 493 60. 000 01. 282 7 2.518 4 1.452 3
4. 534 0 1.914 32. 688 81. 107 5M 4
3.714 91. 297 31. 282 70. 000 02. 105 7
4. 248 52. 088 64. 448 23. 641 73. 078 1MS 1. 297 21. 772 9 2.518 42. 105 70. 000 04. 633 12. 677 73. 626 53. 694 6 1.769 2M 6 4.312 14. 670 2 1.452 34. 248 5 4. 633 10. 000 01. 852 04. 564 7 4. 829 33. 862 8M l 4.016 13. 652 64. 534 02. 088 62. 677 71. 852 00. 000 02. 952 6 1.767 52. 002 7MS 2. 864 64. 655 1 1.914 34. 448 23. 626 54. 564 72. 952 60. 000 0 1.444 94. 735 5M 9 1.725 33. 007 82. 688 83. 641 73. 694 64. 829 3 1.767 5 1.444 90. 000 01. 548 8M 10
1.095
4. 480 9
1. 107 5
3. 078 1
1.769 2
3. 862 8
2. 002 7
4. 735 5
1.548 8
0.
000 0
108武汉理工大学学报(信息与管理工程版)
2017年2月
该算例的调度如图5 (b )所示，m ate 声1为 23.481 2，算法在求解质量上改进了 9.40%。为 更直观地观察改进遗传算法的收敛过程，图6给 出改进算法的收敛曲线，发现由于初始化改进，算 法在初期就很快到较好的初始解。迭代前期小 生境划分平衡了选择压力，曲线最优解下降速度
很快。后期种质量趋于近优解并集中到/， 下降较为平缓，基本上在20代到最优解，并且 种均值很接近最优解，运算质量和效率均有较 大改进。
0 20 40 60 80 100 120 140 160 180 200
迭代次数
图6
改进G A - G a n tt 收敛曲线
(8 x 8P -
FJSP ，运输时间 1 〜5，Cm a x = 21.462 7)
4
结论
为实现精细化管理，提高工件响应速度，将物
流业和柔性制造相融合，以柔性作业车间为背景， 引入了运输时间独立时间影响因子。笔者建立了 考虑运输时间的FJSP 调度模型，实现了运输时间 的优化；在传统遗传算法的框架下，设计了新的种 初始化方法，并引入小生境思想的局部搜索弥 补G A 易早熟的缺陷；编程实现了改进算法，运用 标准
实例测试并比较算法的性能。实验分析表 明，考虑运输时间的优化调度方案更符合实际，笔 者提出的小生境遗传算法与传统遗传算法相比有 明显的优势。
参考文献：
[1]
P E Z Z E L L A F , M O R G A N T I G , C IA S C H E T T I G. A genetic algo rithm fo r the fle x ib le jo b - shop scheduling problem [ J ]. Computers and O perations R esea rch, 2008,35(10) ：3202 -3212.
[2]
X IN G L N , C H E N Y W , W A N G P , et al. A kn o w ledge-based ant colony o p tim ization fo r fle x ib le jo b shop scheduling problem s [ J ]. A p p lie d Soft Com putin g ,2010,10(3) ：888 -896.
[3
] 贾兆红.粒子优化算法在柔性作业车间调度中的
应用研究[D ].合肥：中国科学技术大学，2008.
表2
实验验证结果对比运输
时间
算例笔者算法
Cm a x
RE1/%R E2/%
传统G A K A C E M
调度加人
运输时间
8 x
8
弧齿
15.728 1 9.36 2.06 17.199 7 16.052 20 〜1 10
x 10 8.087 9 17.40
7.26 9.495 0 8.675 1
15 x
10 15.199 6 19.49 36.13 18.161 7 20.691 9
8 x 8 21.462 7 9.40 25.58 23.481 2 26.951 81 〜5 10 x 10 11.007 8 12.56 13.04 12.390 2 12.443 1
睫毛器
15 x 10 19.578 9 14.56 35.11 22.429 4 26.454 08 x 8 29.906 6 11.47 15.37 33.336 0 34.502 010
x 10 20.191 8 13.18 20.19 22.852 2 24.268 315 x 10 29.960 8 28.03 67.54 38.360 1 50.196 8
10其中，Cm a x 表示当前算法的最优解；表示 此算法与传统G A 间的相对误差；表示此算 法与KACEM 最优调度中加入运输时间求解的相 对误差。计算结果表明，不论是与传统G A 还是 与加入运输时间的最优调度方案相比，笔者提出 的改进算法总能得到更好的近优解。并且随着工 件数量和机器选择的增加，越来越大，这说明 对于大规模工件和柔性车间，笔者算法的优势更 明显。从相对误差来看，基本上狀2大于狀1， 说明考虑运输时间的调度更符合实际优化。
以算例8 x 8 (运输时间在1〜
5)为例，改进
算法和原始G A 的调度甘特图对比如图5所示， 圈出的部分即表示工序/62的加工及相应的运输
部分。运用改进算法得到最优调度如图5(a )所 7K ，删^哪抓为21.4627 ；对应传统遗传算法对
木马检测
(b )
传统遗传算法
图5
调度甘特图对比（8
X 8P -FJSP ，运输时间1〜5)
5
050505C
55443320u
o s d s s ^o s
m
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议