求解具有预防性维护的并行机调度的遗传算法

李同玲，王 宏，林 丹

（天津大学 理学院，天津 300072）

1 概述

假设机器持续不断工作的生产计划在现实中根本无法实施。由于设备极其昂贵和复杂，实际生产中，设备发生故障会给整个生产车间带来影响，进而降低生产效率。文献[1]指出对设备进行有效的预防性维护就能够提高生产效率和生产的安全性能。因此在编制生产计划的过程中应考虑机器的维护。近年来很多学者在此方面进行了许多研究，并得到了很多重要的结论。

Liao等[2]设计了一个分支定界算法和启发式算法求解以最小化最大延误时间为目标的单机周期维护问题。Ji[3]讨论了目标为最小化总工期的周期性单机排序问题，指出最长加工时间是最优离线算法。周炳海等[4]研究了集成生产与预防性维护的流水线车间的调度问题，并设计了一个简单启发式算法对其进行求解。Sbih等[5]分别提出启发式算法和分支定界方法求解关于单机周期维护和弹性的周期维护的调度问题。文献[6]研究了弹性周期性维护的单机调度问题，将周期维护的生产过程看作是一个装箱问题，提出的六种启发式算法进行求解，实验结果表明，加工时间降序排列的最先适配法的效果最好。文献[7]提出了用粒子群算法算法来解决单机定期维修活动调度问题。文献[8]分别研究了周期性和决策性两种预防性维护的两台并行机调度问题，并对两种维护分别进行降序最先适配启发式和最短加工时间启发式的分析。

预防性维护问题分为两种：周期性维护和决策性维护。周期性维护是指维护任务的时间表在编制工件调度方案之前已经确定。决策性维护指维护任务的时间和工件调度同时编制[8]。以上文献研究的问题多集中在周期性维护上，而大多数文献都假设订单在0时刻均可以加工，实际上订单是动态到达的。本文将研究工件带有释放时间的预防性维护的并行机调度问题，并对该问题设计了一种遗传算法寻找最优工件序列，对于给定的工件序列设计了最先适配启发式算法求其最优时间表。

2 问题描述

本文研究的问题描述如下：N个独立的工件i∈{1, 2, , N}在M台并行机j∈{1, 2, , M}上加工。工件是动态到达的，即工件i的释放时间ri不全为0，每个工件i的加工时间是Pi。在生产加工过程中，每台机器同时只能加工一个工件，机器持续工作一段时间BL后必须进行预防性维护，每一次机器的维护时间是m。本文考虑预防性维护中的一种——决策性维护。目标是确定各工件i在机器上的开始时间STi和完工时间CTi及机器的维护时间表，使得总工期Cmax最小。本文规定Pi≤BL；并把在每台机器上连续加工的工件记为一个批次k (k=1, 2, , K) ，机器j上的第k批次的开始时间和完工时间分别记为SMkj和CMkj；每个工件在任何一台机器上加工不允许中断；工件的加工时间和释放时间、机器维护时间都已知。

3 给定工件序列的单机调度算法

对求解带有释放时间的工件在具有预防性维护的并行机调度问题，本文分为两部分构成，首先确定每台并行机上的工件序列，然后分别根据工件序列来确定每个工件的开工和完工时间，即确定每个工件的时间表。本节主要介绍已知机器j上的工件序列来确定工件时间表的一种启发式算法，此方法类似于装箱问题的最先适配算法。算法如下：

初始化：令批次k＝1，SMkj＝0，机器的当前完工时间CM＝0。

1）从k＝1批次开始，依照工件序列的优先顺序检查所有未被排产的工件i是否可以放到第一批次进行加工。若工件i的释放时间ri和机器的当前完工时间CM中较大者加上其加工时间Pi不大于机器可持续加工时间BL，即max{ri, CM}+Pi≤BL，则工件i可放到第一批次加工，工件i的开工时间STi＝max{ri, CM}，完工时间CTi＝STi+Pi，此时机器的当前完工时间CM＝CTi；否则工件i不可在第一批次加工。重复直到所有工件检查完。若所有工件都已安排完，算法停止；否则，批次k加工完毕，则CMkj＝CM，转2）。

2）进行第k批次的机器维护，从CMkj开始维护，维护的完工时间为CMkj＋m ，机器的当前完工时间CM＝CMkj。接着机器开始下一批次的加工，令k＝k＋1，则SMkj＝CM。

3）依照工件序列的优先顺序检查所有未被安排的工件i是否可以放到批次k中进行加工。若工件的释放时间ri和机器的当前完工时间CM最大者减去批次k的开始时间SMkj加上该工件的加工时间Pi不大于BL，即max{ri, CM}-SMkj＋Pi≤BL，则工件i可放到第k批次上加工，其开工时间STi＝max{ri, CM}，完工时间CTi＝STi＋Pi，此时机器的当前完工时间CM＝CTi；否则工件i不可放到第k批次加工。重复直到所有工件检查完。若所有工件都已安排，算法停止；否则，批次k加工完成，则CMkj＝CM，转2）。

4 遗传算法

遗传算法基于达尔文的自然选择原理，通过对候选解进行选择、交叉、变异等操作，模拟自然界的“优胜劣汰”的自然选择过程，反复迭代自动寻优，最终得到问题的最优解。根据工件加工调度问题的特点,具体设计了相应的编码、解码方案及其遗传算子。

4.1 编码方案

用遗传算法解决排序问题的首要任务就是对问题进行编码，即把一个解表示成一条染色体。假设有N个工件，M台机器，则一条染色体I由两部分组成，可表示为：

其中A＝(J1, J2, , JN)，Ji∈{1, 2, , N}为一个工件序列向量，表示所有工件的一个排列。R＝(MJ1, MJ2, , MJN)，MJi∈{1, 2, , N}为机器向量，表示工件序列向量中各工件对应的加工机器。A和R中的基因分别称为工件基因和机器基因。可知，染色体一旦确定，则工件分配的机器和每台机器上的工件序列就可确定。如工件J1在机器 MJ1上加工，…，工件Ji在机器MJi上加工，…，依次类推。

4.2 解码方案

每条染色体需要进行解码以得到每个工件的开始加工时间、完工时间及每台机器维护时间。按照本文的编码方法，每台机器上的工件序列已经固定，因此，对于每台机器上工件的时间表可以按照第3节介绍的最先适配算法求解。

4.3 产生初始种群

设种群规模为popsize，初始种群中的每个染色体按照如下方法产生：首先随机产生一个工件序列A＝(J1, J2, , JN)，每个工件基因均为1到N的整数；然后对于A中每个工件Ji从其机器集合(1, 2, , M)中随机选择一机器MJi组成机器向量R。

4.4 选择

本文采用精英选择策略，即从当前群体中选择h＝popsize×15%个最好的个体组成高质量解集HQS，为了保持多样性，需要设置一个阈值t，使HQS中每个个体之间的距离不小于t，其中两个个体I1和I2间的距离d (I1, I2)定义为：

其中 ：

HQS被直接复制到下一代。若在当前群体中没有h个满足条件的个体，则可以按照初始群体产生的方法随机产生一些个体放到HQS中，以确保HQS中包含h个个体。

4.5 交叉

参与交叉的两个个体，一个从种群中随机选取，另一个从高质量解集HQS中按顺序依次选取。采用一点交叉方法进行交叉，设参与交叉操作的两个个体一个为母体，另一个为父体，经交叉操作后产生两个个体，一个为女儿，一个为儿子。具体操作为：随机选择一个正整数c (1＜c＜N)作为交叉点，女儿的工件序列向量和机器向量的前c个位置基因分别继承母体的工件序列向量和机器向量的前c个基因，而女儿的工件链表的后N-c位置的基因来源于父体的机器向量，其中在女儿中已有的工件不再考虑，且保持其在父体中的相对位置；女儿后N-c位置的机器基因继承其相应位置的工件基因在父体中对位置的机器基因。产生儿子的方法与此相类似，只需交换父体和母体的位置即可。

4.6 变异

本文设计对染色体进行两次独立变异， 变异1：染色体I中的工件序列向量A及机器向量中相应的每个基因依变异概率发生变异，首先随机产生两个整数i, j∈{1, 2, , N}且i≠j，然后交换工件序列向量和机器向量中i和j位置上的基因。变异2：对染色体I中机器向量中每个机器基因MJi依变异概率发生变异，从机器集合{1, 2, , M}中随机选一机器替换MJi。

5 实验结果

为了验证本文设计算法的有效性，随机产生了280个算例，实验设计的参数主要有订单数N＝10, 20, 30, 50, 100, 150, 200；机器数M＝1, 2, 4,6。对于这两个参数采用因子实验设计法共设计28个实验，对于每个实验随机产生10个算例，则共有280个算例。每个例子中订单的加工时间服从区间[10, 35]均匀分布的整数，释放时间服从区间[0, 48]的整数，机器最长持续工作时间BL＝40，机器维修时间为m＝3。

为了方便，称采用最先适配算法解码的遗传算法为GA+FF。文献[8]提出了求解带有决策维护的并行机调度问题的启发式算法，该算法是将各工件的加工时间按升序进行排列，然后按照此排列的顺序号除以机器数所得的余数加 ，作为对应工件所进行加工的机器号，最后每台机器按照加工时间升序进行排序计算各个工件的时间表。我们将此算法进行了修改：分配给每台机器的工件及工件序列方法与该算法相同，只是最后计算各工件的时间表时采用本文3节介绍的最先适配算法。将修改后的算法简记为SPT+FF。

表1列出了GA+FF和SPT+FF两个算法分别计算每个实验中10个算例的总工期平均值。通过比较可以看出，GA+FF的计算结果都优于算法SPT+FF。

表1 GA+FF和SPT+FF的总工期平均值

6 结束语

本文研究了多台并行机工件动态到达的调度模型，对于预防性维护最小总完工时间问题，首先建立最先适配算法的模型对工件进行安排，然后设计一种遗传算法寻找工件的最优排序，通过大量实验与SPT+FF进行了比较，说明GA+FF可以很好的解决该问题。

[1] R. H. P. M. ArtS, G. M. Knapp, M. J. Lawrence. Some aspects of measuring maintenance in the process industry[J]. Journal of Quality in Maintenance Engineering, 1998,4: 6-11.

[2] C.J. Liao, W. J. Chen. Single-machine scheduling with periodic maintenance and nonredeemable jobs [J].Computers and Operations Research, 2003, 30: 1335-1347.

[3] M. Ji, Y. He, T. C. E. Cheng. Single-machine scheduling with periodic maintenance to minimize makespan [J].Computers & Operations Research, 2007, 34: 764-1770.

[4] 周炳海, 蒋舒宇, 王世进, 吴斌, 奚立峰. 集成生产与预防性维护的流水线车间调度算法 [J]. 大连海事大学报,2007, 33(3): 32-35.

[5] M. Sbihi, C. Varnier. Single-machine scheduling with periodic and flexible periodic maintenance to minimize maximum tardiness [J]. Computers & Industrial Engineering, 2008, 55: 830-840.

[6] C. Low, M. Ti, Ch-J Hsu, Ch-T Su. Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance [J]. Applied mathematical modeling , 2010, 34: 334-342.

[7] Ch. Low, Ch-J Hsu , Ch-T Su. A modified particle swarm optimization algorithm for a single-machine scheduling problem with periodic maintenance [J]. Expert Systems with Applications.2010. 37: 6429-6434.

[8] 孙凯彪, 李金权, 王加银. 两台同型机多阶段维护调度问题的若干结果 [J]. 北京师范大学学报(自然科学版),2008-04, 44(4): 343-347.