多阶段可替换分组并行机调度问题的求解

苗 峰,谢安桓,王富安,喻 峰,周 华

（1.浙江大学流体动力与机电系统国家重点实验室,浙江杭州310027；2.中国船舶重工集团第七○七研究所九江分部,江西九江332007）

多阶段可替换分组并行机调度问题的求解

苗 峰1,谢安桓1,王富安2,喻 峰2,周 华1

（1.浙江大学流体动力与机电系统国家重点实验室,浙江杭州310027；2.中国船舶重工集团第七○七研究所九江分部,江西九江332007）

针对一类多阶段可替换分组并行机混流生产调度问题,以最小化最大完工时间为目标建立问题的数学模型,提出一种嵌入混合启发规则的遗传算法,采用分段独立编码的染色体和改进的遗传算子.依靠遗传算法的全局搜索能力确定启发规则的最优决策变量,根据决策变量采用包含多种规则的混合规则确定各阶段调度方案；同时解决了调度问题的路径选择子问题和加工排序子问题,调度方案自动满足模型约束.算法求解速度快,求解结果具有较高的负荷平衡率.针对不同规模的算例,仿真验证了算法的有效性,仿真结果表明该算法的综合性能指标优于嵌入单一启发规则的遗传算法.

并行多机调度；启发式算法；遗传算法

生产调度是企业生产管理过程的重要环节,目前学者的研究重点转向实际生产中常见的带有特殊工艺、设备约束的多机混流生产调度问题［1-3］.Gupta［4］证明即使对于2阶段并行机调度,以最小化最大完工时间为目标的问题已经是NP-Hard问题；Oguz等［5-6］研究了工位数分别为2和1的2阶段工位可替换混流调度问题,但认为替换工位不影响加工效率；赵月等［7］研究了包含批调度工序的3阶段并行机调度问题,利用混合禁忌搜索算法求解,但认为并行机完全等同,工件无分组约束；张洁等［8］针对多阶段带非等效并行机的调度问题设计了2阶段蚁群算法进行双目标优化,考虑了任务优先级及交货期约束,但求解模型不存在有批处理设备约束的工艺阶段.

综上,多阶段并行机调度问题是作业车间调度问题和并行机调度问题的混合,目前学者的研究多认为同阶段并行机完全等同,且没有同时考虑包含工件分组、非等同替换机、批调度工序等多因素的多阶段并行机调度问题的研究,而此类问题在电子、电器、机械等行业的实际混流生产中大量存在.

本文从过滤器混流生产线的生产实际出发,描述了一类多阶段可替换分组并行机混流生产调度问题,包含多个生产阶段,各阶段均有分组并行机,且包含非等同可替换工位组和批调度工序.以最小化最大完工时间为目标建立了问题的数学模型,设计了一种嵌入混合启发规则的遗传算法对问题进行求解,通过算例验证了算法的有效性.

1 问题描述

有n种工件待生产,每个工件均要经过装配、试验、二次装配3个工序,由于试验工序的安装和拆卸时间不能忽略,将试验工序划分为安装、试验、拆卸3个阶段.约定装配、安装、试验、拆卸、二次装配阶段的编号为k（k＝1,2,…,5）,所有工件均要依次经过以上5个阶段.由于不同种类工件工艺及试验设备的限制,将工件种类分配为2个装配组集合O1、O2和2个试验组集合Q1、Q2.

对于装配和二次装配阶段k（k＝1,5）：工位集合记为Mk＝MkO1∪MkO2,MkO1、MkO2分别为装配组O1、O2的工位集合,MkO1＝｛MkO1j｜j＝1,…, mkO1｝,MkO2＝｛MkO2j｜j＝1,…,mkO2｝,mkO1、mkO2为工位个数.O1种类工件初始分配给MkO1,O2种类工件初始分配给MkO2.MkO1、MkO2互为可替换工位组,替换工位能够完成异组工件的操作,但由于工具、工艺的差异,替换操作降低工作效率.

对于试验工序3个阶段k（k＝2,3,4）：工位（工人）集合记为Mk＝MkQ1∪MkQ2,MkQ1、MkQ2分别为2个试验组Q1、Q2的工位（工人）集合,MkQ1＝｛MkQ1j｜j＝1,…,mkQ1｝,MkQ2＝｛MkQ2j｜j＝1,…, mkQ2｝,mkQ1、mkQ2为工位（工人）个数.由于工艺和设备约束,Q1种类工件只能分配给MkQ1,Q2种类工件只能分配给MkQ2,即MkQ1、MkQ2不可替换；安装（k＝2）和拆卸（k＝4）阶段共用工人,即M2Q1＝M4Q1,M2Q2＝M4Q2,显然M2＝M4；安装（k＝2）和拆卸（k＝4）阶段由工人M2（M4）占用工位M3进行操作；同组工件试验（k＝3）分批进行,同批工件全部完成安装后,各工位才能同时开始试验,且必须同时结束,然后各自拆卸,即试验（k＝3）阶段为批调度.

有以下已知参数：第i（i＝1,2,…,n）种工件在k（k＝1,5）阶段的初始分配组、替换组操作时间为（tpki,tki）,其中tpki＜tki；k（k＝2,3,4）阶段时间为tpki；每种工件的需求个数为Ni（i＝1,2,…,n）,待调度工件总数为

2 数学模型

tSijk表示第i种第j个工件第k阶段的开始时间,tCijk表示第i种第j个工件第k阶段的结束时间,gijkl＝1表示第i种第j个工件第k阶段分配给编号为l（l∈MC）的工位,否则gijkl＝0.

决策变量为各工件在各阶段工位的分配结果和操作顺序,即各工件在每阶段的分配结果gijkl、开始时间tSijk、结束时间tCijk,求解目标为最小化最大完工时间.

对于多阶段并行机调度问题,最大完工时间tmax等于所有工件各阶段完工时间的最大值,即

定义Wl表示所有分配给编号为l的工位（工人）的操作集合,即

本文求解的数学模型如下.

式（3）为目标函数,即最小化最大完工时间；式（4）～（5）为每种工件的分组唯一性约束；式（6）为工序的先后顺序约束；式（7）为操作时间约束；式（8）为每阶段分配结果的唯一性约束；式（9）为同一工位（工人）在同一时刻处理工件的唯一性约束；式（10）-（11）为每阶段分配结果的区域和设备分组约束；式（12）为决策变量取值约束.

3 混合启发规则

基于第2节的模型,根据生产实际提出以下假设：

1）所有工件和工位（工人）在0时刻均可用,模型中5个阶段的操作时间均包含工件的准备时间；

2）相邻加工阶段间有足够的缓冲区,工件加工完成后不允许继续占用工位,要在缓冲区中等待；

3）加工过程一旦开始,不允许中断,工位（工人）在整个过程中无故障；

4）试验阶段（k＝3）,只要剩余工件足够,每批必须将本组试验工位装满；

5）试验阶段（k＝3）同批工件的开始时间为本批最后一个工件的安装（k＝2）完成时间,上一批所有工件拆卸（k＝4）完成前不允许新一批工件安装.

多阶段调度问题需解决路径选择子问题和加工排序子问题［9］.路径选择子问题即确定工件在各个阶段的操作工位（工人）；加工排序子问题即确定分配给同一工位（工人）的所有工件的加工顺序.本节采用混合启发规则同时解决2个子问题,使用的调度规则的含义如下：

1）最早可用机器优先原则（first available machine,FAM）,在选择工位（工人）时,分配给可用时间最早的工位（工人）,以减小等待时间；

2）最短加工时间机器优先原则（shortest processing machine,SPM）,在选择工位（工人）时,分配给处理该工序所用时间最短的工位（工人）,以减少人力成本,提高效率；

3）最小负荷工位优先原则（least load machine,LLM）,在选择工位（工人）时,分配给已承担负荷最小的工位（工人）,以提高负荷平衡率；

4）Random规则,在选择工位（工人）时,随机分配.

对于装配和二次装配阶段k（k＝1,5）,定义替换延迟因子Rk∈R＋辅助决策.工件到达时,确定初始分配组的最早可用工位G及其可用时间tG,确定替换组的最早可用工位及其可用时间t,分以下3种情况：

情况1 tG≤t：则依据FAM规则,将工件分配给G.

情况2 tG＞t且tG－t≤Rktpki：则依据SPM规则,将工件分配给G.

情况3 tG＞t且tG－t＞Rktpki：则依据FAM规则,将工件分配给.

等待和替换操作虽然会延长单个工件的本阶段通过时间,但可能同时减少后续工位和后续工件的等待时间,使整个调度完成时间缩短,因此Rk直接影响工位的分配结果和任务的总完成时间.

可以看出,当Rk＝0（k＝1,5）时,以上3种情况退化为单一FAM规则；当Rk＝＋∞（k＝1,5）时,以上3种情况退化为单一SPM规则.

对于试验工序3个阶段k（k＝2,3,4）,由于不存在替换组,工件到达时依据单一FAM规则分配给最早可用工位G.

另外,对所有阶段k（k＝1,2,…,5）,若存在多个可用时间相同的最早可用工位（工人）,依据LLM规则将工件分配给当前负荷最小的工位（工人）；若多个最早可用工位（工人）当前负荷相同,依据Random规则随机分配给其中之一.

运用以上混合启发规则的步骤如下：

步骤1 将所有工件排成序列D1,作为第1阶段的投产序列,排在前面的工件优先投产.

步骤2 根据D1逐个提取工件,按照调度规则分配给工位集M1.O1种类的工件完成装配（k＝1）记为事件集E11,O2种类的工件完成装配（k＝1）记为事件集E12.分别将E11和E12按事件发生时间升序排列,对应工件顺序作为第2阶段投产序列D21和D22.

步骤3 根据D2h顺序提取m3Qh个工件,按照调度规则分配给工人集M2Qh占用工位集M3Qh进行安装（k＝2）；更新本批工件试验（k＝3）开始时间和结束时间；对本批工件按照调度规则分配工人集M4Qh进行拆卸（k＝4）；将本批工件完成拆卸（k＝4）记入事件集E4Qh.其中：h＝1,2.

步骤4 重复步骤3直到所有工件完成安装（k＝2）、试验（k＝3）、拆卸（k＝4）；所有工件完成拆卸（k＝4）记为事件集E4＝E4Q1∪E4Q2.

步骤5 将E4按事件发生时间升序排列,对应工件顺序作为第5阶段投产序列D5.

步骤6 按D5顺序逐个提取工件,按照调度规则分配给工位集M5,得到最终调度结果.

混合启发规则根据工件前一阶段的完成顺序,使用Rk（k＝1,5）决策变量,采用包含FAM、SPM、LLM、Random的混合规则确定下一阶段的调度方案；同时解决了路径选择子问题和加工排序子问题,调度结果自动满足模型约束.

4 嵌入混合启发规则的遗传算法

第3节的混合启发规则可以得到较优的调度方案,规则中第1阶段的投产序列D1和替换延迟因子Rk为决策参数,直接决定了调度结果；对于不同调度对象,无法根据经验确定合适的D1和Rk.本节利用遗传算法的全局搜索能力确定D1和Rk（k＝1,5）,设计一种嵌入混合启发规则的遗传算法.

4.1 编码与解码

4.2 适应度函数

遗传算法通过适应度函数来评估个体性能并指导搜索,性能不良的适应度函数往往导致“欺骗现象”［10］,本文的求解目标为最小化最大完工时间,由于采用混合启发规则,解码容易得到目标值差异不大的一组较优解,若直接采用最大完工时间的倒数作为适应度值,容易陷入局部最优而停止继续优化.

寻找种群中最优个体的完成时间tmin,对每个个体的完成时间tP作标定,合理的放大适应度值之间的差距,提高算法的选择和搜索能力,适应度函数如下：

4.3 选择算子

根据个体的适应度值计算其累计选择概率,采用保留最优个体的轮盘赌方法选择个体遗传给子代,保证了算法的收敛性.

4.4 交叉算子

由于染色体3部分的编码方式和含义不同,3部分独立进行交叉操作.

第1部分：已知n种工件的需求向量为［N1,N2,…,Nn］.为保证交叉得到的子代满足工件种类和个数约束,基于线性顺序交叉算子（linear order crossover,LOX）算子［11］,设计一种改进的线性顺序交叉算子（modified linear order crossover, MLOX）.

例如：对于n＝4,工件需求向量为［2,1,3, 2］的问题,假设父代染色体第1部分为P1＝［1,3, 2,3,1,3,4,4］,P2＝［2,4,3,1,4,3,3,1］,运用MLOX算子的过程如图1所示：

第2和第3部分：使用两点交叉算子分别进行交叉.即随机选取2个交叉位置,交换父代染色体两交叉位置之间的片段,其余基因不变,得到子代染色体.

4.5 变异算子

首先,产生新的随机染色体代替选择和交叉得到的子代中重复出现的个体,减弱优势个体对进化方向的控制程度,增强算法的搜索能力.

然后,染色体3部分独立变异：第1部分采用改进的互换变异算子,即随机选取2个变异位置,如果两位置基因相同则重新选取,直至得到2个不同值的基因位置,交换两位置基因；第2和第3部分采用互斥变异算子,即随机选取一个变异位置,将基因值进行0-1互斥替换.

图1 改进的线性顺序交叉算子示意图Fig.1 Schematic diagram of MLOX operator

4.6 初始种群与停止准则

初始种群采用随机方式生成,染色体第1部分采用所有工件的随机全排列,第2和第3部分每一位在中随机选取.

以预先设定的最大繁殖代数为停止准则.

5 算例分析

表1 生产线配置Tab.1 Production line configuration

表2 工件工艺参数Tab.2 Process parameters of productions

首先,计算需求向量为［2,5,4,6,3］共计20件的算例验证算法有效性.设定种群规模p＝30,交叉概率pc＝0.8,变异概率pm＝0.1,最大代数为100；运用本文算法得到的最优解的完成时间为142.5,最优解第一阶段投产序列D1＝［4,2,4,4,4,4,4,2,3,3, 5,5,1,5,3,2,3,1,2,2］,分阶段甘特图如图2所示,图中调度块中间的字符i-j表示种类为i的第j个工件,时间块下方的数字表示本操作的持续时间.

图2 最优调度甘特图Fig.2 Gantt diagram of optimal solution

为进一步验证算法性能,针对不同规模的算例用本文算法与以下2种算法进行比较：

1）SPM＆GA算法：嵌入单一SPM规则的遗传算法.

2）FAM＆GA算法：嵌入单一FAM规则的遗传算法.

以上2种算法采用D1作为染色体,随机生成初始种群,选择算子采用保留最优个体的轮盘赌算子,交叉算子采用MLOX算子.

表3 算例参数Tab.3 Parameters of examples

算例计算结果对比见表4：表中：tRmin为10次计算最大完成时间最小值,为10次计算的完成时间的平均值,tRmax为10次计算最大完成时间最大值,Ns为10次计算最大完成时间中小于本文算法10次完成时间平均值的个数,较大的Ns表明算法获得较优解的概率高,更稳定有效,¯s为10次计算结果的每阶段同组工位负荷的平均标准差的平均值,较小的表明调度方案具有较高的工位负荷平衡率.

从表4中可以看出,由于遗传算法在有限代数内优化结果的随机性以及不同求解问题对不同调度规则的适应性差异,算例2中出现本文算法平均指标和较优解比例等指标略差于FAM＆GA算法的情况,但随着求解问题规模的扩大,本文算法在最优指标tRmin、平均指标、最劣指标tRmax和较优解的比例Ns等指标上表现出明显的优势.

综上,本文算法能够获得较小的最大完成时间且具有较高的同组工位平衡率,计算量小,求解效果稳定,能够有效解决不同规模多阶段多组可替换并行机的调度问题.大量算例仿真证明,本文算法对交叉概率pc、变异概率pm等遗传算法参数的变化不敏感,易于应用于实际生产调度.

6 结 语

表4 算例计算结果Tab.4 Calculation results of examples

针对一类多阶段可替换分组并行机混流生产调度问题,以最小化最大完工时间为优化目标建立问题的数学模型,提出一种嵌入混合启发规则的遗传算法对问题进行求解.采用混合启发规则的决策变量分段组成染色体,利用遗传算法确定最优决策变量的值,应用混合启发规则解码得到调度方案.大量算例表明算法能够获得很好的优化结果,且调度结果具备较高的工位平衡率,比较表明本文算法求解结果明显优于嵌入单一启发规则的遗传算法.

本文仅考虑了最小化最大完工时间的单目标优化,值得进一步针对多阶段可替换分组并行机调度的多目标优化研究如何构造相应的适应度函数；另外,本文算法只考虑了同阶段同组工人负荷平衡,针对全生产线工位的负荷平衡,实现不同调度任务的工位数量动态配置具有进一步的研究价值.

（References）：

［1］刘志雄,王少梅.基于粒子群算法的并行多机调度问题研究［J］.计算机集成制造系统,2006,12（2）：183-187.

LIU Zhi-xiong,WANG Shao-mei.Research on parallel machines scheduling problem based on particle swarm optimization algorithm［J］.Computer Integrated Manufacturing Systems,2006,12（2）：183-187.

［2］贺仁杰,谭跃进.具有时间窗口约束的并行机床调度问题研究［J］.系统工程,2004,22（5）：18-22.

HE Ren-jie,TAN Yue-jin.On parallel machine scheduling problem with time windows［J］.Systems Engineering,2004,22（5）：18-22.

［3］胡大勇,姚振强.调整时间与顺序相关的等同并行机调度［J］.机械工程学报,2011,47（16）：160-165.

HU Da-yong,YAO Zhen-qiang.Identical parallel machines scheduling with sequence-dependent setup times［J］.Journal of Mechanical Engineering,2011,47（16）：160-165.

［4］GUPTA J N D.Two-stage hybrid flow shop scheduling problem［J］.Journal of the Operational Research Society,1988,39（4）：359-364.

［5］OGUZ C,LIN B M T,EDWIN C T C.Two-stage flow shop scheduling with a common second-stage machine［J］.Computers&operations research,1997,24（12）：1169-1174.

［6］HARIRI A M A,POTTS C N.A branch and bound algorithm for the two-stage assembly scheduling problem［J］.European Journal of Operational Research,1997, 103（3）：547-556.

［7］赵月,胡玉梅.求解可重入并行机调度的混台禁忌搜索算法［J］.计算机应用,2012,32（9）：2451-2454.

ZHAO Yue,HU Yu-mei.Hybrid tabu search for scheduling reentrant jobs on parallel machines［J］.Journal of Computer Applications,2012,32（9）：2451-2454.

［8］张洁,张朋,刘国宝.基于两阶段蚁群算法的带非等效并行机的作业车间调度［J］.机械工程学报,2013,49（6）：136-144.

ZHANG Jie,ZHANG Peng,LIU Guo-bao.Two-stage ant colony algorithm based job shop scheduling with unrelated parallel machines［J］.Journal of Mechanical Engineering,2013,49（6）：136-144.

［9］陈亮,王世进,周炳海.柔性作业车间调度问题的集成启发式算法［J］.计算机工程,2008,34（1）：256-258.

CHEN Liang,WANG Shi-jin,ZHOU Bing-hai.Integrated heuristic algorithm for flexible job-shop scheduling problems［J］.Computer Engineering,2008,34（1）：256-258.

［10］庄新村,卢宇灏,李从心.基于遗传算法的车间调度问题［J］.计算机工程,2006,32（1）：193-194.

ZHUANG Xin-cun,LU Yu-hao,LI Cong-xin.Solving job shop scheduling problem by genetic algorithm［J］.Computer Engineering,2006,32（1）：193-194.

［11］ZHENG D Z,WANG L.An effective hybrid heuristic for flow shop scheduling［J］.The International Journal of Advanced Manufacturing Technology,2003,21（1）：38-44.

Method for multi-stage alternative grouping parallel machines scheduling problem

MIAO Feng1,XIE An-huan1,WANG Fu-an2,YU Feng2,ZHOU Hua1
（1.State Key Laboratory of Fluid Power Transmission and Control,Zhejiang University,Hangzhou 310027,China；2.Jiujiang Branch of 707 Research Institute of CSIC,Jiujiang 332007,China）

To solve the mixed flow scheduling problem with multi-stage alternative grouping parallel machines,the mathematical model to minimize the maximum completion time was constructed and a hybrid heuristic-genetic algorithm was developed,the algorithm bases on piecewise independent coding method and modified genetic operators.The optimal decision variables of scheduling rules is determined by the global search ability of genetic algorithm.Scheduling scheme of each stage is determined by using the decision variables and the hybrid heuristic rules which contains a variety of scheduling rules.The algorithm can solve path selection sub-problems and processing sorting sub-problems at the same time,and the results automatically satisfy model constraints.This algorithm has following advantages：high arithmetic speed,optimum results taking into higher rates of load-balancing and etc.Simulation examples of different scales verify the effectiveness of the algorithm.The comparison indicates that the composite indicator of this algorithm is superior to that of single heuristic-genetic algorithms.

parallel machines scheduling；heuristic algorithm；genetic algorithm

10.3785／j.issn.1008-973X.2015.05.008

TP 18；TP 301.6

A

1008-973X（2015）05-0866-07

2014-05-19. 浙江大学学报（工学版）网址：www.journals.zju.edu.cn／eng

国家自然科学基金创新研究群体科学基金资助项目（51221004）.

苗峰（1990－）,男,硕士生,主要从事生产线设计与调度的相关研究.E-mail：miaofeng646＠zju.edu.cn

周华,男,教授,博导.E-mail：zhouh＠cmee.zju.edu.cn