求解多目标柔性作业车间调度问题的两阶段混合Pareto蚁群算法

赵博选,高建民,陈琨

(西安交通大学机械工程学院,710049,西安)



求解多目标柔性作业车间调度问题的两阶段混合Pareto蚁群算法

赵博选,高建民,陈琨

(西安交通大学机械工程学院,710049,西安)

针对多目标柔性作业车间调度问题(FJSP)分解得到的作业分派、排序子问题仍是多目标优化问题的情况,提出了一种求解该问题的分层Pareto优化框架,并采用该框架构建了两阶段混合Pareto蚁群算法的求解算法,其中两个Pareto蚁群系统分别求解多目标作业分派、排序问题。结合GT算法、排产规则评估和过滤第一阶段的分派方案,将具有较好评估全局解的分派方案作为分派阶段的精英档案,并输入给排序蚁群系统获取其非支配调度解,进而获取问题全局非支配解。子问题算法混合了各目标相关的邻域搜索策略,与Pareto蚁群算法结合,以期提高解的质量。通过求解带有平均工件加权延迟时间指标的多个FJSP基准算例,验证了算法的有效性。计算结果表明,该分层Pareto优化框架对原问题进行分层分解,有利于降低原问题的复杂性,相比多数文献,算法能够获得各基准算例Pareto非支配解,从而为分解求解复杂多目标调度优化问题提供了一种途径。

多目标柔性作业车间调度;分层Pareto优化;两阶段Pareto蚁群算法;邻域搜索

柔性作业车间调度问题(FJSP)是传统作业车间调度问题的扩展。在柔性作业车间调度问题中,每道工序的加工设备是不确定的。工件可以在多个可选择设备上加工,采用不同加工设备所需加工时间不同,且工件可能重复访问同一设备,设备不确定性和可重复访问性增加了FJSP调度优化的复杂性,使FJSP成为更加复杂的NP-hard问题。FJSP包含作业分派(OA)与排序(OS)两部分内容,其求解方法可分为集成求解和分层求解,集成求解同时考虑OA与OS的优化[1-4],分层求解根据两子问题的继承性分阶段优化,进而得到问题全局解,降低了问题复杂性[5-7]。

多目标FJSP求解方法分为加权和优化及Pareto优化两类。加权和优化采用已知权重将多目标优化转化为单目标优化[6-8],Pareto优化基于Pareto最优的思想获取问题解空间多样化、近优性的非支配前沿[9-10]。加权和优化可在各目标权重已知的情况快速得到问题部分解,但大多数车间生产内外部环境动态变化,Pareto优化为生产管理者提供数量较多的调度方案以供决策。

按照问题分解求解的思想,原问题被分解之后,子问题围绕与之相关的目标子集优化。例如,多目标FJSP分解之后的OA子问题根据问题本身性质,其目标子集包含总负荷与负荷均衡度等相关指标,而OS子问题目标子集包含完工周期与交付性相关指标,故多目标FJSP分解之后得到两个多目标优化子问题。当分层求解方法面对两阶段均属于多目标优化问题时,除构建子问题求解算法外,如何选取前者解集进入后者求解算法是该问题的关键。分层加权和求解方法可采用加权和方式对前者结果进行评估,选择最优结果进入后者,但分层Pareto求解方法却不能简单将前者非支配解集提交给后者求解算法。

本文结合分层求解和Pareto优化方法,研究求解多目标FJSP的分层Pareto求解方法,构建两阶段混合Pareto蚁群算法求解柔性作业车间调度问题。Pareto蚁群算法混合各目标相关的邻域搜索算法,实现二者协同进化。

1 FJSP描述

记J={Ji,1≤i≤n}为调度工件集合,工件序号为i;每个工件Ji包含ni道工序,工序顺序预先确定,工件Ji的第j道工序可以表示为Oij;工件具有不同的权重系数ωi和交货期di。记M={Mk,1≤k≤m}为加工设备集合,设备序号为k;可以加工工序Oij的设备集合为Mij⊆M,工序Oij在Mk上加工,不可中断,且加工时间为tijk。

要求为每个工件的工序选择合适的加工设备并确定各设备上的工序加工顺序及开始加工时间,同时满足各工件的加工工艺等约束条件,实现多个调度性能指标最优。

考虑最大完工时间最小、总负荷最小、最大设备负荷最小和平均工件加权延迟时间最小4种性能指标,即

(1)

(2)

(3)

(4)

决策变量

(5)

(6)

约束条件

(7)

∀1≤i≤n, 1≤j≤ni, 1≤i′≤n, 1≤j′≤n,

(8)

(9)

(10)

2 一种两阶段Pareto优化算法框架

由于设备的非等效性、工艺的多样性以及设备可重入性,FJSP分解之后的OA与OS子问题两者解空间的非支配性不具备继承性,即OA子问题的非支配前沿分派解经过OS子问题优化后不一定是OS子问题的非支配前沿调度解,且OS子问题的非支配前沿调度解不一定是由OA子问题的非支配前沿分派解得来,所以不能简单保留OA子问题的非支配前沿解作为第1阶段的优化结果。分层求解方法需要对前者子问题的求解结果进行评估和优选,一方面尽可能过滤较差分派解进入第2阶段,另一方面不能丢失问题最优解对应的分派解。采用启发式规则排产算法快速构建分派方案的优秀调度解,得到分派解的全局目标值参与评估和优选,最终选择评估后具有较优全局目标值的分派解作为第1阶段的优化结果。

通过大量仿真实验提出分层Pareto优化算法框架前,总结2个改进措施:①子问题1优化一定次数后,使其较优解处于较稳定时才进行评估和优选,有利于降低评估与优选操作运行次数,根据非支配关系,子问题1的非支配解集一定是问题全局解(所有目标集合)的非支配解集;②评估和优选之后的较优解暂时保留在第1阶段精英档案中,每次评估和优选之后更新该精英档案,等第1阶段优化完毕后,将该精英档案输出给第2阶段进行搜索。这样可大量过滤算法运行过程中的较差分派解,且将两子问题之间的嵌套关系改成并列关系,有利于减少算法运行时间。求解多目标FJSP的分层Pareto优化算法框架如图1所示。

图1 分层Pareto优化算法框架

3 两阶段混合Pareto蚁群算法

3.1 FJSP析取图描述

为了应用蚁群算法,FJSP问题用析取图表示为D=(O,A,B),其中O为节点集合,A为连接弧集合,B为析取弧集合。开始节点OS和结束节点OE分别用于连接各工件的首尾工序;有向弧表示各工件的工艺路线,连接具有顺序约束的工序节点;析取弧表示不同工件之间可能工序的顺序关系,以待确定;同一工序的不同可选设备节点之间不存在析取弧。与JSSP问题不同的是,该析取图将可选设备添加在工序节点中,且不是所有的节点都要被遍历,调度结果只是所有节点的部分连接图。同一工序的设备节点具有互斥关系,当某工序节点的加工设备确定,该工序的其他设备节点即被舍弃。每个节点被表述为(Oi,j,Mk),表示工件的第j道工序在设备k上加工,4个工件的析取图描述如图2所示。多目标蚁群算法会得到多个加工路径,这些加工路径对应的解在解空间具有非支配性。

图2 FJSP问题析取图描述示例

3.2 两阶段混合Pareto蚁群系统构建

详细的Pareto蚁群算法关键操作可参考文献[11-12]。OA蚁群系统根据信息素与启发式信息确定各工序操作的加工设备,每只蚂蚁遍历路径前随机排列所有工序,并保证工艺可行性,如图3所示。

图3 父代蚁群系统搜索示例

给定x为工序总数,y为设备总数,信息素矩阵构建为[τv,k]x×y,工序设备节点总负荷相关启发式信息为其加工时间的倒数,工序设备节点负荷偏差相关启发式信息为该设备已分配负荷的倒数。为使分母不为0,预先给每个设备预设合适的已分配负荷初始值。

图5 基于关键路径及公共关键块的完工周期相关邻域搜索操作示意图

如图4所示,OS蚁群系统通过遍历所有工序操作节点来构建分派方案调度解,考虑到优化目标的正则性,本文结合GT算法[10]来缩小搜索范围,减少算法搜索时间。具体流程为:①添加各工件首工序至可选工序任务集合,并计算集合中各工序操作最早可能开工与完工时间;②找出任务集合中工序操作最早可能完工时间和分派设备;③找出任务集合中分派在设备上最早可能开工时间小于完工时间的工序操作,形成冲突工序操作集合;④根据蚁群启发式策略从操作集合中选择一个工序安排,从任务集合中剔除该工序,如果该工序不是工件末工序,添加其下一工序操作至任务集合;⑤更新任务集合中受影响工序操作最早可能开工与完工时间,如果任务集合为空,停止,否则返回至流程②。

图4 OS蚁群系统搜索示例

完工周期相关启发式信息为该弧段后工序任务加工时间的倒数;交付性相关启发式信息为该弧段后工序任务分解交付期的倒数。计算各工件工序操作的分解交付期,即

(11)

3.3 邻域搜索策略

单目标优化问题中,当邻域搜索解较优时代替初始解,而在多目标优化问题中,若邻域搜索得到的解与原先解比较具有非支配性时,将该邻域搜索解保存于缓冲池中。当所有邻域搜索执行完毕后,从缓冲池取出非支配解,更新原始档案。由于各目标的互斥性,本文提出与各目标相关的邻域搜索策略,每次邻域搜索以期某个目标相比之前更优,邻域搜索策略如下。

(1)总负荷目标相关的邻域搜索。找到分派工序数目最多的设备,随机选择该设备上某一工序,改派至其他较小加工时间可选设备上。

(2)最大设备负荷目标相关的邻域搜索。按照已分派负荷对设备排序,随机选择最大负荷设备上工序操作分派在其他较小负荷可选设备上。

(3)完工周期目标相关的邻域搜索。要想缩短完工周期,邻域搜索只有通过移动关键路径上的工序才可能减少最大完工时间,而当调度方案含有多条关键路径时,只有基于公共关键块的邻域结构才会有助于缩短完工周期。本文基于公共关键块采用以下邻域结构:块首工序插入到块内工序之后;块尾工序插入到块内工序之前;块内工序插入到块首之前;块内工序插入到块内之后;块首或块尾两工序交换。图5归纳了基于关键路径及公共关键块的完工周期相关邻域搜索策略所包含的操作。

(4)加权延迟时间相关邻域搜索。文献[4]介绍了一种交换式交付期相关邻域搜索策略,先比较工件完工时间与交货期,将其分为提前类和延迟类,逐个设备寻找相邻工序满足前工序属于提前类、后工序属于延迟类的两相邻工序,然后交换它们。

3.4 两阶段混合Pareto蚁群算法流程

在OA、OS Pareto蚁群系统中,每次迭代得到的所有蚂蚁解经历了新信息素矩阵和随机权重的引导,新的蚂蚁解对档案的补充增加了档案解的多样性,而邻域搜索可进一步提高解的质量。在OS蚁群系统中对精英档案EA_OS进行邻域搜索,而在OA蚁群系统中对所有蚂蚁新解和精英档案EA_OA进行邻域搜索,用所有新解更新EA_OA和最优新分派解档案Best_OA_New,Best_OA_New为多次迭代之后需要评估的分派解档案。

本文采用算法迭代达到预定最大次数、非支配解集不再变化达到预定次数两种算法为终止条件,算法详细流程如图6、7所示。

图6 OA蚁群系统算法流程

3.5 OA分派解评估与优选

本文结合GT算法与多种排产规则为分派解构建可行调度方案,评估完工周期与平均加权延迟时间指标。排产规则包括随机选择规则,最早完工时间优先,最早操作分解交货期优先,最多工作量剩余优先,最多操作数目剩余优先。按照事先设计好的概率分配,选取排产规则确定GT算法中冲突工序顺序,得到该分派方案的调度解参与评估,当出现多种可选状况时采用随机选择规则辅助选择。对各个新分派解按照以上方法构建多个可行调度解(本文设定为30),与分派解子目标集联合,并添加至分派解全局精英档案gEA_OA,根据支配关系从gEA_OA中保留一定数量较优分派方案,实现gEA_OA档案更新,在该档案中一个分派解可能对应多个非支配全局精英解。

4 算例分析

为证实算法的有效性,本文应用该算法求解了带有平均加权延迟时间指标的多组基准算例,分别为Kacem8×8算例、10×7算例、10×10算例和15×10算例,工件交付期信息如表1所示,其中时间为无量纲单位时间。算法参数:前3个算例蚂蚁数目P=20,蚂蚁信息素初值τ0=1;15×10算例蚂蚁数目P=30,τ0=0.1,挥发系数ξ=0.1,全局释放系数ρ=0.1,信息素权重因子α=1,启发性知识权重因子β=1,伪随机概率q0=0.6。仿真实验表明,该参数组合能使两阶段Pareto蚁群算法在禁用邻域搜索操作时得到较好质量的问题解集。

图7 OS蚁群系统算法

分派阶段的全局精英档案gEA_OA的规模会影响算法整体运行时间。根据试验数据,问题Pareto非支配前沿对应的分派解主要属于分派解全局精英档案gEA_OA的前几个非支配等级,说明了评估和优选的有效性,根据该特征、结合问题规模,可控制该档案的规模。本文前3个算例设置的gEA_OA档案规模为30,15×10算例设置的gEA_OA档案规模为40。按照以上设置,将算法运行10次,对各算例的运行时间(均值/方差)分别为152/28.3,162/23.7,168/31.2,445/34.8 s。编程语言为Matlab2010,运行环境为CPU i3-2120,主频为-3.30～3.30 GHz,内存为4 GB。表2给出了附加平均工件加权延迟时间指标的Pareto最优解,粗体字符表示从文献[3-4,6-10]获取的Pareto非支配解。

5 结 论

多目标问题分解得到的子问题往往也是多目标优化问题,本文尝试求解多目标FJSP的两阶段Pareto优化方法,构建了两阶段混合Pareto蚁群算法,Pareto蚁群系统分别求解多目标作业分派和排序问题。评估操作快速对分派解进行评估,并保留具有较好评估全局解的分派方案作为分派问题的精英档案,将精英档案输入给排序蚁群系统以获取非支配调度解,最终获取问题全局非支配前沿。子问题算法混合了与各目标相关的邻域搜索策略,以提高问题解的质量。通过求解多个基准算例,算法可以获取现有文献各算例给出的非支配解,从而验证了该求解方法的有效性。本文为多目标优化问题的分层Pareto优化方法提供了一种途径,未来将继续改进算法,并尝试应用该算法求解实际调度问题。

表1 工件交付期

表2 附加平均工件加权延迟时间的部分Pareto最优解

[1] 莫建麟, 吴喆. 基于混合遗传禁忌的多目标柔性作业车间调度 [J]. 重庆师范大学学报(自然科学版), 2013, 30(2): 87-91. MO Jianlin, WU Zhe. Multi-objective flexible job shop scheduling based on hybrid genetic & tabu algorithm [J]. Journal of Chongqing Normal University (Natural Science), 2013, 30(2): 87-91.

[2] 张超勇, 董星, 王晓娟, 等. 基于改进非支配排序遗传算法的多目标柔性作业车间调度 [J]. 机械工程学报, 2010, 46(11): 156-164. ZHANG Chaoyong, DONG Xing, WANG Xiaojuan, et al. Improved NSGA-II for the multi-objective flexible job-shop scheduling problem [J]. Journal of Mechanical Engineering, 2010, 46(11): 156-164.

[3] MOSLEHI G, MAHNAM M. A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search [J]. International Journal of Production Economics, 2011, 129(1): 14-22.

[4] GAO K Z, SUGANTHAN P N, PAN Q K. Pareto-based grouping discrete harmony search algorithm for multi-objective flexible job shop scheduling [J]. Information Sciences, 2014, 289(1): 76-79.

[5] 张洁, 张朋, 刘国宝. 基于两阶段蚁群算法的带非等效并行机的作业车间调度 [J]. 机械工程学报, 2013, 49(6): 136-144. ZHANG Jie, ZHANG Peng, LIU Guobao. Two-stage ant colony algorithm based job shop scheduling with unrelated parallel machines [J]. Journal of Mechanical Engineering, 2013, 49(6): 136-144.

[6] XING Lining, CHEN Yingwu. An efficient search method for multi-objective flexible job shop scheduling problems [J]. Journal of Intelligent Manufacturing, 2009, 20(3): 283-293.

[7] XING Lining, CHEN Yingwu. Multi-objective flexible job shop schedule: design and evaluation by simulation modeling [J]. Applied Soft Computing, 2009, 9(1): 362-376.

[8] XIA Weijun, WU Zhiming. An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems [J]. Computers & Industrial Engineering, 2005, 48(2): 409-425.

[9] LI Junqing, PAN Q, LIANG Y C. An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems [J]. Computers & Industrial Engineering, 2010, 59(4): 647-662.

[10]CHIANG T C, LIN H J. A simple and effective evolutionary algorithm for multi-objective flexible job shop scheduling [J]. International Journal of Production Economics, 2013, 141(1): 87-98.

[11]GARCIA-MARTINEZ C, CORDON O, HERRERA F. A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for the bi-criteria TSP [J]. European Journal of Operational Research, 2007, 180(1): 116-148.

[12]DOERNER K, GUTJAHR W J. Pareto ant colony optimization: a meta-heuristic approach to multi-objective portfolio selection [J]. Annals of Operations Research, 2004, 131(1): 79-99.

[本刊相关文献链接]

刘岳镭,冯祖仁,任晓栋.具有恶化效应的双代理单机最优调度算法.2016,50(6):9-14.[doi:10.7652/xjtuxb201606002]

陈鹏飞,李昕怡,齐勇,等.单步启发式策略的备份虚拟机复用策略.2016,50(1):100-107.[doi:10.7652/xjtuxb201601 016]

杨鹏飞,王泉.片上网络异构多核系统任务调度与映射.2015,49(6):72-76.[doi:10.7652/xjtuxb201506012]

王丽霞,曲桦,赵季红,等.软件定义网络中应用二值粒子群优化的控制器部署策略.2015,49(6):67-71.[doi:10.7652/xjtuxb201506011]

周光辉,苗发祥,李彦广.数控加工中心任务与刀具集成调度模型及改进自适应遗传算法.2014,48(12):1-7.[doi:10.7652/xjtuxb201412001]

邵成成,王锡凡,王秀丽,等.主动配电系统与主网的有功协调.2014,48(11):58-63.[doi:10.7652/xjtuxb201411010]

李彬,宋立明,李军,等.长叶片透平级多学科多目标优化设计.2014,48(1):1-6.[doi:10.7652/xjtuxb201401001]

(编辑 赵炜 杜秀杰)

Two-Stage Hybrid Pareto Ant Colony Algorithm for Multi-Objective Flexible Job Shop Scheduling

ZHAO Boxuan,GAO Jianmin,CHEN Kun

(School of Mechanical Engineering, Xi’an Jiaotong University, Xi’an 710049, China)

Multi-objective flexible job shop scheduling can be divided into two sub-problems, namely job assignment and sorting, which are often multi-objective optimization problems. Aiming at this situation, this paper presents a layered Pareto optimization frame for multi-objective flexible job shop problem and proposes a two-stage hybrid Pareto ant colony algorithm for multi-objective operation assignment (OA) and operation sequencing (OS) sub-problems. Embedding multiple scheduling rules in GT algorithm is used to evaluate and filter the assignment solutions. The global optimal non-dominated front of the original problem is obtained by scheduling optimization as the elite archive of assignments. Each Pareto ant colony algorithm is combined with the neighborhood search strategies related to different objectives. The co-evolutionary can obtain high-quality solutions to multi-objective FJSP. Finally, by solving four benchmark instances considering minimizing the mean weighted tardiness time, the effectiveness of the method is testified. The simulation results show that the layered Pareto optimization frame helps to reduce complexity of the problem, and compared with other literatures, the proposed algorithm can obtain the Pareto non-dominant solutions of each instance, providing a new way for solving complex multi-objective scheduling problems.

multi-objective flexible job shop scheduling; layered Pareto optimization; two-stage Pareto ant colony algorithm; neighborhood search

2015-11-23。 作者简介:赵博选(1986—),男,博士生;高建民(通信作者),男,教授,博士生导师。 基金项目:国家科技重大专项资助项目(2012ZX04010-071)。

时间:2016-05-24

10.7652/xjtuxb201607022

F406.2

A

0253-987X(2016)07-0145-07

网络出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20160524.1204.002.html