第17卷第3期 智能系统学报 Vol.17 No.3 2022年5月 CAAI Transactions on Intelligent Systems May 2022 D0:10.11992/tis.202103006 网络出版地址：https:/ns.cnki.net/kcms/detail/23.1538.TP.20211210.2314.004html 含忽略工序和不相关机的混合流水车间调度 轩华，樊银格，李冰 (郑州大学管理工程学院，河南郑州450001) 摘要：研究从炼钢等生产过程提炼出的含忽略工序和不相关并行机的混合流水车间调度问题，以最小化最大 完工时间为目标，建立整数规划模型，并提出结合全局搜索、自适应遗传算法和候鸟优化的遗传候鸟优化算法 以求解该模型。在算法中采用与处理时间相关的全局搜索和随机程序以获得初始种群，提出自适应交叉和变 异操作改进遗传算法解，在迭代进程中，引入基于工件、机器和工序位3种邻域搜索结构的候鸟优化算法更新 最佳解。仿真实验中将遗传候鸟优化算法的实验结果与几种启发式算法进行对比，证明了模型和算法的有效性。 关键词：忽略工序；不相关并行机：混合流水车间；全局搜索：自适应遗传算法；领域搜索；：最大完工时间：遗传 候鸟优化算法 中图分类号：TP39:TB49文献标志码：A文章编号：1673-4785(2022)03-0459-12 中文引用格式：轩华，樊银格，李冰.含忽略工序和不相关机的混合流水车间调度J.智能系统学报，2022,17(3)：459-470. 英文引用格式：XUAN Hua,FAN Yinge,.LI Bing.Hybrid flowshop scheduling with missing operations and unrelated machines CAAI transactions on intelligent systems,2022,17(3):459-470. Hybrid flowshop scheduling with missing operations and unrelated machines XUAN Hua,FAN Yinge,LI Bing (School of Management Engineering,Zhengzhou University,Zhengzhou 450001,China) Abstract:The hybrid flowshop scheduling problem with missing processes and unrelated parallel machines extracted from steelmaking and other production processes is studied.An integer programming model is formulated to minimize the maximum completion time,and a genetic migrating birds optimization algorithm based on the global search,self-ad- aptive genetic algorithm,and migrating birds optimization is proposed to solve the model.The initial population is ob- tained by the global search considering the machine processing time and random procedure.Then,self-adaptive crossov- er and mutation operators are developed to improve the solutions of the genetic algorithm.In the iterative process,mi- grating birds optimization combined with three neighborhood search structures based on the job,machine,and opera- tion position is introduced to update the best solutions.Finally,the experimental results of the genetic migrating birds optimization algorithm are compared with several heuristic algorithms to prove the effectiveness of the proposed model and algorithm. Keywords:missing operations;unrelated parallel machines;hybrid flowshop;global search;self-adaptive genetic al- gorithm;neighborhood search;maximum completion time;genetic migrating birds optimization algorithm 含忽略工序的混合流水车间调度(hybrid见。在经典混合流水车间调度问题中，通常假定 flowshop scheduling with missing operation,HF- 工件经所有工序处理，但在实际生产中，工件会 SMO)在炼钢、不锈钢、塑料等制造工业较为常 忽略某些工序，即一些工件可能不经某些工序处 收稿日期：2021-03-03.网络出版日期：2021-12-13. 理，如炼钢-连铸生产中，由电弧炉或转炉生产的 基金项目：国家自然科学基金项目(U1804151):河南省科技攻 钢水要在高温下经精炼和连铸工序进行加工，不 关计划项目(202102310310). 通信作者：轩华.E-mail:hxuan@zzu.edu.cn 同的钢种对生产路线的要求会有所不同，像Q235
DOI: 10.11992/tis.202103006 网络出版地址: https://kns.cnki.net/kcms/detail/23.1538.TP.20211210.2314.004.html 含忽略工序和不相关机的混合流水车间调度 轩华，樊银格，李冰 （郑州大学 管理工程学院，河南 郑州 450001） 摘 要：研究从炼钢等生产过程提炼出的含忽略工序和不相关并行机的混合流水车间调度问题，以最小化最大 完工时间为目标，建立整数规划模型，并提出结合全局搜索、自适应遗传算法和候鸟优化的遗传候鸟优化算法 以求解该模型。在算法中采用与处理时间相关的全局搜索和随机程序以获得初始种群，提出自适应交叉和变 异操作改进遗传算法解，在迭代进程中，引入基于工件、机器和工序位 3 种邻域搜索结构的候鸟优化算法更新 最佳解。仿真实验中将遗传候鸟优化算法的实验结果与几种启发式算法进行对比，证明了模型和算法的有效性。 关键词：忽略工序；不相关并行机；混合流水车间；全局搜索；自适应遗传算法；领域搜索；最大完工时间；遗传 候鸟优化算法 中图分类号：TP39;TB49 文献标志码：A 文章编号：1673−4785(2022)03−0459−12 中文引用格式：轩华, 樊银格, 李冰. 含忽略工序和不相关机的混合流水车间调度 [J]. 智能系统学报, 2022, 17(3): 459–470. 英文引用格式：XUAN Hua, FAN Yinge, LI Bing. Hybrid flowshop scheduling with missing operations and unrelated machines[J]. CAAI transactions on intelligent systems, 2022, 17(3): 459–470. Hybrid flowshop scheduling with missing operations and unrelated machines XUAN Hua，FAN Yinge，LI Bing (School of Management Engineering, Zhengzhou University, Zhengzhou 450001, China) Abstract: The hybrid flowshop scheduling problem with missing processes and unrelated parallel machines extracted from steelmaking and other production processes is studied. An integer programming model is formulated to minimize the maximum completion time, and a genetic migrating birds optimization algorithm based on the global search, self-adaptive genetic algorithm, and migrating birds optimization is proposed to solve the model. The initial population is obtained by the global search considering the machine processing time and random procedure. Then, self-adaptive crossover and mutation operators are developed to improve the solutions of the genetic algorithm. In the iterative process, migrating birds optimization combined with three neighborhood search structures based on the job, machine, and operation position is introduced to update the best solutions. Finally, the experimental results of the genetic migrating birds optimization algorithm are compared with several heuristic algorithms to prove the effectiveness of the proposed model and algorithm. Keywords: missing operations; unrelated parallel machines; hybrid flowshop; global search; self-adaptive genetic algorithm; neighborhood search; maximum completion time; genetic migrating birds optimization algorithm 含忽略工序的混合流水车间调度（ hybrid flowshop scheduling with missing operation，HFSMO）在炼钢、不锈钢、塑料等制造工业较为常 见。在经典混合流水车间调度问题中，通常假定 工件经所有工序处理，但在实际生产中，工件会 忽略某些工序，即一些工件可能不经某些工序处 理，如炼钢-连铸生产中，由电弧炉或转炉生产的 钢水要在高温下经精炼和连铸工序进行加工，不 同的钢种对生产路线的要求会有所不同，像 Q235 收稿日期：2021−03−03. 网络出版日期：2021−12−13. 基金项目：国家自然科学基金项目（U1804151）；河南省科技攻 关计划项目（202102310310）. 通信作者：轩华. E-mail：hxuan@zzu.edu.cn. 第 17 卷第 3 期 智 能 系 统 学 报 Vol.17 No.3 2022 年 5 月 CAAI Transactions on Intelligent Systems May 2022
第17卷 智能系统学报 ·460· 普通碳钢要略过RH(Ruhrstahl-.Hausen)真空精炼 研究尚缺乏，还有待进一步探讨。就优化算法而 炉阶段。考虑到并行机的新旧程度或异构性， 言，文献[1,3-10]的研究说明了进化算法求解 由此衍生出本文所研究的带不相关并行机的HF HFSMO问题有较大潜力，如文献[4,9]利用单独 SMO。由于HFS(hybrid flowshop scheduling)问题 的遗传算法和模拟退火算法求解含同构机的最大 是NP-hard2I,带不相关并行机的HFSMO是 完工时间问题。混合算法通常能扩大搜索的范 HF$问题的扩展且其更为复杂，它不仅要确定工 围，提高解的质量，因此关于混合算法求解这类 件的处理序列，还需确定工件在每道未忽略工序 问题的研究还有待进一步探讨。候鸟优化(i- 的机器分配，所以本文研究的更复杂的带不相关 grating birds optimization,MBO)算法作为一种新 并行机的HFSMO也是NP-hard。 兴的群智能优化算法，已广泛应用于生产调度领 目前，已有不少学者研究HFSMO。就两道工 域，如流水车间调度2训、混合流水车间调度2-2 序的HFSMO而言，Tseng等研究了工序1有一 和柔性作业车间调度42，它最早是由Duman等阿 台机器且工序2有两台同构机的情况，假定工序 提出并应用于二次分配问题。因此，本文结合全 1可忽略，提出了一种启发式算法以最小化最大完 局搜索、自适应遗传算法和候鸟优化提出一种遗 工时间。就含同构并行机的多工序HFSMO而言， 传候鸟优化算法(genetic migrating birds optimiza- 为最小化最大完工时间，Saravanan等4-提出了 tion algorithm,GMBOA)解决含不相关并行机的 遗传算法、模拟退火算法和粒子群算法，Marichelvam HFSMO,通过仿真实验验证所提算法的有效性和 等基于遗传算法和分散搜索算法提出了一种改 可行性。 进的混合遗传分散搜索算法，Dios等-1提出了一 些分派规则和改进启发式来求解该问题：为最小 1问题描述与建模 化平均拖期，Saravanan等9提出了遗传算法与模 1.1 问题描述 拟退火算法；为最小化平均滞留时间、总提前、总 含不相关并行机的HFSMO问题包括来自集 拖期和关键机器跳过率的加权和，Li等0针对铁 合J={1,2,…,n且将在h道工序上处理的n个工件， 水系统提出了一种改进离散人工蜂群算法；为了 每道工序s有m,台不相关并行机，即对于每道工 最小化最大完工时间、总等待时间以及处理时间 序，工件在m,台并行机上的处理时间相互独立，仅 与标准处理时间的偏差之和，Long等0针对炼钢- 取决于工件与机器的匹配程度。每个工件可能会 连铸生产系统提出了一种改进遗传算法。 忽略某些工序。每台机器一次只能处理一个工件， 目前，已有不少学者在不相关并行机环境下 而每个工件一次至多在一台机器进行处理。调度 研究HFS问题。针对单目标问题，Meng等研 目标是确定工件处理序列和机器分配，以最小化 究了节能HFS,并提出改进的遗传算法以最小化 最大完工时间。所研究问题的其他假设如下： 机器闲置消耗。为最小化最大完工时间，Q加等回 1)工件的开工应在其释放时间之后： 研究了批量调度HFS,提出两阶段蚁群算法；罗 2)机器准备时间与工件顺序无关，且包含在 函明等1针对多工序HFS,提出离散布谷鸟算法； 处理时间中； 轩华等针对带有限缓冲HFS,提出基于遗传算 3)所有机器在整个计划时间段内连续可用： 法和禁忌搜索的混合启发式算法。针对多日标问 4)工件一旦在某台机器上开始处理后，不允 题，Zhou等9研究了带模糊处理时间的HFS,设 许中断，直至该工序完成： 计差分进化算法以最小化总加权交付损失和总能 5)工件处理无优先级要求； 耗。Yu等6针对带机器能力约束和依赖加工序 6)工序之间的转移时间忽略不计： 列设置时间的HFS,提出带多重解码框架的进化 7)相邻工序之间的缓冲区容量无限。 算法以最小化总拖期和总设置时间。Zhou等可 1.2 模型构建 研究了带节能区间的HFS,提出新的帝国竞争算 由前述可知，每个工件实际访问的总工序数 法以解决以总能耗和最大完工时间为目标的双目 O,≤h,虽然工件需经h道工序完成其处理任务，但 标问题。 部分工件j的处理略过了h-O道工序，即这些工 就目前查阅的文献而言，HFSMO已引起众多 件未经h-O道工序处理而直接进入后续工序。 学者的关注，既有的研究聚焦于同构机环境。现 含不相关并行机的HFSMO模型如下： 有的带不相关并行机的HFS不考虑带忽略工序 所研究问题的目标是满足所有约束条件下最 特性，关于不相关并行机环境下HFSMO问题的 小化最大完工时间Cx,即
普通碳钢要略过 RH（Ruhrstahl-Hausen）真空精炼 炉阶段[1]。考虑到并行机的新旧程度或异构性， 由此衍生出本文所研究的带不相关并行机的 HFSMO。由于 HFS (hybrid flowshop scheduling) 问题 是 NP-hard[ 2 ] ，带不相关并行机的 HFSMO 是 HFS 问题的扩展且其更为复杂，它不仅要确定工 件的处理序列，还需确定工件在每道未忽略工序 的机器分配，所以本文研究的更复杂的带不相关 并行机的 HFSMO 也是 NP-hard。 目前，已有不少学者研究 HFSMO。就两道工 序的 HFSMO 而言，Tseng 等 [3] 研究了工序 1 有一 台机器且工序 2 有两台同构机的情况，假定工序 1 可忽略，提出了一种启发式算法以最小化最大完 工时间。就含同构并行机的多工序 HFSMO 而言， 为最小化最大完工时间，Saravanan 等 [4-5] 提出了 遗传算法、模拟退火算法和粒子群算法，Marichelvam 等 [6] 基于遗传算法和分散搜索算法提出了一种改 进的混合遗传分散搜索算法，Dios 等 [7-8] 提出了一 些分派规则和改进启发式来求解该问题；为最小 化平均拖期，Saravanan 等 [9] 提出了遗传算法与模 拟退火算法；为最小化平均滞留时间、总提前、总 拖期和关键机器跳过率的加权和，Li 等 [10] 针对铁 水系统提出了一种改进离散人工蜂群算法；为了 最小化最大完工时间、总等待时间以及处理时间 与标准处理时间的偏差之和，Long 等 [1] 针对炼钢- 连铸生产系统提出了一种改进遗传算法。 目前，已有不少学者在不相关并行机环境下 研究 HFS 问题。针对单目标问题，Meng 等 [11] 研 究了节能 HFS，并提出改进的遗传算法以最小化 机器闲置消耗。为最小化最大完工时间，Qin 等 [12] 研究了批量调度 HFS，提出两阶段蚁群算法；罗 函明等[13] 针对多工序 HFS，提出离散布谷鸟算法； 轩华等[14] 针对带有限缓冲 HFS，提出基于遗传算 法和禁忌搜索的混合启发式算法。针对多目标问 题，Zhou 等 [15] 研究了带模糊处理时间的 HFS，设 计差分进化算法以最小化总加权交付损失和总能 耗。Yu 等 [16] 针对带机器能力约束和依赖加工序 列设置时间的 HFS，提出带多重解码框架的进化 算法以最小化总拖期和总设置时间。Zhou 等 [17] 研究了带节能区间的 HFS，提出新的帝国竞争算 法以解决以总能耗和最大完工时间为目标的双目 标问题。 就目前查阅的文献而言，HFSMO 已引起众多 学者的关注，既有的研究聚焦于同构机环境。现 有的带不相关并行机的 HFS 不考虑带忽略工序 特性，关于不相关并行机环境下 HFSMO 问题的 研究尚缺乏，还有待进一步探讨。就优化算法而 言，文献 [1, 3-10] 的研究说明了进化算法求解 HFSMO 问题有较大潜力，如文献 [4, 9] 利用单独 的遗传算法和模拟退火算法求解含同构机的最大 完工时间问题。混合算法通常能扩大搜索的范 围，提高解的质量，因此关于混合算法求解这类 问题的研究还有待进一步探讨。候鸟优化（migrating birds optimization，MBO）算法作为一种新 兴的群智能优化算法，已广泛应用于生产调度领 域，如流水车间调度[18-21] 、混合流水车间调度[22-23] 和柔性作业车间调度[24-26] ，它最早是由 Duman 等 [27] 提出并应用于二次分配问题。因此，本文结合全 局搜索、自适应遗传算法和候鸟优化提出一种遗 传候鸟优化算法（genetic migrating birds optimization algorithm, GMBOA）解决含不相关并行机的 HFSMO，通过仿真实验验证所提算法的有效性和 可行性。 1 问题描述与建模 1.1 问题描述 J = {1,2,··· ,n} h n s ms ms 含不相关并行机的 HFSMO 问题包括来自集 合 且将在 道工序上处理的 个工件， 每道工序 有 台不相关并行机，即对于每道工 序，工件在 台并行机上的处理时间相互独立，仅 取决于工件与机器的匹配程度。每个工件可能会 忽略某些工序。每台机器一次只能处理一个工件， 而每个工件一次至多在一台机器进行处理。调度 目标是确定工件处理序列和机器分配，以最小化 最大完工时间。所研究问题的其他假设如下： 1）工件的开工应在其释放时间之后； 2）机器准备时间与工件顺序无关，且包含在 处理时间中； 3）所有机器在整个计划时间段内连续可用； 4）工件一旦在某台机器上开始处理后，不允 许中断，直至该工序完成； 5）工件处理无优先级要求； 6）工序之间的转移时间忽略不计； 7）相邻工序之间的缓冲区容量无限。 1.2 模型构建 j Oj ⩽ h h h−Oj h−Oj 由前述可知，每个工件 实际访问的总工序数 ，虽然工件需经 道工序完成其处理任务，但 部分工件 j 的处理略过了 道工序，即这些工 件未经 道工序处理而直接进入后续工序。 含不相关并行机的 HFSMO 模型如下： Cmax 所研究问题的目标是满足所有约束条件下最 小化最大完工时间 ，即 第 17 卷 智 能 系 统 学 报 ·460·
·461· 轩华，等：含忽略工序和不相关机的混合流水车间调度 第3期 minz=Cmax (1) 种群以提高初始解的质量，设计自适应更新策略 s.t.Cmx≥Ch,j (2) 以计算交叉概率及变异概率山，以此执行交叉和 式中：Ch表示工件j(j=1,2,…,n)在工序h的完工 变异操作。最后，引入结合邻域搜索的候鸟优化 时间。式(2)通过检查工件在最终工序h的完工时 算法以扩大遗传算法解的邻域搜索范围，从而获 间，确定最大完工时间。 得较好的近优解。 Cis=(1-Wis)Cis-1+Wis (3) 2.1 编码、解码和适应度选择 k=1 含不相关并行机的HFSMO需确定工件在每 式中：m,为工序s(s=1,2,,h)可利用的机器数； 道工序的机器分配，因此设计基于机器号的整数 F为一个足够大的数；P为工件在工序s的机器 编码方案以表述机器分配序列σ。考虑到HFS的 k(k=1,2,,m)上的处理时间；W为二元参数， 多工序处理需求，令每个工件所忽略的工序数不 若工件在工序s上处理，其值为1，否则为0：B:表 超过h-2,根据忽略工序比例p,随机产生每个工 示工件j在工序s的开工时间；X为二元变量，若 件的未忽略工序信息序列r,如图1(n=5,h=5和 工件j在工序s的机器k上处理，其值为1，否则为 p=0.6),其中U:表示工件j在阶段s的工序；然后 0。式(3)定义了工件在每道工序的完工时间，若 基于τ生成相应工件的机器号M,为平衡并行机 工件未在工序s处理，则它在该工序的完工时间 器的负荷，令其值满足[1，m,]的均匀分布，从而形 为它在紧前未忽略工序的完工时间。 成长度为nh(1-p)的一个染色体，其中每个元素 ∑X=1,以s (即工序位上的数值)为对应工件所在工序分配 的机器号。 该约束确保每个工件在任一工序只能分派到 UU UU UUU:UUU 台机器进行处理。 Cja≤B+1,s∈l,2,…,h-1,j 图1未忽略工序信息序列 该约束说明了每个工件只完完成前一工序的 Fig.1 Information sequence of unmissing operations 处理任务后方可开始下一道工序的处理。 初始化种群时，由于每道工序所含的机器为 B1≥RYj 不相关并行机，考虑不同的机器处理同一工件的 式中R为工件的释放时间。该约束描述了工件 时间不同，而最大完工时间与工件的处理时间相关。 只有到达生产系统才可开始处理。 因此，基于张国辉等2的研究提出考虑处理时间 B≥(Cs-Z批s2).WxW,j,i,k,s,j≠i(4) 的全局搜索以产生一个个体，而其他个体则由随 B≥(Cs-(1-Zt)2)WW,Vjii,k,s,j≠i(5) 机程序生成。令数组0={P11,P21,…,PmP12,…, 式中：Z为二元变量，若工件和j在工序s的机器 Pm,P1h,P2h,…,Pmh}为记录从工序1到工序h的 k上处理且工件j早于工件i,其值为1，否则为0。 每台机器的累计处理时间的一维数组，其初始值 这两个约束表示：同一道工序分派在同一台机器 均设为0，全局搜索从任一工件开始，对它的第 处理的两个工件之间的优先级关系，若Zk=0且 一道未忽略工序“，将可利用并行机的工件处理时 W=W=1,约束式(4)描述了工件j在工序s的机 间分别与数组内该机器位置的数值相加，即对 器k上的开工时间必须在工件的完工时间之后， k=1,2,,m,计算{P+pk,从中选择累计处理 若Z=1且W:=W=1,约束式（⑤）描述了工件i在 时间最短的机器K作为工件j在工序所分配的机 工序s的机器k上的开工时间必须在工件的完工 器，将该机器号填入个体内工序位(h(1-P)-1)+1), 时间之后。 令Pa=min(P+ps,更新数组0；然后，对工件j Ba≥0，Ca≥0Hi,s (6) 的第2,3，…，h(1-p)道工序重复上述过程，从而完 Xk∈{0,1，Zk∈{0,1，方s (7) 成该工件所有工序的机器分配。接着，再从剩余 约束式(6)、(7)定义了变量取值范围。 工件集内随机选择一个工件执行上述过程，直至 2遗传候鸟优化算法 完成所有工件未忽略工序的机器分配。结合随机 程序产生的(e-1)个个体共同构成了如图2所示 遗传算法广泛用于求解HFSMO问题，为 的种群规模为e的初始种群。 使遗传算法有效求解含不相关并行机的HF- 为计算最大完工时间，需为分配至同一台机 SMO问题，设计基于机器号的编码方案，采用考 器的工件进行排序，为此，设计了基于最短处理 虑机器处理时间的全局搜索和随机程序生成初始 时间的解码方案，即对于机器分配序列σ，当
minz = Cmax (1) s.t. Cmax ⩾ Cjh,∀ j (2) Cjh j j = 1,2,··· ,n h h 式中： 表示工件 （ ）在工序 的完工 时间。式 (2) 通过检查工件在最终工序 的完工时 间，确定最大完工时间。 Cjs = (1−Wjs)·Cj,s−1 +Wjs · Bjs + ∑ms k=1 Xjks·Pjks ,∀ j,s (3) ms s s = 1,2,· · ·,h F Pjks j s k k = 1,2,· · ·,ms Wjs j s Bjs j s Xjks j s k j s 式中： 为工序 （ ）可利用的机器数； 为一个足够大的数； 为工件 在工序 的机器 （ ）上的处理时间； 为二元参数， 若工件 在工序 上处理，其值为 1，否则为 0； 表 示工件 在工序 的开工时间； 为二元变量，若 工件 在工序 的机器 上处理，其值为 1，否则为 0。式 (3) 定义了工件在每道工序的完工时间，若 工件 未在工序 处理，则它在该工序的完工时间 为它在紧前未忽略工序的完工时间。 ∑ms k=1 Xjks = 1,∀ j,s 该约束确保每个工件在任一工序只能分派到 一台机器进行处理。 Cjs ⩽ Bj,s+1,s ∈ {1,2,··· ,h−1},∀ j 该约束说明了每个工件只完完成前一工序的 处理任务后方可开始下一道工序的处理。 Bj1 ⩾ Rj ,∀ j Rj 式中 为工件 j 的释放时间。该约束描述了工件 只有到达生产系统才可开始处理。 Bjs ⩾ (Cis −Zjiks ·Ω)· WjsWis,∀ j,i, k,s, j , i (4) Bis ⩾ (Cjs −(1−Zjiks)·Ω)· WjsWis,∀ j,i, k,s, j , i (5) Zjiks i j s k j i Zjiks = 0 Wjs = Wis = 1 j s k i Zjiks = 1 Wjs = Wis = 1 i s k j 式中： 为二元变量，若工件 和 在工序 的机器 上处理且工件 早于工件 ，其值为 1，否则为 0。 这两个约束表示：同一道工序分派在同一台机器 处理的两个工件之间的优先级关系，若 且 ，约束式 (4) 描述了工件 在工序 的机 器 上的开工时间必须在工件 的完工时间之后， 若 且 ，约束式 (5) 描述了工件 在 工序 的机器 上的开工时间必须在工件 的完工 时间之后。 Bjs ⩾ 0,Cjs ⩾ 0,∀ j,s (6) Xjks ∈ {0,1},Zjiks ∈ {0,1},∀ j,s (7) 约束式 (6)、(7) 定义了变量取值范围。 2 遗传候鸟优化算法 遗传算法已广泛用于求解 HFSMO 问题，为 使遗传算法有效求解含不相关并行机 的 HFSMO 问题，设计基于机器号的编码方案，采用考 虑机器处理时间的全局搜索和随机程序生成初始 ξ ψ 种群以提高初始解的质量，设计自适应更新策略 以计算交叉概率 及变异概率 ，以此执行交叉和 变异操作。最后，引入结合邻域搜索的候鸟优化 算法以扩大遗传算法解的邻域搜索范围，从而获 得较好的近优解。 2.1 编码、解码和适应度选择 σ p τ n = 5,h = 5 p = 0.6 U s j j s τ Ms j [1,ms] n · h ·(1− p) 含不相关并行机的 HFSMO 需确定工件在每 道工序的机器分配，因此设计基于机器号的整数 编码方案以表述机器分配序列 。考虑到 HFS 的 多工序处理需求，令每个工件所忽略的工序数不 超过 h−2，根据忽略工序比例 ，随机产生每个工 件的未忽略工序信息序列 ，如图 1（ 和 ），其中 表示工件 在阶段 的工序；然后 基于 生成相应工件的机器号 ，为平衡并行机 器的负荷，令其值满足 的均匀分布，从而形 成长度为 的一个染色体，其中每个元素 （即工序位上的数值）为对应工件所在工序分配 的机器号。 U1 3 U1 4 U2 2 U2 3 U3 4 U3 5 U4 4 U4 5 U5 2 U5 5 图 1 未忽略工序信息序列 Fig. 1 Information sequence of unmissing operations θ = {ps11, ps21,··· , psm11 , ps12,··· , psm21 , ps1h, ps2h,··· , psmh h} h j u θ k = 1,2,· · ·,mu {Pjku + psku} k ′ j u (h(1− p)(j−1)+1) psuk′ = min{Pjku + psku} θ 2,3,··· ,h(1− p) (e−1) e 初始化种群时，由于每道工序所含的机器为 不相关并行机，考虑不同的机器处理同一工件的 时间不同，而最大完工时间与工件的处理时间相关。 因此，基于张国辉等[28] 的研究提出考虑处理时间 的全局搜索以产生一个个体，而其他个体则由随 机程序生成。令数组 为记录从工序 1 到工序 的 每台机器的累计处理时间的一维数组，其初始值 均设为 0，全局搜索从任一工件 开始，对它的第 一道未忽略工序 ，将可利用并行机的工件处理时 间分别与数组 内该机器位置的数值相加，即对 ，计算 ，从中选择累计处理 时间最短的机器 作为工件 在工序 所分配的机 器，将该机器号填入个体内工序位 ， 令 ，更新数组 ；然后，对工件 j 的第 道工序重复上述过程，从而完 成该工件所有工序的机器分配。接着，再从剩余 工件集内随机选择一个工件执行上述过程，直至 完成所有工件未忽略工序的机器分配。结合随机 程序产生的 个个体共同构成了如图 2 所示 的种群规模为 的初始种群。 σ 为计算最大完工时间，需为分配至同一台机 器的工件进行排序，为此，设计了基于最短处理 时间的解码方案，即对于机器分配序列 ， 当 ·461· 轩华，等：含忽略工序和不相关机的混合流水车间调度 第 3 期
第17卷 智能系统学报 ·462· s=1时，将分派到在同一台机器处理的工件按照 E.MP MMM MH M MH M ME MS 最短处理时间规则进行排序，当s>1时，对同一台 ! 机器上处理的工件采用先到先加工规则生成处理 E:M MMM MMM MM MS 序列，然后基于最早空闲机器原则依次将各工件 ↓ 安排在所分配机器。对于工件的忽略工序，则按 D.M MME MMMMM MP M 照约束式(3)确定其在忽略工序的完工时间。 MMMMMM MH MM MS D:MM ME N MM MHM M MS 图4均匀两点交叉（g1) MMM MP MMMM MM Fig.4 Uniform two-point crossover (g=1 MMM MR MM MP MM MS 采用自适应更新策略确定交叉概率专，用以确 定是否执行上述交叉操作，计算如下： MMMMMM MM MM 5-传s-5B+F-n F(g) F(g)≥Fawe 图2初始种群 Fig.2 Initial population F(g)<Favg 式中：A为当前迭代数；B为最大迭代数；Fw为当 本文的目标是最小化最大完工时间，故将适 前种群的平均适应度值。 应度函数表示为目标函数的倒数，即个体g的适应 2.3变异操作 度函数为F(g)=1/Cmax(g)。采用轮盘赌选择法，个 体适应度值越大，被选择的概率也越大。 变异操作是根据变异概率通过改变父代个体 2.2交叉操作 的机器号以产生子代个体的过程。本文提出了基 于随机机器选择的单点变异和基于机器最短处理 采用单点交叉和均匀两，点交叉两种方式执行 时间的多点变异两种方式。 交叉操作。在0和1中随机生成一个整数v,当 1)基于随机机器选择的单点变异 v=0时，执行单点交叉，即随机选择两个父代个体 从父代个体E,中随机选择一个工序位x(1≤ E,和E2,随机生成一个工序位x(1≤x≤nh(1-p), 交换E,和E,中所选工序位x的机器号，保持其他工 x≤nh(1-p),将该工序位的机器号重新在1，m,] 之间随机生成，如图5。 序位的机器号不变，从而生成子代个体D和D2,如 图3。当v=1时，执行均匀两点交叉，首先，随机 E:M MME MMM MMI M ME 选择两个父代个体E和E2,随机生成两个工序位 x和y(1≤x<y≤nh(1-p),将E和E2分为3段，然 D MMM MEMMS M MY M MS 后，从{0,1,2}中随机产生一个数q,当q=0时，将 图5基于随机机器选择的单点变异 E,和E2中处于工序位x之前的区段交换，作为子代 Fig.5 Single point mutation based on random machine se- 个体D和D2的第一段；q=1时，交换E,和E2中工序 lection 位x和y之间的区段，作为D,和D2的中间段； 2)基于机器最短处理时间的多点变异 q=2时，对E,和E2中处于工序位y之后的区段进行 推广Chang等2的研究，提出基于机器最短 交换，作为D和D2的第三段；保留子代个体中其他 处理时间的多点变异操作。从父代个体E依次取 段与父代个体相同，以产生子代个体D,和D2,如 出工序位x的机器号，比较从区间[O,1]生成的随 图4。 机数w与变异概率山，若w<山，则从工序位x可利用 的并行机中选择处理时间最短的机器替换原有机 E MMM MP MM MMP ME M 器号，否则，保持原有机器号不变，对个体内所有 E:MMMMM"MM MY MMS 工序位完成上述操作后，生成新个体D,如图6。 ↓ E MM M MP MM MMP MMS D.M MME MMMM MS MEMS DM MMM MM M MS M MS D:M MM MP MMM MS MM 图6基于机器最短处理时间的多点变异 图3单点交叉 Fig.6 Multi-point mutation based on the shortest pro- Fig.3 Single-point crossover cessing time of the machine
s = 1 s > 1 时，将分派到在同一台机器处理的工件按照 最短处理时间规则进行排序，当 时，对同一台 机器上处理的工件采用先到先加工规则生成处理 序列，然后基于最早空闲机器原则依次将各工件 安排在所分配机器。对于工件的忽略工序，则按 照约束式 (3) 确定其在忽略工序的完工时间。 M1 13 M1 14 M2 12 M2 13 M3 14 M3 15 M4 14 M4 15 M5 12 M5 15 M1 23 M1 24 M2 22 M2 23 M3 24 M3 25 M4 24 M4 25 M5 22 M5 25 M1 33 M1 34 M2 32 M2 33 M3 34 M3 35 M4 34 M4 35 M5 32 M5 35 M1 e3 M1 e4 M2 e2 M2 e3 M3 e4 M3 e5 M4 e4 M4 e5 M5 e2 M5 e5 ... 图 2 初始种群 Fig. 2 Initial population g F(g) = 1/Cmax(g) 本文的目标是最小化最大完工时间，故将适 应度函数表示为目标函数的倒数，即个体 的适应 度函数为 。采用轮盘赌选择法，个 体适应度值越大，被选择的概率也越大。 2.2 交叉操作 v v = 0 E1 E2 x(1 ⩽ x ⩽ n · h ·(1− p)) E1 E2 x D1 D2 v = 1 E1 E2 x y(1 ⩽ x < y ⩽ n · h ·(1− p)) E1 E2 q q = 0 E1 E2 x D1 D2 q = 1 E1 E2 x y D1 D2 q = 2 E1 E2 y D1 D2 D1 D2 采用单点交叉和均匀两点交叉两种方式执行 交叉操作。在 0 和 1 中随机生成一个整数 ，当 时，执行单点交叉，即随机选择两个父代个体 和 ，随机生成一个工序位 ， 交换 和 中所选工序位 的机器号，保持其他工 序位的机器号不变，从而生成子代个体 和 ，如 图 3。当 时，执行均匀两点交叉，首先，随机 选择两个父代个体 和 ，随机生成两个工序位 和 ，将 和 分为 3 段，然 后，从{0, 1, 2}中随机产生一个数 ，当 时，将 和 中处于工序位 之前的区段交换，作为子代 个体 和 的第一段； 时，交换 和 中工序 位 和 之间的区段，作为 和 的中间段； 时，对 和 中处于工序位 之后的区段进行 交换，作为 和 的第三段；保留子代个体中其他 段与父代个体相同，以产生子代个体 和 ，如 图 4。 M1 13 M1 14 M2 12 M2 13 M3 14 M3 15 M4 14 M4 15 M5 12 M5 E 15 1 M1 33 M1 34 M2 32 M2 13 M3 34 M3 35 M4 34 M4 35 M5 32 M5 D 35 2 M1 33 M1 34 M2 32 M2 33 M3 34 M3 35 M4 34 M4 35 M5 32 M5 E 35 2 M1 13 M1 14 M2 12 M2 33 M3 14 M3 15 M4 14 M4 15 M5 12 M5 D 15 1 图 3 单点交叉 Fig. 3 Single-point crossover M1 33 M1 34 M2 32 M2 13 M3 14 M3 15 M4 14 M4 35 M5 32 M5 D 35 2 M1 33 M1 34 M2 32 M2 33 M3 34 M3 35 M4 34 M4 35 M5 32 M5 E 35 2 M1 13 M1 14 M2 12 M2 13 M3 14 M3 15 M4 14 M4 15 M5 12 M5 E 15 1 M1 13 M1 14 M2 12 M2 33 M3 34 M3 35 M4 34 M4 15 M5 12 M5 D 15 1 图 4 均匀两点交叉（q=1） Fig. 4 Uniform two-point crossover（q=1） 采用自适应更新策略确定交叉概率 ξ ，用以确 定是否执行上述交叉操作，计算如下[29] ： ξ = ξmax −(ξmax −ξmin) ( λ β + F(g) Fmax − Favg ) , F(g) ⩾ Favg ξmin, F(g) < Favg 式中： λ 为当前迭代数； β 为最大迭代数； Favg为当 前种群的平均适应度值。 2.3 变异操作 变异操作是根据变异概率通过改变父代个体 的机器号以产生子代个体的过程。本文提出了基 于随机机器选择的单点变异和基于机器最短处理 时间的多点变异两种方式。 1）基于随机机器选择的单点变异 E1 x(1 ⩽ x ⩽ n · h ·(1− p)) [1,ms] 从父代个体 中随机选择一个工序位 ，将该工序位的机器号重新在 之间随机生成，如图 5。 E1 D1 M1 13 M1 14 M2 12 M2 13 M3 14 M3 15 M4 14 M4 15 M5 12 M5 15 M1 13 M1 14 M2 ′12 M2 13 M3 14 M3 15 M4 14 M4 15 M5 12 M5 15 图 5 基于随机机器选择的单点变异 Fig. 5 Single point mutation based on random machine selection 2）基于机器最短处理时间的多点变异 E1 x w ψ w < ψ x D1 推广 Chang 等 [29] 的研究，提出基于机器最短 处理时间的多点变异操作。从父代个体 依次取 出工序位 的机器号，比较从区间 [0, 1] 生成的随 机数 与变异概率 ，若 ，则从工序位 可利用 的并行机中选择处理时间最短的机器替换原有机 器号，否则，保持原有机器号不变，对个体内所有 工序位完成上述操作后，生成新个体 ，如图 6。 E1 D1 M1 13 M1 14 M2 12 M2 13 M3 14 M3 15 ... M4 14 M4 15 M5 12 M5 15 M1 ′13 M1 14 M2 12 M2 13 M3 14 M3 15 M4 14 M4 15 M5 12 M5 ′15 图 6 基于机器最短处理时间的多点变异 Fig. 6 Multi-point mutation based on the shortest processing time of the machine 第 17 卷 智 能 系 统 学 报 ·462·
·463· 轩华，等：含忽略工序和不相关机的混合流水车间调度 第3期 自适应变异概率4由式(8)确定： r=2,则执行N2;若r=3,令max=1,执行N3;若 F(g) r=4,令Lmx=4,执行N1;若r=5,令mx=2,执行 F max -Favg F(g)≥Favg N3;若r=6,令Lax=6,执行N1。该过程往复o次产 中an,F(g)y,算法停止，输出最佳解； 应个体的适应度值，从中选取适应度值最大的机 否则，返回3)。 器号填入该工序位，重复该过程直至达到最大循 2.5遗传候鸟优化算法流程 环次数x。 首先，考虑本文研究的问题是含不相关机的 引入上述邻域搜索结构执行候鸟优化算法， HFSMO,其不仅与工件的处理序列有关，还与工 具体步骤如下： 件在每道工序的机器分配相关，因此本文设计基 1)参数初始化。设置Lmax、m以及候鸟优化 于机器号的编码方案，在解码时采用最短处理时 最大迭代数y,巡回数Gx,令而=1，G1=1,=1, 间和先进先出规则确定工件处理序列：采用考虑 候鸟种群规模为6。 机器处理时间的全局搜索产生一个个体，用随机 2)初始种群生成。设计初始种群由3部分构 程序生成剩余(e-1)个个体以生成种群规模为e的 成：①对每个工件的未忽略工序，从可利用的并 初始种群：计算适应度，根据轮盘赌法选择个体 行机中选择工件处理时间最短的机器作为该工件 生成新种群；对新种群根据自适应更新策略计算 分配的机器，从而产生一个个体；②应用前述全 交叉概率及变异概率山，以此执行交叉和变异操 局搜索方法产生50%(6-1)个个体；③从GA解中 作，得到遗传进化后的最佳解并记录历史最佳 选取最好的50%(6-1)个个体。从6个个体中选取 解。最后，当最佳解T次没变时，按照基于3种邻 最大完工时间最小的个体作为领飞鸟，其余均为 域搜索结构的候鸟优化产生新解，若新解优于历 跟飞鸟，若跟飞鸟与领飞鸟相同，则将领飞鸟通 史最佳解，则更新历史最佳解，否则保持原解不 过基于机器最短处理时间的多点变异或邻域搜索 变，重复上述过程直至满足算法的停止标准。 结构N(Lx=2)产生新跟飞鸟：若新跟飞鸟与其 综上所述，所研究的GMBOA执行如下： 余跟飞鸟相同，则对新跟飞鸟继续应用邻域搜索 1)设置种群规模e,最大迭代数B和累计数T, 结构N进行更新，直至产生与其余跟飞鸟不同的 令Z=F,A=1,t=1: 新跟飞鸟。 2)若λ>B或CPU达到最大运行时间，程序停 3)领飞鸟进化。随机产生[1,6]之间的一个 止，输出最佳解；否则，执行3)： 整数r,若r=1,令Lax=2,对领飞鸟执行N1;若 3)结合随机程序和全局搜索产生初始种群：
自适应变异概率 ψ 由式 (8) 确定： ψ = ψmax −(ψmax −ψmin) ( λ β + F(g) Fmax − Favg ) ,F(g) ⩾ Favg ψmin,F(g) γ ¯ ，算法停止，输出最佳解； 否则，返回 3）。 2.5 遗传候鸟优化算法流程 (e−1) e ξ ψ T 首先，考虑本文研究的问题是含不相关机的 HFSMO，其不仅与工件的处理序列有关，还与工 件在每道工序的机器分配相关，因此本文设计基 于机器号的编码方案，在解码时采用最短处理时 间和先进先出规则确定工件处理序列；采用考虑 机器处理时间的全局搜索产生一个个体，用随机 程序生成剩余 个个体以生成种群规模为 的 初始种群；计算适应度，根据轮盘赌法选择个体 生成新种群；对新种群根据自适应更新策略计算 交叉概率 及变异概率 ，以此执行交叉和变异操 作，得到遗传进化后的最佳解并记录历史最佳 解。最后，当最佳解 次没变时，按照基于 3 种邻 域搜索结构的候鸟优化产生新解，若新解优于历 史最佳解，则更新历史最佳解，否则保持原解不 变，重复上述过程直至满足算法的停止标准。 综上所述，所研究的 GMBOA 执行如下： e β T Z ∗ = F λ = 1 t = 1 1）设置种群规模 ，最大迭代数 和累计数 ， 令 ， ， ； 2）若 λ > β 或 CPU 达到最大运行时间，程序停 止，输出最佳解；否则，执行 3）； 3）结合随机程序和全局搜索产生初始种群； ·463· 轩华，等：含忽略工序和不相关机的混合流水车间调度 第 3 期
第17卷 智能系统学报 ·464· 4)计算每个个体的适应度值，使用轮盘赌选 真实验得到最佳的一组设置，即5mas=0.9、专mim=0.5 择法获取适应度值高的个体； 少max=0.2和ψmin=0.02;参考文献[22]，并经过仿真 5)根据交叉概率，从单点交叉和均匀两点交 实验测试GMBOA中的6=31、y=10、Gmx=10 叉2种方式随机选择1种生成新个体： o=3;基于GA的4种算法和IDABC的种群规模 6)根据变异概率山，随机执行基于随机机器 e=100:由于MBO&NS的种群规模必须为奇数， 选择的单点变异或基于机器最短处理时间的多点 所以其种群规模e=101;DABC的参数与文献[30] 变异； 的设置相同，最大迭代数B=100,最大CPU时间 7)若当前迭代得到的最佳解Z≠Z,Z= 为720s:考虑到GA的运行时间较短，将MBO&NS、 min(Z,Z,t=1,A=A+1,转至2)；否则，t=t+1, GMBOAL、AGA&LS、IDABC和GMBOA的停止 执行8)： 时间设为TGA运行100次所需时间。 8)若t=T,执行9)，否则，A=A+1,转至2)： 问题产生如下：n={20,30,40,50,80,100,120,150}, 9)调用候鸟优化算法，若得到的最佳解优于 h={5,10,15,201,m,=5。借鉴Dios等7-1关于忽略 Z,更新Z,否则，保留Z不变；t=1,A=1+1,转至2)。 工序比例的设定，将本文的忽略工序比例分别 取为20%、40%和60%。每个工件在同一道工序 3仿真实验 不同机器上的处理时间P.不同且满足[1,99]之 间的均匀分布。 本文所提的遗传候鸟优化算法将全局搜索、 自适应遗传算法和候鸟优化相结合，为了验证所 3.2数据实验与结果分析 提出的算法性能，从传统算法、与其他算法结合 参数{n,h,p的不同组合产生96组问题规模， 的混合算法、解码规则、已发表的文献的算法 每种规模随机运行10个实例，取10次测试结果 4个角度选择传统遗传算法(traditional genetic al- 的平均值作为对应规模问题的测试结果。 gorithm,TGA),结合3种领域搜索结构候鸟优化 定义相对偏差为 (migrating birds optimization neighborhood R=CIGA-COMOAX100% CGMBOA search,MBO&NS)、基于最长处理时间规则解码 的遗传候鸟优化算法(genetic migrating birds op- R2= CMBO&NS-CGMBOA 100% CGMBOA timization algorithm L,GMBOAL)、结合局域搜索 R3= CGMBOA-CGMB0A×100% 的自适应遗传算法(adaptive genetic algorithm& CGMBOA local search,AGA&LS)与文献[30]的改进人工蜂 R4= CAGALS-COMBOA100% 群算法(improved artificial bee colony,.IDABC)进行 CGMBOA 对比。采用Matlab R20l4b进行编程，在CPU为 R=CIDARC-COMOA 100% CGMBOA Inter Core i5-5200U,内存为4GB,主频2.2GHz的 由于本文所提的算法迭代100次的CPU时 微机上运行。 间略长，为在较短的运行时间内测试所提算法的 3.1参数设置 有效性，兼顾算法对比的公平性，将TGA迭代100 为公平比较TGA、MBO&NS、GMBOAL、 次所需的时间作为对比算法MBO&NS、GMBOAL、 AGA&LS、IDABC和GMBOA这6种算法，TGA AGA&LS、IDABC和所提出算法GMBOA的停止 中的和山的取值通过仿真实验得到最佳的一组 条件，以此对比算法的性能，所以表1~6列出的 设置，即E=0.8和w=0.2;GMBOAL、AGA&LS和 CPU时间为TGA迭代100次的时间。表1~6列 GMBOA中的Eas、专mn、中max和bmn的取值是通过仿 出了5种算法求解不同规模问题的实验结果。 表1忽略工序比例为20%时中小规模问题的测试结果 Table 1 Testing results for small and medium scale problems with the proportion 20%of missing operations nxh TGA MBO&NS GMBOAL AGA&LS IDABC GMBOA R%R/%R/%R,/%R/%CPU时间s 20×5 209.9 208.2 184.1 176.5 188.9 172.3 21.82 20.84 6.852.44 9.63 22.01 30×5 280.1 260.3 224.2 218.1 228.4 203.7 37.51 27.79 10.067.07 12.13 25.19 40×5318.6 284.9 261.5 242.4 261.7 232.0 37.3322.8012.724.4812.80 28.84 50×5335.7 335.0 285.0 271.8 296.0 263.2 27.5527.28 8.283.2712.46 31.44 20×10337.3 355.8 299.0 285.8 300.9 277.1 21.7328.40 6.853.14 8.59 44.14
4）计算每个个体的适应度值，使用轮盘赌选 择法获取适应度值高的个体； 5）根据交叉概率 ξ ，从单点交叉和均匀两点交 叉 2 种方式随机选择 1 种生成新个体； 6）根据变异概率 ψ ，随机执行基于随机机器 选择的单点变异或基于机器最短处理时间的多点 变异； Z λ , Z ∗ Z ∗ = min{Z λ ,Z ∗ } t = 1 λ = λ+1 t = t + 1 7 ）若当前迭代得到的最佳解 ， ， ， ，转至 2）；否则， ， 执行 8）； 8）若 t = T ，执行 9），否则， λ = λ+1 ，转至 2）； Z ∗ Z ∗ Z ∗ t = 1 λ = λ+1 9）调用候鸟优化算法，若得到的最佳解优于 ，更新 ，否则，保留 不变； ， ，转至 2）。 3 仿真实验 本文所提的遗传候鸟优化算法将全局搜索、 自适应遗传算法和候鸟优化相结合，为了验证所 提出的算法性能，从传统算法、与其他算法结合 的混合算法、解码规则、已发表的文献的算法 4 个角度选择传统遗传算法 (traditional genetic algorithm, TGA)，结合 3 种领域搜索结构候鸟优化 算法 (migrating birds optimization & neighborhood search, MBO&NS )、基于最长处理时间规则解码 的遗传候鸟优化算法 (genetic migrating birds optimization algorithm L, GMBOAL)、结合局域搜索 的自适应遗传算法 (adaptive genetic algorithm & local search, AGA&LS) 与文献 [30] 的改进人工蜂 群算法 (improved artificial bee colony, IDABC) 进行 对比。采用 Matlab R2014b 进行编程，在 CPU 为 Inter Core i5-5200U，内存为 4 GB，主频 2.2 GHz 的 微机上运行。 3.1 参数设置 ξ ψ ξ = 0.8 ψ = 0.2 ξmax ξmin ψmax ψmin 为公平比较 TGA、MBO&NS、 GMBOAL、 AGA&LS、IDABC 和 GMBOA 这 6 种算法，TGA 中的 和 的取值通过仿真实验得到最佳的一组 设置，即 和 ；GMBOAL、AGA&LS 和 GMBOA 中的 、 、 和 的取值是通过仿 ξmax = 0.9 ξmin = 0.5 ψmax = 0.2 ψmin = 0.02 δ = 31 γ = 10 Gmax = 10 o = 3 e = 100 e = 101 β = 100 真实验得到最佳的一组设置，即 、 、 和 ；参考文献 [22]，并经过仿真 实验测试 GMBOA 中的 、 、 、 ；基于 GA 的 4 种算法和 IDABC 的种群规模 ；由于 MBO&NS 的种群规模必须为奇数， 所以其种群规模 ；IDABC 的参数与文献 [30] 的设置相同，最大迭代数 ，最大 CPU 时间 为 720 s；考虑到 GA 的运行时间较短，将 MBO&NS、 GMBOAL、AGA&LS、IDABC 和 GMBOA 的停止 时间设为 TGA 运行 100 次所需时间。 n = {20,30,40,50,80,100,120,150} h = {5,10,15,20} ms = 5 p Pjks 问题产生如下： ， ， 。借鉴 Dios 等 [7-8] 关于忽略 工序比例的设定，将本文的忽略工序比例 分别 取为 20%、40% 和 60%。每个工件在同一道工序 不同机器上的处理时间 不同且满足 [1, 99] 之 间的均匀分布。 3.2 数据实验与结果分析 参数 {n,h, p} 的不同组合产生 96 组问题规模， 每种规模随机运行 10 个实例，取 10 次测试结果 的平均值作为对应规模问题的测试结果。 定义相对偏差为 R1 = CTGA −CGMBOA CGMBOA ×100% R2 = CMBO& NS −CGMBOA CGMBOA ×100% R3 = CGMBOAL −CGMBOA CGMBOA ×100% R4 = CAGA& LS −CGMBOA CGMBOA ×100% R5 = CIDABC −CGMBOA CGMBOA ×100% 由于本文所提的算法迭代 100 次的 CPU 时 间略长，为在较短的运行时间内测试所提算法的 有效性，兼顾算法对比的公平性，将 TGA 迭代 100 次所需的时间作为对比算法 MBO&NS、GMBOAL、 AGA&LS、IDABC 和所提出算法 GMBOA 的停止 条件，以此对比算法的性能，所以表 1~6 列出的 CPU 时间为 TGA 迭代 100 次的时间。表 1~6 列 出了 5 种算法求解不同规模问题的实验结果。 表 1 忽略工序比例为 20% 时中小规模问题的测试结果 Table 1 Testing results for small and medium scale problems with the proportion 20% of missing operations n×h TGA MBO&NS GMBOAL AGA&LS IDABC GMBOA R1 /% R2 /% R3 /% R4 /% R5 /% CPU时间/s 20×5 209.9 208.2 184.1 176.5 188.9 172.3 21.82 20.84 6.85 2.44 9.63 22.01 30×5 280.1 260.3 224.2 218.1 228.4 203.7 37.51 27.79 10.06 7.07 12.13 25.19 40×5 318.6 284.9 261.5 242.4 261.7 232.0 37.33 22.80 12.72 4.48 12.80 28.84 50×5 335.7 335.0 285.0 271.8 296.0 263.2 27.55 27.28 8.28 3.27 12.46 31.44 20×10 337.3 355.8 299.0 285.8 300.9 277.1 21.73 28.40 6.85 3.14 8.59 44.14 第 17 卷 智 能 系 统 学 报 ·464·
·465· 轩华，等：含忽略工序和不相关机的混合流水车间调度 第3期 续表1 nxh TGA MBO&NS GMBOAL AGA&LS IDABC GMBOA RR% R%R%R%CPU时间/s 30×10 387.5 409.7 358.6 338.2 364.1 327.1 18.4725.25 9.633.3911.31 52.65 40×10475.7 438.4 390.3 378.7 395.0 362.9 31.0820.807.55 4.35 8.85 60.41 50×10513.3 501.8 431.8 405.4 425.2 399.2 28.5825.708.17 1.55 6.51 67.85 20×15408.1 431.7 373.8 376.8 405.6 358.2 13.9320.524.365.1913.23 70.29 30×15506.5 530.0 441.6 421.2 441.6 409.8 23.6029.337.762.78 7.76 84.45 40×15 542.2 582.1 478.4 468.4 484.5 451.4 20.1228.955.983.77 7.33 98.44 50×15664.6 633.4 530.2 522.6 535.4 518.2 28.2522.232.320.85 3.32 111.03 20×20562.7 572.3 463.0 453.8 509.5 447.2 25.8327.973.531.48 13.93 100.58 30×20578.7 635.0 526.5 506.2 538.9 495.6 16.7728.136.232.14 8.74 119.15 40×20 752.3 693.1 568.8 565.3 580.3 552.3 36.2125.492.992.35 5.07 136.65 50×20792.7 782.2 635.1 637.5 640.0 634.5 24.9323.280.090.47 0.87 156.92 平均 479.1 478.4 403.2 391.8 412.3 381.5 25.8625.306.463.05 8.91 75.63 表2忽略工序比例为20%时大规模问题测试结果 Table 2 Testing results for large scale problems with the proportion 20%of missing operations nxh TGA MBO&NS GMBOAL AGA&LS IDABC GMBOA R%R2/%R/%R,/%R/%CPU时间s 80×5 475.1 468.6 414.5 414.5 408.8 375.0 26.6924.9610.531.75 9.01 40.47 100×5 563.0 555.2 499.5 461.1 495.6 443.426.9725.2112.653.9911.77 49.34 120×5 574.9 639.4 564.6 520.4 556.1 508.812.9925.2110.972.28 9.30 58.26 150x5 715.7 742.2 640.7 607.3 644.3 587.621.8026.319.043.35 9.65 68.37 80×10 679.6 641.9 551.3 538.6 535.8 527.2 28.9121.764.572.16 1.63 96.02 100×10 748.5 743.6 635.8 614.0 620.9 605.2 23.68.22.875.061.45 2.59 112.20 120×10 893.1 844.7 748.7 706.3 707.7 690.6 29.3222.318.412.27 2.48 125.84 150×101041.7 975.5 841.4 788.7 810.0 769.4 35.3926.79 9.362.51 5.28 150.04 80x15 870.7 838.0 700.7 680.3 673.6 667.4 30.4625.56 4.99 1.93 0.93 150.26 100×151037.4 933.4 783.6 780.8 7652 764.8 35.6422.04 2.462.09 0.05 181.06 120×151100.4 1029.9 889.2 878.1 867.8 867.2 26.8918.762.541.26 0.07 213.00 150×151234.9 1091.1 996.5 972.4 961.5 960.9 28.5113.553.701.20 0.06 259.82 80×20 989.2 981.7 825.9 803.0 796.5 795.0 24.4323.483.891.01 0.19 218.39 100×201117.7 1095.5 922.4 914.8 895.5 894.524.9522.47 3.122.27 0.11 262.73 120×201326.5 1211.5 1020.4 1003.6 991.2 989.734.0322.413.101.40 0.15 303.08 150×201305.6 1368.0 1150.1 1135.1 1124.51123.316.2321.782.391.05 0.11 380.04 平均 917.1 885.0 761.6 738.7 740.9 723.126.6822.846.052.003.34 166.81 表3忽略工序比例为40%时中小规模问题测试结果 Table 3 Testing results for small and medium scale problems with the proportion 40%of missing operations nxh TGA MBo&NS GMBOAL AGA&Ls IDABC GMBOA R,%R,%R,%R/%RJ%CPU时间/S 20×5163.7 183.3 149.9 145.4 151.5 143.6 14.0027.654.391.255.50 20.95 30×5212.2 209.5 175.1 172.7 183.3 163.1 30.1028.457.365.8912.39 24.42 40×5253.3 209.8 189.5 184.0 197.8 179.4 41.1916.955.632.5610.26 27.81
续表 1 n×h TGA MBO&NS GMBOAL AGA&LS IDABC GMBOA R1 /% R2 /% R3 /% R4 /% R5 /% CPU时间/s 30×10 387.5 409.7 358.6 338.2 364.1 327.1 18.47 25.25 9.63 3.39 11.31 52.65 40×10 475.7 438.4 390.3 378.7 395.0 362.9 31.08 20.80 7.55 4.35 8.85 60.41 50×10 513.3 501.8 431.8 405.4 425.2 399.2 28.58 25.70 8.17 1.55 6.51 67.85 20×15 408.1 431.7 373.8 376.8 405.6 358.2 13.93 20.52 4.36 5.19 13.23 70.29 30×15 506.5 530.0 441.6 421.2 441.6 409.8 23.60 29.33 7.76 2.78 7.76 84.45 40×15 542.2 582.1 478.4 468.4 484.5 451.4 20.12 28.95 5.98 3.77 7.33 98.44 50×15 664.6 633.4 530.2 522.6 535.4 518.2 28.25 22.23 2.32 0.85 3.32 111.03 20×20 562.7 572.3 463.0 453.8 509.5 447.2 25.83 27.97 3.53 1.48 13.93 100.58 30×20 578.7 635.0 526.5 506.2 538.9 495.6 16.77 28.13 6.23 2.14 8.74 119.15 40×20 752.3 693.1 568.8 565.3 580.3 552.3 36.21 25.49 2.99 2.35 5.07 136.65 50×20 792.7 782.2 635.1 637.5 640.0 634.5 24.93 23.28 0.09 0.47 0.87 156.92 平均 479.1 478.4 403.2 391.8 412.3 381.5 25.86 25.30 6.46 3.05 8.91 75.63 表 2 忽略工序比例为 20% 时大规模问题测试结果 Table 2 Testing results for large scale problems with the proportion 20% of missing operations n×h TGA MBO&NS GMBOAL AGA&LS IDABC GMBOA R1 /% R2 /% R3 /% R4 /% R5 /% CPU时间/s 80×5 475.1 468.6 414.5 414.5 408.8 375.0 26.69 24.96 10.53 1.75 9.01 40.47 100×5 563.0 555.2 499.5 461.1 495.6 443.4 26.97 25.21 12.65 3.99 11.77 49.34 120×5 574.9 639.4 564.6 520.4 556.1 508.8 12.99 25.21 10.97 2.28 9.30 58.26 150×5 715.7 742.2 640.7 607.3 644.3 587.6 21.80 26.31 9.04 3.35 9.65 68.37 80×10 679.6 641.9 551.3 538.6 535.8 527.2 28.91 21.76 4.57 2.16 1.63 96.02 100×10 748.5 743.6 635.8 614.0 620.9 605.2 23.68 22.87 5.06 1.45 2.59 112.20 120×10 893.1 844.7 748.7 706.3 707.7 690.6 29.32 22.31 8.41 2.27 2.48 125.84 150×10 1041.7 975.5 841.4 788.7 810.0 769.4 35.39 26.79 9.36 2.51 5.28 150.04 80×15 870.7 838.0 700.7 680.3 673.6 667.4 30.46 25.56 4.99 1.93 0.93 150.26 100×15 1037.4 933.4 783.6 780.8 765.2 764.8 35.64 22.04 2.46 2.09 0.05 181.06 120×15 1100.4 1029.9 889.2 878.1 867.8 867.2 26.89 18.76 2.54 1.26 0.07 213.00 150×15 1234.9 1091.1 996.5 972.4 961.5 960.9 28.51 13.55 3.70 1.20 0.06 259.82 80×20 989.2 981.7 825.9 803.0 796.5 795.0 24.43 23.48 3.89 1.01 0.19 218.39 100×20 1117.7 1095.5 922.4 914.8 895.5 894.5 24.95 22.47 3.12 2.27 0.11 262.73 120×20 1326.5 1211.5 1 020.4 1003.6 991.2 989.7 34.03 22.41 3.10 1.40 0.15 303.08 150×20 1305.6 1368.0 1 150.1 1135.1 1124.5 1 123.3 16.23 21.78 2.39 1.05 0.11 380.04 平均 917.1 885.0 761.6 738.7 740.9 723.1 26.68 22.84 6.05 2.00 3.34 166.81 表 3 忽略工序比例为 40% 时中小规模问题测试结果 Table 3 Testing results for small and medium scale problems with the proportion 40% of missing operations n×h TGA MBO&NS GMBOAL AGA&LS IDABC GMBOA R1 /% R2 /% R3 /% R4 /% R5 /% CPU时间/s 20×5 163.7 183.3 149.9 145.4 151.5 143.6 14.00 27.65 4.39 1.25 5.50 20.95 30×5 212.2 209.5 175.1 172.7 183.3 163.1 30.10 28.45 7.36 5.89 12.39 24.42 40×5 253.3 209.8 189.5 184.0 197.8 179.4 41.19 16.95 5.63 2.56 10.26 27.81 ·465· 轩华，等：含忽略工序和不相关机的混合流水车间调度 第 3 期
第17卷 智能系统学报 ·466· 续表3 n×hTGA MBO&NS GMBOAL AGA&LS IDABC GMBOA R1/%R2/%R3/%R/%R/%CPU/s 50×5 271.0 233.6 218.8 218.7 221.7 204.3 32.65 14.34 7.10 7.05 8.52 30.58 20×10 286.5 276.2 241.8 232.1 250.0 226.7 26.38 21.84 6.66 2.38 10.28 41.27 30×10343.5 304.7 280.0 267.8 283.2 260.2 32.0117.107.61 2.92 8.12 51.89 40×10322.9 339.7 292.1 285.8 298.0 272.5 18.5024.667.194.88 9.36 58.25 50×10364.0 380.0 319.9 319.7 329.6 306.0 18.9524.184.544.48 7.71 65.19 20×15370.0 353.0 297.5 298.2 327.4 283.7 30.4224.434.865.1115.40 63.90 30×15395.7 394.5 341.9 342.9 350.4 323.8 22.2121.835.595.90 8.21 77.76 40×15428.9 429.6 349.1 356.5 362.0 339.6 26.3026.502.804.98 6.60 91.36 50×15548.7 470.1 393.0 394.8 397.5 385.5 42.3321.951.952.41 3.11 102.45 20×20402.0 425.0 344.8 346.6 391.3 335.4 19.8626.712.803.34 16.67 88.09 30×20488.9 484.3 401.0 404.3 435.3 393.0 24.4023.232.042.8810.76 107.85 40×20465.8 530.7 425.6 423.3 450.3 412.412.9528.693.202.64 9.19 126.48 50×20575.9 586.1 474.0 469.0 491.8 458.0 25.7427.973.492.40 7.38 144.08 平均 368.3 363.1 305.9 303.9 320.1 293.0 26.1223.534.833.829.34 70.15 表4忽略工序比例为40%时大规模问题测试结果 Table 4 Testing results for large scale problems with the proportion 40%of missing operations nxh TGA MBO&NS GMBOAL AGA&LS IDABC GMBOA R/%R2/%R3/%R/%R/%CPU/s 80×5 331.6 353.6 293.3 291.7 307.3 277.2 19.6227.565.815.23 10.86 40.12 100×5 413.2 416.8 364.7 348.7 368.1 332.2 24.3825.479.784.97 9.75 46.86 120×5466.1 475.7 412.9 410.4 423.5 383.3 21.6024.117.727.0710.49 53.21 150×5560.1 529.9 473.7 452.7 476.4 422.5 32.5725.4212.127.15 12.76 62.78 80×10463.4 494.2 411.2 404.2 410.2 390.5 18.6726.565.303.51 5.04 89.57 100×10571.2 555.8 475.9 462.7 480.4 456.2 25.2121.834.321.42 5.30 103.36 120×10687.2 618.9 537.1 528.6 537.1 513.4 33.8520.554.622.96 4.62 118.47 150×10688.3 650.9 598.8 590.5 610.0 575.2 19.6613.164.102.66 6.05 143.00 80×15650.9 626.3 521.2 509.0 510.7 500.0 30.1825.264.241.80 2.14 141.67 100×15704.0 686.8 588.1 577.3 568.1 564.6 24.6921.644.162.25 0.62 168.76 120×15742.8 767.4 659.5 648.0 635.2 629.5 18.0021.914.772.94 0.91 196.93 150×15892.9 889.7 741.8 735.1 724.7 719.7 24.0723.623.072.14 0.69 225.99 80×20 783.6 716.8 599.4 595.7 585.4 581.6 34.7323.25 3.062.42 0.65 198.27 100×20 911.1 811.5 685.0 671.6 665.8 663.8 37.2622.253.191.18 0.30 233.16 120×20987.4 923.9 778.0 761.2 755.5 754.8 30.8222.403.070.85 0.09 269.46 150×201106.6 1013.6 846.0 840.6 835.1 834.9 32.5421.401.330.68 0.02 325.50 平均685.0 658.2 561.7 551.8 555.8 537.526.7422.905.043.084.39 151.07 表5忽略工序比例为60%时中小规模问题测试结果 Table 5 Testing results for small and medium scale problems with the proportion 60%of missing operations nxh TGA MBO&NS GMBOAL AGA&LS IDABC GMBOA R:/%R2/%R3/%R/%R/%CPU/s 20×5108.0 103.9 88.0 93.4 112.4 87.723.1518.470.346.5028.1619.03
续表 3 n×h TGA MBO&NS GMBOAL AGA&LS IDABC GMBOA R1 /% R2 /% R3 /% R4 /% R5 /% CPU时间/s 50×5 271.0 233.6 218.8 218.7 221.7 204.3 32.65 14.34 7.10 7.05 8.52 30.58 20×10 286.5 276.2 241.8 232.1 250.0 226.7 26.38 21.84 6.66 2.38 10.28 41.27 30×10 343.5 304.7 280.0 267.8 283.2 260.2 32.01 17.10 7.61 2.92 8.12 51.89 40×10 322.9 339.7 292.1 285.8 298.0 272.5 18.50 24.66 7.19 4.88 9.36 58.25 50×10 364.0 380.0 319.9 319.7 329.6 306.0 18.95 24.18 4.54 4.48 7.71 65.19 20×15 370.0 353.0 297.5 298.2 327.4 283.7 30.42 24.43 4.86 5.11 15.40 63.90 30×15 395.7 394.5 341.9 342.9 350.4 323.8 22.21 21.83 5.59 5.90 8.21 77.76 40×15 428.9 429.6 349.1 356.5 362.0 339.6 26.30 26.50 2.80 4.98 6.60 91.36 50×15 548.7 470.1 393.0 394.8 397.5 385.5 42.33 21.95 1.95 2.41 3.11 102.45 20×20 402.0 425.0 344.8 346.6 391.3 335.4 19.86 26.71 2.80 3.34 16.67 88.09 30×20 488.9 484.3 401.0 404.3 435.3 393.0 24.40 23.23 2.04 2.88 10.76 107.85 40×20 465.8 530.7 425.6 423.3 450.3 412.4 12.95 28.69 3.20 2.64 9.19 126.48 50×20 575.9 586.1 474.0 469.0 491.8 458.0 25.74 27.97 3.49 2.40 7.38 144.08 平均 368.3 363.1 305.9 303.9 320.1 293.0 26.12 23.53 4.83 3.82 9.34 70.15 表 4 忽略工序比例为 40% 时大规模问题测试结果 Table 4 Testing results for large scale problems with the proportion 40% of missing operations n×h TGA MBO&NS GMBOAL AGA&LS IDABC GMBOA R1 /% R2 /% R3 /% R4 /% R5 /% CPU时间/s 80×5 331.6 353.6 293.3 291.7 307.3 277.2 19.62 27.56 5.81 5.23 10.86 40.12 100×5 413.2 416.8 364.7 348.7 368.1 332.2 24.38 25.47 9.78 4.97 9.75 46.86 120×5 466.1 475.7 412.9 410.4 423.5 383.3 21.60 24.11 7.72 7.07 10.49 53.21 150×5 560.1 529.9 473.7 452.7 476.4 422.5 32.57 25.42 12.12 7.15 12.76 62.78 80×10 463.4 494.2 411.2 404.2 410.2 390.5 18.67 26.56 5.30 3.51 5.04 89.57 100×10 571.2 555.8 475.9 462.7 480.4 456.2 25.21 21.83 4.32 1.42 5.30 103.36 120×10 687.2 618.9 537.1 528.6 537.1 513.4 33.85 20.55 4.62 2.96 4.62 118.47 150×10 688.3 650.9 598.8 590.5 610.0 575.2 19.66 13.16 4.10 2.66 6.05 143.00 80×15 650.9 626.3 521.2 509.0 510.7 500.0 30.18 25.26 4.24 1.80 2.14 141.67 100×15 704.0 686.8 588.1 577.3 568.1 564.6 24.69 21.64 4.16 2.25 0.62 168.76 120×15 742.8 767.4 659.5 648.0 635.2 629.5 18.00 21.91 4.77 2.94 0.91 196.93 150×15 892.9 889.7 741.8 735.1 724.7 719.7 24.07 23.62 3.07 2.14 0.69 225.99 80×20 783.6 716.8 599.4 595.7 585.4 581.6 34.73 23.25 3.06 2.42 0.65 198.27 100×20 911.1 811.5 685.0 671.6 665.8 663.8 37.26 22.25 3.19 1.18 0.30 233.16 120×20 987.4 923.9 778.0 761.2 755.5 754.8 30.82 22.40 3.07 0.85 0.09 269.46 150×20 1106.6 1013.6 846.0 840.6 835.1 834.9 32.54 21.40 1.33 0.68 0.02 325.50 平均 685.0 658.2 561.7 551.8 555.8 537.5 26.74 22.90 5.04 3.08 4.39 151.07 表 5 忽略工序比例为 60% 时中小规模问题测试结果 Table 5 Testing results for small and medium scale problems with the proportion 60% of missing operations n×h TGA MBO&NS GMBOAL AGA&LS IDABC GMBOA R1 /% R2 /% R3 /% R4 /% R5 /% CPU时间/s 20×5 108.0 103.9 88.0 93.4 112.4 87.7 23.15 18.47 0.34 6.50 28.16 19.03 第 17 卷 智 能 系 统 学 报 ·466·
·467· 轩华，等：含忽略工序和不相关机的混合流水车间调度 第3期 续表5 nxh TGA MBO&NS GMBOAL AGA&LS IDABC GMBOA R1/%R2/%R3/%Ra/Rs/% CPU时间/s 30×5131.4 128.9 110.9 121.2 119.1 108.2 21.4419.132.5012.01 10.07 22.81 40×5144.6 123.9 116.6 121.6 126.9 113.0 27.96 9.653.19 7.61 12.30 26.38 50x5 184.9 159.8 135.8 150.3 155.2 130.8 41.3622.17 3.8214.91 18.65 28.89 20×10179.0 178.4 161.9 159.3 196.9 161.1 11.1110.74 0.50 -1.1222.22 37.10 30×10 243.3 214.0 193.3 189.3 196.9 184.8 31.6615.80 4.60 2.44 6.55 46.70 40×10253.4 245.9 202.6 202.6 210.2 193.6 30.8927.01 4.65 4.65 8.57 53.31 50×10289.1 249.6 218.0 217.0 230.1 205.6 40.6121.406.03 5.5411.92 59.73 20×15271.9 262.7 230.5 222.7 265.3 224.8 20.95 16.862.54-0.93 18.02 56.62 30×15299.2 273.6 236.6 241.6 258.3 2297 30.2619.113.005.18 12.45 71.15 40×15307.0 315.5 257.0 262.8 277.1 21.5824.951.784.08 9.74 83.09 50×15345.8 335.5 271.7 280.4 286.0 265.6 30.2026.32 2.305.57 7.68 94.93 20×20 296.0 303.1 260.1 269.4 313.3 263.4 12.3815.07-1.25 2.2818.94 78.94 30×20336.9 352.3 291.0 292.9 318.6 284.2 18.5423.96 2.39 3.06 12.10 98.34 40×20401.7 367.5 304.5 316.8 331.3 300.7 33.5922.211.26 5.3510.18 114.12 50×20 434.9 415.1 316.5 328.1 337.8 314.6 38.2431.950.60 4.29 7.37 130.60 平均264.2 251.9 212.2 216.8 233.5 207.5 27.1220.302.395.0913.43 63.86 表6忽略工序比例为60%时大规模问题测试结果 Table 6 Testing results for large scale problems with the proportion 60%of missing operations n×h TGA MBO&NS gMBOaL aga&ls IDABC GMBOA R%R%R/%R,% R/%CPU时间/s 80×5 255.9 204.0 186.5 194.0 189.7 179.0 42.9613.97 4.198.385.98 38.14 100×5 281.2 241.9 220.3 232.4 235.2 212.4 32.3913.893.729.4210.73 43.26 120×5 318.6 289.1 261.0 265.3 284.7 252.4 26.2314.543.415.11 12.80 51.75 150×5371.3 349.8 312.7 308.0 342.0 307.5 20.7513.761.690.1611.22 58.90 80×10 359.3 328.0 277.3 274.5 278.8 262.2 37.0325.105.764.69 6.33 79.09 100×10407.8 388.5 332.1 336.7 322.3 316.1 29.0122.905.066.521.96 92.60 120×10394.9 424.3 367.6 364.2 364.9 342.4 15.3323.927.366.37 6.57 106.71 150×10507.5 477.6 401.4 399.1 407.1 387.6 30.9323.223.562.97 5.03 126.37 80×15414.2 445.1 347.4 362.0 362.8 346.4 19.5728.490.294.50 4.73 127.90 100×15480.3 465.7 381.5 389.6 385.8 373.0 28.7724.852.284.45 3.43 148.57 120×15588.4 534.1 438.9 437.9 430.5 428.1 37.4424.762.522.290.56 170.06 150×15598.2 564.3 479.1 491.8 483.6 465.9 28.4021.122.835.56 3.80 205.08 80×20527.7 495.6 411.4 412.8 423.4 401.3 31.5023.502.522.87 5.51 178.11 100×20579.6 548.5 452.9 455.5 450.6 447.5 29.5222.571.211.790.69 208.59 120×20641.0 594.3 505.5 501.3 496.7 494.1 29.7320.282.311.46 0.05 241.16 150×20766.8 675.5 566.7 568.4 557.3 556.6 37.7721.361.812.120.13 288.17 平均 468.3 439.1 371.4 374.6 376.0 360.8 29.8321.143.164.29 4.97 135.28
续表 5 n×h TGA MBO&NS GMBOAL AGA&LS IDABC GMBOA R1 /% R2 /% R3 /% R4 /% R5 /% CPU时间/s 30×5 131.4 128.9 110.9 121.2 119.1 108.2 21.44 19.13 2.50 12.01 10.07 22.81 40×5 144.6 123.9 116.6 121.6 126.9 113.0 27.96 9.65 3.19 7.61 12.30 26.38 50×5 184.9 159.8 135.8 150.3 155.2 130.8 41.36 22.17 3.82 14.91 18.65 28.89 20×10 179.0 178.4 161.9 159.3 196.9 161.1 11.11 10.74 0.50 -1.12 22.22 37.10 30×10 243.3 214.0 193.3 189.3 196.9 184.8 31.66 15.80 4.60 2.44 6.55 46.70 40×10 253.4 245.9 202.6 202.6 210.2 193.6 30.89 27.01 4.65 4.65 8.57 53.31 50×10 289.1 249.6 218.0 217.0 230.1 205.6 40.61 21.40 6.03 5.54 11.92 59.73 20×15 271.9 262.7 230.5 222.7 265.3 224.8 20.95 16.86 2.54 -0.93 18.02 56.62 30×15 299.2 273.6 236.6 241.6 258.3 229.7 30.26 19.11 3.00 5.18 12.45 71.15 40×15 307.0 315.5 257.0 262.8 277.1 252.5 21.58 24.95 1.78 4.08 9.74 83.09 50×15 345.8 335.5 271.7 280.4 286.0 265.6 30.20 26.32 2.30 5.57 7.68 94.93 20×20 296.0 303.1 260.1 269.4 313.3 263.4 12.38 15.07 -1.25 2.28 18.94 78.94 30×20 336.9 352.3 291.0 292.9 318.6 284.2 18.54 23.96 2.39 3.06 12.10 98.34 40×20 401.7 367.5 304.5 316.8 331.3 300.7 33.59 22.21 1.26 5.35 10.18 114.12 50×20 434.9 415.1 316.5 328.1 337.8 314.6 38.24 31.95 0.60 4.29 7.37 130.60 平均 264.2 251.9 212.2 216.8 233.5 207.5 27.12 20.30 2.39 5.09 13.43 63.86 表 6 忽略工序比例为 60% 时大规模问题测试结果 Table 6 Testing results for large scale problems with the proportion 60% of missing operations n×h TGA MBO&NS GMBOAL AGA&LS IDABC GMBOA R1 /% R2 /% R3 /% R4 /% R5 /% CPU时间/s 80×5 255.9 204.0 186.5 194.0 189.7 179.0 42.96 13.97 4.19 8.38 5.98 38.14 100×5 281.2 241.9 220.3 232.4 235.2 212.4 32.39 13.89 3.72 9.42 10.73 43.26 120×5 318.6 289.1 261.0 265.3 284.7 252.4 26.23 14.54 3.41 5.11 12.80 51.75 150×5 371.3 349.8 312.7 308.0 342.0 307.5 20.75 13.76 1.69 0.16 11.22 58.90 80×10 359.3 328.0 277.3 274.5 278.8 262.2 37.03 25.10 5.76 4.69 6.33 79.09 100×10 407.8 388.5 332.1 336.7 322.3 316.1 29.01 22.90 5.06 6.52 1.96 92.60 120×10 394.9 424.3 367.6 364.2 364.9 342.4 15.33 23.92 7.36 6.37 6.57 106.71 150×10 507.5 477.6 401.4 399.1 407.1 387.6 30.93 23.22 3.56 2.97 5.03 126.37 80×15 414.2 445.1 347.4 362.0 362.8 346.4 19.57 28.49 0.29 4.50 4.73 127.90 100×15 480.3 465.7 381.5 389.6 385.8 373.0 28.77 24.85 2.28 4.45 3.43 148.57 120×15 588.4 534.1 438.9 437.9 430.5 428.1 37.44 24.76 2.52 2.29 0.56 170.06 150×15 598.2 564.3 479.1 491.8 483.6 465.9 28.40 21.12 2.83 5.56 3.80 205.08 80×20 527.7 495.6 411.4 412.8 423.4 401.3 31.50 23.50 2.52 2.87 5.51 178.11 100×20 579.6 548.5 452.9 455.5 450.6 447.5 29.52 22.57 1.21 1.79 0.69 208.59 120×20 641.0 594.3 505.5 501.3 496.7 494.1 29.73 20.28 2.31 1.46 0.05 241.16 150×20 766.8 675.5 566.7 568.4 557.3 556.6 37.77 21.36 1.81 2.12 0.13 288.17 平均 468.3 439.1 371.4 374.6 376.0 360.8 29.83 21.14 3.16 4.29 4.97 135.28 ·467· 轩华，等：含忽略工序和不相关机的混合流水车间调度 第 3 期
第17卷 智能系统学报 ·468· 从表1~6可知： 比TGA、MBO&NS、GMBOAL、AGA&LS、ID 1)当p=20%时，对于中小规模问题，在平均 ABC产生了较好的解。 CPU时间75.63s内，由TGA、MBO&NS、 3)当p=60%时，对于中小规模问题，在平均 GMBOAL、AGA&LS、IDABC和GMBOA得到的 CPU时间63.86s内，由TGA、MBO&NS、GMBOAL 平均目标值分别为479.1、478.4、403.2、391.8、412.3、 AGA&LS、IDABC和GMBOA得到的平均目标值 381.5。GMBOA得到的目标值较TGA改进25.86%， 分别为264.2、251.9、212.2、216.8、233.5、207.5。 较MBO&NS改进25.30%，较GMBOAL改进 GMB0A的目标值较TGA改进27.12%，较 6.46%,较AGA&LS改进3.05%，较IDABC改进 MBO&NS改进20.30%，较GMBOAL改进2.39%， 8.91%。 较AGA&LS改进5.09%，较IDABC改进13.43% 对于大规模问题，在平均CPU时间166.81s 对于大规模问题，在平均CPU时间135.28s 内，由TGA、MBO&NS、GMBOAL、AGA&LS、ID- 内，由TGA、MBO&NS、GMBOAL、AGA&LS、ID- ABC和GMBOA得到的平均目标值分别为917.1、 ABC和GMBOA得到的平均目标值分别为 885.0、761.6、738.7、740.9、723.1。GMB0A的目 468.3、439.1、371.4、374.6、376.0、360.8。GMB0A 标值较TGA改进26.68%，较MBO&NS改进 的目标值较TGA改进29.83%，较MBO&NS改进 22.84%,较GMBOAL改进6.05%，较AGA&LS改 21.14%,较GMB0AL改进3.16%，较AGA&LS改 进2.00%，较DABC改进3.34%。 进4.29%、较DABC改进4.97%。 从平均性能来看，对于不同规模问题，在总平 虽然小规模问题20×10、20×15和20×20的 均时间121.22s内，TGA、MBO&NS、GMBOAL、 3个实例中GMBOA的目标值略差于AGA&LS AGA&LS、IDABC和GMBOA的平均目标值分别 或GMBOAL,但随着问题规模的增大，GMBOA 为698.1、681.7、582.4、565.3、576.6、552.3。GMB0A 得到的解的质量一致优于其他5种算法。 的目标值较TGA改进26.27%，较MBO&NS改进 从平均性能来看，对于不同规模问题，在总平 24.07%,较GMB0AL改进6.26%，较AGA&LS改 均时间99.57s内，TGA、MBO&NS、GMBOAL、 进2.53%，较DABC改进6.13%。整体来看，在相 AGA&LS、IDABC和GMBOA的平均目标值分别 同CPU时间内，GMBOA的表现明显优于TGA、 为366.3、345.5、291.8、295.7、304.8、284.2。GMB0A MBO&NS、GMBOAL、AGA&LS、IDABC. 的目标值较TGA改进28.48%，较MBO&NS改进 2)当p=40%时，对于中小规模问题，在平均 20.72%,较GMB0AL改进2.78%，较AGA&LS改 CPU时间70.15s内，由TGA、MBO&NS、GMBOAL、 进4.69%，较IDABC改进9.20%。因此，GMBOA AGA&LS、IDABC和GMBOA得到的平均目标值 表现最好，尤其是对于大规模问题。 分别为368.3、363.1、305.9、303.9、320.1、293.0。 4)综上可知，在相同CPU时间内，虽然当忽 GMB0A的目标值较TGA改进26.12%，较 略工序比例较高时GMBOA求解小规模问题的一 MBO&NS改进23.53%，较GMBOAL改进4.83%， 些实例的表现略差于其他算法，但平均性能均优 较AGA&LS改进3.82%，较DABC改进9.34%。 于TGA、MBO&NS、GMBOAL、AGA&LS、ID 对于大规模问题，在平均CPU时间151.07s ABC。 内，由TGA、MBO&NS、GMBOAL、AGA&LS、ID- 4结束语 ABC和GMBOA得到的平均目标值分别为685.0、 658.2、561.7、551.8、555.8、537.5。GMB0A的目 本文研究了含忽略工序和不相关并行机的混 标值较TGA改进26.74%，较MBO&NS改进 合流水车间调度问题，以最小化最大完工时间为 22.90%,较GMB0AL改进5.04%，较AGA&LS改 目标建立了整数规划模型，进而结合全局搜索、 进3.08%、较DABC改进4.39%。 自适应遗传算法和候鸟优化提出一种遗传候鸟优 从平均性能来看，对于不同规模问题，在总平 化算法以获取近优解。首先，设计基于机器号的 均时间110.61s内，TGA、MBO&NS、GMBOAL、 编码方案，采用全局搜索和随机程序生成初始种 AGA&LS、IDABC和GMBOA的平均目标值分别 群，然后执行随迭代进化过程而调整的自适应交 为526.7、510.7、433.8、427.9、438.0、415.3。GMB0A 叉和变异操作，从而得到改进的GA解，引入基 的目标值较TGA改进26.43%，较MBO&NS改进 于3种邻域结构的候鸟优化算法扩大解的搜索空 23.22%,较GMB0AL改进4.94%，较AGA&LS改 间以更新GA解。大量随机数据的仿真实验证明 进3.45%，较IDABC改进6.87%。因此，GMBOA 所提遗传候鸟优化算法能够在相同的CPU时间
从表 1~6 可知： 1）当 p = 20% 时，对于中小规模问题，在平均 C P U 时 间 75.63 s 内 ， 由 TGA 、 MBO&NS 、 GMBOAL、AGA&LS、IDABC 和 GMBOA 得到的 平均目标值分别为 479.1、478.4、403.2、391.8、412.3、 381.5。GMBOA 得到的目标值较 TGA 改进 25.86%， 较 MBO&NS 改进 25.30%，较 GMBOAL 改进 6.46%，较 AGA&LS 改进 3.05%，较 IDABC 改进 8.91%。 对于大规模问题，在平均 CPU 时间 166.81 s 内， 由 TGA、MBO&NS、GMBOAL、AGA&LS、IDABC 和 GMBOA 得到的平均目标值分别为 917.1、 885.0、761.6、738.7、740.9、723.1。GMBOA 的目 标值较 TGA 改进 26.68%，较 MBO&NS 改进 22.84%，较 GMBOAL 改进 6.05%，较 AGA&LS 改 进 2.00%，较 IDABC 改进 3.34%。 从平均性能来看，对于不同规模问题，在总平 均时间 121.22 s 内，TGA、MBO&NS、GMBOAL、 AGA&LS、IDABC 和 GMBOA 的平均目标值分别 为 698.1、681.7、582.4、565.3、576.6、552.3。GMBOA 的目标值较 TGA 改进 26.27%，较 MBO&NS 改进 24.07%，较 GMBOAL 改进 6.26%，较 AGA&LS 改 进 2.53%，较 IDABC 改进 6.13%。整体来看，在相 同 CPU 时间内，GMBOA 的表现明显优于 TGA、 MBO&NS、GMBOAL、AGA&LS、IDABC。 2）当 p = 40% 时，对于中小规模问题，在平均 CPU 时间 70.15 s 内，由 TGA、MBO&NS、GMBOAL、 AGA&LS、IDABC 和 GMBOA 得到的平均目标值 分别为 368.3、363.1、305.9、303.9、320.1、293.0。 GMBO A 的目标值 较 T G A 改 进 26.12% ， 较 MBO&NS 改进 23.53%，较 GMBOAL 改进 4.83%， 较 AGA&LS 改进 3.82%，较 IDABC 改进 9.34%。 对于大规模问题，在平均 CPU 时间 151.07 s 内， 由 TGA、MBO&NS、GMBOAL、AGA&LS、IDABC 和 GMBOA 得到的平均目标值分别为 685.0、 658.2、561.7、551.8、555.8、537.5。GMBOA 的目 标值较 TGA 改进 26.74%，较 MBO&NS 改进 22.90%，较 GMBOAL 改进 5.04%，较 AGA&LS 改 进 3.08%、较 IDABC 改进 4.39%。 从平均性能来看，对于不同规模问题，在总平 均时间 110.61 s 内，TGA、MBO&NS、GMBOAL、 AGA&LS、IDABC 和 GMBOA 的平均目标值分别 为 526.7、510.7、433.8、427.9、438.0、415.3。GMBOA 的目标值较 TGA 改进 26.43%，较 MBO&NS 改进 23.22%，较 GMBOAL 改进 4.94%，较 AGA&LS 改 进 3.45%，较 IDABC 改进 6.87%。因此，GMBOA 比 TGA、MBO&NS、GMBOAL、AGA&LS、IDABC 产生了较好的解。 3）当 p = 60% 时，对于中小规模问题，在平均 CPU 时间 63.86 s 内，由 TGA、MBO&NS、GMBOAL、 AGA&LS、IDABC 和 GMBOA 得到的平均目标值 分别为 264.2、251.9、212.2、216.8、233.5、207.5。 GMBO A 的目标值 较 T G A 改 进 27.12% ， 较 MBO&NS 改进 20.30%，较 GMBOAL 改进 2.39%， 较 AGA&LS 改进 5.09%，较 IDABC 改进 13.43%。 对于大规模问题，在平均 CPU 时间 135.28 s 内， 由 TGA、MBO&NS、GMBOAL、AGA&LS、IDA BC 和 GMBO A 得到的平均目标值分别 为 468.3、439.1、371.4、374.6、376.0、360.8。GMBOA 的目标值较 TGA 改进 29.83%，较 MBO&NS 改进 21.14%，较 GMBOAL 改进 3.16%，较 AGA&LS 改 进 4.29%、较 IDABC 改进 4.97%。 虽然小规模问题 20×10、20×15 和 20×20 的 3 个实例中 GMBOA 的目标值略差于 AGA&LS 或 GMBOAL，但随着问题规模的增大，GMBOA 得到的解的质量一致优于其他 5 种算法。 从平均性能来看，对于不同规模问题，在总平 均时间 99.57s 内 ，TGA、MBO&NS、GMBOAL、 AGA&LS、IDABC 和 GMBOA 的平均目标值分别 为 366.3、345.5、291.8、295.7、304.8、284.2。GMBOA 的目标值较 TGA 改进 28.48%，较 MBO&NS 改进 20.72%，较 GMBOAL 改进 2.78%，较 AGA&LS 改 进 4.69%，较 IDABC 改进 9.20%。因此，GMBOA 表现最好，尤其是对于大规模问题。 4）综上可知，在相同 CPU 时间内，虽然当忽 略工序比例较高时 GMBOA 求解小规模问题的一 些实例的表现略差于其他算法，但平均性能均优 于 TGA、MBO&NS、GMBOAL、AGA&LS、IDABC。 4 结束语 本文研究了含忽略工序和不相关并行机的混 合流水车间调度问题，以最小化最大完工时间为 目标建立了整数规划模型，进而结合全局搜索、 自适应遗传算法和候鸟优化提出一种遗传候鸟优 化算法以获取近优解。首先，设计基于机器号的 编码方案，采用全局搜索和随机程序生成初始种 群，然后执行随迭代进化过程而调整的自适应交 叉和变异操作，从而得到改进的 GA 解，引入基 于 3 种邻域结构的候鸟优化算法扩大解的搜索空 间以更新 GA 解。大量随机数据的仿真实验证明 所提遗传候鸟优化算法能够在相同的 CPU 时间 第 17 卷 智 能 系 统 学 报 ·468·
