（西安工程大學(xué) 機電學(xué)院，西安 710048）

0 引言

加工車間調(diào)度問題是貼近企業(yè)生產(chǎn)實際的一種生產(chǎn)調(diào)度問題，也是學(xué)者們研究最多的一類問題。但是在傳統(tǒng)的調(diào)度研究中，大多數(shù)的學(xué)者著重研究確定的加工車間調(diào)度問題，而在實際的加工生產(chǎn)中，加工時間受各種各樣的不確定因素的影響，是不確定的。此外，隨著機器的老化，發(fā)生機器故障的概率也會加大，就需要考慮對機器進行定期或者不定期的維護，而且機器在維護期內(nèi)是不能被使用，這種機器的不可用性就造成了生產(chǎn)加工時間的延長[1]，綜合上述的因素，可以得出傳統(tǒng)的確定的加工車間調(diào)度的研究在實際應(yīng)用中存在著一定的缺陷。因此，考慮車間調(diào)度的不確定加工時間以及設(shè)備維護的相互影響，更加符合車間調(diào)度的實際情況。

近年來，許多學(xué)者將自己的研究放在加工時間的隨機性上，文獻[2]朱顥和唐萬生研究了加工時間為連續(xù)隨機變量的加工車間調(diào)度問題，并對其進行求解，但沒有考慮到實際加工中機器的故障維護的問題。文獻[3]Wu和Zhou以最大期望延遲最小化為目標進行了隨機調(diào)度的研究，但沒有對機器的維護狀態(tài)作為約束進行研究。文獻[4]Gu J, Gu M, Cao C等研究了類似的隨機加工時間的加工車間調(diào)度問題，并設(shè)計出了協(xié)同量子進化算法對問題進行求解，但主要是對算法進行了改進；還有一部分學(xué)者將設(shè)備維護周期作為加工車間的約束進行研究，文獻[5]Khelifati S L，Benbouzid S F假設(shè)機器需要周期性地在時間窗內(nèi)進行維護，采用多智能體算法求解問題，但主要是對智能算法的應(yīng)用，并沒有對車間調(diào)度進行深入研究；文獻[6]Aggoune R，Pormann M C假設(shè)機器存在周期性的不可用時間段，且不可用期的數(shù)量已知，設(shè)計了結(jié)合啟發(fā)式規(guī)則的禁忌搜索算法，有效的提高加工效率；文獻[7]Choi B C，Lee K，研究了機器具有周期性不可用且工件加工時間成比例的流水線系統(tǒng)優(yōu)化問題，只是正對加工時間成比例的流水線問題，沒有普遍性。文獻[8]邵健一，周炳?？紤]串行生產(chǎn)系統(tǒng)的可靠性，提出基于設(shè)備機會維護的維護策略，沒有對機器維護周期進行深入的考慮研究；文獻[9]周炳海，蔣舒宇考慮機器的預(yù)防性維護，設(shè)計了基于NEH（Nawaz-Enscore-Ham）的啟發(fā)式算法，主要是對算法的改進，沒有進行綜合的考慮。上述研究要么只是考慮加工時間隨機的車間調(diào)度，要么集中在考慮設(shè)備周期維護的流水車間調(diào)度問題，但都沒有將加工時間隨機的加工車間調(diào)度問題與設(shè)備周期維護結(jié)合起來。但是實際的加工生產(chǎn)中往往是以上兩類因素綜合作用的，因此考慮設(shè)備周期性維護和加工隨機性的聯(lián)合優(yōu)化研究更有實際意義。

本文在考慮了機器加工時間的隨機性的基礎(chǔ)上，提出一種考慮隨機加工時間和設(shè)備維護周期的聯(lián)合優(yōu)化的加工車間調(diào)度模型，此模型以最大完工時間的期望最小為目標函數(shù)，將設(shè)備維護周期作為模型中的一個約束條件，當(dāng)遇到設(shè)備維護周期時，必須等到機器修復(fù)完成后才能重新進行加工。然后，利用多層編碼的遺傳算法全局搜索能力強、收斂速度快、計算簡單的特性對該問題進行求解。最后，以實例驗證了上述模型的正確性及算法的有效性。

1 問題建模

此問題針對的是m臺機器的加工車間調(diào)度問題，在這個調(diào)度問題中需要加工n個工件，而且每個工件的每一道加工工序只能在特定的機器上進行加工，且工序的加工順序也必須是確定，機器的加工時間用符合正態(tài)分布的隨機變量表示，并且在加工的過程中存在機器的預(yù)防性維護周期，在遇到維護周期時不能進行工件的加工，最終的調(diào)度優(yōu)化目標為決策各機器上的工件加工順序，使最大完工時間的期望最小，即：

本問題的基本假設(shè)條件為：

1）在t=0時，所有工件都能被機器加工，所有的機器都能開始加工工件；

2）工件的加工時間為隨機變量，服從正態(tài)分布；

3）一臺機器在加工工件的某一道工序時，只有這一道工序被加工完畢，才能加工這個工件或其他工件的下一道工序；

4）一個工件只能在一臺機器上加工一次；

5）工件間的加工順序隨機；

6）工件在加工時是連續(xù)的，中間不能有停頓；

7）當(dāng)遇到預(yù)防性維護周期Tm時，機器需要進行預(yù)防性維護，即存在機器的不可用期其中l(wèi)m為機器m的第lm個預(yù)防性維護周期。

8）工件在加工的過程中遇到預(yù)防性周期維護時，工件加工狀態(tài)將被打斷，加工狀態(tài)被打斷的工件必須進行重新加工。

建立模型所需參數(shù)為：

lm：為機器m的第個預(yù)防性維護周期；

Tm：為機器m的預(yù)防性維護周期；

Tikq：工件Ji的第k道工序在機器Mq上的加工時間；

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

Sikq：工件Ji的第k道工序在機器Mq上加工的開始時間；

Tieq：工件Ji的最后一道工序在機器Mq上的完工時間；

Fi：工件Ji的最終完工時間，1≤i≤n。

模型的調(diào)度優(yōu)化目標是使得最大完工時間的期望最小，所以，最終的目標函數(shù)為：

式(3)表示所有工序的加工時間服從正態(tài)分布；式(4)表示機器上加工工件要符合工藝約束，且不同機器不能同時加工同一工序；式(5)表示加工要符合設(shè)備約束,且兩個工件不能在同一機器上加工；式(6)表示工件Ji的第k道工序在機器Mq上的開始時間，在第lm個預(yù)防性維護之后開始；式(7)表示工件Ji的第k道工序在機器Mq上的完工時間在第lm個預(yù)防性維護之前結(jié)束。

此模型中，工序加工時間為已知均值和方差，符合正態(tài)分布的隨機變量，工序總的完工時間是隨機值；雖然已知每個工件本身的加工工序，但是在機器上的加工順序是未知的；雖然機器的預(yù)防性維護周期的長度是一定的，但是工件加工時所經(jīng)歷的預(yù)防性維護周期的個數(shù)卻是不同的?；谏鲜鰩讉€不確定的條件，在滿足工序的約束條件的基礎(chǔ)上，根據(jù)模型來確定最終的最優(yōu)的聯(lián)合優(yōu)化調(diào)度方案。

2 基于改進遺傳算法的模型求解

由于本文考慮了加工時間的不確定性和機器的周期性維護這兩個影響生產(chǎn)加工的因素，傳統(tǒng)的二進制編碼的遺傳算法已經(jīng)不能很好的解決本加工車間調(diào)度問題[10]，因此本文綜合考慮了隨機加工時間和機器的預(yù)防性維護周期的車間調(diào)度的特點，對傳統(tǒng)的遺傳算法的編碼方式進行改進，設(shè)計了多層編碼的編碼方式。提出加工時間服從正態(tài)分布、最大完成時間的期望值作為目標函數(shù)的車間調(diào)度問題，加工時間的函數(shù)表達式為：

具體算法的求解實現(xiàn)過程如下：

步驟1：個體采用多層整數(shù)編碼的編碼方式，每個個體表示整個車間全部工件的加工順序。初始化種群，加工工件數(shù)為n，每個工件的工序數(shù)為k，機器數(shù)為m加工時間服從均值為μ，方差為σ2的正態(tài)分布。如個體[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：根據(jù)目標函數(shù)及約束條件計算個體的適應(yīng)度值，適應(yīng)度值為全部工件的完工時間，適應(yīng)度值函數(shù)為：

步驟3：本文采用的是用隨機數(shù)比較的輪盤賭法，按照一定的選擇概率選擇適應(yīng)度值較好的個體，個體每次被選中的概率為：

p(i)表示個體i在每次選擇中被選中的概率。

步驟4：為了使交叉后產(chǎn)生很好的個體，且避免交叉后產(chǎn)生非法解，本文采用一種基于海明距離的方法[11]，對個體進行交叉操作，從而推動種群向前進化。交叉后可能存在某些工件的工序多余，某些工件的工序缺失，這時就要對工序按照交叉前個體的操作機器來調(diào)整個體的加工機器，將交叉后有問題的個體調(diào)整成合理的個體。

步驟5：變異操作，首先從進行過交叉操作的種群中隨機選取將要進行變異的個體，然后在此個體上隨機的選擇兩個變異位置，最后把個體中兩個位置上的加工工序以及對應(yīng)的加工機器序號對換，就得到新的個體。

步驟6：判斷算法是否結(jié)束。若滿足約束條件，算法結(jié)束，輸出車間調(diào)度的甘特圖；若不滿足，返回步驟2。

通過上述對改進遺傳算法的描述，可以得到改進遺傳算法的流程圖，如圖1所示。

3 實例分析

為了有效的評價本文提出的聯(lián)合優(yōu)化模型和多層編碼的遺傳算法，進行如下的實驗設(shè)計：工件數(shù)n=4，每個工件有4道工序，機器數(shù)m=4，預(yù)防性維護周期Tm=15，種群數(shù)目N=50，最大迭代次數(shù)即遺傳代數(shù)為100，交叉概率為0.7，變異概率為0.5。表1為每道工序的加工時間對應(yīng)的均值矩陣，表2為每道工序的加工時間對應(yīng)的方差矩陣，表3為工序所對應(yīng)機器的機器矩陣。

圖1 改進遺傳算法流程圖

表1 工序加工時間的均值矩陣

表2 工序加工時間的方差矩陣

表3 工序所對應(yīng)的加工機器矩陣

【】【】

算法的搜索過程如圖2所示。

圖2 算法搜索過程

由圖2可以看出，最優(yōu)適應(yīng)值在最初的時候保持在12，經(jīng)過3次迭代之后最優(yōu)適應(yīng)度值保持在11.7。平均適應(yīng)度值從初始的無窮大經(jīng)過迭代一直在降低，經(jīng)過6次迭代之后出現(xiàn)明顯的波動，當(dāng)?shù)?0次之后平均適應(yīng)度值大約等于最優(yōu)適應(yīng)度值。從圖2中可以明顯的得出此算法經(jīng)過幾次迭代就可以得到最優(yōu)的車間調(diào)度方案，說明應(yīng)用此算法可以有效的解決此聯(lián)合優(yōu)化模型問題。

雖然本文中考慮了設(shè)備周期性維護的時間，但是與文獻[1]相比，算法搜索在尋優(yōu)過程中需要的迭代次數(shù)遠遠少于文獻[1]中的迭代次數(shù)，說明多層編碼的遺傳算法對解決車間調(diào)度問題具有更好的尋優(yōu)效果。而且本文中考慮了設(shè)備的周期性維護時間，更加符合現(xiàn)代工業(yè)生產(chǎn)中車間調(diào)度的實際情況。

上述實例驗證了本文中聯(lián)合優(yōu)化模型的合理性，也驗證了基于多層編碼的遺傳算法對于解決考慮機器預(yù)防性維護周期的加工時間服從正態(tài)分布的不確定加工車間調(diào)度問題有效性和實用性。

4 結(jié)論

本文考慮到加工車間調(diào)度的實際情況，將不確定加工時間和機器的預(yù)防性維護周期考慮到車間調(diào)度問題中。由于機器加工時間的隨機性，提出一種考慮服從正態(tài)分布的隨機加工時間和機器預(yù)防性維護周期的聯(lián)合優(yōu)化的加工車間調(diào)度模型，該模型以最大完工時間的期望最小為目標函數(shù)，利用基于多層編碼的遺傳算法對該問題進行求解。通過實例驗證了模型的合理性以及算法的有效性。

[1]張思源,陸志強,崔維偉.考慮設(shè)備周期性維護的流水車間生產(chǎn)調(diào)度優(yōu)化算法[J].計算機集成制造系統(tǒng),2014,(06):1379.

[2]朱顥,唐萬生.加工時間為連續(xù)隨機變量的JobShop調(diào)度問題[J].系統(tǒng)工程與電子技術(shù).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的串行生產(chǎn)系統(tǒng)機會維護建模方法[J].計算機集成制造系統(tǒng),2013,19(5):1051.

[9]周炳海,蔣舒宇.集成生產(chǎn)與預(yù)防性維護的流水車間調(diào)度算法[J].大連海事大學(xué)學(xué)報,2007,33(3):32.

[10]趙詩奎.基于新型鄰域結(jié)構(gòu)的混合算法求解作業(yè)車間調(diào)度[J].機械工程學(xué)報,2016,(09):141.

[11]鄒澤樺,曾九孫,蔡晉輝.改進遺傳算法求解柔性作業(yè)車間調(diào)度問題[J].計算機測量與控制,2017,(04):167.