王建軍，劉曉盼，劉 鋒，王杜娟

(1. 大連理工大學(xué)系統(tǒng)工程研究所，遼寧 大連 116023；2. 東北財(cái)經(jīng)大學(xué)管理科學(xué)與工程學(xué)院，遼寧 大連 116025)

?

隨機(jī)機(jī)器故障下加工時(shí)間可控的并行機(jī)魯棒調(diào)度

王建軍1，劉曉盼1，劉 鋒2，王杜娟1

(1. 大連理工大學(xué)系統(tǒng)工程研究所，遼寧 大連 116023；2. 東北財(cái)經(jīng)大學(xué)管理科學(xué)與工程學(xué)院，遼寧 大連 116025)

現(xiàn)實(shí)生產(chǎn)環(huán)境中經(jīng)常面臨隨機(jī)機(jī)器故障，造成初始調(diào)度方案性能惡化。針對(duì)并行機(jī)環(huán)境下工件加工時(shí)間可控，提出內(nèi)外兩層嵌套式的魯棒調(diào)度策略，旨在降低隨機(jī)機(jī)器故障造成的成本損失期望，干擾發(fā)生后通過局部修復(fù)實(shí)現(xiàn)跟初始計(jì)劃的匹配。內(nèi)層建立非線性0-1混合整數(shù)規(guī)劃模型，通過二次錐化方法來求解初始調(diào)度方案在隨機(jī)機(jī)器故障干擾情景下的成本損失期望。外層設(shè)計(jì)基于工件柔性和機(jī)器不可用概率的排序算法；由于問題內(nèi)在的復(fù)雜性，利用遺傳算法優(yōu)化工件柔性參數(shù)，進(jìn)而增強(qiáng)初始調(diào)度方案的魯棒性。最后設(shè)計(jì)隨機(jī)仿真實(shí)驗(yàn)，分別驗(yàn)證了在機(jī)器故障所造成的單位時(shí)間擾動(dòng)成本不同時(shí)和機(jī)器維修水平不同時(shí)所提魯棒調(diào)度策略的有效性。

魯棒調(diào)度；并行機(jī)；加工時(shí)間可控；隨機(jī)機(jī)器故障；匹配

1 引言

制造企業(yè)實(shí)際生產(chǎn)過程中往往面臨諸多不確定性因素，如機(jī)器故障、訂單變更等干擾事件，這些干擾事件常常造成初始調(diào)度方案執(zhí)行不暢、效率低下、甚至不再可行[1]。面對(duì)不確定性事件造成的負(fù)面影響，如何制定出具有較強(qiáng)抗干擾能力的魯棒調(diào)度方案已成為生產(chǎn)調(diào)度干擾管理領(lǐng)域研究的一個(gè)熱點(diǎn)問題[2]。

隨機(jī)機(jī)器故障是生產(chǎn)加工系統(tǒng)中最為常見和重要的一類干擾事件[3]。目前，在隨機(jī)機(jī)器故障干擾下的魯棒調(diào)度問題已受到學(xué)術(shù)界的廣泛關(guān)注[4-9,12-13]。如針對(duì)加工時(shí)間固定的情形，通常采用的魯棒調(diào)度方法為插入空閑時(shí)間，即在相鄰工件之間插入一段緩沖時(shí)間來吸收隨機(jī)機(jī)器故障造成的擾動(dòng)。該方法首次由Mehta等[4]提出，并利用該方法有效降低了車間作業(yè)環(huán)境下機(jī)器故障導(dǎo)致的工件最大延遲時(shí)間?；诓迦肟臻e時(shí)間的思想，尹文君等[5]采用雙子樹結(jié)構(gòu)編碼的遺傳編碼系統(tǒng)，使工件排序和空閑時(shí)間插入過程有效融合，獲得拖期性能和預(yù)測能力較好的單機(jī)魯棒調(diào)度。李巧云等[6]則提出通過閾值來控制空閑時(shí)間插入與否，使得空閑時(shí)間得到充分利用。同樣是單機(jī)環(huán)境，Liu 等[7]在優(yōu)化初始調(diào)度性能的基礎(chǔ)上，考慮干擾發(fā)生后新舊計(jì)劃偏差，從而轉(zhuǎn)化為雙目標(biāo)問題，并提出兩階段多種群遺傳算法求解。而Al-Hinai等[8]將問題擴(kuò)展到柔性作業(yè)車間，并設(shè)計(jì)混合遺傳算法進(jìn)行了求解。雖然插入空閑時(shí)間能夠吸收機(jī)器故障造成的負(fù)面影響，使初始調(diào)度方案具有較好的魯棒性，但該方法往往會(huì)造成機(jī)器低效率利用[9]。

現(xiàn)實(shí)中機(jī)器資源往往是有限的，而且工件加工時(shí)間可以通過增加成本方式壓縮控制[10]，此時(shí)插入空閑時(shí)間則需要增加額外的壓縮費(fèi)用而不再適用。針對(duì)加工時(shí)間可控的情形，Akturk等[11]在并行機(jī)環(huán)境下通過壓縮工件加工時(shí)間的方式，使得某一時(shí)刻后新舊加工時(shí)間表能夠匹配，從而有效降低了機(jī)器故障帶來的擾動(dòng)。同樣是并行機(jī)環(huán)境，Gurel等[12]考慮到在擾動(dòng)時(shí)間限定條件下，不同的初始加工排序會(huì)產(chǎn)生不同的壓縮成本。采用將柔性較好，即吸收干擾能力較強(qiáng)的工件安排在機(jī)器不可用概率較高時(shí)間段的方式進(jìn)行工件排序，有效降低了因機(jī)器故障而增加的壓縮成本，并在各機(jī)器故障發(fā)生時(shí)刻和維修時(shí)間服從相同分布情況下獲得魯棒性較好的初始調(diào)度方案。Gurel等[12]中的排序策略相同，劉鋒等[13]研究了單機(jī)環(huán)境下的初始加工時(shí)間表制定問題，并通過遺傳算法確定柔性參數(shù)的方式對(duì)工件柔性度量進(jìn)行了改進(jìn)。

除上述文獻(xiàn)在初始調(diào)度方案制定時(shí)，考慮不確定性因素，從而獲得抗干擾能力較強(qiáng)的魯棒調(diào)度外；在執(zhí)行過程中制定有效的動(dòng)態(tài)調(diào)度也可以提高調(diào)度的魯棒性[14]。Tang Lixin等[15]研究了煉鋼-連鑄生產(chǎn)過程中發(fā)生隨機(jī)干擾事件后的動(dòng)態(tài)調(diào)度問題，通過改進(jìn)差分進(jìn)化算法對(duì)加工時(shí)間表重新優(yōu)化排序。實(shí)際中調(diào)度方案制定往往是多目標(biāo)決策，F(xiàn)elix等[16]針對(duì)油輪在運(yùn)集和配送地點(diǎn)處的動(dòng)態(tài)調(diào)度問題，就運(yùn)輸成本最小化和服務(wù)水平最大化兩個(gè)目標(biāo)，利用改進(jìn)多目標(biāo)蟻群優(yōu)化算法獲得較好的有效前沿解。與前者調(diào)度方案生成不同，Shen Xiaoning等[17]研究了柔性作業(yè)車間下的動(dòng)態(tài)調(diào)度問題，提出基于預(yù)測-反應(yīng)式的多目標(biāo)進(jìn)化算法，并結(jié)合決策者偏好建立數(shù)學(xué)模型來確定調(diào)度方案。

由文獻(xiàn)綜述可知，第一，加工時(shí)間可控情形下的魯棒調(diào)度研究相對(duì)較少且成本損失僅考慮了壓縮費(fèi)用，并未考慮因“中斷-重復(fù)”操作造成的資源浪費(fèi)和給其它生產(chǎn)活動(dòng)造成的損失，而該些費(fèi)用普遍存在于生產(chǎn)實(shí)踐[18]。第二，雖然在制定魯棒調(diào)度中應(yīng)用到機(jī)器故障概率分布信息，但未考慮各機(jī)器由于進(jìn)廠日期、使用生命周期及歷史磨損程度不同等原因而導(dǎo)致的故障發(fā)生概率及其分布函數(shù)的差異性[19]?；谝陨蟽牲c(diǎn)研究不足，本文針對(duì)最一般平行機(jī)環(huán)境——并行機(jī)下機(jī)器加工能力有限且工件加工時(shí)間可控問題，提出內(nèi)外兩層嵌套式的魯棒調(diào)度策略，旨在有效降低隨機(jī)故障給生產(chǎn)加工系統(tǒng)帶來的成本損失期望，獲得具有魯棒性的初始調(diào)度方案。

2 問題描述

如圖1所示，機(jī)器發(fā)生故障后考慮“中斷-重復(fù)”操作，即被機(jī)器故障強(qiáng)制中斷加工的工件需要重新加工[13]。因機(jī)器故障和“中斷-重復(fù)”操作使機(jī)器可用加工時(shí)間減少，為完成加工任務(wù)而需要壓縮未完工工件的加工時(shí)間，同時(shí)可能造成機(jī)器工件的重新分配[22]。在此過程中考慮系統(tǒng)成本損失最小化。一方面是與調(diào)度本身相關(guān)的損失ΔC，主要包括“中斷-重復(fù)”造成的資源浪費(fèi)和加工時(shí)間壓縮所增加的成本；另一方面是機(jī)器故障給其它相關(guān)生產(chǎn)活動(dòng)造成的損失h·ΔT，其中ΔT為各機(jī)器擾動(dòng)時(shí)間段之和，h為單位時(shí)間擾動(dòng)給其它相關(guān)生產(chǎn)活動(dòng)造成的損失。而以系統(tǒng)成本損失最小化為目標(biāo)的重調(diào)度模型(RSM)將在4.2節(jié)詳細(xì)闡述。

圖1 初始調(diào)度方案與局部重調(diào)度方案甘特圖

本文的研究目的是獲得具有魯棒性的初始調(diào)度方案，降低隨機(jī)機(jī)器故障造成的系統(tǒng)成本損失期望。常見的魯棒性度量是實(shí)際調(diào)度性能與計(jì)劃調(diào)度之間偏差的期望指標(biāo)。然而故障發(fā)生時(shí)刻和維修時(shí)間在未發(fā)生前都是未知[7]，因此根據(jù)機(jī)器發(fā)生故障的概率及其概率分布信息來模擬機(jī)器故障發(fā)生的情景，魯棒性度量則采用調(diào)度性能期望[23-24]。此處為系統(tǒng)成本損失期望：E(ΔC+h·ΔT)，其對(duì)應(yīng)決策者為風(fēng)險(xiǎn)中性類型。系統(tǒng)成本損失期望越小，則代表初始調(diào)度方案魯棒性越好。

3 機(jī)器工件分配模型

為獲得魯棒調(diào)度，首先是以加工成本最小化為目標(biāo)確定機(jī)器工件的分配，即確定每臺(tái)機(jī)器所要加工的工件以及各工件加工時(shí)間的壓縮量。定義0-1變量xij，若工件j在機(jī)器i上加工則xij=1，否則xij=0。連續(xù)變量yij是工件j在機(jī)器i上加工時(shí)的加工時(shí)間壓縮量。從而機(jī)器工件分配模型可以用以下非線性0-1混合整數(shù)規(guī)劃模型表示：

(1)

uijxij≥yij≥0,i=1,…,m,j=1,…n

(2)

(3)

xij∈{0,1},yij∈R+,i=1,…,m,j=1,…,n

(4)

其中約束(1)保證分配到機(jī)器i上的工件加工時(shí)間之和不超過機(jī)器可用加工時(shí)間段Di；約束(2)表示只有工件j在機(jī)器i上加工，即xij=1時(shí)，加工時(shí)間pij才可能被壓縮且壓縮量滿足0≤yij≤uij；約束(3)表示各工件只能在一臺(tái)機(jī)器上加工；約束(4)是對(duì)變量xij,yij的取值范圍限制。

當(dāng)模型中uij=0時(shí)模型MJ0為一般意義上的指派問題，非線性壓縮成本函數(shù)f(y)=kya/b使模型求解難度加大，通過文獻(xiàn)[20]可知，上述數(shù)學(xué)模型為NP難問題。即使非線性函數(shù)為二次函數(shù)時(shí)利用現(xiàn)有商業(yè)軟件求解較大規(guī)模的問題也具有一定的挑戰(zhàn)性。為了有效求解該問題，首先引入變量tij將非線性目標(biāo)轉(zhuǎn)換為約束條件，如模型MJ1所示：

(5)

(5′)

此時(shí)便可利用ILOGCPLEX12.4版本求解器進(jìn)行建模求解，其有效性已在文獻(xiàn)[20]中得以證明。

4 工件次序確定模型

在確定機(jī)器工件分配后，進(jìn)一步需要確定每臺(tái)機(jī)器上的工件加工次序。為此，設(shè)計(jì)了如圖2所示內(nèi)外兩層嵌套結(jié)構(gòu)的工件次序確定模型，內(nèi)層結(jié)構(gòu)主要用來計(jì)算初始調(diào)度方案的魯棒性度量，即系統(tǒng)成本損失期望E(ΔC+h·ΔT)；外層結(jié)構(gòu)則是對(duì)初始調(diào)度方案的優(yōu)化。該模型由初始調(diào)度模塊、預(yù)案反應(yīng)模塊、遺傳優(yōu)化模塊三個(gè)子模塊構(gòu)成。首先調(diào)用初始調(diào)度模塊，將柔性較好的工件安排在機(jī)器不可用概率較高時(shí)間段，從而由工件柔性度量轉(zhuǎn)化為工件加工次序；然后調(diào)用預(yù)案反應(yīng)模塊，計(jì)算給定工件加工次序在N種干擾情景下的系統(tǒng)成本損失期望；最后通過遺傳算法模塊優(yōu)化工件柔性度量，進(jìn)而達(dá)到優(yōu)化工件加工次序，增強(qiáng)魯棒性的目的。上述三個(gè)子模塊的具體實(shí)現(xiàn)將在下面分別闡述。

圖2 工件次序確定模型

第二步則依據(jù)機(jī)器i的故障發(fā)生時(shí)刻及維修時(shí)間概率分布情況，依概率隨機(jī)產(chǎn)生ni次干擾事件。

4.1 初始調(diào)度模塊

初始調(diào)度模塊主要是基于機(jī)器不可用概率分布函數(shù)，將柔性較好的工件安排到機(jī)器不可用概率較高的加工時(shí)間段，制定出初始加工時(shí)間表。其中機(jī)器不可用概率是指在t時(shí)刻或之前發(fā)生機(jī)器故障而導(dǎo)致t時(shí)刻機(jī)器不可用的概率。

(1)工件柔性度量指標(biāo)及計(jì)算

指標(biāo)1：工件剩余可壓縮量wj，計(jì)算公式為：

指標(biāo)2：壓縮成本函數(shù)的平均坡度Δj，反映工

件進(jìn)一步壓縮的過程中平均單位壓縮成本。該值越小，壓縮成本越小，柔性越好。計(jì)算公式為：

指標(biāo)5：工件在機(jī)器間轉(zhuǎn)移的最小成本LBj，設(shè)λi1和λi2分別表示機(jī)器i1和i2上工件的一階導(dǎo)數(shù)，即工件邊際壓縮成本。則工件從機(jī)器i1轉(zhuǎn)移到機(jī)器i2上加工所發(fā)生的轉(zhuǎn)移成本為：

機(jī)器間轉(zhuǎn)移成本越小，干擾發(fā)生時(shí)工件移到其它機(jī)器上加工所付出代價(jià)越小，即柔性越好。由于本文所研究環(huán)境為并行機(jī)，因此最小轉(zhuǎn)移成本為：

以上五個(gè)柔性指標(biāo)分別從不同角度反映工件柔性，根據(jù)與工件柔性正負(fù)向關(guān)系，采用線性加權(quán)方式對(duì)工件柔性進(jìn)行度量。柔性參數(shù)αi∈[0,1]，將通過4.3中遺傳優(yōu)化模塊進(jìn)行確定和優(yōu)化。

(2)機(jī)器不可用概率分布函數(shù)

研究故障發(fā)生時(shí)刻及維修時(shí)間分別服從指數(shù)分布且不同機(jī)器故障分布函數(shù)不同的情況。記機(jī)器i發(fā)生故障的概率pi，故障發(fā)生時(shí)刻分別服從參數(shù)為λi的指數(shù)分布，進(jìn)而可得生產(chǎn)加工車間故障發(fā)生時(shí)刻x所服從的概率密度函數(shù)為：

同時(shí)記加工車間的維修時(shí)間y服從參數(shù)為λy的指數(shù)分布，則由文獻(xiàn)[12]可知在t時(shí)刻或之前發(fā)生故障而使t時(shí)刻出現(xiàn)機(jī)器不可用概率密度函數(shù)為：

下面給出機(jī)器不可用概率密度函數(shù)Pd(t)為單峰函數(shù)的簡單證明。

首先，機(jī)器發(fā)生故障的概率密度函數(shù)fx(x)為多個(gè)指數(shù)分布函數(shù)線性加權(quán)和，因此可得fx(x)為單調(diào)遞減函數(shù)，即單峰函數(shù)且在0處取得最大值。其次，根據(jù)文獻(xiàn)[12]中引理3.2當(dāng)fx(x)在[0,+∞)上為單峰函數(shù)且有最大值時(shí)，相應(yīng)機(jī)器不可用概率密度函數(shù)Pd(t)在[0,+∞)區(qū)間也為單峰函數(shù)。因此可證機(jī)器不可用概率Pd(t)是單峰函數(shù)。

(3)基于機(jī)器不可用概率分布的工件排序算法

在確定工件柔性度量和機(jī)器不可用概率之后，需要將柔性較好的工件安排在機(jī)器不可用概率較高的時(shí)間段來確定各機(jī)器上工件加工次序。為此設(shè)計(jì)了如下工件排序算法，具體步驟如下：

步驟1：令ts=0,te=Di，同時(shí)將本機(jī)器上加工工件按照柔性從小到大的順序依次排列。

步驟2：取柔性最小工件j及其加工時(shí)間pj，

分別計(jì)算當(dāng)其排到左邊和右邊時(shí)的機(jī)器不可用概率，計(jì)算公式為：

步驟3：若Pleft

步驟4：檢查是否還有剩余未安排工件，如果有則返回步驟2，否則結(jié)束。

4.2 預(yù)案反應(yīng)模塊

預(yù)案反應(yīng)模塊主要是計(jì)算機(jī)器故障給系統(tǒng)造成的成本損失。為了使系統(tǒng)成本損失最小，而對(duì)未完工工件進(jìn)行局部重調(diào)度，使新舊加工時(shí)間表能夠在某一時(shí)刻之后完全一致，并稱這一刻為匹配點(diǎn)。進(jìn)行局部重調(diào)度的工件集包括被機(jī)器中斷加工工件和還未開始加工工件。它們需要重新確定加工機(jī)器xij和壓縮量yij；此外引入0-1變量zj，當(dāng)zj=1表示該工件的開始加工時(shí)間為所在機(jī)器的匹配時(shí)間點(diǎn)。此模塊用到的參數(shù)定義如下：

S:初始加工時(shí)間表

sj:S中工件j的開始加工時(shí)間

M*:發(fā)生故障的機(jī)器

t*:機(jī)器故障發(fā)生的時(shí)刻

d*:機(jī)器故障維修的時(shí)間

j*:因機(jī)器故障而中斷加工的工件

J:需要進(jìn)行重調(diào)度的工件集合J={j|sj≥t*或者j*}

Ji:J的子集，機(jī)器i上需要重調(diào)度的工件集

Pj:表示同一臺(tái)機(jī)器上開始加工時(shí)間可以作為匹配點(diǎn)的工件j及其之前的工件集;

tj:工件j開始加工時(shí)間作為匹配點(diǎn)時(shí)，所在機(jī)器i上與原調(diào)度不一致的加工時(shí)間；

當(dāng)i=M*時(shí),tj=sj-t*；

ei:機(jī)器i上最后加工工件的完工時(shí)間Di作為匹配點(diǎn)時(shí)，該機(jī)器上與原調(diào)度不一致的加工時(shí)間表長度；

當(dāng)i=M*時(shí),ei=Di-t*；

di:機(jī)器i上可以利用的剩余加工時(shí)間；

當(dāng)i=M*時(shí),di=Di-(t*+d*)；

機(jī)器故障發(fā)生后與初始調(diào)度方案相關(guān)的成本損失主要包括兩方面。一方面是調(diào)度本身所造成的成本損失ΔC，主要包括重調(diào)度造成的壓縮成本增加和“中斷-重復(fù)”操作造成的資源浪費(fèi)，即可表示為：ΔC=ΔC壓縮費(fèi)用+ΔC資源浪費(fèi)。前者通過新舊調(diào)度方案壓縮成本差計(jì)算，后者按照被中斷工件的已完工比例來計(jì)算，如下所示：

另一方面則是由于新舊加工時(shí)間表不一致而給其它生產(chǎn)活動(dòng)造成的損失。其中擾動(dòng)時(shí)間段ΔT主要包括機(jī)器故障維修時(shí)間和因重調(diào)度而產(chǎn)生擾動(dòng)時(shí)間；設(shè)單位時(shí)間擾動(dòng)給其它生產(chǎn)活動(dòng)造成的成本損失為h，則給其它生產(chǎn)活動(dòng)造成的損失為：

綜上所述，機(jī)器故障后給生產(chǎn)系統(tǒng)造成的成本損失為ΔC+h·ΔT。預(yù)案反應(yīng)模塊則是以最小化生產(chǎn)系統(tǒng)成本損失為目標(biāo)函數(shù)建立重調(diào)度數(shù)學(xué)規(guī)劃模型進(jìn)行求解。具體模型可以表述為如下所示的非線性混合0-1整數(shù)規(guī)劃：

(RSM)min ΔC+h·ΔT

(6)

yij≤uijxij,i=1,…,m,且j∈J

(7)

(8)

(9)

(10)

(11)

(12)

xij∈{0,1},yij∈R+,i=1,…,m,且j∈J

(13)

(14)

其中約束(6)保證在剩余可用加工時(shí)間內(nèi)完成加工任務(wù)；約束(7)為壓縮量限制；約束(8)保證工件只能在一臺(tái)機(jī)器上加工；約束(9)表示各機(jī)器上的匹配點(diǎn)可能為未加工工件開始加工時(shí)間且如果是則只能有一點(diǎn)；約束(10)(11)(12)則表示各機(jī)器匹配點(diǎn)之后的工件及其壓縮量保持不變；約束(13)(14)則是變量取值的約束。與機(jī)器工件分配模型MJ0相似，該模型目標(biāo)函數(shù)中同樣含有非線性函數(shù)；通過二次錐化處理后用ILOGCPLEX12.4軟件進(jìn)行求解，在此不再詳述。

4.3 遺傳優(yōu)化模塊

遺傳優(yōu)化模塊主要是通過遺傳算法對(duì)柔性度量

(1)編碼。采用非負(fù)實(shí)數(shù)編碼，種群個(gè)體用五維向量{α1,α2,α3,α4,α5}表示，其中αi取[0,1]間實(shí)數(shù)；初始種群由隨機(jī)函數(shù)生成指定規(guī)模的五維向量構(gòu)成。

(2)個(gè)體評(píng)價(jià)。在進(jìn)化過程中對(duì)于任意個(gè)體{α1,α2,α3,α4,α5}。首先，根據(jù)4.1初始調(diào)度模塊中柔性度量Fj公式計(jì)算出每個(gè)工件的柔性，并且按照該模塊中工件排序算法來確定相應(yīng)的初始加工時(shí)間表。然后，依概率產(chǎn)生N種的干擾情景，利用4.2預(yù)案反應(yīng)模塊中的RSM數(shù)學(xué)模型計(jì)算出每種干擾情景下的成本損失。最后，取N種干擾情景下的系統(tǒng)成本損失期望E(ΔC+h·ΔT)來評(píng)價(jià)該個(gè)體。該值越小證明初始加工時(shí)間表的魯棒性越強(qiáng)，即個(gè)體的適應(yīng)度也就越大。

(3)遺傳操作。為了保存種群優(yōu)良特性同時(shí)更新種群進(jìn)行選擇、交叉、變異操作。本研究中選擇操作采用錦標(biāo)賽制；交叉操作采用離散重組的方式進(jìn)行；變異操作則是均勻變異算子。鑒于遺傳操作屬于經(jīng)典研究內(nèi)容且非研究重點(diǎn)，細(xì)節(jié)方面不做過多解釋。

(4)終止條件。當(dāng)進(jìn)化到指定代數(shù)則終止算法，

圖3 遺傳算法流程圖

5 數(shù)值算例

本節(jié)通過數(shù)值算例來驗(yàn)證所提魯棒調(diào)度策略有效性。在排序方法方面，與經(jīng)典SPT規(guī)則對(duì)比；已有學(xué)者證明機(jī)器故障發(fā)生時(shí)刻服從指數(shù)分布時(shí)SPT規(guī)則能夠最小化期望工作流時(shí)間[26]，因而以此制定初始調(diào)度方案是一種應(yīng)對(duì)隨機(jī)機(jī)器故障較好的方法。在柔性度量方面，與Gurel等[12]提出的解析式柔性度量對(duì)比。同時(shí)為了驗(yàn)證魯棒調(diào)度策略普適性，設(shè)計(jì)了兩組實(shí)驗(yàn)算例。分別驗(yàn)證在機(jī)器故障對(duì)其它生產(chǎn)活動(dòng)影響不同時(shí)和機(jī)器維修水平不同時(shí)的有效性。兩組實(shí)驗(yàn)都是依概率產(chǎn)生50次干擾情景，遺傳算法則采用15條染色體運(yùn)行30代。

5.1 單位時(shí)間擾動(dòng)成本不同時(shí)有效性檢驗(yàn)

E[λ·ΔC+(1-λ)·ΔT]

當(dāng)λ=0時(shí)，h=+∞表示其它生產(chǎn)活動(dòng)對(duì)擾動(dòng)時(shí)間非常敏感；因而調(diào)度自身所增加的成本可以忽略不計(jì)，目標(biāo)函數(shù)則為E[ΔT]。當(dāng)λ=1時(shí)，h=0表示機(jī)器故障對(duì)其它生產(chǎn)活動(dòng)的影響可以忽略不計(jì)；成本損失僅僅是調(diào)度本身所造成的，目標(biāo)函數(shù)則為E[ΔC]。除上述兩種情況外，λ的取值根據(jù)實(shí)際生產(chǎn)中單位擾動(dòng)時(shí)間的成本損失h確定。

本文采用將柔性較好工件安排在機(jī)器不可用概率較高時(shí)間段的方式進(jìn)行排序。如圖4所示與經(jīng)典SPT規(guī)則比較，當(dāng)λ在0～1間變動(dòng)時(shí)，本文排序方法對(duì)應(yīng)系統(tǒng)成本損失期望一直處于SPT排序方法下面。從而驗(yàn)證了所提排序方法有效性。

圖4 本文排序方法與SPT規(guī)則系統(tǒng)成本損失誤差棒圖

同時(shí)與劉鋒等[13]中的解析式柔性度量不同，本文利用遺傳算法優(yōu)化柔性參數(shù)的方式來確定工件柔性度量。因此就柔性度量方式上與劉鋒等[13]中針對(duì)故障發(fā)生時(shí)刻和維修時(shí)間概率分布為Exp-Exp情況時(shí)所提出的五種解析式柔性度量對(duì)比。針對(duì)不同柔性度量，定義改進(jìn)率指標(biāo)R，計(jì)算公式如下所示，其中E(CSPT)和E(CF)分別表示在SPT規(guī)則和不同柔性度量下的系統(tǒng)成本損失期望。

表1 不同柔性度量下的改進(jìn)率指標(biāo)1/0.1Di(%)

表1為擾動(dòng)系數(shù)λ在0～1區(qū)間變化時(shí)，各柔性度量的改進(jìn)率指標(biāo)R值。表2為50次干擾情景下擾動(dòng)系數(shù)λ從0～1變化11次過程中系統(tǒng)成本損失期望的95%置信區(qū)間估計(jì)，以及比SPT規(guī)則成本損失較小的實(shí)驗(yàn)次數(shù)。

由表1和表2可見，本文所對(duì)應(yīng)改進(jìn)率指標(biāo)R大于0，改進(jìn)數(shù)量最多，置信區(qū)間上下界小于SPT從而驗(yàn)證了所提排序方法比SPT規(guī)則有效。同時(shí)與五種解析式度量相比，遺傳算法確定柔性度量的方式改進(jìn)率R較大，改進(jìn)數(shù)量較多且置信區(qū)間偏小，從而驗(yàn)證了所提柔性度量方式的有效性。綜上可知，無論單位擾動(dòng)時(shí)間給其它生產(chǎn)活動(dòng)造成的成本損失h為多少，所提魯棒調(diào)度策略都能有效降低隨機(jī)機(jī)器故障造成的成本損失期望。

5.2 機(jī)器維修水平不同時(shí)有效性檢驗(yàn)

表2 系統(tǒng)成本損失期望95%置信區(qū)間和較SPT改進(jìn)數(shù)量

表3為機(jī)器故障維修時(shí)間分別服從參數(shù)為1/0.1Di和1/0.15Di指數(shù)概率分布時(shí)，擾動(dòng)系數(shù)λ取0.0，0.5，1.0時(shí)的改進(jìn)率指標(biāo)R值。表4則為在50次干擾情景下，機(jī)器故障參數(shù)與擾動(dòng)系數(shù)組合的6次變化過程中系統(tǒng)成本損失期望的95%置信區(qū)間估計(jì)，以及比SPT規(guī)則排序系統(tǒng)成本損失較小的實(shí)驗(yàn)次數(shù)。在不同的機(jī)器維修水平下，本文改進(jìn)率指標(biāo)R值大于SPT和各解析式擾動(dòng)度量，同時(shí)改進(jìn)數(shù)量總體最多且系統(tǒng)成本損失期望的置信區(qū)間上下界最小。從而表明所提魯棒策略在排序方法和柔性度量方式上分別比SPT排序和解析式柔性度量要好，從而驗(yàn)證了在不同機(jī)器維修水平下的有效性。

表3 不同機(jī)器維修水平下改進(jìn)率指標(biāo)R(%)

表4 系統(tǒng)成本損失期望95%置信區(qū)間和較SPT改進(jìn)數(shù)量

5.3 結(jié)果分析

通過兩組實(shí)驗(yàn)對(duì)比表明，在排序方法上與經(jīng)典SPT規(guī)則對(duì)比，驗(yàn)證了將柔性較好的工件安排在機(jī)器不可用概率較高的時(shí)間段能夠有效降低干擾發(fā)生后系統(tǒng)成本損失期望。排序方法相同的情況下，在柔性度量方面與解析式柔性度量方式對(duì)比，驗(yàn)證了遺傳算法確定柔性度量的有效性。主要原因是各柔性指標(biāo)是從不同角度來度量工件柔性的。例如工件剩余可壓縮量是從時(shí)間的角度來度量柔性，該值越大表示能夠使擾動(dòng)時(shí)間段越?。欢杀緣嚎s函數(shù)的二階導(dǎo)數(shù)則是從成本角度來度量工件柔性的，該值越小則壓縮單位時(shí)間所付出的成本越小。因此當(dāng)擾動(dòng)時(shí)間段對(duì)其它生產(chǎn)活動(dòng)的影響程度不同時(shí)，即單位時(shí)間擾動(dòng)成本h發(fā)生變化時(shí)，工件各柔性度量指標(biāo)參數(shù)也應(yīng)做出調(diào)整。也就是說不存在唯一柔性度量對(duì)不同的目標(biāo)函數(shù)均有效。而遺傳算法確定柔性度量方式正是由于其能夠根據(jù)目標(biāo)函數(shù)來調(diào)整柔性度量，從而保證了該方法的有效性。

6 結(jié)語

本文在并行機(jī)環(huán)境下，針對(duì)機(jī)器加工能力有限且工件加工時(shí)間可控情況中隨機(jī)機(jī)器故障問題。提出內(nèi)外兩層嵌套式的魯棒調(diào)度策略，內(nèi)層結(jié)構(gòu)通過建立非線性0-1混合整數(shù)規(guī)劃來計(jì)算初始調(diào)度方案在依概率產(chǎn)生的多種干擾情景下的成本損失期望；外層結(jié)構(gòu)以成本損失期望為個(gè)體評(píng)價(jià)指標(biāo)，通過遺傳算法來優(yōu)化工件柔性參數(shù)進(jìn)而提高初始調(diào)度方案魯棒性。

通過數(shù)值實(shí)驗(yàn)表明：(1)在排序方法上與經(jīng)典的SPT規(guī)則對(duì)比，將柔性較好的工件安排在機(jī)器不可用概率較高時(shí)間段的排序策略使得系統(tǒng)成本損失期望更低；(2)在柔性度量上與解析式柔性度量對(duì)比，通過遺傳算法確定柔性度量的方式平均改進(jìn)率指標(biāo)較高；(3)在機(jī)器故障對(duì)其它相關(guān)生產(chǎn)活動(dòng)影響不同時(shí)和機(jī)器維修水平不同時(shí)，魯棒調(diào)度策略同樣具有有效性。

本研究有助于企業(yè)制定魯棒性較好的初始調(diào)度方案，使機(jī)器故障發(fā)生給生產(chǎn)加工系統(tǒng)造成成本損失期望最小。未來進(jìn)一步的研究方向包括兩個(gè)方面，一是可以將所提魯棒調(diào)度策略應(yīng)用到其它類型的干擾事件應(yīng)對(duì)研究中，二是可向魯棒性替代度量及柔性參數(shù)確定方面深入研究和改進(jìn)。

附錄: 指標(biāo)4證明

設(shè)L/ny0=θ，上式可變形為：

將(1+θ)a-1-aθ(1+θ)a-1按泰勒公式展開為：

即證C′(n)<0，因此當(dāng)需要壓縮的時(shí)間長度相同時(shí)，壓縮工件越多則成本越少。又由于受匹配時(shí)間的限制，所以工件加工時(shí)間越短則放置的工件數(shù)量越多，進(jìn)而使得工件柔性越好。

[1] 劉樂, 周泓. 一種常見干擾條件下的開放式車間重調(diào)度研究[J].管理科學(xué)學(xué)報(bào),2014, 17(6): 28-48.

[2]AhmadiE,ZandiehM,FarrokhM,etal.Amultiobjectiveoptimizationapproachforflexiblejobshopschedulingproblemunderrandommachinebreakdownbyevolutionaryalgorithms[J].Computers&OperationsResearch, 2016, 73: 56-66.

[3]FazayeliM,AleaghaMR,BashirzadehR,etal.Ahybridmeta-heuristicalgorithmforflowshoprobustschedulingundermachinebreakdownuncertainty[J].InternationalJournalofComputerIntegratedManufacturing, 2016, 29(7): 709-719.

[4]MehtaSV,UzsoyRM.Predictableschedulingofajobshopsubjecttobreakdowns[J].IEEETransactionsonRoboticsandAutomation, 1998, 14(3):365-378.

[5] 尹文君, 劉民, 吳澄. 隨機(jī)故障下單機(jī)魯棒調(diào)度算法的遺傳編程方法[J]. 清華大學(xué)學(xué)報(bào)(自然科學(xué)版), 2005, 45(1): 81-84.

[6] 李巧云, 王冰, 王曉明. 隨機(jī)機(jī)器故障下單機(jī)預(yù)測調(diào)度方法[J]. 系統(tǒng)工程理論與實(shí)踐, 2011, 31(12): 2387-2393.

[7]LiuLin,GuHanyu,XiYugeng.Robustandstableschedulingofasinglemachinewithrandommachinebreakdowns[J].InternationalJournalofAdvancedManufacturingTechnology, 2007, 31(7-8): 645-654.

[8]Al-HinaiN,ElMekkawyTY.Robustandstableflexiblejobshopschedulingwithrandommachinebreakdownsusingahybridgeneticalgorithm[J].InternationalJournalofProductionEconomics, 2011, 132(2): 279-291.

[9]XiongJian,XingLining,ChenYingwu.Robustschedulingformulti-objectiveflexiblejob-shopproblemswithrandommachinebreakdowns[J].InternationalJournalofProductionEconomics, 2013, 141(1): 112-126.

[10]YangBibo,GeunesJ.Predictive-reactiveschedulingonasingleresourcewithuncertainfuturejobs[J].EuropeanJournalofOperationalResearch, 2008, 189(3):1267-1283.

[11]AkturkMS,AtamturkA,GurelS.Parallelmachinematch-upschedulingwithmanufacturingcostconsiderations[J].JournalofScheduling, 2010, 13(1): 95-110.

[12]GurelS,KorpeogluE,AkturkMS.Ananticipativeschedulingapproachwithcontrollableprocessingtimes[J].Computers&OperationsResearch, 2010, 37(6):1002-1013.

[13] 劉鋒, 王征, 王建軍, 等. 加工能力受擾的可控排序干擾管理[J]. 系統(tǒng)管理學(xué)報(bào), 2013, 22(4): 505-512.

[14] 邊志興. 作業(yè)車間的模糊動(dòng)態(tài)調(diào)度問題研究[J].中國管理科學(xué),2008,16(S1):76-83.

[15]TangLixin,ZhaoYue,LiuJiyin.Animproveddifferentialevolutionalgorithmforpracticaldynamicschedulinginsteelmaking-continuouscastingproduction[J].IEEETransactionsonEvolutionaryComputation, 2014, 18(2):209-225.

[16]FelixTS,ShekharP,TiwariMK.Dynamicschedulingofoiltankerswithsplittingofcargoatpickupanddeliverylocations:Amulti-objectiveantcolony-basedapproach[J].InternationalJournalofProductionResearch, 2014, 52(24):7436-7453.

[17]ShenXiaoning,YaoXin.Mathematicalmodelingandmulti-objectiveevolutionaryalgorithmsappliedtodynamicflexiblejobshopschedulingproblems[J].InformationSciences, 2015, 298:198-224.

[18]LiuLe,ZhouHong.Ontheidenticalparallel-machinereschedulingwithjobreworkdisruption[J].Computers&IndustrialEngineering, 2013, 66(1): 186-198.

[19]CuiWeiwei,LuZhiqiang,PanErshun.Integratedproductionschedulingandmaintenancepolicyforrobustnessinasinglemachine[J].Computers&OperationsResearch, 2014, 47: 81-91.

[20]AkturkMS,AtamturkA,GurelS.Astrongconicquadraticreformulationformachine-jobassignmentwithcontrollableprocessingtimes[J].OperationsResearchLetters, 2009, 37(3): 187-191.

[21] 李素粉, 朱云龍, 尹朝萬. 具有隨機(jī)加工時(shí)間和機(jī)器故障的流水車間調(diào)度[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2005, 11(10):1425-1429.

[22] 劉鋒, 王建軍, 饒衛(wèi)振, 等. 安裝時(shí)間與次序相關(guān)的生產(chǎn)調(diào)度干擾管理研究[J].中國管理科學(xué),2014, 22(1):45-54.

[23]BonfillA,EspunaA,PuigjanerL.Proactiveapproachtoaddresstheuncertaintyinshort-termscheduling[J].Computers&ChemicalEngineering, 2008, 32(8):1689-1706.

[24]WuSD,ByeonE,StorerRH.Agraph-theoreticdecompositionofthejobshopschedulingproblemtoachieveschedulingrobustness[J].OperationsResearch, 1999, 47(1): 113-124.

[25]AlizadehF,GoldfarbD.Second-orderconeprogramming[J].MathematicalProgramming, 2003, 95(1):3-51.

[26]AdiriI,BrunoJ,FrostigE,etal.Single-machineflow-timeschedulingwithasinglebreakdown[J].ActaInformatica, 1989, 26(7): 679-685.

RobustSchedulingofUnrelatedParallelMachinesSubjecttoStochasticBreakdownsandControllableProcessingTimes

WANGJian-jun1,LIUXiao-pan1,LIUFeng2,WANGDu-Juan1

(1.InstituteofSystemsEngineering,DalianUniversityofTechnology,Dalian116023,China; 2.SchoolofManagementScienceandEngineering,DongbeiUniversityofFinance&Economics,Dalian116025,China)

Inevitable machine breakdowns always degrade the performance of the initial schedule in the practice. Considering the controllable processing time in unrelated parallel machines layout, how to generate a robust schedule to reduce the expectation value of the loss cost caused by the stochastic machine failures is studied. Therefore, a robust scheduling strategy of two nested layers is designed. In the inner layer, a nonlinear 0-1 mixed integer model is built to calculate the expectation of the loss cost. Because of the model’s complexity, it is translated into second-order cone constrains for solving efficiency. In the outer layer, sorting algorithm is designed based on the job’s flexibility and the probability of machine unavailability. Due to inherent complex and unstructured nature, genetic algorithm is used to optimize job’s flexible parameters, and to further enhance the robustness of the initial schedule. Through randomly generated numerical experiments, It shows that the proposed scheduling strategy is robust against different disturbance cost per unit time and different mean time to repair of machine breakdown. The research has a certain reference for sorting robust schedule and optimizing job’s flexible parameters.

robust scheduling; unrelated parallel machines; controllable processing time; stochastic breakdowns; match-up

1003-207(2017)03-0137-10

10.16381/j.cnki.issn1003-207x.2017.03.016

2015-03-21；

2015-10-13

國家自然科學(xué)基金資助項(xiàng)目(71271039, 71672019, 71502026)；教育部“新世紀(jì)優(yōu)秀人才支持計(jì)劃”項(xiàng)目(NCET-13-0082)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(DUT14YQ211)

王建軍(1977-)，男(漢族)，河北保定人，大連理工大學(xué)系統(tǒng)工程研究所教授，博士生導(dǎo)師，研究方向：干擾管理、生產(chǎn)調(diào)度等，E-mail:.drwangjj@dlut.edu.cn.

C939

A