第45卷第7期 机械工程学报 Vol.45 No.7 2009 年 7 月 JOURNAL OF MECHANICAL ENGINEERING Jul. 2009
DOI:10.3901/JME.2009.07.145 改进遗传算法求解柔性作业车间调度问题*
张国辉 高 亮 李培根 张超勇
(华中科技大学数字制造装备与技术国家重点实验室 武汉 430074 )
摘要:分析柔性作业车间调度问题的特点，提出一种求解该问题的改进遗传算法。在考虑各个机器负荷平衡，所有机器上的 总负荷和最大完工时间等性能指标更加合理情况下，设计一种全局搜索、局部搜索和随机产生相结合的初始化方法，提高种 群初始解的质量，加快遗传算法的收敛速度。结合问题特点设计合理的染色体编码方式、交叉算子和变异算子，防止遗传操 作过程中非法解的产生，避免染色体的修复，提高求解效率。使用文献中相同的实例测试利用初始化方法的改进遗传算法， 并将计算结果与文献中其他遗传算法的测试结果进行比较，验证所提出的初始化方法的可行性和有效性。 关键词:遗传算法 柔性作业车间调度 初始化
中图分类号:TP301
Improved Genetic Algorithm for the Flexible Job-shop Scheduling Problem
ZHANG Guohui GAO Liang LI Peigen ZHANG Chaoyong (State Key Lab of Digital Manufacturing Equipment and Technology, Huazhong University of Science & Technology, Wuhan 430074)
Abstract:The characteristic of the flexible job shop scheduling problem (FJSP) is analyzed, an improved genetic algorithm is proposed to solve the FJSP. To keep workload balance among the machines, improve the quality of the initial population and accelerate the speed of the algorithm’s convergence, a new initialization method is proposed, which combines with global search, local search and random generation. Considering the characteristic of the problem, rational chromosome encoding, crossover operator and mutation operator are designed to prevent the generation of illegal solutions, avoid chromosome repair and improve efficiency of the algorithm. The improved genetic algorithm is tested on instances taken from the literature and compared with their results. The computation results show that the improved genetic algorithm is feasible and effective.
Key words:Genetic algorithm Flexible job shop scheduling
0 前言*
柔性作业车间调度问题(Flexible job-shop scheduling problem, FJSP)是传统作业车间调度问题 (Job-shop scheduling problem, JSP)的扩展。在传统的 作业车间调度问题中，每个工件的加工工序是预先 确定的，并且每一道工序的加工机器和加工时间也 是预先确定的。而在柔性作业车间调度问题中，每 道工序的加工机器是不确定的。每个工件的每一道 工序可以在多个可选择的加工机器上进行加工，并 且选择不同的加工机器所需要的加工时间是不同 的。这增加了调度的灵活性，比较符合生产的实际
∗ 国家高技术研究发展计划(863 计划，2006AA04Z131, 2007AA04Z107) 和国家自然科学基金(50305008)资助项目。20080823 收到初稿， 20090306 收到修改稿
Initialization
情况，是迫切需要解决的一类调度问题。 与传统的作业车间调度问题相比，柔性作业车 间调度问题减少了机器约束，加大了机器的不确定 性，扩大了可行解的搜索范围，是更加复杂的 NP-Hard 问题。目前，求解 FJSP 的常用方法有模拟 退火(SA)、禁忌搜索(TS)、粒子群算法(PSO)和遗传 算法(GA)等[1-4]。其中遗传算法以其鲁棒性好、通用 性强、计算性能优良，且具有隐含并行性和全局搜 索能力等特点，用其求解 FJSP 的文献相对较多。 杨晓梅等[5]和席卫东等[6]在遗传算法的染色体编码 上进行了改进，张超勇等[3]在遗传算法的流程逻辑 上进行了改进，以提高求解效率。柔性作业车间调 度问题不仅要对工序进行排序，而且还面临对可选 机器选择的问题，考虑因素较多，使调度问题更加 复杂。本文针对 FJSP 特点，提出一种新的初始化
146 机械工程学报 第45卷第7期期
方法，得到较好的初始解，使得利用遗传算法求解 FJSP 时在求解速度和求解质量上都有明显提高。
1 柔性作业车间调度问题描述 柔性作业车间调度问题的描述如下:n 个工件
{J1, ,Jn}要在m台机器{M1, ,Mm}上加工。每个 工件包含一道或多道工序，工序顺序是预先已确定
的，每道工序可以在多台不同加工机器上进行加工， 工序的加工时间随加工机器的不同而不同。调度目 标是为每道工序选择最合适的机器、确定每台机器 上各个工件工序的最佳加工顺序以及开工时间，使 整个系统的某些性能指标达到最优。因此，柔性作 业车间调度问题包含两个子问题:确定各工件的加 工机器和确定各个机器上的加工先后顺序。
每道工序可以在任意一个可选择的加工机器上 进行加工的调度称为完全柔性作业车间调度;反之， 每道工序只能在部分可选的加工机器上进行加工的 调度称为部分柔性作业车间调度，如表 1 所示。
表 1 一个部分柔性作业车间调度问题实例
(1) 最大完工时间 CM
minCM=min(max(Ck)) 1≤k≤m (1)
式中， Ck 是机器 M k 的完工时间。 (2) 最大负荷机器负荷 WM
minWM=min(max(Wk)) 1≤k≤m (2) 式中，Wk 是机器Mk 的工作负荷。
(3) 所有机器的总负荷WT
表 1 是一个包括 2 个工件、5 台机器的柔性作 业车间调度问题的加工机器和加工时间表。其中， “—”表示此工序不能选择对应的机器进行加工。表 1 所列问题是一个部分柔性作业车间调度问题，如 果表 1 中所有的“—”都对应加工时间，表明每个 工件的每道工序对所有的机器都可以进行选择加
工，就是完全柔性作业车间调度问题。
2 改进遗传算法求解柔性作业车间调 度问题
2.1 染色体编码和解码 编码和解码是指解和染色体之间的相互转换，
是应用遗传算法的首要和关键问题。柔性作业车间 调度问题需要为每道工序在可加工机器集中选择一 台加工机器并对所有的工序进行排序。为此，柔性 作业车间调度编码由两部分组成:一部分是机器染 色体，基于机器分配的编码，确定所选择的加工机 器，对应机器选择子问题;另一部分是工序染色体， 基于工序的编码，确定工序间的先后加工顺序，对 应工序先后加工的排序子问题。融合这两种编码方 法，形成一条染色体，也就是柔性作业车间调度的 一个可行解。
设工序总数为 l ，依次从时间表中对应的第一 个工件第一道工序直到最后一个工件最后一道工序 为止，工序号分别用1,2, ,l表示。对于l道工序， 形成l个可选择机器的子集分别为{S1,S2, ,Sl}，其 中第 i 道工序的可加工机器集合表示为 Si 。 Si 中可
选加工机器的个数为ri，表示为{mi1,mi2, ,miri}。
第一部分基因串的长度为 l，表示为 g1g2g3 gi gl 。其中第i个基因gi 为[1,ri ]内的整 数，表示第 i 个工序的加工机器号为集合 Si 中的第 gi个元素migi 。如第1道工序有5台机器作为可选
择机器，则ri =5。即第 1 道工序可选机器集为 {M1,M2,M3,M4,M5}，根据在[1,5]中随机产生的整 数 g1 ，从集合中确定第 1 道工序加工时所用的机器。
工件 工序
O11 J1 O12 O13 O21 J2 O22 O23
可选择的加工机器
M1 M2 M3 M4 M5
26534 — 8 — 4 — 4 — 3 6 2 3—6—5 465—— — 7 11 5 8
minWT =min
∑ k=1
W (3) k
m
注:J1 表示工件 1，O12 表示第 1 个工件的第 2 道工序，其余类似。
此外，在加工过程中还需要满足下面的约束 条件。
(1) 同一台机器上在同一时刻只能加工一个 工件。
(2) 同一工件的同一道工序在同一时刻只能 被一台机器加工。
(3) 每个工件的每道工序一旦开始加工不能 中断。
(4) 不同工件之间具有相同的优先级。
(5) 不同工件的工序之间没有先后约束，同一 工件的工序之间有先后约束。
(6) 所有工件在零时刻都可以被加工。
本文中同时考虑三种性能指标:最大完工时间
最小、最大负荷机器负荷最小和所有机器上的总负
荷最小，这三种性能指标的目标函数分别如下。
月 2009 年 7 月 张国辉等:改进遗传算法求解柔性作业车间调度问题 147
如g1 =2，则机器M2为第1道工序加工时所用的机 器。以此类推，确定第2,3, ,l工序的加工机器。 表 1 所表示的 FJSP 问题中，总共有 6 道工序，假 设此部分基因串为2-1-4-3-2-3，则表示这 6 道工序 的加工机器分别为M2 -M2 -M5 -M5 -M2 -M4 。
第二部分基因串的长度也为 l，对应于一串工 件号的排列，其中每个工件号出现的次数为此工件 包括的工序总数。从左到右扫描染色体，对于第 j 次出现的工件序号，表示该工件的第 j 道工序。对 于表 1 所表示的 FJSP 问题，假设一个可行的第二 部分基因串可以表示为1-2-2-1-1-2 ，对应的工序顺序 表示为O -O -O -O -O -O 。
生的方法。 GS:设置一个数组，长度和机器数相等，数组
的顺序依次对应加工机器的顺序，每一位上的值对 应相应机器上的加工时间。随机在工件集中选择一 个工件，从当前工件的第一道工序开始，将当前工 序的可选加工机器的加工时间加上数组中对应的时 间，从中选择最短的时间作为当前工序的加工机器， 并且将数组更新，即把被选择的加工机器的加工时 间加到数组中相应的位置上，依次类推直到当前工 件的所有工序的加工机器选择完毕，然后再随机选 择一个工件开始，直到所有工件的工序选择完毕。 这样保证了最短加工机器先被选到而且保证了加工 机器上的工作负荷平衡。具体执行步骤如下。
步骤 1:设置一个整型数组，长度等于所有机 器的总数，并且依次对应机器[M1, ,Mm ]上的加工
时间总负荷。同时初始化数组中每一个元素值为 0。 步骤 2:随机从工件集中选择一个工件，同时
选择当前工件的第一道工序。
步骤 3:将当前工序的可选加工机器集中的加
工机器的加工时间和数组中相应机器位置的时间数
值相加，但不更新数组。
步骤 4: 从相加后的时间值中，选择最小的那 台机器作为当前工序的加工机器，同时按照第 2.1 节描述的编码方式，在染色体的相应位置记录 gi 。
步骤 5:将当前被选择的加工机器的加工时间 相加到数组中相应位置机器的加工负荷中，同时更 新数组作为下一次选择的依据。
步骤 6:选择当前工件的下一道工序，重复执 行步骤 3~5，直到当前工件的所有工序的加工机器 选择完毕。
步骤 7:从工件集中除去已被选择的工件，从 剩下的工件集中随机选择一个工件，同时选择当前 工件的第一道工序，重复执行步骤 3~6，直到工件 集中的所有工件被选择完毕。
以表 1 柔性作业车间调度问题为例，假设第一 次随机选择到的加工工件是工件 J1，由于只有两个 工件因此第二次选择的只有工件 J2，那么前四道工 序的执行过程如图 1 所示。
LS:同全局搜索原理上基本一致，但是每次对 一个工件选择完毕时，数组需要重新设置为 0，并 且不存在随机选择工件。设置一个数组，长度和机 器数相等，选择工件集中第一个工件，选择当前工 件的第一道工序开始，将当前工序的可选加工机器 的加工时间加上数组中对应的时间，从中选择最短 的时间作为当前工序的加工机器，并且将数组更新， 即把被选择的加工机器的加工时间加到数组中相应
11 21 22 12 13 23
解码时先根据第一部分基因串确定每道工序的
加工机器，然后依据第二部分基因串确定每台加工
机器上的加工工序的顺序，即转换为一个有序的工
序表，最后根据此工序表对各工序以最早允许的加
工时间逐一进行加工，将所有工序都安排在适当的
加工位置，从而产生可行调度方案，保证生成的调
度是主动调度。
2.2 初始化方法 初始解的质量对遗传算法求解的速度和质量有
非常大的影响。FJSP 不但要解决机器选择问题还要 解决所有工序排序问题。目前，大部分文献一般采 用的是随机初始化，使得初始解的质量偏低，导致 要增加迭代次数或种群大小来达到最优解或近似最 优解，这势必增加优化时间。KACEM 等[7-8]提出利 用时间表的 AL(Approach by localization)的方法进 行种群的初始化，取得了一定的成效。然而，所有 时间表的不断复制更新加大了资源的消耗，同时搜 索机制是在所有的备选机器中选择最小的，虽然效 果上有明显改善，但是搜索时间过长。HO 等[9]利用 经典 JSP 问题中的规则提出混合规则启发式机器排 序初始化方法(Composite dispatching rules，CDRs)， 然而这些规则仅应用于工序排序的初始化，没有考 虑机器选择问题。针对 FJSP 的特点，本文提出两 种新的初始化方法:全局搜索(Global search, GS)和 局部搜索(Local search, LS)，使各个被选择的机器的 工作负荷尽量平衡，充分提高机器的利用率，同时 还要考虑最大完工时间最小。GS 以深度优先进行搜 索，所有工件的工序的加工机器选择完毕时，进行 下一次循环时数组中各元素的值重置为 0;LS 是以 广度优先进行搜索，每一个工件的工序选择加工机 器完毕时，进行下一个工件工序的加工机器选择前 将数组各元素的值重置为 0。初始化种群时仍有一 定比例的个体采用随机产生，例如:种群的 60%采 用全局搜索，30%采用局部搜索，10%采用随机产
148 机械工程学报 第45卷第7期期
的位置上，依次类推直到当前工件的所有工序的加 工机器选择完毕，然后数组每一位重新设置为 0， 选择下一个工件，直到所有工件选择完毕。这样保 证了一个工件的工序中优先加工时间最短或者说选 择机器负荷最小的加工机器进行加工。具体执行步 骤如下。
图 1 GS 实例执行流程图
步骤 1:设置一个整型数组，长度等于所有机
器的总数，并且依次对应机器[M1, ,Mm ]上的加工 时间总负荷。同时初始化数组中每一个元素值为 0。
步骤 2:选择工件集中的第一个工件，同时选 择当前工件的第一道工序。
步骤 3:将当前工序的可选加工机器集中的加 工机器的加工时间和数组中相应机器位置的时间数 值相加，但不更新数组。
步骤 4:从相加后的时间值中，选择最小的那 台机器作为当前工序的加工机器，同时按照第 2.1 节描述的编码方式，在染色体的相应位置记录 gi 。
步骤 5:将当前被选择的加工机器的加工时间 相加到数组中相应位置机器的加工负荷中，同时更 新数组作为下一次选择的依据。
步骤 6:选择当前工件的下一道工序，重复执 行步骤 3~5，直到当前工件的所有工序的加工机器 选择完毕。
步骤 7:将数组中的每一位元素的值重新设置 为0。
步骤 8:从工件集中除去已被选择的工件，选 择工件集中下一个工件，同时选择当前工件的第一 道工序，重复执行步骤 3~7，直到工件集中的所有 工件被选择完毕。
以表 1 柔性作业车间调度问题为例，依次选择 工件 J1 和工件 J2，那么工件 J1 的三道工序加工机器 的选择执行过程如图 2 所示。
图 2 LS 实例执行流程图
另外，为了保证初始种群的多样性，种群中的
一部分采用随机初始化方法。按照工件的顺序，对
每个工件的每道工序的加工机器进行随机选择，产
生初始染色体。
2.3 选择操作 选择操作是根据个体的适应度值的高低选择适
应度值高的个体遗传到下一代种群中，淘汰适应度 低的个体。大部分文献中采用轮盘赌的方法进行选 择，需要进行目标值和适应值之间的转换，选择不 同的转换参数对运算结果有一定的影响。在本文中 采用 GOLDBERG 等[10]提出的锦标赛方法，目标值 直接就是适应值，免去中间的转换。从种群中随机 选择三个个体，选择最好的个体放到交叉池中，同 时被选择的个体还放回到种群中，可以重新参与选 择。
2.4 交叉操作 交叉操作主要是为了能够保留父代个体中的优
良信息，产生新的基因组合。交叉操作的优劣直接 影响产生后代的优劣和遗传算法收敛的速度与计算 效率。染色体中的两部分基因串采用同一交叉概率 分别进行，其中第一部分机器染色体的基因串采用 两点交叉，第二部分采用一种张超勇等[3]采用的基 于工件的 POX 交叉。
第一部分基因串采用两点交叉的方法，首先随
机选择两个交叉点，然后将两个父代位于两交叉点
月 2009 年 7 月 张国辉等:改进遗传算法求解柔性作业车间调度问题 149
之内的基因互换，从而得到两个交叉后代。 第二部分的基因串采用一种基于工件的 POX 交叉，该交叉操作的过程为:所有的工件随机分成 两 个 集 合 J s 1 和 J s 2 ， 子 代 染 色 体 c1 / c 2 继 承 父 代 p1/p2中集合Js1/Js2内的工件所对应的基因， c1/c2其余的基因位则分别由p2/p1删除了c1/c2中
已经确定的基因后所剩的基因按顺序填充。
2.5 变异操作 变异操作主要是为了维持群体的多样性，防止
早熟现象同时改善算法的局部搜索性能。针对柔性
作业车间调度问题中每道工序可以有多台机器加工
的特点，第一部分变异时，在机器染色体基因串中
随机选择一个位置，在此工序的机器集中随机选择
一个与它不相等的整数，替换当前的基因，这样得
到的解保证是可行解。
第二部分进行互换变异，即从染色体中随机选 择两个位置的基因，然后将它们进行位置的互换， 基于工序的编码保证了这种变异方法产生的是可 行解。
2.6 改进遗传算法执行流程 求解柔性作业车间调度问题比传统的作业车间
调度问题更加复杂，需要为每道工序在可选机器集
中选择一台机器和对每道工序进行排序，这两部分
一起构成了一种调度方案。结合新提出的初始化方
法，对遗传算法进行了改进，改进遗传算法的具体
步骤如下。
(1) 确定参数。包括种群规模、迭代次数、初 始化方法比例(GS，LS 以及随机的)、交叉概率、变 异概率。
(2) 按照设定的比例，利用提出的初始化方法 对种群进行初始化，产生质量较好的初始种群。
(3) 评价种群中每个染色体个体的适应度值即 目标值，如果满足结束条件输出最优解或者近似最 优解，并且结束运行;否则执行步骤(4)。
(4) 执行改进的锦标赛选择操作，选取下一代 种群。
(5) 对种群中满足交叉概率的染色体个体按照 交叉策略进行交叉。
(6) 对交叉得到的种群满足变异概率的染色体 个体按照变异策略进行变异，得到新一代种群。
(7) 返回步骤(3)。
终止条件一般是评价后的目标值达到预先设定
的目标值或者迭代的代数超过了设定的迭代次数。
本文实例测试时，选择了设定迭代次数。
3 计算结果与比较
为了验证比较算法性能，使用与文献[8, 11]等 相同的数据集进行测试，这些数据集包括三个柔性 作业车间问题实例分别是 8 个工件在 8 台机器上加 工的 8×8 部分柔性作业车间调度问题，10 个工件在 10 台机器上加工的 10×10 完全柔性作业车间调度问 题和 15 个工件在 10 台机器上加工的 15×10 完全柔 性作业车间调度问题。
改进的遗传算法采用Visual C++编程，程序在 环境为 P4 CPU，主频 1.8 GHz，内存为 512 MB 的 个人计算机上运行。经过多次实例测验比较，当 GS 比例为 60%，LS 比例为 30%，随机比例为 10%时 初始化产生的解的质量较好，其他运行参数为:种 群规模 Ps=200，迭代次数 G=100，交叉概率 Pc=0.8，变异概率 Pm=0.01。
表 2 中给出了三个柔性作业车间实例问题，8×8 问题、10×10 问题、15×10 问题的三个目标值的计 算结果。给出了本文利用新的初始化方法改进的遗 传算法与 KACEM[7]方法、XIA 等[11]方法和张超勇 等[3]方法在不同性能指标函数情况下的测试结果的 比较，这些指标函数包括最大完工时间 CM 最小、 最大负荷机器负荷 WM 最小和所有机器上总工作负 荷WT最小。
从表 2 可以看出，对于三个测试实例，改进遗 传算法在三个目标函数上都取得了较好的测试结 果，每一个目标值等于或者优于其他三个算法得到 的最优解。如求解 8×8 问题时，和 KACEM 等方法 的结果相比较在CM和WT都有了更好的结果。求解 10×10 问题时，和 XIA 等方法的结果相比较在 CM 相等情况下 WM 和 WT 都取得了更好的结果。求解 15×10 问题，和 XIA 等方法的结果相比较在最大完 工时间在其他两目标值相同的情况下缩短了 1 个时 间单位。同时使用新的初始化方法的改进遗传算法 在计算时间上也比较的快。
图 3~5 分别表示表 2 中列出的三个实例问题得 到较好解的甘特图。如图 6 所示，针对 8×8 柔性作 业车间问题实例的一个目标值最大完工时间最小， 测试本文中提出的新的初始化方法的收敛速度、参 数和前面设置的参数相同，可以看出利用提出的初 始化方法的收敛速度快于完全随机初始化产生初始 种群的初始化方法。试验结果显示，本文提出的新 的初始化方法改进的遗传算法求解柔性作业车间调 度问题在初始解的质量上和解的质量上都有明显提
150 机械工程学报 第45卷第7期期 高，并且收敛速度也有明显提高。
实例问题
(n×m) 8×8
测试结果比较
张超勇等方法
种群 平均时间 t/s
改进的 GA 最好值 计算时间
目标函数
CM WM WT CM
KACEM 等方法
15 16 15 16 14
表 2 XIA 等方法
N/A N/A 12 13 11 200 79 75 75 73 N/A
7 7 7
5 6 5 200 9.0 6 4.1
最好值
17.0 14
12 2.7 N/A 77
10.2
10×10 WM WT
CM 15×10 WM WT
45 44 N/A 24 12
11 11 N/A 91 91
N/A 42 11
N/A N/A 11 12.7 91
16.9 7
注:“N/A”为文献中没有计算此目标值。
图3
8×8实例的解(CM =14，WM =12，WT =77)
图 6
8×8 实例 CM 的收敛比较图
4 结论
图4
10×10实例的解(CM =7，WM =6，WT =42)
(1) 研究了三种性能目标下(最大完工时间最 小、最大负荷机器负荷最小和所有机器总负荷最小) 柔性作业车间调度问题，提出一种求解该问题的改 进遗传算法。
(2) 设计了一种新的 GS、LS 和随机搜索相结 合的初始化方法，提高种群初始解的质量，加快遗 传算法的收敛速度。使用文献中相同的实例测试采 用提出的初始化方法的改进遗传算法，并且将计算 结果与文献中其他遗传算法的测试结果进行比较， 计算结果有了进一步提高，同时计算时间有了一定 的缩短，验证了所提出的初始化方法的可行性和有 效性。
参考文献
[1] ZHANG H P，GEN M.Multistage-based genetic algorithm for flexible job-shop scheduling problem [J].Complexity International，2005，11:223-232.
[2] MASTROLILLI M，GAMBARDELLA L M.Effective
图5
15×10实例的解(CM =11，WM =11，WT =91)
月 2009 年 7 月 张国辉等:改进遗传算法求解柔性作业车间调度问题 151
neighborhood functions for the flexible job shop problem
[J].Journal of Scheduling，2000，3(1):3-20.
[3] 张超勇，饶运清，李培根，等.柔性作业车间调度问题的
两级遗传算法[J]. 机械工程学报，2007，43(4):119-124. ZHANG Chaoyong，RAO Yunqing，LI Peigen，et al.Bilevel genetic algorithm for the flexible job-shop scheduling problem[J]. Chinese Journal of Mechanical Engineering, 2007，43(4):119-124.
[4] GAO L，PENG C Y，ZHOU C，et al.Solving flexible job-shop scheduling problem using general particle swarm optimization[C]//Proceedings of The 36th International Conference on Computers & Industrial Engineering, Taipei, China.2006:3 018-3 027.
[5] 杨晓梅，曾建潮.遗传算法求解柔性 job shop 调度问题[J]. 控制与决策，2004，19(10):1 197-1 200.
YANG Xiaomei，ZENG Jianchao.Solving flexible job shop scheduling problem using genetic algorithm[J].Control and Decision，2004，19(10):1 197-1 200.
[6] 席卫东，乔兵，朱剑英. 基于改进遗传算法的柔性作业车 间调度[J].哈尔滨工业大学学报，2007，39(7):1 151-1 153. XI Weidong，QIAO Bing， ZHU Jianying.A genetic algorithm for flexible job shop scheduling based on two-substring gene coding method[J].Journal of Harbin Institute of Technology，2007，39(7):1 151-1 153.
[7] KACEM I.Genetic algorithm for the flexible job-shop scheduling problem[J].IEEE International Conference on Systems，Man. and Cybernetics, 2003，4:3 464-3 469.
[8] KACEM I，HAMMADI S，BORNE P.Approach by localization and multi-objective evolutionary optimization for flexible job-shop scheduling problems[J].IEEE Transactions on Systems，Man. and Cybernetics，Part C，2002，32(1): 408-419.
[9] HO N B，TAY J C.GENACE:An efficient cultural algorithm for solving the flexible job-shop problem[C]//Proceedings of 2004 Congress on Evolutionary Computation，Piscataway， IEEE，2004:1 759-1 766.
[10] GOLDBERG D E，DEB K.A comparative analysis of selection schemes used in genetic algorithms[C]//RAWLINS G ， ed . Foundations of Genetic Algorithms ， Morgan Kaufmann， 1991:69-93.
[11] XIA W J，WU Z M.An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problem[J].Computer & Industrial Engineering，2005，48: 409-425.
作者简介:张国辉，男，1980 年出生，博士研究生。主要研究方向为柔 性作业车间调度。
E-mail:zhanggh@smail.hust.edu.cn