設(shè)備故障條件下柔性作業(yè)車間重調(diào)度方法

包 博，張 琳，張 搏

空軍工程大學(xué) 防空反導(dǎo)學(xué)院，西安 710051

1 引言

在實(shí)際生產(chǎn)環(huán)境中，各類不確定因素，如：加工設(shè)備故障、緊急件加入、物料供應(yīng)短缺等，會(huì)導(dǎo)致車間工況變化，使得原調(diào)度方案不再可行，進(jìn)而需要重新制定調(diào)度方案以進(jìn)行后續(xù)生產(chǎn)，即重調(diào)度[1-2]。設(shè)備故障是生產(chǎn)中最為普遍的一類不確定因素，針對車間調(diào)度中的設(shè)備隨機(jī)故障問題，學(xué)者們提出了許多行之有效的動(dòng)態(tài)調(diào)度方法[3-5]。文獻(xiàn)[6]針對調(diào)度過程中的設(shè)備故障干擾，基于滾動(dòng)時(shí)域優(yōu)化框架，提出改進(jìn)的事件和周期混合驅(qū)動(dòng)的動(dòng)態(tài)調(diào)度方法。文獻(xiàn)[7]將多代理系統(tǒng)、遺傳算法與滾動(dòng)窗口法有機(jī)地結(jié)合，提出了一種車間動(dòng)態(tài)調(diào)度方法。文獻(xiàn)[8]分析車間生產(chǎn)環(huán)境復(fù)雜和生產(chǎn)過程中各種隨機(jī)擾動(dòng)，提出車間動(dòng)態(tài)重調(diào)度優(yōu)化方法。重調(diào)度方法在動(dòng)態(tài)調(diào)度中顯示了較好的效果，重調(diào)度方法、策略逐漸成為了車間調(diào)度問題中的研究重點(diǎn)。文獻(xiàn)[9]針對機(jī)器故障條件下的混合流水車間重調(diào)度問題，提出了一種新的重調(diào)度模型。文獻(xiàn)[10]在開放式車間中，針對機(jī)器持續(xù)不可用干擾，提出了三種特定的重調(diào)度策略。文獻(xiàn)[11]提出了插入重調(diào)度和完全重調(diào)度策略，有效縮短了車間的加工時(shí)間。但相關(guān)研究主要存在兩方面不足：首先，重調(diào)度必然導(dǎo)致調(diào)度成本的增加，已有方法往往忽視了重調(diào)度成本而僅側(cè)重于調(diào)度效率。其次，已有重調(diào)度方法在運(yùn)用多種重調(diào)度策略時(shí)，通常先選擇重調(diào)度策略進(jìn)而在此策略下制定重調(diào)度方案，而這種方式難以確保重調(diào)度策略所得方案能夠適應(yīng)該擾動(dòng)景況。

針對設(shè)備隨機(jī)故障條件下的柔性作業(yè)車間調(diào)度問題，本文系統(tǒng)分析重調(diào)度成本，綜合運(yùn)用部分右移重調(diào)度策略以及完全重調(diào)度策略，從而提出一種重調(diào)度方法。采用免疫遺傳算法實(shí)現(xiàn)模型的求解計(jì)算，并結(jié)合算例驗(yàn)證方法的有效性。

2 問題描述

柔性作業(yè)車間調(diào)度，可簡單描述為：若干工件Ji(i=1,2,…,n)在設(shè)備 Mj(j=1,2,…,m)上進(jìn)行加工；Oik表示工件的第k(k=1,2,…,l)道工序；工件可選擇加工設(shè)備 Mj開展工序Oik，表示為 pijk，Tijk表示 pijk對應(yīng)的處理時(shí)間；工件嚴(yán)格依照工藝路線進(jìn)行加工，每道工序可選擇若干設(shè)備執(zhí)行操作。在滿足特定約束條件下，需將工件的全部工序合理安排至機(jī)器設(shè)備上，并使調(diào)度方案達(dá)到最優(yōu)性能指標(biāo)[12]。

結(jié)合上述分析，以最小化完工時(shí)間為目標(biāo)，柔性作業(yè)車間調(diào)度問題可描述為數(shù)學(xué)模型：

其中，式（1）為目標(biāo)函數(shù)，eik是工序Oik的結(jié)束時(shí)刻，開始時(shí)刻為sik；式（2）表示每道工序僅選擇一臺(tái)設(shè)備執(zhí)行操作，xijk為0/1變量，為1時(shí)表示工序Oik選擇了機(jī)器Mj執(zhí)行操作；式（3）表示工序自身的時(shí)間約束關(guān)系；式（4）、（5）分別表示工件在工序上的時(shí)間約束和機(jī)器設(shè)備上各工序的時(shí)間約束，其中siu、eiu分別表示設(shè)備Mj上第u道工序的開始、結(jié)束時(shí)刻。

在實(shí)際的車間生產(chǎn)調(diào)度中，設(shè)備故障將使得生產(chǎn)無法按照原有的調(diào)度計(jì)劃繼續(xù)進(jìn)行。設(shè)備故障的發(fā)生表現(xiàn)出隨機(jī)性，其隨機(jī)性可以從三個(gè)方面進(jìn)行描述：故障發(fā)生設(shè)備的隨機(jī)性；故障發(fā)生時(shí)刻的隨機(jī)性；故障持續(xù)時(shí)間的隨機(jī)性。

3 重調(diào)度方法

重調(diào)度是在擾動(dòng)發(fā)生后，重新編制調(diào)度方案，對調(diào)度計(jì)劃進(jìn)行局部或全局調(diào)整。針對設(shè)備隨機(jī)故障，重調(diào)度方法要求能夠適應(yīng)各種景況的設(shè)備故障干擾，在不同程度擾動(dòng)下保證重調(diào)度效果。另外，在重調(diào)度過程中需要考慮調(diào)度成本的合理性。本文提出重調(diào)度方法，首先基于工件信息生成初始調(diào)度方案，當(dāng)擾動(dòng)發(fā)生，輸入擾動(dòng)信息并通過重調(diào)度生成新方案。重調(diào)度的關(guān)鍵步驟包括構(gòu)建重調(diào)度成本函數(shù)、設(shè)計(jì)重調(diào)度策略等[13]。

3.1 重調(diào)度成本

在重調(diào)度方案中，工序的開始加工時(shí)間偏移、工序加工設(shè)備的調(diào)整和以及相同工序在不同設(shè)備上的操作時(shí)間不相同，造成的物料調(diào)動(dòng)量增加以及存儲(chǔ)時(shí)間變動(dòng)等，使得重調(diào)度成本增加。本文基于工件與設(shè)備兩個(gè)層面，從時(shí)間偏差的角度，建立重調(diào)度成本函數(shù)。

提出假設(shè)：假設(shè)預(yù)調(diào)度方案為Q，即正在執(zhí)行的調(diào)度方案。擾動(dòng)后經(jīng)重調(diào)度生成的調(diào)度方案為Q′，此時(shí)并不表示為最終所選擇的重調(diào)度方案。Q、Q′的任務(wù)完成時(shí)間分別表示為Z、Z′，工件工序Oik的開始時(shí)刻分別表示為 sik、s′ik，結(jié)束時(shí)刻分別表示為 eik、e′ik，工序Oik的工時(shí)分別為tik、t′ik，工序Oik選擇的操作設(shè)備分別表示為 pijk、p′ijk。

（1）工序開始時(shí)間偏差成本

工序由于開始時(shí)間的提前或延后，導(dǎo)致物料準(zhǔn)備時(shí)間產(chǎn)生變動(dòng)，使得運(yùn)輸、儲(chǔ)存成本增加，因此采用開始時(shí)間偏差成本對此類重調(diào)度成本進(jìn)行描述。

工序Oik在新舊方案中的開始加工時(shí)間偏差為：

工件總的偏差成本表示為：

（2）工時(shí)偏差成本

工時(shí)的增加，導(dǎo)致人工作業(yè)時(shí)間、設(shè)備使用時(shí)間增加，因此采用工序工時(shí)偏差成本對此類重調(diào)度成本進(jìn)行描述。

工時(shí)增加量為：

工時(shí)偏差成本表示為：

（3）設(shè)備變更成本

工件工序操作設(shè)備的變更，將增加人力勞動(dòng)及調(diào)運(yùn)成本，因此采用設(shè)備變更成本對此類重調(diào)度成本進(jìn)行描述。

工序Oik變更，則表示為：

設(shè)備變更成本表示為：

綜上，重調(diào)度成本函數(shù)表示為：

其中，ω1、ω2、ω3為3類重調(diào)度成本的權(quán)重系數(shù)，ω1+ω2+ω3=1。權(quán)重系數(shù)表示3個(gè)子成本所占重調(diào)度成本的比重，權(quán)重系數(shù)由專家采用“德爾菲法”確定，經(jīng)過調(diào)查、征詢意見、匯總綜合、反饋、再調(diào)查這一反復(fù)過程。

重調(diào)度目標(biāo)函數(shù)綜合考慮任務(wù)完工時(shí)間增量、重調(diào)度成本兩方面，表示為：

其中，有 μ1+μ2=1，μ1、μ2為兩類指標(biāo)的權(quán)重系數(shù)，同樣采用“德爾菲法”進(jìn)行確定。

3.2 重調(diào)度策略

重調(diào)度將部分重調(diào)度策略與完全重調(diào)度策略相結(jié)合，利用兩者優(yōu)勢，以在不同擾動(dòng)景況下，保證重調(diào)度方案的先進(jìn)性。

3.2.1完全重調(diào)度

完全重調(diào)度是指對故障發(fā)生后的所有工件進(jìn)行重新調(diào)度安排，它與靜態(tài)調(diào)度的根本區(qū)別在于每個(gè)機(jī)器的開始加工時(shí)間不同。完全重調(diào)度可保證重調(diào)度方案的優(yōu)化性，但會(huì)隨之產(chǎn)生額外較大的重調(diào)度成本。

完全重調(diào)度的基本步驟為：

步驟1確定重調(diào)度工序集合。重調(diào)度工序集合包含未開始的所有工序，以及因?yàn)樵O(shè)備故障導(dǎo)致中斷的工序。

步驟2確定每個(gè)機(jī)器的開始加工時(shí)間，機(jī)器的開始加工時(shí)間為故障發(fā)生后該機(jī)器的最早空閑時(shí)間。故障發(fā)生時(shí)，如果第 j臺(tái)機(jī)器正好處于空閑，則該機(jī)器的開始加工時(shí)間為0；如果第 j臺(tái)機(jī)器正在加工某道工序，且該工序的剩余加工時(shí)間為t，則該機(jī)器的開始加工時(shí)間為t。

步驟3基于優(yōu)化算法，對重調(diào)度工序集合中的工序進(jìn)行優(yōu)化調(diào)度，形成重調(diào)度方案。

3.2.2部分右移重調(diào)度

部分右移重調(diào)度是指對受到設(shè)備故障直接或間接影響的工序執(zhí)行調(diào)整。該策略只對受影響工序的開始時(shí)間進(jìn)行推遲處理，不改變工序次序和工序?qū)?yīng)的操作設(shè)備，避免了完全重調(diào)度帶來的額外成本過度增大的問題，但同時(shí)存在工序開始時(shí)間移動(dòng)量較大的問題。

部分右移重調(diào)度的基本步驟為：

步驟1確定故障設(shè)備位置，并預(yù)估故障修復(fù)時(shí)間。

步驟2基于“二元分支”機(jī)理，從受到直接干擾的工序開始，分析確定出預(yù)調(diào)度方案中直接或間接的受影響的工序集合。

步驟3逐步后移調(diào)整工序計(jì)劃，直到滿足各類時(shí)間約束條件，形成重調(diào)度方案。

部分右移重調(diào)度具體操作方法可參見文獻(xiàn)[10]。

3.3 重調(diào)度流程

在整個(gè)調(diào)度過程中，預(yù)調(diào)度方案生成階段以最小化完成時(shí)間作為目標(biāo)，而在重調(diào)度方案生成階段中，由于考慮了方案變動(dòng)帶來的調(diào)度成本增加，因而兼顧最小化完成時(shí)間和最小化重調(diào)度成本兩方面目標(biāo)。為保證重調(diào)度方案的質(zhì)量，重調(diào)度同時(shí)采用部分右移重調(diào)度和完全重調(diào)度兩種策略，在兩者形成的方案中選擇較優(yōu)方案。重調(diào)度流程如圖1所示。

圖1 重調(diào)度方法流程

重調(diào)度策略的基本步驟：

步驟1以最小化任務(wù)完成時(shí)間作為目標(biāo)函數(shù)1，如式（1），基于智能優(yōu)化算法產(chǎn)生預(yù)調(diào)度方案。

步驟2依照預(yù)調(diào)度方案進(jìn)行生產(chǎn)，當(dāng)擾動(dòng)發(fā)生，轉(zhuǎn)至步驟3；否則，依照預(yù)調(diào)度方案繼續(xù)生產(chǎn)。

步驟3人工輸入擾動(dòng)信息，包括故障位置、故障時(shí)刻、預(yù)計(jì)故障修復(fù)時(shí)間。

步驟4采用部分右移重調(diào)度形成方案A，并計(jì)算該方案對應(yīng)目標(biāo)函數(shù)2的函數(shù)值，重調(diào)度目標(biāo)函數(shù)2如式（13）；同時(shí)，依據(jù)目標(biāo)函數(shù)2，采用完全重調(diào)度策略，基于智能優(yōu)化算法形成重調(diào)度方案B；比較重調(diào)度方案A、B的重調(diào)度目標(biāo)函數(shù)值大小，選取兩者中較優(yōu)的方案作為重調(diào)度方案，更新預(yù)調(diào)度方案，轉(zhuǎn)至步驟2。

4 免疫遺傳算法

柔性作業(yè)車間調(diào)度問題是一類典型的NP難問題，學(xué)者們針對此類問題提出了許多求解算法，如禁忌搜索算法[14]、遺傳算法[15]、蟻群算法[16]、粒子群算法[17]等。遺傳算法在解決同類問題上顯示出較好的適用性，但存在迭代后期由于個(gè)體多樣性缺失從而易陷入局部最優(yōu)的問題。為克服遺傳算法在計(jì)算中的早熟收斂問題，提高算法的全局收索能力，本文將免疫系統(tǒng)與遺傳算法相結(jié)合，形成免疫遺傳算法，對問題進(jìn)行求解計(jì)算。

基本流程如圖2所示。

4.1 染色體編碼

染色體同時(shí)對工件的工序加工順序和機(jī)器設(shè)備兩方面信息進(jìn)行描述。本文采用雙層編碼結(jié)構(gòu)對染色體進(jìn)行編碼，染色體前半部分描述裝備的工序加工順序，后半部分描述工序所對應(yīng)的加工設(shè)備。設(shè)染色體如：

圖2 算法流程

其中，xk(k=1,2,…,N)為工序的序號，yk(k=1,2,…,N)為工序所對應(yīng)的加工設(shè)備。

染色體解碼需依據(jù)工序可選設(shè)備信息以及工序工時(shí)信息。對于染色體[1，2，1，2，3，3，2，1，3，3，1，2]，不考慮具體工序工時(shí)，依據(jù)解碼規(guī)則，解碼過程如圖3所示。

圖3 染色體解碼示意圖

4.2 適應(yīng)度函數(shù)

在預(yù)調(diào)度方案生成階段，目標(biāo)函數(shù)為最小化任務(wù)完成時(shí)間。而在重調(diào)度方案生成階段中，目標(biāo)函數(shù)綜合任務(wù)完成時(shí)間偏差以及重調(diào)度成本。

預(yù)調(diào)度方案制定時(shí)，依據(jù)目標(biāo)函數(shù)1，適應(yīng)度函數(shù)分別表示為：

重調(diào)度方案制定時(shí)，依據(jù)目標(biāo)函數(shù)2，適應(yīng)度函數(shù)分別表示為：

由于在初預(yù)調(diào)度方案制定、重調(diào)度方案制定中均采用免疫遺傳算法，區(qū)別僅在于適應(yīng)度函數(shù)，因此在后續(xù)步驟操作設(shè)計(jì)中，適應(yīng)度函數(shù)均用 fv表示。

4.3 親和力、抗體濃度

抗體與抗原之間的親和力用于表示抗體對抗原的識(shí)別程度，針對本文中車間調(diào)度問題，親和力定義為：

相似度是指抗體與其他抗體的相似度。本文采用T0位連續(xù)方法計(jì)算抗體與抗體間的親和力，首先確定一個(gè)親和度判定閾值T0，當(dāng)兩個(gè)個(gè)體有超過T0位或者連續(xù)T0位的編碼相同，則認(rèn)為這兩種個(gè)體“相似”，否則認(rèn)為“不相似”。此處借鑒變形的T0位連續(xù)方法來計(jì)算抗體間的親和度，即：

其中，ku,v為抗體u與抗體s中相同的位數(shù)，L為抗體長度。

抗體的濃度是指群體中相似抗體所占的比例，表示為：

期望繁殖概率由親和力Av與抗體濃度Cv共同決定，表示為：

其中，α為0-1間常數(shù)。由上式可知，染色體適應(yīng)度越好，期望繁殖概率越大；個(gè)體濃度越大，則期望繁殖概率越小。

4.4 選擇、交叉、變異

選擇操作采用輪盤賭的方法，依據(jù)概率選擇出染色體，染色體被選擇的概率為期望繁殖概率，如式（19）。

交叉操作可分為兩步：對兩個(gè)染色體在交叉點(diǎn)處進(jìn)行基因互換；對交叉后的染色體進(jìn)行局部調(diào)整，使得染色體滿足約束條件。交叉操作如：對兩個(gè)染色體進(jìn)行交叉處理，假設(shè)交叉位置為3。在對交叉點(diǎn)處進(jìn)行基因互換后，出現(xiàn)某些工件工序增加、或者減少的情況，對此，把工件工序多出的操作變?yōu)槿笔Р僮?，染色體后半部分不變，從而避免產(chǎn)生非法染色體：

變異操作首先在前半部分隨機(jī)選擇兩個(gè)變異點(diǎn)，然后將前半部分工件工序碼和后半部分機(jī)器設(shè)備碼的對應(yīng)位置上的基因進(jìn)行互換。例如，對某染色體選擇在位置2、3上進(jìn)行交叉變異操作：

5 算例分析

假設(shè)某生產(chǎn)車間利用5組機(jī)器設(shè)備，對6個(gè)工件進(jìn)行加工處理，每個(gè)工件均有5道工序。工件工序的可選操作設(shè)備以及對應(yīng)的加工時(shí)間如表1所示（[可選設(shè)備序號]/[對應(yīng)時(shí)間（天）]）。依據(jù)表中信息，制定調(diào)度方案。

表1 工序可選機(jī)器及對應(yīng)時(shí)間

5.1 參數(shù)設(shè)置及生成預(yù)調(diào)度方案

采用MATLAB編碼完成上述調(diào)度算法，設(shè)置種群數(shù)為40，遺傳代數(shù)為50，交叉率為0.5，變異率為0.4，記憶庫容量為10，閾值T0為0.9，期望繁殖概率中參數(shù)α為0.5。運(yùn)行該算法，得到一套預(yù)調(diào)度方案，如圖4甘特圖所示，圖中“a-b”表示裝備a的第b道工序。

圖4 預(yù)調(diào)度方案

從圖中可以清晰地了解到各道工序?qū)?yīng)的機(jī)器設(shè)備，以及開始、結(jié)束時(shí)間。在未發(fā)生擾動(dòng)情況下，加工生產(chǎn)依照圖中調(diào)度方案執(zhí)行。

5.2 生成重調(diào)度方案

基于圖4預(yù)調(diào)度方案，假設(shè)第20天機(jī)器2上出現(xiàn)故障，工序O33中斷。專家預(yù)估故障修復(fù)時(shí)間為8天，現(xiàn)需要執(zhí)行重調(diào)度得到重調(diào)度方案。

采取本文重調(diào)度方法，依據(jù)“德爾菲法”確定重調(diào)度成本函數(shù)中指標(biāo)權(quán)重 (ω1,ω2,ω3)=(0.1,0.4,0.5)，重調(diào)度目標(biāo)函數(shù)中指標(biāo)權(quán)重(μ1,μ2)=(0.3,0.7)，其他參數(shù)設(shè)置如5.1節(jié)不變。得到重調(diào)度方案如圖5，其中完全重調(diào)度的尋優(yōu)結(jié)果曲線如圖6。

圖5 重調(diào)度方案

圖6 重調(diào)度尋優(yōu)收斂曲線

在故障發(fā)生時(shí)刻，未開始進(jìn)行處理的工件工序參與了重調(diào)度。從圖中結(jié)果可以看出，部分工序所選擇操作的機(jī)器發(fā)生了變化，由此可以判斷，在重調(diào)度中完全重調(diào)度所得到的調(diào)度結(jié)果優(yōu)于部分右移重調(diào)度的調(diào)度結(jié)果，因而該方法自動(dòng)選擇了完全重調(diào)度策略所得到的重調(diào)度方案。

為了驗(yàn)證上述分析判斷，即重調(diào)度中完全重調(diào)度所得到的調(diào)度結(jié)果優(yōu)于部分右移重調(diào)度的調(diào)度結(jié)果，依據(jù)部分右移重調(diào)度策略的算法規(guī)則得到相應(yīng)的重調(diào)度方案，并計(jì)算重調(diào)度目標(biāo)函數(shù)值。重調(diào)度方案甘特圖如圖7所示。

圖7 部分右移重調(diào)度方案

從圖中可以看出，工件工序并未改變操作設(shè)備，在開始、結(jié)束時(shí)間上發(fā)生了不同程度的后移。對比圖5可以發(fā)現(xiàn)，采用右移重調(diào)度，完工時(shí)間推遲了8天；而采用完全重調(diào)度，完工時(shí)間僅推遲了2天，因而在完成時(shí)間這一指標(biāo)上完全重調(diào)度所得方案表現(xiàn)較好。通過計(jì)算，部分右移重調(diào)度相應(yīng)的重調(diào)度目標(biāo)函數(shù)值為5.47，大于完全重調(diào)度相應(yīng)的重調(diào)度目標(biāo)函數(shù)值。分析可知，雖然完全重調(diào)度所得方案在執(zhí)行成本上表現(xiàn)較差，但綜合兩方面指標(biāo)進(jìn)行計(jì)算，完全重調(diào)度所得方案表現(xiàn)更優(yōu)。

5.3 設(shè)備故障景況分析

故障不同發(fā)生時(shí)間、不同修復(fù)時(shí)長都將對重調(diào)度效果造成影響，為探究不同擾動(dòng)景況下重調(diào)度方法中兩種策略的表現(xiàn)，通過對比實(shí)驗(yàn)對兩種策略進(jìn)行比較分析。

設(shè)置4組故障發(fā)生時(shí)間（5，15，25，35（天）），4組故障修復(fù)時(shí)間（2，4，6，8（天））。在16種景況下，分別采用完全重調(diào)度策略和部分右移重調(diào)度策略進(jìn)行重調(diào)度實(shí)驗(yàn)，分別計(jì)算出重調(diào)度目標(biāo)函數(shù)值。16種景況均隨機(jī)重復(fù)10次，并計(jì)算平均值。

從圖8結(jié)果中可以看出，在晚期、微小擾動(dòng)下，部分右移重調(diào)度策略往往得到更好的重調(diào)度結(jié)果，而在早期、擾動(dòng)較大情況下，完全重調(diào)度通常能得到較好重調(diào)度結(jié)果。作為本文方法中的兩種策略，綜合使用兩種方法，彌補(bǔ)了單一方法的弊端，能夠?qū)崿F(xiàn)不同擾動(dòng)情境下，盡可能保證重調(diào)度方案的先進(jìn)性。

圖8 兩種策略重調(diào)度結(jié)果

6 結(jié)束語

本文針對設(shè)備隨機(jī)故障條件下的柔性作業(yè)車間調(diào)度問題進(jìn)行了研究，提出了一種基于組合策略的重調(diào)度方法。在重調(diào)度方法中，對重調(diào)度成本進(jìn)行了詳細(xì)分析并建立重調(diào)度成本函數(shù)，綜合運(yùn)用了兩種重調(diào)度策略，結(jié)合免疫算法對遺傳算法進(jìn)行了改進(jìn)，用于模型的求解計(jì)算。通過算例分析，驗(yàn)證了方法的可行性和有效性。結(jié)果表明，不同擾動(dòng)景況下各種策略表現(xiàn)存在差異，本文所提出方法能夠更好適應(yīng)多種景況。在后續(xù)研究中，需要進(jìn)一步挖掘設(shè)備故障的重調(diào)度策略，橫向上對其他不確定事件的重調(diào)度方法進(jìn)行研究。