趙嬋媛, 陸志強, 崔維偉

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

?

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

趙嬋媛1, 陸志強1, 崔維偉2

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

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

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

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

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

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

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

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

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

1.1 問題描述

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

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

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

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

定義的決策變量如下.

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

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

輔助變量如下.

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

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

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

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

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

2 算法設(shè)計

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

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

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

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

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

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

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

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

7) 若st

8) 若r

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

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

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

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

(16)

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

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

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

2.2 代理指標(biāo)

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

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

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

圖2 帶有緩沖時間的流水線基礎(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)的驗證 運用VS C#進行編程, 通過仿真數(shù)據(jù)實驗對前述代理指標(biāo)進行評價, 比較原目標(biāo)函數(shù)與代理指標(biāo)的相關(guān)性及計算用時. 本文采用置信區(qū)間法計算仿真重復(fù)次數(shù), 取顯著水平為1%, 求得重復(fù)次數(shù)為1 000.

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

3 數(shù)據(jù)實驗

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

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

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

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

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

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

圖3 不同決策方法下質(zhì)量魯棒性與解魯棒性的對比圖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)重下緩沖時間為決策量時與緩沖均為期望值時zq的分布概率Pd比較. 從圖4(a)～(c)可以看出,zq的權(quán)重越大,均值越小但更分散,而緩沖時間為決策量比為期望值時的zq分布更集中.如圖4(d)所示為無緩沖與緩沖為期望值時zq的分布比較.可以看出,無緩沖時zq的概率分布最分散.即使不考慮zs而只考慮zq的穩(wěn)定性,也有必要插入一定的緩沖時間.

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

4 結(jié) 語

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

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

趙嬋媛(1990—), 女, 碩士生, 從事串行生產(chǎn)線生產(chǎn)調(diào)度的研究. ORCID: 0000-0002-6582-2860. E-mail: zhchy90@hotmail.com 通信聯(lián)系人: 陸志強, 男, 教授. 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