考虑机器周期性维护的不确定加工车间调度优化研究

（西安工程大学 机电学院，西安 710048）

0 引言

加工车间调度问题是贴近企业生产实际的一种生产调度问题，也是学者们研究最多的一类问题。但是在传统的调度研究中，大多数的学者着重研究确定的加工车间调度问题，而在实际的加工生产中，加工时间受各种各样的不确定因素的影响，是不确定的。此外，随着机器的老化，发生机器故障的概率也会加大，就需要考虑对机器进行定期或者不定期的维护，而且机器在维护期内是不能被使用，这种机器的不可用性就造成了生产加工时间的延长[1]，综合上述的因素，可以得出传统的确定的加工车间调度的研究在实际应用中存在着一定的缺陷。因此，考虑车间调度的不确定加工时间以及设备维护的相互影响，更加符合车间调度的实际情况。

近年来，许多学者将自己的研究放在加工时间的随机性上，文献[2]朱颢和唐万生研究了加工时间为连续随机变量的加工车间调度问题，并对其进行求解，但没有考虑到实际加工中机器的故障维护的问题。文献[3]Wu和Zhou以最大期望延迟最小化为目标进行了随机调度的研究，但没有对机器的维护状态作为约束进行研究。文献[4]Gu J, Gu M, Cao C等研究了类似的随机加工时间的加工车间调度问题，并设计出了协同量子进化算法对问题进行求解，但主要是对算法进行了改进；还有一部分学者将设备维护周期作为加工车间的约束进行研究，文献[5]Khelifati S L，Benbouzid S F假设机器需要周期性地在时间窗内进行维护，采用多智能体算法求解问题，但主要是对智能算法的应用，并没有对车间调度进行深入研究；文献[6]Aggoune R，Pormann M C假设机器存在周期性的不可用时间段，且不可用期的数量已知，设计了结合启发式规则的禁忌搜索算法，有效的提高加工效率；文献[7]Choi B C，Lee K，研究了机器具有周期性不可用且工件加工时间成比例的流水线系统优化问题，只是正对加工时间成比例的流水线问题，没有普遍性。文献[8]邵健一，周炳海考虑串行生产系统的可靠性，提出基于设备机会维护的维护策略，没有对机器维护周期进行深入的考虑研究；文献[9]周炳海，蒋舒宇考虑机器的预防性维护，设计了基于NEH（Nawaz-Enscore-Ham）的启发式算法，主要是对算法的改进，没有进行综合的考虑。上述研究要么只是考虑加工时间随机的车间调度，要么集中在考虑设备周期维护的流水车间调度问题，但都没有将加工时间随机的加工车间调度问题与设备周期维护结合起来。但是实际的加工生产中往往是以上两类因素综合作用的，因此考虑设备周期性维护和加工随机性的联合优化研究更有实际意义。

本文在考虑了机器加工时间的随机性的基础上，提出一种考虑随机加工时间和设备维护周期的联合优化的加工车间调度模型，此模型以最大完工时间的期望最小为目标函数，将设备维护周期作为模型中的一个约束条件，当遇到设备维护周期时，必须等到机器修复完成后才能重新进行加工。然后，利用多层编码的遗传算法全局搜索能力强、收敛速度快、计算简单的特性对该问题进行求解。最后，以实例验证了上述模型的正确性及算法的有效性。

1 问题建模

此问题针对的是m台机器的加工车间调度问题，在这个调度问题中需要加工n个工件，而且每个工件的每一道加工工序只能在特定的机器上进行加工，且工序的加工顺序也必须是确定，机器的加工时间用符合正态分布的随机变量表示，并且在加工的过程中存在机器的预防性维护周期，在遇到维护周期时不能进行工件的加工，最终的调度优化目标为决策各机器上的工件加工顺序，使最大完工时间的期望最小，即：

本问题的基本假设条件为：

1）在t=0时，所有工件都能被机器加工，所有的机器都能开始加工工件；

2）工件的加工时间为随机变量，服从正态分布；

3）一台机器在加工工件的某一道工序时，只有这一道工序被加工完毕，才能加工这个工件或其他工件的下一道工序；

4）一个工件只能在一台机器上加工一次；

5）工件间的加工顺序随机；

6）工件在加工时是连续的，中间不能有停顿；

7）当遇到预防性维护周期Tm时，机器需要进行预防性维护，即存在机器的不可用期其中lm为机器m的第lm个预防性维护周期。

8）工件在加工的过程中遇到预防性周期维护时，工件加工状态将被打断，加工状态被打断的工件必须进行重新加工。

建立模型所需参数为：

lm：为机器m的第个预防性维护周期；

Tm：为机器m的预防性维护周期；

Tikq：工件Ji的第k道工序在机器Mq上的加工时间；

Oikq：工件Ji的第k道工序在机器Mq上加工；

Sikq：工件Ji的第k道工序在机器Mq上加工的开始时间；

Tieq：工件Ji的最后一道工序在机器Mq上的完工时间；

Fi：工件Ji的最终完工时间，1≤i≤n。

模型的调度优化目标是使得最大完工时间的期望最小，所以，最终的目标函数为：

式(3)表示所有工序的加工时间服从正态分布；式(4)表示机器上加工工件要符合工艺约束，且不同机器不能同时加工同一工序；式(5)表示加工要符合设备约束,且两个工件不能在同一机器上加工；式(6)表示工件Ji的第k道工序在机器Mq上的开始时间，在第lm个预防性维护之后开始；式(7)表示工件Ji的第k道工序在机器Mq上的完工时间在第lm个预防性维护之前结束。

此模型中，工序加工时间为已知均值和方差，符合正态分布的随机变量，工序总的完工时间是随机值；虽然已知每个工件本身的加工工序，但是在机器上的加工顺序是未知的；虽然机器的预防性维护周期的长度是一定的，但是工件加工时所经历的预防性维护周期的个数却是不同的。基于上述几个不确定的条件，在满足工序的约束条件的基础上，根据模型来确定最终的最优的联合优化调度方案。

2 基于改进遗传算法的模型求解

由于本文考虑了加工时间的不确定性和机器的周期性维护这两个影响生产加工的因素，传统的二进制编码的遗传算法已经不能很好的解决本加工车间调度问题[10]，因此本文综合考虑了随机加工时间和机器的预防性维护周期的车间调度的特点，对传统的遗传算法的编码方式进行改进，设计了多层编码的编码方式。提出加工时间服从正态分布、最大完成时间的期望值作为目标函数的车间调度问题，加工时间的函数表达式为：

具体算法的求解实现过程如下：

步骤1：个体采用多层整数编码的编码方式，每个个体表示整个车间全部工件的加工顺序。初始化种群，加工工件数为n，每个工件的工序数为k，机器数为m加工时间服从均值为µ，方差为σ2的正态分布。如个体[2 3 4 1 2 1 3 4 2 1 3 3 2 2 1 3]，该个体表达的是4个工件在3台机器上的加工顺序，前8位表示工件的加工顺序依次是工件2、工件3、工件4、工件1、工件2、工件1、工件3、工件4，后8位表示加工机器，依次为机器2、机器1、机器3、机器3、机器2、机器2、机器1、机器3。

步骤2：根据目标函数及约束条件计算个体的适应度值，适应度值为全部工件的完工时间，适应度值函数为：

步骤3：本文采用的是用随机数比较的轮盘赌法，按照一定的选择概率选择适应度值较好的个体，个体每次被选中的概率为：

p(i)表示个体i在每次选择中被选中的概率。

步骤4：为了使交叉后产生很好的个体，且避免交叉后产生非法解，本文采用一种基于海明距离的方法[11]，对个体进行交叉操作，从而推动种群向前进化。交叉后可能存在某些工件的工序多余，某些工件的工序缺失，这时就要对工序按照交叉前个体的操作机器来调整个体的加工机器，将交叉后有问题的个体调整成合理的个体。

步骤5：变异操作，首先从进行过交叉操作的种群中随机选取将要进行变异的个体，然后在此个体上随机的选择两个变异位置，最后把个体中两个位置上的加工工序以及对应的加工机器序号对换，就得到新的个体。

步骤6：判断算法是否结束。若满足约束条件，算法结束，输出车间调度的甘特图；若不满足，返回步骤2。

通过上述对改进遗传算法的描述，可以得到改进遗传算法的流程图，如图1所示。

3 实例分析

为了有效的评价本文提出的联合优化模型和多层编码的遗传算法，进行如下的实验设计：工件数n=4，每个工件有4道工序，机器数m=4，预防性维护周期Tm=15，种群数目N=50，最大迭代次数即遗传代数为100，交叉概率为0.7，变异概率为0.5。表1为每道工序的加工时间对应的均值矩阵，表2为每道工序的加工时间对应的方差矩阵，表3为工序所对应机器的机器矩阵。

图1 改进遗传算法流程图

表1 工序加工时间的均值矩阵

表2 工序加工时间的方差矩阵

表3 工序所对应的加工机器矩阵

【】【】

算法的搜索过程如图2所示。

图2 算法搜索过程

由图2可以看出，最优适应值在最初的时候保持在12，经过3次迭代之后最优适应度值保持在11.7。平均适应度值从初始的无穷大经过迭代一直在降低，经过6次迭代之后出现明显的波动，当迭代到10次之后平均适应度值大约等于最优适应度值。从图2中可以明显的得出此算法经过几次迭代就可以得到最优的车间调度方案，说明应用此算法可以有效的解决此联合优化模型问题。

虽然本文中考虑了设备周期性维护的时间，但是与文献[1]相比，算法搜索在寻优过程中需要的迭代次数远远少于文献[1]中的迭代次数，说明多层编码的遗传算法对解决车间调度问题具有更好的寻优效果。而且本文中考虑了设备的周期性维护时间，更加符合现代工业生产中车间调度的实际情况。

上述实例验证了本文中联合优化模型的合理性，也验证了基于多层编码的遗传算法对于解决考虑机器预防性维护周期的加工时间服从正态分布的不确定加工车间调度问题有效性和实用性。

4 结论

本文考虑到加工车间调度的实际情况，将不确定加工时间和机器的预防性维护周期考虑到车间调度问题中。由于机器加工时间的随机性，提出一种考虑服从正态分布的随机加工时间和机器预防性维护周期的联合优化的加工车间调度模型，该模型以最大完工时间的期望最小为目标函数，利用基于多层编码的遗传算法对该问题进行求解。通过实例验证了模型的合理性以及算法的有效性。

[1]张思源,陆志强,崔维伟.考虑设备周期性维护的流水车间生产调度优化算法[J].计算机集成制造系统,2014,(06):1379.

[2]朱颢,唐万生.加工时间为连续随机变量的JobShop调度问题[J].系统工程与电子技术.2007, 29(005):759.

[3]Wu X, Zhou X.Stochastic scheduling to minimize expected maximum lateness[J].European Journal of Operational Research,2008,190(1):103.

[4]Gu J, Gu M, Cao C, et al. A novel competitive co-evolutionary quantum genetic algo-rithm for stochastic job shop scheduling problem[J].Computers & Operations Research,2010,37(5):927.

[5]Khelifati S L，Benbouzid S F. A multi-Agent scheduling approach for the joint scheduling of jobs and maintenance operations in the Flow Shop sequencing problem[J].Lecture Notes in Computer Science,2011,6923:60.

[6]Aggoune R，Pormann M C. Flow shop scheduling problem with a limited machine availability: a heuristic approach[J].International Journal of Production Economics,2006,99(1/2):4.

[7]Choi B C,Lee K，et al. Flow shops with machine maintenance:ordered and proportionate cases[J].International Journal of Production Research,2010,207(1):97.

[8]邵健一,周炳海.基于CCR的串行生产系统机会维护建模方法[J].计算机集成制造系统,2013,19(5):1051.

[9]周炳海,蒋舒宇.集成生产与预防性维护的流水车间调度算法[J].大连海事大学学报,2007,33(3):32.

[10]赵诗奎.基于新型邻域结构的混合算法求解作业车间调度[J].机械工程学报,2016,(09):141.

[11]邹泽桦,曾九孙,蔡晋辉.改进遗传算法求解柔性作业车间调度问题[J].计算机测量与控制,2017,(04):167.