考慮設(shè)備故障的Job Shop調(diào)度問(wèn)題研究

吳正佳 望 蕓 付先旺 何海洋 華 露

(1. 三峽大學(xué) 機(jī)械與動(dòng)力學(xué)院， 湖北 宜昌 443002； 2. 中國(guó)電建集團(tuán) 貴陽(yáng)勘測(cè)設(shè)計(jì)研究院有限公司， 貴陽(yáng) 550081)

?

考慮設(shè)備故障的Job Shop調(diào)度問(wèn)題研究

吳正佳1望 蕓1付先旺1何海洋2華 露1

(1. 三峽大學(xué) 機(jī)械與動(dòng)力學(xué)院， 湖北 宜昌 443002； 2. 中國(guó)電建集團(tuán) 貴陽(yáng)勘測(cè)設(shè)計(jì)研究院有限公司， 貴陽(yáng) 550081)

在實(shí)際的企業(yè)生產(chǎn)加工過(guò)程中存在許多擾動(dòng)因素，設(shè)備故障就是其中的典型．對(duì)于Job Shop中的設(shè)備故障問(wèn)題，傳統(tǒng)的調(diào)度方法主要是完全重調(diào)度和直接右移，但是對(duì)系統(tǒng)的穩(wěn)定性影響較大且效率不高．基于此，文章提出了一種新的調(diào)度策略—解碼右移策略．根據(jù)故障出現(xiàn)時(shí)間早晚、故障修復(fù)時(shí)間長(zhǎng)短以及問(wèn)題規(guī)模大小設(shè)計(jì)了8組仿真實(shí)驗(yàn)，并構(gòu)建了偏離度和延遲度兩個(gè)評(píng)價(jià)指標(biāo)對(duì)該策略的有效性進(jìn)行驗(yàn)證．實(shí)驗(yàn)結(jié)果表明解碼右移調(diào)度策略的偏離度相比于整體右移策略降低了41.45%，相比于完全重調(diào)度策略降低了69.01%；其延遲度相比于其它兩種策略有一定優(yōu)勢(shì)．

Job Shop； 設(shè)備故障； 解碼右移策略； 仿真

近10年來(lái)，考慮設(shè)備故障的Job Shop調(diào)度問(wèn)題研究已經(jīng)取得了一些進(jìn)展[1-4]．王超[5]認(rèn)為可以將設(shè)備故障按大小分為兩種情況，當(dāng)出現(xiàn)大故障時(shí)，將故障設(shè)備直接退出調(diào)度；當(dāng)出現(xiàn)小故障時(shí)，等待設(shè)備修復(fù)后再投入生產(chǎn)．劉琳[6]提出了空閑時(shí)間插入法，首先生成一個(gè)初始調(diào)度順序，然后根據(jù)工件和故障的特征插入相應(yīng)的空閑時(shí)間，以吸收故障對(duì)原調(diào)度的影響．Alpay[7]則認(rèn)為，在擾動(dòng)發(fā)生時(shí)，如果只是重新調(diào)度直接或間接受擾動(dòng)影響的工件，能夠有效地減少生產(chǎn)周期，同時(shí)也能減少重調(diào)度與預(yù)調(diào)度的偏差．張利平[8]設(shè)計(jì)出帶空閑時(shí)間的預(yù)-反應(yīng)策略，該策略對(duì)小規(guī)模的新工件車間有較好的效率和穩(wěn)定性．對(duì)于Job Shop調(diào)度過(guò)程中出現(xiàn)的設(shè)備故障問(wèn)題，現(xiàn)有的解決方法主要分為直接右移[9]和完全重調(diào)度兩種[10]，但是這兩種策略的調(diào)度效果并不令人滿意．完全重調(diào)度由于要重新對(duì)所有工件進(jìn)行調(diào)度，導(dǎo)致系統(tǒng)的穩(wěn)定性很低；直接右移由于要等待設(shè)備修復(fù)完成，造成了時(shí)間的浪費(fèi)，效率不高．

基于上述分析，本文提出了一種解碼右移調(diào)度策略，該策略的主要思路為：從故障發(fā)生時(shí)刻開(kāi)始對(duì)預(yù)調(diào)度方案重新解碼，保證工件的加工順序不變，只是將工件向右移動(dòng)一定距離，以獲得最優(yōu)調(diào)度方案．設(shè)計(jì)實(shí)驗(yàn)仿真將解碼右移策略、直接右移和完全調(diào)度策略進(jìn)行對(duì)比，驗(yàn)證解碼右移調(diào)度策略的有效性，為實(shí)際的生產(chǎn)調(diào)度提供一定的指導(dǎo)意見(jiàn)．

1 Job Shop調(diào)度問(wèn)題模型

Job Shop調(diào)度一般描述為n個(gè)工件{J1，J2，…，Jn}在m臺(tái)設(shè)備{M1，M2，…，Mm}上加工，每一個(gè)工件有p道工序，用Oij表示第i個(gè)工件的第j道工序，各工序之間的加工路線相互獨(dú)立．表1是3個(gè)工件在3臺(tái)設(shè)備上加工的Job Shop調(diào)度問(wèn)題的實(shí)例．

表1 某Job Shop調(diào)度問(wèn)題的加工時(shí)間表

Job Shop的調(diào)度目標(biāo)是確定各個(gè)設(shè)備上每個(gè)工件的加工順序，并確定每道工序開(kāi)始加工的時(shí)間，使得系統(tǒng)的調(diào)度目標(biāo)達(dá)到最優(yōu)．本文結(jié)合生產(chǎn)實(shí)際，從最大完工時(shí)間f1和拖期懲罰f2兩個(gè)方面來(lái)構(gòu)建目標(biāo)函數(shù)：

(1)

(2)

(3)

其中，Ck是第k臺(tái)設(shè)備上所有工件完成加工的時(shí)間，Ci是第i個(gè)工件所有工序完成加工的時(shí)間，Di是工件Ji的交貨期．如果工件Ji完成加工的時(shí)間大于交貨期，則需要受到拖期懲罰，用δi表示拖期懲罰系數(shù)．式(3)表示總目標(biāo)f為兩個(gè)目標(biāo)函數(shù)值求和．

此外，在加工的過(guò)程中需要滿足以下約束：1)各個(gè)工件的加工路線是固定的，不能做任何改變；2)在任意時(shí)刻，一臺(tái)設(shè)備只能進(jìn)行一道工序的加工；3)在任意時(shí)刻，一個(gè)工件只能占用一臺(tái)設(shè)備加工；4)同一工件不同工序間應(yīng)該有先后順序的約束．

2 考慮設(shè)備故障的解碼右移策略

解碼右移策略的關(guān)鍵是確定故障發(fā)生時(shí)設(shè)備的工件是否完成了解碼．如果工件已完成解碼，則保持其加工信息(工件開(kāi)始加工的時(shí)間等)不變；如果工件未完成解碼，則按照原調(diào)度方案繼續(xù)解碼，只是故障發(fā)生后第一個(gè)加工的工件的開(kāi)始加工時(shí)間有所改變．本文對(duì)上述兩種情況分別進(jìn)行討論，流程圖如圖1所示．

圖1 解碼右移調(diào)度策略流程圖

假設(shè)故障發(fā)生時(shí)刻為T(mén)，修復(fù)時(shí)間r．如果故障設(shè)備M正在加工，設(shè)加工工件Xij，其預(yù)調(diào)度方案中的開(kāi)始加工時(shí)間SMxij，完工時(shí)間CMxij；如果發(fā)生在空閑時(shí)間，假設(shè)設(shè)備M發(fā)生故障后第一個(gè)加工的工件是Yij，其預(yù)調(diào)度方案中的開(kāi)始加工時(shí)間是SMyij．

1) 故障發(fā)生時(shí)設(shè)備M正在加工

假設(shè)所有工序的加工是可間斷的，則以故障點(diǎn)為分界點(diǎn)，工件Xij后續(xù)部分的開(kāi)始加工時(shí)間Ts為：

(4)

此工件在故障設(shè)備上剩余部分的加工時(shí)間tsx：

(5)

(6)

該狀態(tài)下故障設(shè)備的下一個(gè)工件最早開(kāi)始加工時(shí)間Tsij為：

(7)

由上式可知，若下一個(gè)加工的工件是其第一道工序，則最早開(kāi)始加工時(shí)間相當(dāng)于在前一個(gè)工件的完工時(shí)間上延長(zhǎng)設(shè)備修復(fù)時(shí)間長(zhǎng)度；若下一個(gè)加工的工件不是其第一道工序，則需將前一個(gè)工件的實(shí)際完工時(shí)間與下一個(gè)工件的前道工序完成時(shí)間Tei(j-1)作比較．

2)故障發(fā)生時(shí)設(shè)備M為空閑

故障發(fā)生時(shí)刻到下一個(gè)工件開(kāi)始加工之間的時(shí)間間隔tsy為：

(8)

(9)

由上式可知，在此狀態(tài)下，下一個(gè)工件的最早開(kāi)始時(shí)間相當(dāng)于在故障時(shí)刻延長(zhǎng)了修復(fù)時(shí)間的長(zhǎng)度．

為了驗(yàn)證此調(diào)度策略的可行性，本文從企業(yè)最為關(guān)注的調(diào)度穩(wěn)定性和調(diào)度效率兩個(gè)角度出發(fā)，構(gòu)建偏離度和延遲度兩個(gè)評(píng)價(jià)指標(biāo)對(duì)調(diào)度結(jié)果進(jìn)行評(píng)價(jià)．

①偏離度，用來(lái)表示調(diào)度策略的穩(wěn)定性：

(10)

②延遲度，表征調(diào)度策略的效率：

(11)

3 遺傳算法在Job Shop調(diào)度問(wèn)題中的應(yīng)用

遺傳算法(genetic algorithm , GA)在1975年被美國(guó)的Holland教授首次提出，他借鑒了生物界適者生存、優(yōu)勝劣汰的遺傳機(jī)制，通過(guò)模擬自然進(jìn)化過(guò)程來(lái)搜索最優(yōu)解．遺傳算法由于其全局優(yōu)化搜索能力強(qiáng)、搜索效率高等優(yōu)勢(shì)被廣泛應(yīng)用于Job Shop調(diào)度問(wèn)題的求解中．針對(duì)Job Shop調(diào)度問(wèn)題的特點(diǎn)，本文采用基于工序的編碼方式，隨機(jī)生成初始解，經(jīng)過(guò)輪盤(pán)賭選擇、單點(diǎn)交叉與插入變異，通過(guò)判斷是否滿足優(yōu)化規(guī)則來(lái)終止計(jì)算，得到最終調(diào)度方案．算法流程如圖2所示．

圖2 遺傳算法流程圖

Step 1：設(shè)計(jì)編碼與解碼

編碼和解碼是使用遺傳算法的首要問(wèn)題，它是指染色體與調(diào)度解之間的轉(zhuǎn)換．由于不同的工序?qū)?yīng)不同的加工時(shí)間，所以在設(shè)計(jì)編碼方式時(shí)要基于工序，染色體上的每一個(gè)基因代表每一道工序．在編碼染色體中，用工序所在的工件號(hào)來(lái)表示，工件號(hào)第k次出現(xiàn)即表示該工件的第k道工序．以表1中的加工實(shí)例，若設(shè)計(jì)的染色體為1-2-2-3-1-2-3-1-3，則對(duì)應(yīng)工序的加工順序?yàn)镺11-O21-O22-O31-O12-O23-O32-O13-O33．

解碼即根據(jù)染色體得到工序的加工順序．對(duì)于Job Shop調(diào)度問(wèn)題，當(dāng)對(duì)某一道工序進(jìn)行加工時(shí)，需要滿足兩個(gè)條件：一是該工序的前道工序已經(jīng)加工完成；二是該加工機(jī)器已完成上一個(gè)工件的加工．

Step 2：初始化

遺傳算法的第一步是產(chǎn)生初始染色體，即初始化．選擇應(yīng)用廣泛、操作簡(jiǎn)單的隨機(jī)初始化方式．隨機(jī)生成初始加工順序，即為初始染色體．

Step 3：選擇操作

設(shè)計(jì)適應(yīng)度函數(shù)對(duì)染色體的適應(yīng)度值計(jì)算之后，就要選擇適應(yīng)度較好的個(gè)體遺傳．目前研究中最常見(jiàn)的有輪盤(pán)賭與錦標(biāo)賽方法，由于輪盤(pán)賭方式運(yùn)用了概率的思想，適應(yīng)度大的個(gè)體被選擇的幾率較大，很好地印證了生物學(xué)中“適者生存”的思想，故使用輪盤(pán)賭方法進(jìn)行選擇．

Step 4：交叉操作

為了得到適應(yīng)度更高的個(gè)體，在選擇之后通常還要進(jìn)行交叉操作．本文采用選擇單點(diǎn)交叉方式，在父代染色體中隨機(jī)產(chǎn)生一個(gè)點(diǎn)，以點(diǎn)為界將染色體分為J1和J2兩部分，子代C1繼承父代P1的J1部分和父代P2的J2部分，C1則繼承P2的J1部分和P1的J2部分．

圖3 單點(diǎn)交叉示意圖

Step 5：變異操作

變異的目的是加快收斂速度，同時(shí)避免陷入局部最優(yōu)．設(shè)計(jì)變異方法時(shí)應(yīng)該考慮到越大的擾動(dòng)對(duì)原有調(diào)度解的影響越大，越能幫助跳出局部區(qū)域，所以較好的變異方式是能較大地改變?cè)腥旧w的排列方式．本文采用插入變異方式，隨機(jī)選擇一段基因插入到染色體中的一個(gè)隨機(jī)位置，染色體中其它基因位置保持不變．

圖4 插入變異示意圖

4 實(shí)驗(yàn)仿真

4.1 參數(shù)設(shè)定

1)問(wèn)題規(guī)模：?jiǎn)栴}分為小規(guī)模和大規(guī)模兩種，分別是6×6和10×10標(biāo)準(zhǔn)案例．

2)擾動(dòng)時(shí)間：擾動(dòng)時(shí)間分為早和晚，其中較早時(shí)間以總完工時(shí)間1/3時(shí)刻為例，較晚時(shí)間以總完工時(shí)間2/3時(shí)刻為例．

3)擾動(dòng)程度：用故障修復(fù)時(shí)間來(lái)衡量擾動(dòng)程度，分為高(修復(fù)時(shí)間為完工時(shí)間的30%)和低(修復(fù)時(shí)間為完工時(shí)間的3%)兩種．

運(yùn)用控制變量法分別固定以上3種變量，共設(shè)計(jì)了8組實(shí)驗(yàn)，實(shí)驗(yàn)內(nèi)容見(jiàn)表2．

表2 仿真實(shí)驗(yàn)內(nèi)容

4.2 仿真結(jié)果

以實(shí)驗(yàn)1為例，使用遺傳算法對(duì)6×6規(guī)模問(wèn)題進(jìn)行求解，生成甘特圖如圖5所示．

圖5 6×6初始調(diào)度甘特圖

假定故障設(shè)備為2，故障時(shí)刻為2，修復(fù)時(shí)間為16，使用解碼右移策略進(jìn)行調(diào)度，遺傳算法求解，得到的甘特圖如圖6所示．

圖6 6×6解碼右移策略甘特圖

分別使用3種調(diào)度策略對(duì)8個(gè)實(shí)驗(yàn)進(jìn)行調(diào)度仿真，得到的結(jié)果見(jiàn)表3和表4．

表3 不同調(diào)度策略仿真結(jié)果(偏離度)

表4 不同調(diào)度策略仿真結(jié)果(延遲度)

1)對(duì)比不同組實(shí)驗(yàn)的結(jié)果

不論是偏離度還是延遲度，可以發(fā)現(xiàn)都是第3組的實(shí)驗(yàn)值最小，第6組的實(shí)驗(yàn)值最大，這說(shuō)明偏離度和延遲度都是隨著問(wèn)題規(guī)模的由小到大、擾動(dòng)時(shí)間的由晚到早、擾動(dòng)程度的由低到高而增大的．

為了進(jìn)一步驗(yàn)證上述結(jié)論，分別比較兩個(gè)表中的1和5，2和6，3和7，4和8組實(shí)驗(yàn)，發(fā)現(xiàn)在相同的擾動(dòng)時(shí)間和干擾程度下，大規(guī)模問(wèn)題的偏離度和延遲度均高于小規(guī)模問(wèn)題，這是因?yàn)榇笠?guī)模問(wèn)題所要調(diào)度的工件較多，所以會(huì)對(duì)其產(chǎn)生較大的影響；比較1和3，2和4，5和7，6和8組實(shí)驗(yàn)，發(fā)現(xiàn)在相同的調(diào)度規(guī)模和干擾程度下，擾動(dòng)出現(xiàn)越晚，偏離度和延遲度越小，這是由于擾動(dòng)出現(xiàn)晚意味著故障發(fā)生在靠后的階段，前面已經(jīng)加工完成了很多工件，需要移動(dòng)的工件較少；比較1和2，3和4，5和6，7和8組實(shí)驗(yàn)，發(fā)現(xiàn)在相同調(diào)度規(guī)模和擾動(dòng)時(shí)間下，干擾程度高的偏離度和延遲度要高于干擾程度低的，由于干擾程度低即設(shè)備出現(xiàn)故障后能夠很快得到修復(fù)，所以對(duì)調(diào)度造成的影響較小．

2)對(duì)比不同調(diào)度策略的結(jié)果

不同調(diào)度策略之間的偏離度有很大的差別，解碼右移策略的偏離度明顯優(yōu)于其它兩種策略，其平均值相對(duì)于整體右移策略降低了41.45%，相對(duì)于完全重調(diào)度策略降低了69.01%；然而不同調(diào)度策略之間的延遲度差別不是很大，解碼右移策略的延遲度和其它兩種策略相比有一定的優(yōu)勢(shì)．

5 結(jié) 論

1)相比于靜態(tài)調(diào)度，考慮設(shè)備故障的實(shí)時(shí)調(diào)度能夠根據(jù)車間的實(shí)際加工情況迅速做出反應(yīng)，從而達(dá)到較高的效率和穩(wěn)定性．

2)在相同的擾動(dòng)時(shí)間和干擾程度下，規(guī)模較大的調(diào)度出現(xiàn)設(shè)備故障時(shí)受到的影響更大；在相同的調(diào)度規(guī)模和干擾程度下，設(shè)備故障出現(xiàn)較早對(duì)調(diào)度系統(tǒng)會(huì)造成更嚴(yán)重的影響；在相同調(diào)度規(guī)模和擾動(dòng)時(shí)間下，干擾程度高的設(shè)備故障造成的影響更大．

3)在效率一定的情況下，解碼右移策略的穩(wěn)定性相比于其它兩種策略都有很大的優(yōu)勢(shì)；在穩(wěn)定性一定的情況下，解碼右移策略的效率相比于其它兩種策略有一定優(yōu)勢(shì)．

[1] Rahmati Seyed Habib A, Zandieh M. A New Biogeography-Based Optimization (BBO) Algorithm for the Flexible Job Shop Scheduling Problem[J]． International Journal of Advanced Manufacturing Technology， 2012, 58(9-12)：1115-1129．

[2] Rajabinasab Amir, Mansour Saeed. Dynamic Flexible Job Shop Scheduling with Alternative Process Plans： an Agent-based Approach[J]．International Journal of Advanced Manufacturing Technology， 2011, 54(9-12)： 1091-1107．

[3] Moradi E, Ghomi S， Fatemi M T， et al． An Efficient Architecture for Scheduling Flexible Job-shop with Machine Availability Constraints[J]． International Journal of Advanced Manufacturing Technology， 2010, 51(1-4)：325-339．

[4] Al-Hinai Nasr, ElMekkawy T Y. A Efficient Hybridized Genetic Algorithm Architecture for the Flexible Job Shop Scheduling Problem[J]． Flexible Services and Manufacturing Journal 2011, 23(1)：64-85．

[5] 王 超. 基于Petri網(wǎng)的Job Shop調(diào)度問(wèn)題研究[D]．北京：北京交通大學(xué),2011．

[6] 劉 琳. 動(dòng)態(tài)不確定環(huán)境下生產(chǎn)調(diào)度算法研究[D]．上海：上海交通大學(xué),2007．

[7] Alpay S, Yuzugullu N. Dynamic Job Shop Scheduling for Missed Due Date Performance[J]． International Journal of Production Research, 2009, 47(15)： 4047-4062．

[8] 張利平. 作業(yè)車間預(yù)反應(yīng)式動(dòng)態(tài)調(diào)度理論與方法研究[D]．武漢：華中科技大學(xué),2013．

[9] Kamoun H,Sriskandarajah C.The Complexity of Scheduling Jobs in Repetitive Manufacturing Systems[J]． European Journal of Operation Research.1993, 70(3)：350-364．

[10] Jain A K， Elmaraghy H A. Production Scheduling-Rescheduling in Flexible Manufacturing[J]． International Journal of Production Research, 1997, 35(1)：281-309．

[責(zé)任編輯 張 莉]

Research on Job Shop Scheduling Problem Considering Machine Faults

Wu Zhengjia1Wang Yun1Fu Xianwang1He Haiyang2Hua Lu1

(1. College of Mechanical & Power Engineering, China Three Gorges Univ., Yichang 443002, China； 2. Guiyang Survey & Design Institute Co., Ltd., China Electric Power Construction Group, Guiyang 550081, China)

There are many disturbing factors in the actual production process; the machine fault is one of the typical factors. To solve the machine failure of Job Shop problem, the traditional scheduling methods are completely rescheduling and direct right. However, they have greater impact of the system and low efficiency. In light of this, the paper proposes a new scheduling strategy, i.e. decoding right scheduling. 8 simulations are designed about downtime, trouble-shooting time and scale of the problem and two evaluation of deviation and delay are constructed in order to verify the effectiveness of the strategy. The results show that the deviation of decoding right scheduling decreases 41.45% compared with direct right strategy and decreases 69.01% compared with completely rescheduling strategy; and its delay has certain advantages compared with other two methods.

Job Shop; machine fault; decoding right strategy; simulation

10.13393/j.cnki.issn.1672-948X.2016.05.019

2016-05-20

湖北省自然科學(xué)基金資助項(xiàng)目(ZRY2014001091)

吳正佳(1964-)，男，教授，博士，研究方向?yàn)橄冗M(jìn)制造企業(yè)信息系統(tǒng)分析與集成、智能算法理論、設(shè)備綜合管理與檢測(cè)．E-mail：zjwu@ctgu.edu.cn

TH166

A

1672-948X(2016)05-0098-05