利用有限制稳定配对策略求解双目标 柔性作业车间调度问题
杨 宇 黄 敏 王震宇 朱启兵
江南大学物联网工程学院，无锡， 214122
摘要：实际生产中，以最小完工时间和最低成本为目标的调度是柔性作业车间最常见的问题。提出了一种有限制稳定配对策略的双目标柔性作业车间调度问题的求解方法。该方法将双目标优化问题分解为一系列的标量优化子问题，并利用多目标进化算法对子问题进行优化求解；同时，将有限制稳定配对策略用于进化过程中各子问题解的协调选择，以保证解的收敛性和分布性。仿真数据和应用实例表明：该方法可以获得收敛和分布性能更优的调度方案。
关键词：柔性作业车间调度问题（ FJSP）；有限制稳定配对策略；多目标进化算法；收敛性；分布性中图分类号： TH186
DOI：10.3969/j.issn.1004⁃132X.2018.14.015 开放科学(资源服务)标识码(OSID) ：
Solving Bi⁃objective FJSP Using Limited Stable Matching Strategy
YANG Yu HUANG Min WANG Zhenyu ZHU Qibing
School of Internet of Things Engineering,Jiangnan University,Wuxi,Jiangsu,214122
Abstract ： In practical productions，scheduling with bi ⁃ objective including minimum target comple⁃ tion time and minimum production costs was the most common problems in flexible production work⁃ shops. An optimization method with limited stable matching strategy was introduced herein to solve FJSP with the bi ⁃ objective. The method decomposed a bi ⁃ objective optimization problem into a set of scalar optimization subproblems and optimized them using multi⁃objective evolutionary algorithm.Mean⁃ while，the limited stable matching strategy was used for coordinating the solutions of subproblems in the evolution processes to ensure the convergence and diversity of the solutions.The simulation data and ap⁃ plication examples demonstrat that the proposed method may obtain the scheduling scheme with the bet⁃ ter convergence and diversity to meet the different preferences of decision makers.
Key words ： flexible job ⁃ shop scheduling problem（FJSP）；limited stable matching strategy；multi ⁃ objective optimization algorithm；convergence；distribution
0 引言
柔性作业车间调度问题（ flexible job-shop scheduling problem，FJSP）是指在并行机和多功能机并存的作业车间内，合理安排各工件工序的加工机器和作业时间，以实现给定的多性能指标优化 。FJSP包含了机器分配和工序调度两个问
［］ 1题，具有约束条件多、计算复杂度高等特点，属于典型的NP-hard问题 。FJSP的求解策略一直
［］ 2⁃3是生产管理及组合优化领域的研究热点之一，具
收稿日期： 2017－12－28
基金项目：江苏省政策引导类计划（产学研合作）－前瞻性联合研究项目（ BY2016022－32） 有重要的理论意义和实际应用价值。
FJSP需要对生产过程中的多个性能指标进行优化，由于各性能指标往往存在冲突，因此一般难以获得满足各性能指标、同时最优的FJSP 全局解，仅能获得各性能指标最佳均衡的FJSP 满意解，称之为Pareto最优解 。在实际运用中， FJSP
［］ 4往往需要获得一个分布广泛的Pareto 最优解集合，供决策制定者根据其需要（对各性能指标的要求）加以选择 。多目标进化算法（ multi-objec⁃
［］ 5 tive evolutionary algorithm，MOEA）因其在解决FJSP时可获得一致性的Pareto最优解，已经成为解决此类问题常用的方法 。如何在保证解的收［］ 6
· ·
敛性的同时，获得具有广泛分布性的Pareto 最优解集，是利用进化算法求解FJSP的关键 。张超
［］ 7
勇等 采用带精英策略的非支配排序遗传算法
［］ 8
（ non-dominated sorted genetic algorithm，NSGAⅡ）求解 FJSP，获得的最优解较好，但会聚集在Pareto前沿附近的某一个狭小区域内，无法为决策者提供宽泛的选择，且计算代价较大。ZHANG等 针对连续型问题的特点，提出一种基于问题分
［］ 9
解的 MOEA（MOEA based on decomposition， MOEA/D），随后， CHANG等 使用MOEA/D
［］ 10
求解FJSP。MOEA/D算法将多目标优化问题分解为多个单目标优化的子问题，并采用子问题合作方式进行优化，取得了比NSGA ⁃Ⅱ更佳的性能，但进化过程中存在的“超级解”会使解丢失，因此种群的分布性无法得到保证。为了解决“解丢失”的问题， LI等 将稳定配对思想引入MOEA/
［］ 11
D，提出了基于稳定配对选择策略和分解相结合的MOEA（MOEA based on decomposition and sta⁃ ble matching，MOEA/D⁃STM），此算法虽然可以避免解丢失，但在进化过程中，每一代选择到的解的收敛性优于多样性，这个缺点将影响Pareto 最优解集的多样性和收敛性。
因 MOEA/D⁃STM算法在解决连续性问题上的性能优于MOEA / D 算法，且后者在解决FJSP时表现出了良好的性能，故本文将MOEA/ D⁃STM算法引入到FJSP的求解中。针对传统MOEA/D⁃STM算法中配对选择策略缺乏约束限制带来的解的分布性能难以充分保证的缺点，提出了一种有限制的稳定配对选择策略和分解相结合的 MOEA（MOEA based on decomposition and limited stable matching ，MOEA/D⁃LSTM），以平衡进化过程中的收敛性和分布性，并提高Pareto最优解集的收敛性和分布性。通过标准测试集和实际车间生产实例来验证算法的有效性。1 FJSP调度模型
FJSP可具体描述如下： n个待加工工件的集合J= { J1，J2，… ， Jn}，工件在u台机器上加工，机器集合M={M1，M2，…，Mu}，工件Ji包含n（ni> 1）道
i工序，其工序集合Oi ={ Oi1, Oi2, …, Oini }。所有的工序按照制定的加工路线进行，工件Ji的第j（j= 1，2，…， ni）道工序Oij可在多台机器上操作。调度的目标是为每一道工序确定一台机器，同时将机
Σ器上待加工工序做排序，使得系统的整体性能最j优。本文研究的问题是一个有约束的双目标优化问题，即在满足所有约束条件的情况下，优化目标· · 兼顾最小化最大完工时间和最小化总成本。最小化最大完工时间定义如下： é ù
ni min f1 = max ( Ci ) = max ( b ijk Sijk + t ijk Sijk ) （ 1） 1≤ i ≤ n 1≤ i ≤ n
=1
1 工序Oij在机器k上加工
Sijk = （ 2）
0 工序Oij不在机器k上加工
式中， Ci为工件i的完工时间； bij k为在机器k上开始加工工序 Oij的时刻； ti jk为使用机器k加工工序Oij所用的时间； Sijk确定Oij是否在机器k上加工。最小化总成本定义如下：
é ù n ni u min f2 = γi + Σ (+
μijk ν ijk ) Sijk （ 3） =1 =1 k =1
式中， γi为工件i的材料费； μij k、νi jk分别为工序Oij在机器k上的加工费用及人工费。
约束条件：
（ 1）工序约束。工件各工序存在先后顺序，工序Oij必须在工序O（ 完成之后才可以开始加工，即
i j- 1）
Cij - Ci ≥ t ijm Sijm, j = 2, 3, …, ni ;∀ i, j （ 4）
( j - 1)
式中， Cij为工序Oij的完成时刻。
（ 2）机器约束。同一台机器在同一时刻只能加工一道工序，在某时刻hh ( > 0 )，若 Sijk =1则在i ≠ p 或j ≠ q条件下， Spqk ≠1恒成立。
（ 3）连续性约束。任何工序一旦开始加工，则不可被打断，即
{ max { Ci m, b ijm } + t ijm j >1
( j - 1)
Cij = （ 5）
b ijm + t ij j =1
（ 4）除了满足以上约束条件外，还应该满足所有机器在h =0时刻可用，且所有工件优先级相同。
2 基于MOEA/D⁃LSTM算法的FJSP求解2.1 MOEA/D⁃STM算法
MOEA/D⁃STM算法主要包括： ①将一个多目标优化问题转化为多个单目标优化的子问题，并计算候选解集对子问题、子问题对候选解集的偏好矩阵； ②基于偏好矩阵选择具有稳定配对关系的候选解子集； ③对选择的候选解子集进行演化操作并重复步骤② ，最终获得Pareto最优解集。2.1.1 分解多目标优化问题，构建偏好矩阵
设目标空间为 Fx ( ) =[ f1 ( x ), f2 ( x ), ⋯, fm ( x )]∈ Rm ， m为目标空间的维数。利用一组权向量w =( w1, w2, ⋯, wN)将目标空间划分为N个子空间，其中 wt =( wt, 1, wt, 2, ⋯, wt, m) ∈ Rm, t=
m
1, 2, ⋯, Ni ; wt, ≥0且 wt, =1。每个子空间j j
=1代表了一个待求解的子问题， N个子问题记为P = { p1, p2, ⋯, pN}，则 wt代表了子问题pt的权值向量 ΣΣ i j
（图1给出了m= 2， N= 5时的子问题表示）。设X ={ x1, x2, ⋯, x2N}为多目标进化问题的2N个候选解集合，则子问题pt对候选解x （ i= 1，2，… ， 2N）的偏好值
Δp ( pt, xi )= g ( xi | )- z* wt , z* ) = max {| fl ( xi |
l
1≤ l ≤ m wt, l}
（ 6）其中， g ( ⋅ )为切比雪夫距离， z* =( z* 1, z* 2, ⋯, z* ) 为
T m参考点，且z = min fl ( xi ), l = 1, 2, ⋯, m。
xX ∈
候选解xi对子问题pt的偏好值
w F ˉ( xi )
Δx ( xi, pt ) = ||F ˉ( xi )- wt|| （ 7）
w wt
其中， || · ||为欧氏距离， F ˉ( xi 是将F ( xi 归一化处
) )
理后的目标函数值，其第 l 个目标函数值为f ˉ( )=( fl ( x )- xi
x z ) / ( z nad - z )， z nad = max fl ( ), l l l
xX ∈ l = 1, 2, ⋯, m。
对于2N个候选解，可以得到候选解对子问题的偏好矩阵ψx ，其维数为2N×N；同理，可以获得N个子问题对候选解的偏好矩阵ψP ，其维数为N×2N。
2.1.2 选择具有稳定配对关系的候选解子集
对于N个子问题，如果存在一组配对关系
{ ( p1, x1 ),( p2, x2 ), …,( pn, xn ) }( xt ∈ X)且满足下列关系，则称这N个子问题及其配对的候选解构成稳定配对关系:
（ 1）如果候选解xi ∈ X没有和任何子问题pt配对，则对于任意的子问题pt ，其对当前的配对解xt的偏好要优于对xi的偏好，即有Δp ( pt, xt ) < Δp ( pt, xi )；
（ 2）对于已构成配对关系中的任意一个候选解 xt ，不存在除子问题pt 之外的子问题pj (≠ j t )，使得 Δp ( pj, xt ) < Δp ( pt, xt ) ，且 Δx ( xt , pj ) < Δx ( xt , pt )。
从候选解集合X ={ x1, x2, ⋯, x2N}中选择与子问题构成稳定配对关系的候选解子集合
{ x1, x2, ⋯, xN}，在保证进化算法收敛性的同时，可以保证选择的解在目标空间具有较好的分布特性，具体配对过程可由文献［ 12 ］开发的递延接受程序获得。
2.2 MOEA/D-LSTM算法
尽管原始的MOEA/D-STM算法可以在一定程度上保证选择的解在目标空间具有较好的分布特性，但是当原始的候选解集合在目标空间分布不均匀（具有聚集现象）时，其配对选择后的候选解在目标空间中仍然较为聚集，从而最终影响到 候选解在目标空间的分布性。如图1a所示，原始的候选解x1、、、x2 x3 x4分布在p1 和 p2之间的区域 ，构 成 { ( p1, x1 ) ，( p2, x3 ) ，( p3, x4 ) ，( p4, x2 ) ， ( p5, x10 )}稳定配对关系，如果利用稳定配对关系进行选择，则x1、、、、x2 x3 x4 x10将会被选择进入演化操作，从而影响选择的候选解在目标空间分布的多样性。产生这一问题的原因在于原始的MOEA/D⁃STM算法在计算子问题对候选解的偏好值时，没有对精英解的贪婪性进行限制。为此，本文引入一个限制算子，将子问题对候选解的偏好加以约束限制，使被选解在目标空间的分布均匀，此时子问题pt对候选解xi的偏好值
Δp ( pt, xi, θ )= g ( xi | wt, z* ) h ( θ, pt )
sin θ 0 ≤ θ < π ( 2L ) h ( θ, pt ) = （ 9）
1 其他
其中， θ是向量F ( xi )- z*与权向量wt的空间夹角。L为设置的控制参数， L越小，限制作用越强。图1b所示为加入限制算子后的稳定配对关系，可以看出，加入限制算子后，被选择到的解分布性能更为优秀。
（ 8）
图1 稳定配对关系示例
Fig.1 Illustrative examples of stable
matching relationships
2.3 利用MOEA/D⁃LSTM求解FJSP的算法流程
当利用MOEA / D ⁃LSTM 求解 FJSP 时，主要包括下列操作： ①将原始解空间中可行解进行染色体编码和解码； ②对父代染色体进行交叉、变异操作，获得子代染色体； ③对染色体进行选择，若满足截止条件，则停止算法，否则重复进行操作②。
2.3.1 染色体编码与解码染色体编码方式为双层编码 ，每个染色体
［］ 13表示一个可行解，对应工件的加工顺序及所使用的机器。若待加工的工件总数为m，工件i包含ni （ ni> 1）道工序，则染色体是长度为2 Σni
的整数Σni
串。前 个基因为染色体的第一层即工序编码，基因的顺序决定工序的调度顺序，基因i为工
· ·
** l
Tt Tt
* l
i
件 Ji的编号，基因i在工序编码中第j次出现代表
Σni
工件i的第j道工序即Oij。后 个基因为染色体的第二层即机器编码，表示加工每道工序的机器编号，基因p表示所用机器编号即Mp。图2所示为一包含3个工件、3台机器的染色体,工序编码为［ 1321231 ］，代表的加工顺序为［ O11 ， O31 ，，，，， O21 O12 O22 O32 O13 ］，其中， a位置的基因3在工序编码中第2次出现,表示为O32代表工件3的第2道工序；机器编码为［ 2132221 ］，代表加工每道工序所用的机器为［ M2 ，，，， M1 M3 M2 M2 ，， M2 M1 ］。
图2 染色体编码
Fig.2 Chromosome coding染色体解码时首先根据工序编码确定工件及相应的工序，然后从机器编码中找出对应的加工机器，从对应的时间矩阵中找到对应位置的加工时间，这样便可确定工序的加工机器和所用时间。依次扫描工序编码即可确定所有工序的加工顺序以及加工参数，从而得到一个完整可行的工序调度方案。
2.3.2 交叉与变异
本文对交叉操作过程中产生的非法染色体进行修复，结合图3对交叉操作（包含修复操作）步骤做详细说明：首先，在工序编码随机选择两个位置a、b，在机器编码中有两个对应的位置a′ 、b′ ，将两父代染色体ab、和 a′ 、b′之间的部分调换，得到子代1′和子代2′ ；然后，对比子代1′、子代2′与父代染色体的工序编码部分，可知子代1′多了一个基因3、少了一个基因2，子代2′多了一个基因2、少了一个基因3，故将子代1′的基因3与子代2′的基因2对调，并对机器编码做相应的调整，得到子代1″和子代2″；由两条染色体工序编码的变化可知， 2.3.3 染色体选择
本文利用MOEA/D⁃LSTM算法对父代和子代所构成的整个候选集进行选择，以获得具有较· 1746 · c位置的基因2表示工序O22， c′位置的基因2表示用于加工工序O22的机器2，因此，子代1″工序编码中的两个2都表示工序O21，同理，子代2″工序编码中的两个2都表示工序O21。对子代1″和子代2″进行修复操作：将两条染色体ab、之间的部分（做交换的部分）重新编码，并重新选择加工工序的机器，即调整a′ 、b′之间的部分；未交换的部分则保持不变。经过交叉操作得到的子代染色体满足约束条件，为可行解。
图3 交叉操作示意图
Fig.3 Schematic diagram of crossover operator为了防止算法陷入局部收敛 ，提高算法的
［］ 14局部优化能力和种群多样性，需要进行变异操作。个体变异过程如图4所示：首先，从经过交叉形成的2个子代染色体中随机选择1个染色体；然后，在工序编码中随机选择基因a、基因b进行交换，此交换将改变工序编码中每个基因所代表的工序，如c位置的基因1在原染色体表示工序O12，在新染色体变为表示O13， d位置的基因2在原染色体表示工序O22，在新染色体变为表示O21，同时机器编码也随之变化。经此变异操作得到的新染色体能够满足约束条件。 高收敛精度和具有广泛分布的目标函数值。
利用MOEA/D⁃LSTM算法求解FJSP 的整个算法流程如下。
（ 1）初始化。①初始化迭代次数K,种群包含染色体个数N,限制算子控制参数L、交叉概率Pc和变异概率Pm ； ②设置一组均匀分布的权向量w =
( w1, w2, ⋯, wN),其中一个向量wt =( wt, 1, wt, 2, …, wt, m) ∈ Rm, wt, ≥0 ,同时可得子问题集合P =
j
{ p1, p2, …, pN}，计算每一个权向量与其他权向量的欧氏距离，对权向量wt ,设置一个集合B ( t )= { t 1, t 2, …, tT}，此时ww、、、… w 为离wt最近的
t1 t2 tT
T个向量； ③随机产生N个整数编码染色体的种群X ={ x1, x2, …, xN},计算适应度值，令g= 1；并初始化参考点z* =( z* 1, z* 2, …, z* ) 。
T m
（ 2）更新。①生成N个子代染色体。对于i∈ [1， N] ，从B ( i )中随机选择两个索引τκ、 ，进而选择两染色体xκ 和 xτ ；将 xκ 和 xτ作为父代染色体进行模拟二进制交叉和变异操作，生成一个子代染色体xN 。②更新参考点。将父代染色体和
+ i
子代染色体合并解集合X ={ x1, x2, …, x2N } ；计算适应度值，由z = min { fl ( xi )}更新参考点。③更新种群。将染色体集合X和子问题集合P作为输入，生成偏好矩阵ψP 和 ψS ；根据偏好矩阵选择优越的子代染色体作为下一次迭代的父代，并置g ← g +1。
（ 3）算法停止。当g > K时，满足停止条件，输出种群染色体,并解码成调度方案；否则，返回步骤（ 2）。 3 实验设计与结果分析
3.1 仿真算例
3.1.1 实验设置
本文选用 CIMS 领域经典 MK1~MK15 算例 。将NSGA-Ⅱ、MOEA/D-STM和MOEA/
［］ 15
D-LSTM在标准算例上独立运行20次，验证各算法在解决双目标问题的性能。NSGA⁃Ⅱ因其快速排序、及时估算拥挤距离以及容易比较拥挤距离这三个特点，成为CIMS领域最常用的多目标算法之一。NSGA ⁃ Ⅱ需要设置的参数见文献［ 16 ］， MOEA ⁃ STM 需要设置的参数见文献［ 11 ］。MOEA ⁃ LSTM 参数设置：种群染色体数目N = 40，迭代次数K = 400，交叉概率Pc = 0.8，变异概率Pm = 0.6，限制算子控制参数设置L = 2，邻域大小T = 10。
3.1.2 算法收敛性能及分布性能分析
算法的收敛性能决定能否得到一个优秀的解决方案，良好的分布性能则是提供给抉择者宽泛选择的保证。为了验证算法的性能，本文以这两种性能指标来考察三种算法。
表1给出了三种算法获得的最大完工时间和总成本。由表1可以看出，对两目标来说， MOEA/ D⁃LSTM在算例MK01、MK02等 11个标准算例上找到最优解，而NSGA⁃Ⅱ仅在MK03、MK11上找到最优解， MOEA/D⁃STM仅在MK06、MK09上找到最优解。由此可验证MOEA/D⁃LSTM总体上展现出优于MOEA/D⁃STM和 NSGA⁃Ⅱ算
* l
法的收敛性能。
由收敛性能比较结果可知， MOEA/D⁃LSTM仅在4个标准算例上略逊于其他两种算法。为了不失一般性，在比较算法的分布性能时，本文从15个标准算例中选择MK03、MK11、MK15三个标准算例。对每个算法选择包含最小完工时间染色体的种群，并通过非支配排序得到每个种群的Pareto最优解。由于种群不同， Pareto最优解的个数也会不同。由图5a~图5c可知， NSGA⁃Ⅱ有个3 Pare⁃ to最优解， MOEA/D⁃STM有个7 Pareto最优解，而MOEA/D⁃LSTM则有9个 Pareto最优解且在目标空间中分布均匀，分布性能优于前两种算法；由图5e、图 5f可看出， NSGA⁃Ⅱ有个7 Pareto最 优 解 ，但 其 中 3 个 解 拥 挤 在 空 间 Ω1 = { ( f 1, f 2 ) | 750 ≤ f1 ≤ 800, 1 230 ≤ f2 ≤ 1 240}，却没有一个 Pareto 最优解处于空间Ω2 ={( f 1, f 2 ) | 750 ≤ f1 ≤ 8001240 ≤ f2 ≤ 1 250 }中； MOEA/D⁃ STM有个8 Pareto最优解，但其中4个解拥挤在空间 Ω3 ={( f 1, f 2 )| 750 ≤ f1 ≤ 800}， 2 个解拥挤在空间 Ω4 =( f 1, f 2 ) | 810 ≤ f1 ≤ 830, 1 230 ≤ f2 ≤ 1 232}, MOEA/D-LSTM在算例MK11上虽然收敛性能不如NSGA-Ⅱ,但是有8个 Pareto 最优解且在目标空间上均匀分布，分布性能优于前两种算法；由图5g~图5i可以明显看出， MOEA/D⁃ LSTM在算例MK15上，收敛性能和分布性能均优于另外两种算法。综上所述， MOEA/D⁃LSTM在标准算例MK01~MK15上的综合性能优于另外两种算法。
3.2 实例验证
本文以某制桶公司第一生产车间10月份某一订单为例，验证 MOEA / D ⁃ LSTM解决双目标FJSP的性能。订单包括6×30个桶，从原材料到成品需要经过10道工序，该生产车间共有28台机器（编号1~28）用于加工。车间设备名称与编号列于表2，6种桶所需加工工序及其可用的加工机械、所用加工时间如表3所示。
表2 设备及编号
Tab.2 Equipment and number 注：每个单元由两行数字组成，第一行表示加工该工序可用的机器编号，第二行为对应的加工时间，单位为s。
使用3种算法处理该订单，不考虑工件在机器间转移的时间，实验各参数不变，所得结果如表4所示。由表4可知， MOEA/D⁃LSTM算法所得到的最大完工时间最优解为3 991 s，加工成本最优解为5 010.4元，比其他两种算法得到的最优解更好。分布性能如图6所示，由图可知， MOEA/DLSTM算法提供了更为宽泛的调度方案。
图6 3种算法的分布性能比较
Fig.6 Distribution comparison of three algorithms
4 结论
针对 MOEA / D ⁃ STM以及常用算法求解FJSP过程中的弊端，本文提出一种带有限制算子的进化算法MOEA/D⁃LSTM。该算法利用了染色体在目标空间中的位置信息，将位置信息和限制算子相结合计算一个新的偏好值，从而得到一个带限制算子的偏好列表。在配对过程中可以使子问题选择更适合的解，以使每一代解均匀分布，最终得到更好的最优解以及更好的分布性能。从对15个双目标标准测试集和实例的实验结果看， MOEA/D⁃LSTM在保持MOEA/D⁃STM的优良
· 1749 ·
性能的基础上，进一步提高了收敛性能，同时解决了原算法出现的解分布不均匀的问题，给决策者提供更为宽泛的调度方案。
本文未考虑原材料的价格变化、库存量及成品存储费用对最终优化结果的影响，下一步的研究内容将会把原材料的价格波动、原材料库存量以及成品存储费用考虑在内，进一步模拟现实情况。
参考文献：
［ 1 ］ 周辉仁，唐万生，魏颖辉.基于微粒群算法的柔性流水车间调度优化［ J ］ .中国机械工程， 2010，21（9）： 1053⁃1057.
ZHOU Huiren，TANG Wansheng，WEI Yinghui. PSO⁃based Optimization of Flexible Flow⁃shop Scheduling ［］ J .China Mechanical Engineering，2010， 21（9）：1053⁃1057.
［ 2 ］ 王云，谭建荣，冯毅雄,等.基于SPEA的多目标柔性作业车间调度方法［］ J.中国机械工程， 2010，21（10）： 1167⁃1172.
WANG Yun，TAN Jianrong，FENG Yixiong，et al. Multi ⁃ objective Flexible Job ⁃ shop Scheduling Based on Strength Pareto Evolutionary Algorithm ［］ J . China Mechanical Engineering，2010，21（10）：1167⁃1172.
［ 3 ］ 朱传军，邱文，张超勇，等.多目标柔性作业车间稳健性动态调度研究［ J. ］中国机械工程， 2017，28（2）： 173⁃182.
ZHU Chuanjun，QIU Wen，ZHANG Chaoyong，et al. Multi ⁃ objective Flexible Job Shop Dynamic Sched⁃ uling Strategy Aiming at Scheduling Stability and Robustness ［］ J . China Mechanical Engineering， 2017，28（2）：173⁃182.
［ 4 ］ 彭建刚，刘明周，张玺，等.基于Pareto优化的离散自由搜索算法求解多目标柔性作业车间调度问题［ J. ］中国机械工程， 2015，26（5）：620⁃626.
PENG Jiangang，LIU Mingzhou，ZHANG Xi，et al. Discrete Free Search Based on Pareto Optimality for Multi⁃objective Flexible Job⁃shop Scheduling Prob⁃ lem ［］ J .China Mechanical Engineering，2015，26（5）： 620⁃626.
［］ 5 WANG Xiaojuan，GAO Liang，ZHANG Chaoyong， et al. A Multi ⁃ objective Genetic Algorithm Based on Immune and Entropy Principle for Flexible Job ⁃ shop Scheduling Problem ［］ J . International Journal of Advanced Manufacturing Technology ，2010 ，51 （ 5/8）：757⁃767.
［ 6 ］ 公茂果，焦李成，杨咚咚，等.进化多目标优化算法研究［ J ］，软件学报， 2009，20（2）：271⁃289.
GONG Maoguo，JIAO Licheng，YANG Dongdong， et al. Research on Evolutionary Multi ⁃ objective Op⁃ timization Algorithms ［］ J .Journal of Software，2009, 20（2）：271⁃289.
［ 7 ］ 居学尉，贺利军，朱光宇.基于离散Fréchet距离的多
目标优化方法［ J. ］计算机集成制造系统， 2017，23 （ 2）：253⁃260.
JU Xuewei，HE Lijun，ZHU Guangyu. Multi ⁃ objec⁃ tive Optimization Method Based on Discrete Fréchet Distance ［］ J . Computer Integrated Manufacturing Systems，2017，23（2）：253⁃260.
［ 8 ］ 张超勇，董星，王晓娟，等.基于改进非支配排序遗传算法的多目标柔性作业车间调度［ J. ］机械工程学报， 2010.46（11）：156⁃163
ZHANG Chaoyong，DONG Xing，WANG Xiaojuan， et al. Improved NSGA ⁃ Ⅱ for the Multi ⁃ objective Flexible Job ⁃ shop Scheduling Problem ［］ J . Journal of Mechanical Engineering，2010，46（11）：156⁃163. ［］ 9 ZHANG Qingfu，LI Hui.MOEA/D：a Multiobjective Evolutionary Algorithm based on Decomposition ［］ J . IEEE Transaction on Evolutionary Computation， 2007，11（6）：712⁃731.
［］ 10 CHANG Peichan，CHEN S H，ZHANG Qingfu，et al. MOEA / D for Flow Shop Scheduling Problem ［］ C // Proceeding of IEEE Interational Conference on Evolutionary Computation. Hong Kong，2008： 1433⁃1438.
［］ 11 LI Ke，ZHANG Qingfu，KWONG S，et al. Stable Matching Based Selection in Evolutionary Multiob⁃ jective Optimization ［］ J . IEEE Transactionon Evo⁃ lutionary Computation，2014，18（6）：909⁃924.
［］ 12 JIANG Siwei，CAI Zhihua，ZHANG Jie，el al.Mul⁃ tiobjective Optimization by Decomposition with Pa⁃ reto ⁃ adaptive Weight Vectors ［］ C //2011 Seventh International Conference on Natural Computation. Shanghai，2011：1260⁃1264.
［ 13 ］ 陈震.SPEA2多目标进化算法及其在车间调度中的应用研究［ D. ］兰州：兰州理工大学， 2015.
CHEN Zhen. The Research on the Strength Pareto Evolutionary Algorithm 2 and Its Application on the Job Scheduling Problems ［］ D . Lanzhou：Lan⁃ zhou University of Technology，2015.
［ 14 ］ 林震，帅剑平，袁煜.多目标柔性作业车间调度的多交叉策略元胞进化算法［ J. ］科学技术与工程， 2017， 17（7）：69⁃76.
LIN Zhen，SHUAI Jianping，YUAN Yu. Multi ⁃ crossover Strategy of Multiobjective Cellular Ge⁃ netic Algorithm Research on Flexible Job ⁃ shop Scheduling Problem ［］ J . Science Technology and Engineering，2017，17（7）：69⁃76.
［］ 15 PAOLO B. Routing and Scheduling in a Flexible Job Shop by Tuba Search ［］ J . Annals of Operation Research，1993，41（3）：157⁃183 ．
［］ 16 LI Chuanpeng，CUI Huangyong，WANG Guicong. The Optimization of Flexible Job ⁃ shop Scheduling Problem Based on NSGA⁃Ⅱ ［］ J .Advanced Materi⁃ als Research，2013，651：684⁃687.*
(编辑 张 洋)
作者简介：杨宇，男， 1991年生，硕士研究生。研究方向为生产计划与调度、智能调度算法等。朱启兵（通信作者），男， 1973年生,教授。E⁃mail：zhuqib@163.com。