考慮機器周期性維護的不確定加工車間調度優化研究

（西安工程大學 機電學院，西安 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.