考慮隨機(jī)故障的流水線(xiàn)調(diào)度問(wèn)題前攝優(yōu)化方法

趙嬋媛, 陸志強(qiáng), 崔維偉

(1.同濟(jì)大學(xué) 機(jī)械與能源工程學(xué)院, 上海 201804; 2.上海交通大學(xué) 工業(yè)工程與管理系, 上海 200240)

?

考慮隨機(jī)故障的流水線(xiàn)調(diào)度問(wèn)題前攝優(yōu)化方法

趙嬋媛1, 陸志強(qiáng)1, 崔維偉2

(1.同濟(jì)大學(xué) 機(jī)械與能源工程學(xué)院, 上海 201804; 2.上海交通大學(xué) 工業(yè)工程與管理系, 上海 200240)

研究帶有隨機(jī)故障的流水線(xiàn)車(chē)間調(diào)度問(wèn)題, 以質(zhì)量魯棒性和解魯棒性的綜合指標(biāo)為優(yōu)化目標(biāo), 分析故障這一隨機(jī)因素的影響, 采用前攝優(yōu)化理論求解問(wèn)題. 建立問(wèn)題的隨機(jī)規(guī)劃數(shù)學(xué)模型,設(shè)計(jì)內(nèi)、外兩層嵌套式優(yōu)化算法以聯(lián)合決策工件調(diào)度順序與緩沖時(shí)間大小. 在外層, 以NEH啟發(fā)式算法為基礎(chǔ),結(jié)合鄰域搜索決策工件加工順序；在內(nèi)層, 采用遺傳算法搜索緩沖時(shí)間并設(shè)計(jì)有效的代理指標(biāo)作為解的評(píng)價(jià)方式. 數(shù)據(jù)實(shí)驗(yàn)表明, 提出的算法相比2種傳統(tǒng)方法所得到的解的綜合指標(biāo)更優(yōu)異, 且允許決策者根據(jù)不同的偏好選擇不同的優(yōu)化解. 加入緩沖時(shí)間有利于改善解魯棒性指標(biāo),可以提高質(zhì)量魯棒性的穩(wěn)定度.

流水線(xiàn); 隨機(jī)故障; 魯棒性; 代理指標(biāo)

傳統(tǒng)流水線(xiàn)調(diào)度問(wèn)題多假設(shè)機(jī)器在調(diào)度期內(nèi)隨時(shí)可用, 而在實(shí)際生產(chǎn)中受不確定性因素的影響,機(jī)器可能發(fā)生意外故障,會(huì)導(dǎo)致調(diào)度的執(zhí)行偏離計(jì)劃預(yù)期,影響生產(chǎn)交付及物料調(diào)配.解決不確定性調(diào)度問(wèn)題的方法主要有3種:前攝調(diào)度、反應(yīng)調(diào)度以及前攝-反應(yīng)調(diào)度.

前攝調(diào)度是指在生成基礎(chǔ)調(diào)度時(shí)考慮不確定因素的影響,通常以魯棒性為優(yōu)化目標(biāo),以期減少不確定性對(duì)調(diào)度產(chǎn)生的干擾,適用于隨機(jī)事件的可預(yù)知性較好且每次隨機(jī)事件本身單獨(dú)對(duì)調(diào)度解的影響較小的情況.計(jì)算機(jī)仿真技術(shù)與優(yōu)化算法的有效結(jié)合是解決前攝調(diào)度優(yōu)化問(wèn)題的一種重要方法.Zandieh等[1-3]結(jié)合仿真與元啟發(fā)式算法,求解具有隨機(jī)性的混合流水線(xiàn)或作業(yè)車(chē)間的調(diào)度問(wèn)題.冗余調(diào)度是前攝調(diào)度中提高解魯棒性的常用手段,它利用多余的資源應(yīng)對(duì)不確定性情況的發(fā)生[4].Mehta等[5-6]通過(guò)插入緩沖時(shí)間來(lái)吸收故障干擾,試圖改善單機(jī)調(diào)度中的解魯棒性,采用的緩沖時(shí)間均為故障間隔期望值.

反應(yīng)調(diào)度指在調(diào)度初期不考慮不確定因素,而在突發(fā)事件發(fā)生后根據(jù)特定的規(guī)則進(jìn)行調(diào)度,適用于隨機(jī)性大或隨機(jī)性小但單次隨機(jī)事件對(duì)整個(gè)調(diào)度影響較大并且無(wú)法事先預(yù)知的情況.反應(yīng)調(diào)度的優(yōu)點(diǎn)是能夠在短時(shí)間內(nèi)得到可接受的解,但通常不能達(dá)到全局最優(yōu)[7].分派規(guī)則可以被看作是反應(yīng)調(diào)度的一類(lèi)典型規(guī)則,專(zhuān)家學(xué)者針對(duì)混合流水線(xiàn)或作業(yè)車(chē)間提出若干不同的分派規(guī)則,對(duì)不可預(yù)知的不確定性情況作出響應(yīng)[8-12].

前攝-反應(yīng)調(diào)度結(jié)合前兩者,適用于已知部分不確定性,但可能遇到突發(fā)事件的情況,嚴(yán)重偏離基礎(chǔ)調(diào)度時(shí)運(yùn)用重調(diào)度進(jìn)行修正.Katragjini等[13]考慮流水線(xiàn)調(diào)度的3種不確定性,運(yùn)用仿真結(jié)合啟發(fā)式算法求解基礎(chǔ)調(diào)度,比較4種重調(diào)度策略.Wang等[14]提出聚類(lèi)分組法求解混合流水線(xiàn)調(diào)度問(wèn)題,工件根據(jù)不確定性的大小分組,不確定性大的運(yùn)用分派規(guī)則即反應(yīng)調(diào)度,不確定性小的運(yùn)用前攝-反應(yīng)調(diào)度.Rahmani等[15]針對(duì)考慮隨機(jī)加工時(shí)間及新工件到達(dá)的兩機(jī)流水線(xiàn)提出前攝-反應(yīng)調(diào)度方法,前攝調(diào)度考慮隨機(jī)加工時(shí)間,而新工件到達(dá)則觸發(fā)反應(yīng)調(diào)度.

本文針對(duì)考慮隨機(jī)故障的流水線(xiàn)問(wèn)題,已知機(jī)器失效函數(shù)服從指數(shù)分布,屬于可預(yù)知性較好的情況.運(yùn)用前攝調(diào)度策略,在調(diào)度時(shí)考慮故障的影響,以質(zhì)量魯棒性和解魯棒性的綜合指標(biāo)為優(yōu)化目標(biāo),旨在求得受故障干擾影響小、并且能夠維持績(jī)效較好的解.當(dāng)數(shù)據(jù)規(guī)模大時(shí),采用仿真優(yōu)化方法難以在短時(shí)間內(nèi)求得數(shù)值解,本文提出有效代理指標(biāo)代替抽樣仿真模塊的功能,可以大幅度地節(jié)省算法迭代搜索的時(shí)間.

1 問(wèn)題描述與數(shù)學(xué)模型

1.1 問(wèn)題描述

以流水線(xiàn)車(chē)間為研究對(duì)象,即m臺(tái)機(jī)器構(gòu)成的純流水線(xiàn)系統(tǒng),各機(jī)器之間的存儲(chǔ)容量無(wú)限.在調(diào)度計(jì)劃周期內(nèi)共有n個(gè)不同類(lèi)型的工件,每個(gè)工件均需依次經(jīng)過(guò)每臺(tái)機(jī)器,且在每臺(tái)機(jī)器上只加工一次,工件的每道工序在機(jī)器上的加工時(shí)間已知,工件i在機(jī)器k上的加工時(shí)間為pik,所有工件在零時(shí)刻同時(shí)到達(dá)系統(tǒng).任何機(jī)器在加工工件時(shí)都可能發(fā)生意外故障,故障的發(fā)生服從指數(shù)分布,即故障率為常量,記為λk.故障后須對(duì)機(jī)器進(jìn)行小修,小修時(shí)間為tk,修復(fù)結(jié)束后被打斷的工件繼續(xù)加工,即工件屬于可恢復(fù)(resumable)情形.

機(jī)器一旦發(fā)生故障后需要進(jìn)行維修,會(huì)對(duì)基礎(chǔ)調(diào)度產(chǎn)生影響,因此需要一定的重調(diào)度策略來(lái)修正基礎(chǔ)調(diào)度.采用的重調(diào)度策略為右移規(guī)則,即工件作業(yè)順序維持不變,未完成的加工延至維修后,并規(guī)定工件的實(shí)際完成時(shí)間不得早于預(yù)測(cè),即若工件比預(yù)測(cè)完成時(shí)間提前,則該工件不被運(yùn)送到下一臺(tái)機(jī)器上,該機(jī)器也不繼續(xù)加工下一個(gè)工件,以協(xié)調(diào)實(shí)際生產(chǎn)調(diào)度中外部資源如原材料、工具及搬運(yùn)設(shè)施等的調(diào)度.

在已有文獻(xiàn)中,確定性流水線(xiàn)調(diào)度的績(jī)效評(píng)估通常采用制造期(makespan)等目標(biāo)值,然而考慮故障等不確定性因素時(shí)常采用魯棒性指標(biāo)(robustness).魯棒性指標(biāo)可以分為質(zhì)量魯棒性和解魯棒性?xún)煞N.質(zhì)量魯棒性是指調(diào)度計(jì)劃的績(jī)效不會(huì)因?yàn)殡S機(jī)干擾的影響而大幅降低,解魯棒性是指實(shí)際調(diào)度的具體執(zhí)行情況和初始調(diào)度計(jì)劃沒(méi)有太大的偏差[1].基礎(chǔ)調(diào)度計(jì)劃是安排原材料供給、換模、報(bào)價(jià)及交付等的重要依據(jù),一旦更改會(huì)產(chǎn)生庫(kù)存、運(yùn)輸、延期罰款等成本,并使得預(yù)定的計(jì)劃不可行,因此解魯棒性變得越來(lái)越重要.

1.2 數(shù)學(xué)建模

定義的決策變量如下.

xi[j]:0/1變量, 表示工件i在第j個(gè)位置進(jìn)行加工,i=1,2,…,n,j=1,2,…,n.

I[j]k:排在第j個(gè)位置的工件 (以下簡(jiǎn)記為工件[j]) 在機(jī)器k上加工后的緩沖時(shí)間.

輔助變量如下.

p[j]k:工件[j]在機(jī)器k上的加工時(shí)間,j=1,2,…,n,k=1,2,…,m.

s[j]k:基礎(chǔ)調(diào)度中工件[j]在機(jī)器k上開(kāi)始加工時(shí)間.

c[j]k:基礎(chǔ)調(diào)度中工件[j]在機(jī)器k上完成加工時(shí)間.

N[j]k:工件[j]在機(jī)器k上加工時(shí)發(fā)生故障的次數(shù).

根據(jù)問(wèn)題描述及假設(shè), 建立數(shù)學(xué)模型如下.

(1)

s.t.

(2)

(3)

(4)

s[1]1=0,

(5)

c[j]k=s[j]k+p[j]k+I[j]k,?j,?k,

(6)

s[1]k=c[1],k-1,k≥2,

(7)

s[j]1=c[j-1],1,j≥2,

(8)

(9)

(10)

(11)

(12)

(13)

(14)

xi[j]=0 或 1.

(15)

目標(biāo)函數(shù)為質(zhì)量魯棒性與解魯棒性的線(xiàn)性組合,如式(1)所示.式(2)、(3)表示每個(gè)工件能且只能被安排到加工順序中的一個(gè)位置,同時(shí)加工順序中的每個(gè)位置能且只能安排一個(gè)工件.式(4)表示工件的加工時(shí)間與決策變量之間的對(duì)應(yīng)關(guān)系.式(5)～(9)表示前攝調(diào)度中工件開(kāi)始加工時(shí)間和完成加工時(shí)間的遞推式,其中式(6)表示在前攝調(diào)度中加入緩沖時(shí)間,相當(dāng)于人為延長(zhǎng)加工時(shí)間,以吸收機(jī)器故障對(duì)調(diào)度產(chǎn)生的影響.式(10)～(14)表示實(shí)際調(diào)度中一旦發(fā)生故障,運(yùn)用右移策略進(jìn)行重調(diào)度.式(11)中,N[j]k體現(xiàn)了機(jī)器發(fā)生故障的隨機(jī)性,使得模型無(wú)法作為確定性問(wèn)題求解.

2 算法設(shè)計(jì)

2.1 內(nèi)、外層循環(huán)算法設(shè)計(jì)

由上述數(shù)學(xué)模型可以看出,決策變量為0/1整數(shù)變量xi[j]和實(shí)數(shù)變量I[j]k, 其余變量均為輔助間接變量, 這使得該混合整數(shù)規(guī)劃數(shù)學(xué)模型難以直接求解.由于緩沖時(shí)間的最優(yōu)取值非常依賴(lài)于工件的加工順序,采用內(nèi)、外兩層嵌套式優(yōu)化算法解決上述調(diào)度問(wèn)題:外層決策工件順序,內(nèi)層決策緩沖時(shí)間.該外模型具有隨機(jī)性,傳統(tǒng)方法通常以數(shù)理統(tǒng)計(jì)原理,運(yùn)用仿真方法求出目標(biāo)函數(shù)的統(tǒng)計(jì)值,為了讓統(tǒng)計(jì)值具有意義,需要運(yùn)行一定的重復(fù)次數(shù),因而耗時(shí)久不利于大規(guī)模數(shù)據(jù)的內(nèi)、外層搜索,如m=10、n=50、仿真重復(fù)次數(shù)為1 000次時(shí)無(wú)法在幾天內(nèi)求得解,因此本文提出代理指標(biāo),以確定性解析函數(shù)式代替目標(biāo)函數(shù),節(jié)省內(nèi)、外層搜索時(shí)間.算法框架如圖1所示.外層算法Procedure1以NEH啟發(fā)式算法為基礎(chǔ),結(jié)合鄰域搜索決策工件加工順序；內(nèi)層算法Procedure2針對(duì)給定的工件順序,設(shè)計(jì)基于有效代理指標(biāo)的遺傳算法,對(duì)緩沖時(shí)間進(jìn)行有效搜索求解.

2.1.1 外層算法Procedure1: 決策工件順序

3) 取排在第3個(gè)的工件, 分別插入到已有排序的各個(gè)空擋中, 即σ1(j[3],j[1],j[2])、σ2(j[1],j[3],j[2])和σ3(j[1],j[2],j[3]), 比較各排序在插入緩沖時(shí)間后的目標(biāo)值s1、s2和s3, 保留最優(yōu)的排序.

4) 根據(jù)步驟2)、3)類(lèi)推, 直到n個(gè)工件全都進(jìn)行了比較, 此時(shí)最優(yōu)值為sbest, 最優(yōu)解為σbest.

5) 記重復(fù)迭代次數(shù)r=0, 最大重復(fù)迭代次數(shù)為rmax.

圖1 雙層嵌套式算法框架Fig.1 Famework of two-loop nested algorithm

6) 隨機(jī)取出排在第w(w

7) 若st

8) 若r

2.1.2 內(nèi)層算法Procedure2: 計(jì)算緩沖時(shí)間

初始種群:種群數(shù)量是影響算法最優(yōu)化性能和效率的因素之一,目前常用的種群數(shù)目為20～200,本文取種群數(shù)量為200.初始種群中1條初始染色體中各基因均為0,其余199條染色體為隨機(jī)生成.

選擇機(jī)制:輪盤(pán)賭法;跨世代精英策略,即選擇最優(yōu)的種群數(shù)量個(gè)染色體直接進(jìn)入下一代.

交叉機(jī)制:采用中間重組的方法,適用于實(shí)變量,子個(gè)體的產(chǎn)生由式(16)產(chǎn)生.若子個(gè)體<0,則子個(gè)體=0,其中ρ隨機(jī)取[0.75,1.25]的實(shí)數(shù),通過(guò)數(shù)值試驗(yàn)調(diào)試,取交叉概率Pc=0.85.子個(gè)體=父?jìng)€(gè)體1+ρ×(父?jìng)€(gè)體2-父?jìng)€(gè)體1).

(16)

變異機(jī)制:隨機(jī)選擇變異位置,重新隨機(jī)生產(chǎn)該位置的基因,通過(guò)數(shù)值試驗(yàn)調(diào)試,取變異概率Pm=0.25.

終止條件:為了控制兩層嵌套算法的運(yùn)行時(shí)間,限制最大的迭代步數(shù)tmax,通過(guò)數(shù)值試驗(yàn)調(diào)試,取tmax=100.

解的評(píng)價(jià)(適應(yīng)度函數(shù)設(shè)計(jì)):對(duì)于一個(gè)給定的解(包括工件順序與染色體編碼對(duì)應(yīng)的緩沖時(shí)間),由于機(jī)器故障概率以及反應(yīng)調(diào)度規(guī)則的影響,無(wú)法直接推導(dǎo)出解的目標(biāo)函數(shù)值,即質(zhì)量魯棒性與解魯棒性對(duì)應(yīng)的數(shù)學(xué)期望表達(dá)式,而仿真抽樣需要重復(fù)計(jì)算一定次數(shù),耗時(shí)較長(zhǎng),因此設(shè)計(jì)如2.2節(jié)所述的代理指標(biāo)作為適應(yīng)度函數(shù),以表達(dá)式的形式求得目標(biāo)函數(shù)的近似值.

2.2 代理指標(biāo)

由于數(shù)學(xué)模型中的N[j]k是一個(gè)隨機(jī)量, 導(dǎo)致目標(biāo)函數(shù)zq與zs具有隨機(jī)性, 通常由仿真來(lái)得到數(shù)值解.仿真的方法耗時(shí)較久,尤其對(duì)于大規(guī)模問(wèn)題,難以在短時(shí)間內(nèi)計(jì)算得到解.本文設(shè)計(jì)相應(yīng)的代理指標(biāo)作為目標(biāo)函數(shù)的近似函數(shù),本質(zhì)上是以基于代理指標(biāo)的確定性?xún)?yōu)化問(wèn)題代替隨機(jī)優(yōu)化模型,達(dá)到極大地減少算法運(yùn)行時(shí)間的目的.

2.2.1 代理指標(biāo)的相關(guān)分析

目標(biāo)函數(shù)中的質(zhì)量魯棒性zq用c[n]m來(lái)替代, 與文獻(xiàn)[5,6]的研究一致. 解魯棒性zs體現(xiàn)的是基礎(chǔ)調(diào)度與實(shí)際的偏離程度, 突發(fā)故障、流水線(xiàn)調(diào)度系統(tǒng)固有的空閑時(shí)間以及人為插入的緩沖時(shí)間都會(huì)對(duì)zs造成影響, 因此提出的代理指標(biāo)綜合考慮了這三者之間的關(guān)系,突發(fā)故障體現(xiàn)在實(shí)際調(diào)度中,而后兩者體現(xiàn)在基礎(chǔ)調(diào)度中.提出的替代指標(biāo)主要考慮機(jī)器故障發(fā)生后是否會(huì)對(duì)后續(xù)工件的完成加工時(shí)間產(chǎn)生影響,如果后續(xù)總的空閑時(shí)間不為0,則能夠在一定程度上改善實(shí)際生產(chǎn)與基礎(chǔ)調(diào)度的偏離程度,從而改善zs;若后續(xù)空閑時(shí)間不小于故障小修時(shí)間,則說(shuō)明空閑時(shí)間能夠完全吸收故障的影響,計(jì)劃與實(shí)際沒(méi)有偏離.以故障時(shí)間與可用時(shí)間之差的加權(quán)和來(lái)體現(xiàn)空閑時(shí)間是否吸收了故障干擾,即體現(xiàn)基礎(chǔ)調(diào)度與實(shí)際的偏離程度zs.

圖2 帶有緩沖時(shí)間的流水線(xiàn)基礎(chǔ)調(diào)度甘特圖Fig.2 Gantt chart of flow shop baseline schedule with buffer time

(17)

P[j]k=1-exp (-λk·p[j]k),?j,?k,

(18)

(19)

(20)

(21)

(22)

?j,?k,a>j,b>k,

(23)

?j,?k,a≥j,b≥k.

(24)

2.2.2 代理指標(biāo)的驗(yàn)證 運(yùn)用VS C#進(jìn)行編程, 通過(guò)仿真數(shù)據(jù)實(shí)驗(yàn)對(duì)前述代理指標(biāo)進(jìn)行評(píng)價(jià), 比較原目標(biāo)函數(shù)與代理指標(biāo)的相關(guān)性及計(jì)算用時(shí). 本文采用置信區(qū)間法計(jì)算仿真重復(fù)次數(shù), 取顯著水平為1%, 求得重復(fù)次數(shù)為1 000.

如表2所示為每組不同的緩沖時(shí)間下計(jì)算代理指標(biāo)與仿真值的平均用時(shí),按算例進(jìn)行統(tǒng)計(jì),記TSM為計(jì)算代理指標(biāo)的平均時(shí)間,TSP為計(jì)算仿真值的平均用時(shí).可以看出,當(dāng)m=10,n=50時(shí), 采用仿真的方法需要近0.08 s來(lái)計(jì)算一次目標(biāo)值, 約為同等參數(shù)下代理指標(biāo)所用時(shí)間的10倍；對(duì)于內(nèi)層求解緩沖時(shí)間的遺傳算法,僅用于計(jì)算適應(yīng)度函數(shù)的仿真時(shí)間將達(dá)1 600 s；嵌套進(jìn)外層算法經(jīng)過(guò)千次的迭代會(huì)使算法難以在幾天內(nèi)求得解, 運(yùn)用代理指標(biāo)能夠有效地減少計(jì)算時(shí)間.

3 數(shù)據(jù)實(shí)驗(yàn)

3.1 本文算法與傳統(tǒng)方法的比較

實(shí)驗(yàn)參數(shù)如2.2.2節(jié)所述, 不同數(shù)據(jù)規(guī)模下各生成5組包含不同機(jī)器故障率和維修時(shí)間的算例.比較本文算法(取α=0.9,β=0.1)與傳統(tǒng)方法的目標(biāo)值z(mì)q和zs.傳統(tǒng)方法分別為:緩沖時(shí)間為故障維修時(shí)間期望(單機(jī)調(diào)度中通常令緩沖時(shí)間等于期望值[4],即I[j]k=λk·p[j]k·tk)以及無(wú)緩沖時(shí)間(即α=1,β=0).從表3可以看出,無(wú)緩沖的方法相比其余方法雖然得到的zq最好, 但zs最差, 體現(xiàn)所得解在故障環(huán)境下不穩(wěn)定的特征. 本文算法雖然犧牲了一小部分zq, 但所得的zs遠(yuǎn)比緩沖為期望值的算法更好, 且數(shù)據(jù)規(guī)模越大,本文算法的優(yōu)越性越顯著.

表1 代理指標(biāo)與仿真值的相關(guān)度系數(shù)

表3 不同算例下求解緩沖時(shí)間方法的比較

3.2 質(zhì)量魯棒性與解魯棒性的權(quán)衡

質(zhì)量魯棒性和解魯棒性之間需要權(quán)衡,以二者帶權(quán)重的線(xiàn)性組合為目標(biāo)函數(shù)來(lái)解決多目標(biāo)問(wèn)題, 不同權(quán)重下得到不同偏好的解.以n=10、m=5的情況為例,比較不同權(quán)重下的zq和zs,圖3展示了緩沖為決策量、緩沖為期望值以及無(wú)緩沖所得到的解.無(wú)緩沖(α=1,β=0)時(shí)所得到解的zq最好,而加了緩沖時(shí)間能夠明顯改善zs,當(dāng)α=0.9,β=0.1時(shí)的zq已接近緩沖為期望值時(shí)的解,而zs優(yōu)于后者,因此可以使用本文方法犧牲一小部分質(zhì)量魯棒性以獲取解魯棒性的顯著改善.在生產(chǎn)過(guò)程中,可以根據(jù)實(shí)際情況靈活選取權(quán)重α和β.

圖3 不同決策方法下質(zhì)量魯棒性與解魯棒性的對(duì)比圖Fig.3 quality robustness and solution robustness under different decision methods

圖4 不同方法的質(zhì)量魯棒性分布概率Fig.4 Probability distribution of quality robustness under different methods

如圖4所示為上述例子中不同權(quán)重下緩沖時(shí)間為決策量時(shí)與緩沖均為期望值時(shí)zq的分布概率Pd比較. 從圖4(a)～(c)可以看出,zq的權(quán)重越大,均值越小但更分散,而緩沖時(shí)間為決策量比為期望值時(shí)的zq分布更集中.如圖4(d)所示為無(wú)緩沖與緩沖為期望值時(shí)zq的分布比較.可以看出,無(wú)緩沖時(shí)zq的概率分布最分散.即使不考慮zs而只考慮zq的穩(wěn)定性,也有必要插入一定的緩沖時(shí)間.

如圖5所示為不同方法的甘特圖比較.圖中，t為時(shí)間，N為機(jī)器序號(hào).可以看出,當(dāng)不考慮緩沖時(shí)間(α=1,β=0)時(shí),由于流水線(xiàn)上、下游之間的關(guān)系,系統(tǒng)存在少量的空閑時(shí)間,但這些空閑時(shí)間不足以吸收故障帶來(lái)的對(duì)調(diào)度的干擾.緩沖為決策量(α=0.9,β=0.1)與緩沖為期望值相比,所得的緩沖時(shí)間不同.緩沖為期望值時(shí)均勻地在調(diào)度中加入了少量緩沖時(shí)間；當(dāng)緩沖為決策量時(shí),在較易發(fā)生故障的機(jī)器和相應(yīng)較易發(fā)生故障的時(shí)間上加入緩沖時(shí)間,并且受調(diào)度的影響,在加工任務(wù)緊時(shí)自動(dòng)減少緩沖時(shí)間.由前述結(jié)論已知,兩者的質(zhì)量魯棒性zq相接近,而緩沖為決策量時(shí)的解魯棒性zs較優(yōu),由此可見(jiàn)使用本文算法能夠更好地改善解魯棒性.

4 結(jié) 語(yǔ)

本文設(shè)計(jì)了內(nèi)、外兩層嵌套式的前攝優(yōu)化調(diào)度算法,以求解帶有隨機(jī)故障的流水線(xiàn)調(diào)度問(wèn)題.以質(zhì)量魯棒性和解魯棒性綜合指標(biāo)作為目標(biāo)函數(shù),結(jié)合流水線(xiàn)的特點(diǎn)提出代理指標(biāo),并證明了代理指標(biāo)的有效性.與仿真方法相比,可以大幅地節(jié)省計(jì)算時(shí)間.不同數(shù)據(jù)規(guī)模下的實(shí)驗(yàn)結(jié)果顯示,本文算法與2種傳統(tǒng)方法相比,所得到的解的綜合指標(biāo)更優(yōu)異;此外,通過(guò)算例說(shuō)明了雙目標(biāo)不同權(quán)重下目標(biāo)值的變化情況,決策者可以根據(jù)偏好選擇相應(yīng)解.未來(lái)的工作方向是在本文研究的流水線(xiàn)環(huán)境下前攝調(diào)度基礎(chǔ)上, 考慮多種不確定性, 依據(jù)機(jī)器狀態(tài)、故障概率研究由不同反應(yīng)規(guī)則構(gòu)成的反應(yīng)調(diào)度,設(shè)計(jì)相應(yīng)的前攝-反應(yīng)調(diào)度算法.

[1] ZANDIEH M, GHOLAMI M. An immune algorithm for scheduling a hybrid flow shop with sequence-dependent setup times and machines with random breakdowns [J]. International Journal of ProductionResearch, 2009, 47(24): 6999-7027.

[2] CHAARI T, CHAABANE S, LOUKIL T, et al. Agenetic algorithm for robust hybrid flow shop scheduling [J]. International Journal of Computer Integrated Manufacturing, 2011, 24(9): 821-833.

[3] 陳勇,潘益菁,王亞良,等.多態(tài)性作業(yè)車(chē)間魯棒調(diào)度CA-GA建模[J].浙江工業(yè)大學(xué)學(xué)報(bào), 2014(2): 124-131. CHEN Yong, PAN Yi-jing, WANG Ya-liang , et al. Research on modeling of robust scheduling for polymorphism job shop based on cellular automata and genetic algorithm [J]. Journal of Zhejiang University of Technology, 2014(2): 124-131.

[4] HERROELEN W, LEUS R. Project scheduling under uncertainty: survey and research potentials [J]. European Journal of Operational Research, 2005, 165(2):289-306.

[5] MEHTA S V, UZSOY R. Predictable scheduling of a single machine subject to breakdowns [J]. International Journal of Computer Integrated Manufacturing, 1999,12(1): 15-38.

[6] LIU L, GU H, XI Y. Robust and stable scheduling of a single machine with random machine breakdowns [J]. International Journal of Advanced Manufacturing Technology, 2007, 31(7/8): 645-654.

[7] RAJENDRAN C, HOLTHAUS O. A comparative study of dispatching rules in dynamic flowshops and jobshops [J]. European Journal of OperationalResearch, 1999, 116(1): 156-170.

[8] KIANFAR K, GHOMI S M T F, KARIMI B. New dispatching rules to minimize rejection and tardiness costs in a dynamic flexible flow shop [J]. International Journal of Advanced Manufacturing Technology, 2009, 45(7/8): 759-771.

圖5 不同方法下的基礎(chǔ)調(diào)度甘特圖比較Fig.5 Comparison of Gantt charts under different baseline schedules with different methods

[9] HASAN S M K, SARKER R, ESSAM D. Genetic algorithm for job-shop scheduling with machine unavailability and breakdowns [J]. International Journal of Production Research, 2011, 49(16): 4999-5015.

[10] 丁帥,李鐵克,施燦濤. 考慮機(jī)器故障的HFS重調(diào)度研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012, 48(23): 234-238. DING Shuai, LI Tie-ke, SHI Can-tao. Study of hybrid flow shop rescheduling with consideration of machine breakdown [J]. Computer Engineering and Applications, 2012, 48(23): 234-238.

[11] BAI D. Asymptotic analysis of online algorithms and improved scheme for the flow shop scheduling problem with release dates [J]. International Journal of Systems Science, 2015, 46(11): 1994-2005.

[12] ZHAO F, LI N. Flow time and tardiness based on new scheduling rules for dynamic shop scheduling withmachine breakdown [J]. Mechatronics Engineering, Computing and Information Technology, 2014, 556-562: 4412-4416.

[13] KATRAGJINI K, VALLADA E, RUIZ R. Flow shop rescheduling under different types of disruption [J]. International Journal of Production Research, 2013, 51(3): 780-797.

[14] WANG K, CHOI S H, QIN H, et al. A cluster-based scheduling model using SPT and SA for dynamic hybrid flow shop problems [J]. International Journal ofAdvanced Manufacturing Technology, 2013, 67(9-12): 2243-2258.

[15] RAHMANI D, HEYDARI M. Robust and stable flow shop scheduling with unexpected arrivals of new jobs and uncertain processing times [J]. Journal of Manufacturing Systems, 2014, 33(1): 84-92.

Proactive scheduling optimization on flow shops with random machine breakdowns

ZHAO Chan-yuan1, LU Zhi-qiang1, CUI Wei-wei2

(1.DepartmentofMechanicalandEnergyEngineering,TongjiUniversity,Shanghai201804,China;2.DepartmentofIndustrialEngineeringandLogisticsManagement,ShanghaiJiaotongUniversity,Shanghai200240,China)

Flow shop scheduling problems with random machine breakdowns were analyzed in order to optimize the bi-objective of quality robustness and solution robustness. The impact of breakdowns was analyzed by proactive scheduling theory. A stochastic programming mathematical model was proposed. Then the nested algorithm with two loops was developed to simultaneously determine jobs’ sequence and buffer time. The outer optimization loop combined NEH algorithm and neighborhood search method to determine jobs’ sequence. The inner loop adopted the genetic algorithm to optimize the buffer time with an effective surrogate measure, which was adopted as the evaluation method of solutions. Computational results indicate that the solution performance can be significantly improved with the proposed algorithm comparing with the traditional ways, and decision makers can choose different biased solutions according to their preference. Inserting buffer time improved the solution robustness and increased the stability of quality robustness.

flow shop; random machine breakdown; robustness; surrogate measure

2015-04-03. 浙江大學(xué)學(xué)報(bào)(工學(xué)版)網(wǎng)址： www.journals.zju.edu.cn/eng

國(guó)家自然科學(xué)基金資助項(xiàng)目(71171130, 61273035).

趙嬋媛(1990—), 女, 碩士生, 從事串行生產(chǎn)線(xiàn)生產(chǎn)調(diào)度的研究. ORCID: 0000-0002-6582-2860. E-mail: zhchy90@hotmail.com 通信聯(lián)系人: 陸志強(qiáng), 男, 教授. ORCID: 0000-0002-9357-610X. E-mail: zhiqianglu@#edu.cn

10.3785/j.issn.1008-973X.2016.04.007

F 224

A

1008-973X(2016)04-0641-09