2. 西北工业大学 机电学院, 陕西 西安 710072;
3. 西北工业大学 系统集成与工程管理研究所, 陕西 西安 710072;
4. 西北工业大学 计算机学院, 陕西 西安 710072
双资源约束作业车间调度问题(dual resource constrained job shop scheduling problem,DRCJSP)是一类特殊的柔性作业车间调度问题,同时考虑了设备、工人两类资源的能力约束。相对于经典FJSP问题,DRCJSP的调度灵活性及资源配置选择更多,更接近实际生产调度环境,是迫切需要解决的NP-Hard问题。
Elmaraghy等[1]基于同时考虑双资源任务分配的染色体表达形式,用遗传算法(genetic algorithm,GA)求解DRCJSP与JSP,得到针对不同指标的最佳分派规则。周炳海等[2]将DRCJSP问题分解为双资源的分配优化问题与作业序列优化问题2个子问题,然后分别采用基于分派规则与作业块右移规则的GA算法求解上述2个子问题。陶泽等[3]基于带有控制器的Petri网为动态DRCJSP建模,灵活使用GA算法、SA算法、再分配策略等应对各类动态事件。陈勇等[4]针对考虑不确定订单的双资源约束多装配线,提出了一种基于差分进化算法和粒子群算法的混合优化算法,并验证了其可行性和有效性。Araz等[5]基于人工神经网络建立了DRCJSP实时调度模型,有效降低了计算复杂度,但其性能易受到初选分派规则集合和人工神经网络模型准确性的影响。
纵观现有研究,应用智能算法求解DRCJSP问题虽已获得一定成果,但依然存在3点不足:①采用从单一种群出发,不断逼近最优个体的进化模式,优化结果过分依赖初始群体质量;②进化算子仅针对工序信息,缺乏资源配置相关的进化操作;③现有的DRCJSP研究对零件批次、准备时间等影响实际生产调度的因素考虑较少。针对上述问题,作者前期已展开了一系列研究,先后提出了蚁群-退火混合算法[6]和继承式遗传算法[7]求解DRCJSP问题,但前者优化双目标时效果不佳,后者有进一步优化Pareto解集分布均匀程度的空间。
本文针对EDRCJSP问题的多类约束及柔性工艺特点,在文献[8]的算法基础上,引入精英进化与邻域局部搜索等机制进一步优化其全局搜索性能,并通过一系列仿真算例与实例验证了各个优化机制的先进性和算法的有效性。
1 问题描述在EDRCJSP问题中,w个加工效率不同的工人W1,…,Wl,…,Ww,需操作m台设备M1,…,Mk,…,Mm,加工n批工件P1,…,Pi,…,Pn (w<m),要求在各自的批次交付期限TPiE 前完成不同批量B1,…,Bi,…,Bn,加工每个工件需完成一系列的不同工序,其中每道工序均有多种加工路线,即可由不同的工人-设备组合加工完成。每个工人均能操纵2类及以上设备,且操作效率不同。加工设备有数控设备和一般设备2种,一般设备加工需工人全程操作,操作数控设备时,工人只参与加工准备与工件装卸阶段。EDRCJSP调度即在此环境下,通过为所有工序配置最佳的加工资源组合,并确定最优的工序加工顺序,在满足双资源能力约束的前提下,获得性能指标最优的调度方案。
2 BPGA算法研究 2.1 算法设计分支种群遗传算法(branch population genetic algorithm,BPGA)将每个工序的多道工艺路线视作多条分支路径。每次迭代前,根据路径信息素及启发式信息生成染色体分支种群,与当代染色体共同进化。一方面以分支种群为载体继承之前各代种群的“生存经验”,客观反映工序调度次序及工艺选择对于调度指标的影响,正确引导种群的进化及搜索方向;另一方面,通过引入外部染色体增强进化种群的多样性,既可避免算法早熟,又拓展了算法的全局搜索能力。此外,BPGA算法通过以下3种机制,进一步优化算法性能:①精英进化策略,鼓励较优个体间的交叉、变异,以较小运算量得到更优的进化结果;②基于扇形分割的选择算子,在选择存活种群的同时,兼顾种群均匀分布;③构建基于工序关键路径的邻域结构进行邻域搜索,增强全局搜索能力。
2.2 算法关键技术1) 分支种群
针对EDRCJSP中工序调度与资源配置2个子问题以及时间、成本2个优化目标，分别构造基于时间指标与基于成本指标的次序信息素τOOzPxyPij(z=1,2)和资源信息素τROzPijMkWl(z=1,2)共4种信息素。在每次进化前，通过(1)式所示的基于蚂蚁流量[9]的改进伪随机比例状态转移规则生成分支种群。
式中，τPxyOO1Pij和τPxyOO2Pij分别反映工序Pij紧接着Pxy被调度时，时间指标与成本指标的优劣情况；τPijRO1MkWl和τPijRO2MkWl表示工序Pij采用资源组合Mk-Wl加工的双目标期望；ηPijMkWl为采用该资源组合加工工序Pij时的启发式信息；nPxyPij和nPijMkWl分别表示该工序调度次序与该工艺路线在种群中出现的次数，以体现路径蚂蚁流量。BPGA算法在每次种群进化后，根据存活种群Palive与记录全局非劣解的伴随种群Ppareto，分别对4种信息素进行局部更新与全局更新。
2) 精英进化
根据文献[8]得到的结论：当至少一个调度指标优于种群均值的染色体经过交叉变异进化后，有较大几率得到非劣解，并对种群质量有明显优化。在此基础上，BPGA算法提出鼓励精英个体繁殖变异的精英进化算子：提取父辈种群中至少有一个调度指标超过种群目标均值的染色体，构成精英种群，仅对该种群与保存每次迭代非劣解的伴随种群进行下列进化操作；其余染色体直接进入子辈种群接受选择，以增强种群多样性。
(1) 精英交叉
筛选精英种群、伴随种群中双目标均超过种群均值的个体共同组成King种群，每个King染色体与其他所有King染色体以及任意2个非King精英染色体基于POX交叉算子[10]进行交叉进化。
(2) 精英变异
BPGA算法建立包含设备交叉、工人交叉、资源组合变异等资源变异算子[11]与互反变异、插入变异等工序变异算子在内的复合变异策略库。每个King染色体执行策略库中所有变异策略以增加得到非劣解的可能性；剩余的非King精英个体分别选择一种策略执行，避免算法早熟。
(3) 时间复杂度分析
对于每次迭代，假设进化种群、分支种群、非劣解集的数量分别为Nevo、Nant、Np。如采用全进化模式，其运算复杂度为：O(Nevo+2Nevo+4Nevo+8Nevo)=O(15Nevo)。根据Pareto支配关系定义，King种群规模约为0.25Nevo，非King精英种群规模约为0.5Nevo，则精英交叉进化的运算复杂度为O(Nant×0.5Nevo)+O(Nevo),精英变异过程中每个King染色体进行5种变异，运算复杂度为O(1.25Nevo)，非King精英个体仅执行一种变异，运算复杂度为O(0.5Nevo)。因此整个精英进化过程的运算复杂度为O(Nant×0.5Nevo+2.75Nevo),当Nant×0.5Nevo<12.25Nevo，即Nant<24.5时精英进化策略的运算复杂度小于全进化模式。
3) 基于扇形分割的轮盘赌选择算子
每个解在目标空间中表现为一个点，它与原点的连线和坐标横轴构成的夹角θ能够体现解在解空间内的分布。BPGA算法确定非劣伴随种群后，通过基于扇形分割的轮盘赌法，从存活种群中选择优秀且分布均匀的解共同构成进化种群，具体步骤为：①首先找到Cp或Td最优的2个极值个体；②分别用线连接2个极值点与原点，形成一个扇形解区域；③将该扇形区域按角度N等分；④依角度顺序从每个小扇形区域中选择一个解进入进化种群Pevolution，如该区域有多个解，则根据解离原点的距离，按轮盘赌方法进行选择，直至Pevolution规模达到N为止。
4) 邻域结构搜索
解邻域结构设计一直是邻域搜索的关键问题与难点所在，关键路径法是最常用的一种邻域结构生成方式，其中关键工序与关键路径的准确定位成为邻域搜索在JSP调度中取得显著优化效果的基础。潘全科等[12]指出：全局最优解是所有邻域结构的局部最优解，且一种邻域结构的局部最优解往往会在另一种邻域结构的局部最优解附近。Chu[13]提出交换关键工序块上的相邻工序不会影响调度方案的可行性。Nowicki[14]指出只有关键工序块的前2个或后2个相邻关键工序的交换能够优化调度时间指标。
由现有的研究结果可以看出，紧前关键工序的确定是邻域搜索的基础。例如，对于EDRCJSP调度中的某道工序，假定其紧前工序共有4种可能，以图 1为例：①在同一台设备上连续加工，工序“2-1-2”为“1-1-2”的紧前工序；②同一个工人连续加工，“3-1-3”为“1-1-3”的紧前工序；③同一批次的同一工件的2道紧邻工序，如“4-1-2”与“4-1-1”；④同一个工人在数控机床为某个任务上料后立即转移到其他设备上加工另一个任务，如“3-1-2”与“2-1-2”。
|
| 图 1 EDRCJSP调度方案示意图 |
借鉴上述基于关键路径的邻域结构搜索思想，BPGA算法在每次遗传进化后，均对每个非劣解所代表的调度方案从最后一道完成工序开始，按上述4个条件的优先顺序，从后向前寻找关键工序，据此可最终得到关键路径。可将其中由同一资源组合连续加工的多个关键工序称为双资源约束关键块，并据此设计下列3种邻域结构，共同构成邻域种群Pneighbour，与其他染色体共同参与进化选择。
1) 第1邻域：将随机关键工序的加工资源组合更换为效率最高或成本最低组合。
2) 第2邻域：将关键块的前两道工序或最后两道工序互换构成的所有邻域。
3) 第3邻域：如某个关键块中存在不同批次的同工序任务非连续加工，则将较晚开工的任务提前，实现工序合批加工。
3 仿真试验及分析 3.1 优化机制性能仿真分析本文基于文献[11]构造的EDRCJSP随机算例，采用文献[8]的评价指标，分别对分支种群等几种优化机制引入前后的数据进行分析，验证其优化效果。
1) 分支种群优化效果
鉴于可行解是一系列分布在解空间中的点集，时间指标、成本指标分别是其X、Y坐标，本文以
表征种群差异度，越小则种群差异性越小，其中Sx、Sy分别表示种群X、Y坐标的标准差。图 2所示分别为每次迭代时分支种群引入前后进化种群的值，可见引入分支种群有效增强了种群差异性，避免了早熟收敛现象，且使最终非劣解集更接近Pareto前沿，覆盖范围更广，如图 3所示。
|
| 图 2 分支种群对种群差异度的影响 |
|
| 图 3 有无分支种群的最终调度结果 |
2) 精英进化模式
本文在求解随机算例的每次迭代时，针对相同的父辈种群分别采用精英进化与全进化算子进行进化，并对比每次迭代时间及进化后非劣解集的${\bar{S}}$I、Arange、SΔA等性能指标。图 4的${\bar{S}}$I比较结果表明，精英进化所得非劣解集更接近Pareto前沿。但由于侧重于搜索优秀解区域，精英进化模式的全局搜索能力略逊于全进化模式，非劣解集覆盖范围在第100次迭代后略小于全进化模式，如图 5所示。
|
| 图 4 不同进化模式的非劣解集${\bar{S}}$I对比 |
|
| 图 5 不同进化模式的非劣解集Arange对比 |
|
| 图 6 不同进化模式的非劣解集SΔA对比 |
由图 6可见，精英进化算子偏重在优秀解空间的搜索，指标相对稳定，全进化模式则随着算法收敛有一个明显的 下降过程。图 7所示为使用2种进化模式的BPGA算法分别运算同一算例所得结果，全进化模式通过更大规模的运算，算法全局搜索能力更强，非劣解集覆盖范围更大，但最终解集在中间与两端区域分布较密集；精英进化模式的求解结果更趋近于Pareto前沿，虽然覆盖范围略小，但分布更为均匀。
|
| 图 7 不同模式的最终非劣解集对比 |
3) 基于扇形分割的轮盘赌选择算子
针对同一子辈种群，分别采取基于小生境的Pareto排序选择算子[15]和基于扇形分割的轮盘赌选择算子，各自选择规模为N的存活种群，并对比2个存活种群的${\bar{S}}$I、Arange、SΔA等指标，如图 8~图 11所示。Pareto排序选择需要在选择时兼顾解分布均匀程度，即使是Pareto级别较高的解也可能由于附近解密度过大而被淘汰，选择结果的稳定性较差，扇形分割选择则从算子结构层面决定被选种群的均匀分布特征，选择结果更接近Pareto前沿；解覆盖范围与解夹角偏差更是扇形分割选择算子的主要优化方向。由图 11的综合指标对比可见，扇形分割选择的结果明显占优。
|
| 图 8 不同选择算子的${\bar{S}}$I对比 |
|
| 图 9 不同选择算子的Arange对比 |
|
| 图 10 不同选择算子的SΔA对比 |
|
| 图 11 不同选择算子的混合指标对比 |
本文采用文献[8]中的DOIGAII算法和经典多目标进化算法NSGAII[16]作为对比算法，分别运算10组EDRCJSP随机算例20次，并比较结果均值的4种非劣性能评价指标，如表 1所示。
| 算例 | BPGA | DOIGAII | NSGAII | |||||||||
| ${\bar{S}}$I | Arange | SΔA | CH | ${\bar{S}}$I | Arange | SΔA | CH | ${\bar{S}}$I | Arange | SΔA | CH | |
| Pro1 | 0.005 | 21.59 | 49.21 | 1.14 | 0.007 | 7.85 | 48.38 | 4.31 | 0.039 | 54.22 | 53.25 | 3.83 |
| Pro2 | 0.003 | 36.74 | 47.69 | 0.39 | 0.015 | 9.43 | 50.85 | 8.09 | 0.047 | 61.50 | 51.00 | 3.90 |
| Pro3 | 0.013 | 23.56 | 15.83 | 0.87 | 0.024 | 63.83 | 14.51 | 0.55 | 0.200 | 30.51 | 22.56 | 14.79 |
| Pro4 | 0.012 | 44.58 | 36.75 | 0.99 | 0.003 | 34.42 | 62.63 | 0.55 | 0.044 | 52.59 | 53.89 | 4.51 |
| Pro5 | 0.008 | 29.37 | 40.56 | 1.10 | 0.010 | 12.82 | 39.75 | 3.10 | 0.044 | 35.12 | 61.13 | 7.66 |
| Pro6 | 0.004 | 38.30 | 85.32 | 0.89 | 0.009 | 13.11 | 79.88 | 5.48 | 0.053 | 16.22 | 76.65 | 25.05 |
| Pro7 | 0.024 | 69.07 | 6.69 | 0.23 | 0.061 | 55.31 | 6.85 | 0.76 | 0.150 | 47.49 | 8.43 | 2.66 |
| Pro8 | 0.016 | 20.91 | 59.61 | 4.56 | 0.004 | 15.70 | 69.68 | 1.78 | 0.122 | 36.73 | 42.53 | 14.13 |
| Pro9 | 0.011 | 24.33 | 39.72 | 1.80 | 0.012 | 34.74 | 37.12 | 1.28 | 0.037 | 45.09 | 58.50 | 4.80 |
| Pro10 | 0.008 | 20.93 | 43.84 | 1.68 | 0.008 | 16.50 | 65.25 | 3.16 | 0.041 | 42.74 | 56.25 | 5.40 |
DOIGAII算法与BPGA算法的 明显优于NSGAII算法，可见精英进化算子能显著优化BPGA算法的局部搜索能力；而BPGA的 除了算例4和8均优于DOIGAII算法，邻域搜索机制使搜索空间更加逼近Pareto前沿。NSGAII算法使用基于小生境技术的Pareto等级排序，侧重于搜索双目标极值区域，解覆盖范围最大；由于搜索非劣解邻域，BPGA算法的解搜索范围优于DOIGAII算法。但由于引入分支种群，种群多样性得到优化，非劣解集的分布均匀性由于扇形分割选择算子得到有效优化，因此DOIGAII算法与BPGA算法的解集分布更加均匀，且两者不相伯仲。对绝大部分算例，DOIGAII算法与BPGA算法的混合指标均优于NSGAII算法；相比DOIGAII算法，BPGA算法的不仅更优秀而且更加稳定。综上所述，虽然NSGAII算法搜索范围较广，但DOIGAII算法与BPGA算法的搜索范围更加逼近Pareto前沿，且由于精英进化算子与邻域搜索机制的引入，BPGA算法具有更为优秀的鲁棒性与全局搜索性能。
4 结 论本文旨在为EDRCJSP双目标调度优化问题的特点，在遗传算法基础上，通过引入分支种群、精英进化算子、基于被支配域的非劣解集快速优选算子、基于扇形分割的轮盘赌选择算子、邻域搜索等性能优化机制，构造一种BPGA算法。通过各种仿真对比实验，验证了各种优化机制在算法运算效率、局部搜索能力、解分布均匀程度等方面均能得到有效优化，并通过算法性能对比试验进一步验证了用BPGA算法求解EDRCJSP问题的有效性与可行性。
| [1] | Elmaraghy H, Patel V, Abdallah I B. Scheduling of Manufacturing Systems under Dual-Resource Constraints Using Genetic Algorithms[J]. Journal of Manufacturing Systems, 2000, 19(3): 186-201 |
| Click to display the text | |
| [2] |
周炳海, 蒋舒宇, 何平, 等. 基于双重资源的柔性生产系统调度算法[J]. 华南理工大学学报, 2008, 36(4): 45-49 Zhou Binghai, Jiang Shuyu, He Ping, et al. Scheduling Algorithm of Flexible Production System Based on Dual Resource[J]. Journal of South China University of Technology, 2008, 36(4): 45-49 (in Chinese) |
| Cited By in Cnki (9) | |
| [3] |
陶泽, 隋天中, 谢里阳,等. 基于Petri网和GASA的双资源JSP动态优化调度[J]. 东北大学学报, 2007, 28(3): 405-409 Tao Ze, Sui Tianzhong, Xie Liyang, et al. Dynamic Scheduling Optimization of Dual-Resource Based on Petri Net and GASA[J]. Journal of Northeastern University, 2007, 28(3): 405-409 (in Chinese) |
| Cited By in Cnki (26) | |
| [4] |
陈勇, 吴云翔, 王亚良. 订单不确定下双资源约束多装配线鲁棒调度[J]. 中国机械工程, 2014, 25(12): 1567-1573 Chen Yong, Wu Yunxiang, Wang Yaliang. Multi-Assembly Line Robust Scheduling of Double Resource Constrains under Uncertain Orders[J]. China Mechanical Engineering, 2014, 25(12): 1567-1573 (in Chinese) |
| Cited By in Cnki | |
| [5] | Araza U, Salum L. A Multi-Criteria Adaptive Control Scheme Based on Neural Networks and Fuzzy Inference for DRC Manufacturing Systems[J]. International Journal of Production Research, 2010, 48(1): 251-270 |
| Click to display the text | |
| [6] |
李兢尧,孙树栋,黄媛,等. 双资源约束作业车间调度算法研究[J]. 机械工程学报, 2010, 46(22): 175-181 Li Jingyao, Sun Shudong, Huang Yuan, et al. Algorithm for Dual Resource Constrained Job Shop Scheduling[J]. Journal of Mechanical Engineering, 2010, 46(22): 175-181 (in Chinese) |
| Cited By in Cnki (12) | |
| [7] |
李兢尧,孙树栋,黄媛,等. 求解双资源约束车间调度问题的继承式双目标遗传算法[J]. 控制与决策, 2011, 26(12): 1761-1767 Li Jingyao, Sun Shudong, Huang Yuan, et al. Double Objective Inherited Genetic Algorithm for Dual Resource Constrained Job Shop[J]. Control and Decision, 2011, 26(12): 1761-1767 (in Chinese) |
| Cited By in Cnki (6) | |
| [8] |
李兢尧,孙树栋,黄媛,等. 基于时窗的双资源约束车间调度研究[J]. 机械工程学报, 2011, 46(22): 150-159 Li Jingyao, Sun Shudong, Huang Yuan, et al. Research on Dual Resource Constrained Job Shop Scheduling Based on Time Window[J]. Journal of Mechanical Engineering, 2011, 46(22): 150-159 (in Chinese) |
| Cited By in Cnki (4) | |
| [9] |
李兢尧,孙树栋,黄媛,等. 基于自适应参数混合蚁群算法的双资源约束作业车间调度[J]. 西北工业大学学报, 2011, 29(1): 54-61 Li Jingyao, Sun Shudong, Huang Yuan, et al. Solving Dual Resource Constrained Job-Shop Scheduling Problem(DRCJSP) Based on Hybrid Ant Colony Algorithm with Self-Adaptive Parameters[J]. Journal of Northwestern Polytechnical University, 2011, 29(1): 54-61 (in Chinese) |
| Cited By in Cnki (5) | |
| [10] |
张超勇, 饶运清, 李培根. 柔性作业车间调度问题的两级遗传算法[J]. 机械工程学报, 2007, 43(4): 119-124 Zhang Chaoyong, Rao Yunqing, Li Peigen. Bilevel Genetic Algorithm for the Flexible Job-Shop Scheduling Problem[J]. Chinese Journal of Mechanical Engineering, 2007, 43(4): 119-124 (in Chinese) |
| Cited By in Cnki (119) | |
| [11] | Jingyao L, Shudong S, Yuan H. Dual Resource Constrained Job Shop Scheduling Based on Time Window[J]. Chinese Journal of Mechanical Engineering, 2011, 47(16): 150-159 |
| Click to display the text | |
| [12] |
潘全科, 王文宏, 朱剑英. 基于粒子群优化和变邻域搜索的混合调度算法[J]. 计算机集成制造系统, 2007, 13(2): 323-329 Pan Quanke, Wang Wenhong, Zhu Jianying. Hybrid Heuristics Based on Particle Swarm Optimization and Variable Neighborhood Search for Job Shop Scheduling[J]. Computer Integrated Manufacturing Systems, 2007, 13(2): 323-329 (in Chinese) |
| Cited By in Cnki (48) | |
| [13] | Chu C, Proth J M, Wang C. Improving Job Shop Schedules Through Critical Pairwise Exchanges[J]. International Journal of Production Research, 1998, 36(3): 683-694 |
| Click to display the text | |
| [14] | Nowicki E, Smutnicki C. A Fast Taboo Search Algorithm for the Job Shop Scheduling[J]. Management Science, 1996, 42(6): 797-813 |
| Click to display the text | |
| [15] | Doerner K, Gutjahr W, Hartl R, et al. Pareto Ant Colony Optimization: A Metaheuristic Approach to Multiobjective Portfolio Selection[J]. Annals of Operations Research, 2004, 131(1): 79-99 |
| Click to display the text | |
| [16] |
张勇德, 黄莎白. 多目标优化问题的蚁群算法研究[J]. 控制与决策, 2005, 20(2): 170-176 Zhang Yongde, Huang Shabai. On Ant Colony Algorithm for Solving Multiobjective Optimization Problems[J]. Control And Decision, 2005, 20(2): 170-176 (in Chinese) |
| Cited By in Cnki (7) |
2. School of Mechanical Engineering, Northwestern Polytechnical University, Xi'an 710072, China;
3. Institute of System Integrated and Engineering Management, Northwestern Polytechnical University, Xi'an 710072, China;
4. School of Computer, Northwestern Polytechnical University, Xi'an 710072, China
