基于遗传算法的装备维修作业车间并行调度模型

包 博， 李体方， 张 搏

(空军工程大学防空反导学院， 陕西 西安 710051)

在维修设备、人员和材料有限的情况下，合理有效地进行维修作业车间调度，有利于提升维修车间的维修效率。依据车间构成的不同，车间调度问题主要分为单机调度[1]、并行机调度[2]、流水车间调度[3]和作业车间调度[4]等。其中：作业车间调度在实践中应用最为广泛，对其工艺路线柔性以及设备柔性的相关研究较为丰富。杨少华等[5]在柔性作业车间调度模型的基础上，构建了军用飞机维修作业调度模型。朱昱等[6]针对战时装备修理任务调度问题，提出了一种针对串行维修流程，多专业、多作战单元的维修调度模型。随着车间调度技术应用领域的拓展，在调度模式上，出现了工序间并行性增强的新特点，尤其在装备维修车间调度领域，维修作业工序并行性特点更为突出。苏兆锋等[7]对柔性作业调度的串并行模型进行了对比与求解。JAMESC等[8]对包含并行机和返工的作业车间调度问题进行了研究，提出了一种新的调度算法。徐本柱等[9]提出了相同工件的同批工序间、不同工序间可并行的车间调度算法，有效地解决了批量加工车间调度问题。对于装备维修作业车间调度问题，在提高调度柔性的同时，考虑工序的并行性也十分重要。

笔者针对工序可并行条件下的装备维修作业车间调度问题，在柔性作业车间调度问题的基础上，考虑了装备维修工序的并行性特点，建立以维修任务完成时间最小为目标函数的数学模型，设计遗传算法对调度模型进行求解，并通过算例验证方法的可行性和有效性。

1 问题分析及数学模型

1.1 工序并行性

装备维修调度包括串行调度和并行调度，并严格按照设定的维修工艺路线执行各项工序。与单个零件生产中的串行流水生产模式不同，装备维修的流程更加复杂，通常包括分解、部件送修、分装和总装4个环节，维修工艺路线具有明显的并行性。维修工艺路线的并行性通常依据专家经验和计算机辅助工艺规划，在维修规划阶段形成并确定。然而，无论是串行调度还是并行调度，维修工序都必须满足拓扑排序。对于串行调度，在任意时刻，只允许执行至多1项工序；对于并行调度，在任意时刻，没有优先关系的工序可在不同维修单元上同时进行处理。如某型装备的维修工艺路线共包含5道工序，其中：工序1、2与工序3、4之间不存在先后约束，在调度中可并行进行。其维修工艺路线示意图如图1所示。

图1 某型装备维修工艺路线示意图

可采用表格的形式来描述工序间的并行关系，图1中各工序间并行关系的表格描述如表1所示。由表1可更加清晰地了解到任意2道维修工序间的并行关系。

表1 工序并行关系

为了更好地描述调度中装备维修工艺路线的并行性水平，笔者提出了工序并行率，其计算公式为

P=并行关系数/总关系数， 0≤P≤1

。

(1)

1.2 维修作业车间调度数学模型

1) 设Ni(i=1,2,…,n)为第i台待修装备，Mj(j=1,2,…,m)为待修装备的第j个维修单元，Lik为维修第i台待修装备的第k(k=1,2,…,l)道维修工序；Tijk为对装备Ni中第j个维修单元Mj进行维修时所需的维修时间。

2) 当装备按照一定的维修工序顺序进行维修时，每道工序可选择若干个维修单元进行维修。在满足实际约束的条件下，需要将各维修单元合理地安排到各道维修工序上，使调度方案达到最优化。

笔者在柔性作业车间调度的基础上，考虑工序可并行的特点。设PNi(i=1,2,…,n)为装备Ni在维修工艺路线中存在先后顺序约束的相邻工序对集合；对于装备Ni，设Vik为可与工序Oik并行进行的工序集合，当Vik=∅时，维修作业车间调度问题即转变为传统的柔性作业车间调度问题。因此，维修作业车间调度问题是传统柔性作业车间调度问题的拓展。

综上所述，工序可并行的装备维修柔性作业车间调度问题的数学描述为

(2)

式中：sik、eik分别为工序Oik的开始和结束时刻。式(3)表示装备的每道维修工序只选择1个维修单元，其中xijk为0/1变量，当xijk=1时，表示维修时工序Oik选择了维修单元Mj,当xijk=0时，表示维修时工序Oik未选择维修单元Mj；式(4)描述了工序本身的时间约束；式(5)描述了装备非并行工序的开始、结束时间约束，并行工序间不存在时间约束；式(6)描述了装备维修单元上各道工序的时间约束，其中sju、eju分别表示维修单元Mj上第u道工序的开始和结束时刻。

2 遗传算法设计与实现

柔性作业车间调度问题是一类典型的NP(Non-deterministic Polynomial)问题，针对NP问题，学者们提出了许多行之有效的求解算法，如禁忌搜索算法[10]、遗传算法[11]、蚁群算法[12]、粒子群算法[13]等。其中遗传算法对解决该类问题具有较好的适用性[14]，因此笔者采用遗传算法来求解模型。对于维修车间调度问题，需要同时对装备维修工序顺序和工序维修单元2种信息进行描述。因此，采用基于双层编码遗传算法的车间调度算法，其流程如图2所示。

图2 基于双层编码遗传算法的车间调度算法流程

2.1 染色体编码与解码

采用双层编码结构进行染色体编码时，第1层表示装备维修工序的顺序，第2层表示装备的每道工序对应的维修单元。设染色体为

[x1,x2,…,xN,y1,y2,…,yN]，

其中：xt(t=1,2,…,N)为装备序号；yt(t=1,2,…,N)为装备对应的工序所选择的维修单元。

依据工序可选维修单元、工序操作工时和可并行工序数进行染色体解码。对于染色体[1,2,1,2,3,3,2,1,3,3,1,2]，设装备N1、N2的2道工序可并行，装备N3的2道工序只能串行，不考虑具体的工序维修工时，依据解码规则，染色体解码过程的甘特图如图3所示。

2.2 适应度函数

依据目标函数，以全部维修任务完成时间为染色体的适应度值，即

(7)

图3 染色体解码过程甘特图

染色体的适应度值越小，说明维修任务完成时间越短，相应的染色体越好。

2.3 遗传算子

2.3.1 选择算子

选择操作主要采用轮盘赌的方法，依据概率选出适应度好的染色体，适应度值越好,被选中的概率越大，概率计算公式为

(8)

2.3.2 交叉算子

交叉操作分为2步：一是对2个染色体在交叉点处进行基因互换；二是对交叉后的染色体进行局部调整，使染色体满足约束条件。如：对2个染色体进行交叉处理，假设交叉位置为3，首先对交叉点处进行基因互换；但交叉后，发现装备工序有增加或减少的情况，对此，将装备工序多余的操作变为缺失的操作，染色体后半部分不变，从而避免了非法染色体的产生，即

2.3.3 变异算子

进行变异操作时，首先在第1层随机选择2个变异点，然后将第1层维修工序码和第2层维修单元码的对应位置上的基因进行互换。如对某染色体选择在位置2、3上进行的交叉变异操作为

3 算例分析

设某装备修理厂需要完成4套装备大修任务，每套装备的维修任务均包含5道维修工序，由4组维修单元执行维修任务。各装备维修工序的可选维修单元以及对应的维修时间如表2所示。装备N1、N2的维修工艺路线相同，其工序的并行关系如表3所示，装备N3、N4的维修工艺路线相同，其工序的并行关系如表4所示。

表2 工序可选维修单元及维修时间

表3 装备N1、N2工序的并行关系

表4 装备N3、N4的工序并行关系

3.1 参数设置及方案生成

设种群数为40，遗传代数为50，交叉率为0.8，变异率为0.6，采用MATLAB求解模型。

1) 并行调度维修方案

图4为并行调度维修方案的甘特图，图中“i0k”表示装备Ni的第k道工序。求解过程的寻优收敛曲线如图5所示。

由图4可以看出计划维修方案中装备对应的维修单元以及工序的开始、结束时间，由此预期其任务完成时间为39天。在维修调度方案中，部分维修工序存在并行处理的情况，如工序O11-O12，O33-O34，工序并行处理缩短了总维修任务完成时间，提高了维修效率。

图4 并行调度维修方案的甘特图

图5 遗传算法寻优收敛曲线

2) 串行调度维修方案

对染色体进行串行规则解码，即设定装备的维修工艺路线中不存在并行工序，则上述并行调度维修方案所对应的串行调度维修方案的甘特图如图6所示。

图6 串行调度维修方案的甘特图

对比分析串、并行调度维修方案的仿真结果，可以看出：并行调度维修方案中各工序之间的衔接更加紧密，部分工序的完成时间提前;同时，并行调度维修方案的维修完工时间相对较短，表明并行调度的维修效率更高。

3.2 参数并行率分析

参数并行率描述了装备维修工艺路线中工序的并行性水平。笔者在工序数量、工序时长等参数不变的条件下，设置低、中、高3组不同并行性水平(并行率)的维修工艺路线，比较分析工艺路线的并行率对维修效率的影响。3组并行性水平设置如下：

1) 低并行率调度，各装备维修工艺路线的全部工序只可进行串行操作，即各装备的并行率均为0。

2) 中并行率调度，装备维修工艺路线设置如表3、4所示，其中：装备N1、N2的维修工艺路线的并行率为0.6;装备N3、N4的维修工艺路线的并行率为0.3。

3)高并行率调度，装备维修工艺路线的全部工序均可进行并行操作，即各装备的并行率均为1。

对3组维修工艺路线参数进行仿真实验，每组寻优计算重复10次，结果如图7所示。

图7 不同并行性水平下调度维修方案的仿真结果

由图7可以看出：调度中维修工序的并行性水平越高，装备维修的效率越高，其中，完全并行调度(高并行率)较串行调度(低并行率)的平均任务完工时间缩短了26.4%。这是因为，当维修工艺路线中的并行性水平越高时，维修工序之间的时间约束就越少，可同时开展的工序就越多，因而减少了调度中维修单元的闲置等待时间，缩短了装备维修任务完成时间，提高了装备维修效率。

4 结论

针对装备维修调度问题，笔者建立了工序并行条件下的维修作业车间调度模型，研究了维修调度中工序并行性对维修效率的影响，并通过算例进行了验证，结果表明：模型符合装备维修调度实际，可在一定程度上提高维修效率。在维修实践中，工艺路线的并行性在工业路线规划阶段就已确定，因此，在设计维修工艺路线时，应尽量提高工序的并行性。在后续的研究中，将进一步挖掘柔性对并行性的影响，并对大批量、复杂工艺路线条件下的维修工序可并行维修作业车间调度问题进行研究。

参考文献：

[1] YANG S J,YANG D L,Minimizing the total completion time in single-machine scheduling with aging/deteriorating effects and deteriorating maintenance activities[J]. Computers and mathematics with applications,2012,60(1):2161-2169.

[2] 许晓晴,崔文田,林军,等.不确定加工时间下同型并行机的鲁棒排程[J].系统工程,2012,30(2):100-104.

[3] 孙志刚,朱小冬,李锋.一种考虑权重的多专业流水式批量维修任务调度模型[J].装甲兵工程学院学报,2012,26(2):24-28.

[4] 丁雷,王爱民,宁汝新.工时不确定条件下的车间作业调度技术[J].计算机集成制造系统,2010,16(1):96-108.

[5] 杨少华,王瑛,刘刚.多目标军用飞机维修作业调度优化研究[J].计算机工程与应用,2016,52(14):19-26.

[6] 朱昱,王连锋,杨雪松.一种基于维修流程的装备维修任务调度方法[J].兵工自动化,2012,31(12):28-31.

[7] 苏兆锋,邱洪泽.柔性作业调度的串并行模型对比与求解[J].计算机工程与应用,2008,44(9):235-238.

[8] JAMESC C,WU C C ,CHEN C W,et al. Flexible job shop scheduling with parallel machines using genetic algorithm and grouping genetic algorithm[J]. Expert systems with applications,2012,39(1):10016-10021.

[9] 徐本柱,费晓璐,章兴玲.柔性作业车间批量划分与并行调度优化[J].计算机集成制造系统,2016,22(8):1953-1964.

[10] 陆汉东,何卫平,周旭,等.基于禁忌搜索的柔性作业车间分批调度[J].上海交通大学学报,2012,46(12):2003-2008.

[11] 李平,唐秋华,夏绪辉,等.基于双层遗传编码的柔性作业车间自适应重调度研究[J].中国机械工程,2013,24(16):2195-2201.

[12] 张洁,张朋,刘国宝.基于两阶段蚁群算法的带非等效并行机的作业车间调度[J].机械工程学报,2013,49(6):136-144.

[13] 张静,王万良,徐新黎.基于改进粒子群算法求解柔性作业车间批量调度问题[J].控制与决策,2012,27(4):513-518.

[14] 于春风,郭昊,王磊,等.面向任务的装甲装备基本维修单元配置优化[J].装甲兵工程学院学报,2016,30(1):26-28.