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

0 引言

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

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

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

1 問題建模

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

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

1）在t=0時(shí)，所有工件都能被機(jī)器加工，所有的機(jī)器都能開始加工工件；

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

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

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

5）工件間的加工順序隨機(jī)；

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

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

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

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

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

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

Tikq：工件Ji的第k道工序在機(jī)器Mq上的加工時(shí)間；

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

Sikq：工件Ji的第k道工序在機(jī)器Mq上加工的開始時(shí)間；

Tieq：工件Ji的最后一道工序在機(jī)器Mq上的完工時(shí)間；

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

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

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

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

2 基于改進(jìn)遺傳算法的模型求解

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

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

步驟1：個體采用多層整數(shù)編碼的編碼方式，每個個體表示整個車間全部工件的加工順序。初始化種群，加工工件數(shù)為n，每個工件的工序數(shù)為k，機(jī)器數(shù)為m加工時(shí)間服從均值為μ，方差為σ2的正態(tài)分布。如個體[2 3 4 1 2 1 3 4 2 1 3 3 2 2 1 3]，該個體表達(dá)的是4個工件在3臺機(jī)器上的加工順序，前8位表示工件的加工順序依次是工件2、工件3、工件4、工件1、工件2、工件1、工件3、工件4，后8位表示加工機(jī)器，依次為機(jī)器2、機(jī)器1、機(jī)器3、機(jī)器3、機(jī)器2、機(jī)器2、機(jī)器1、機(jī)器3。

步驟2：根據(jù)目標(biāo)函數(shù)及約束條件計(jì)算個體的適應(yīng)度值，適應(yīng)度值為全部工件的完工時(shí)間，適應(yīng)度值函數(shù)為：

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

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

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

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

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

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

3 實(shí)例分析

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

圖1 改進(jìn)遺傳算法流程圖

表1 工序加工時(shí)間的均值矩陣

表2 工序加工時(shí)間的方差矩陣

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

【】【】

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

圖2 算法搜索過程

由圖2可以看出，最優(yōu)適應(yīng)值在最初的時(shí)候保持在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è)備周期性維護(hù)的時(shí)間，但是與文獻(xiàn)[1]相比，算法搜索在尋優(yōu)過程中需要的迭代次數(shù)遠(yuǎn)遠(yuǎn)少于文獻(xiàn)[1]中的迭代次數(shù)，說明多層編碼的遺傳算法對解決車間調(diào)度問題具有更好的尋優(yōu)效果。而且本文中考慮了設(shè)備的周期性維護(hù)時(shí)間，更加符合現(xiàn)代工業(yè)生產(chǎn)中車間調(diào)度的實(shí)際情況。

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

4 結(jié)論

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

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

[2]朱顥,唐萬生.加工時(shí)間為連續(xù)隨機(jī)變量的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ī)會維護(hù)建模方法[J].計(jì)算機(jī)集成制造系統(tǒng),2013,19(5):1051.

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

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

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