柔性Job Shops集成調(diào)度啟發(fā)式算法

周炳海, 趙　猛

(同濟(jì)大學(xué) 機(jī)械與能源工程學(xué)院,上海 201804)

?

柔性Job Shops集成調(diào)度啟發(fā)式算法

周炳海, 趙猛

(同濟(jì)大學(xué) 機(jī)械與能源工程學(xué)院,上海 201804)

摘要:為有效解決柔性作業(yè)車(chē)間(Job Shops)的加工與搬運(yùn)集成調(diào)度問(wèn)題,以最小化最大完工時(shí)間(Makespan)為調(diào)度目標(biāo),建立非線(xiàn)性規(guī)劃模型,提出基于貪婪啟發(fā)式策略的變鄰域搜索算法(GRS-RVNS).根據(jù)準(zhǔn)時(shí)(JIT)生產(chǎn)和均衡生產(chǎn)思想構(gòu)建貪婪啟發(fā)式策略快速求初始解.利用析取圖表示可行解并根據(jù)析取圖調(diào)度的性質(zhì)定理構(gòu)建有效的搜索鄰域,進(jìn)而利用隨機(jī)變鄰域搜索算法對(duì)初始解進(jìn)行優(yōu)化.對(duì)提出的算法進(jìn)行仿真實(shí)驗(yàn)分析,結(jié)果表明：該算法求解時(shí)間短、調(diào)度方法有競(jìng)爭(zhēng)性.

關(guān)鍵詞：搬運(yùn)；柔性作業(yè)車(chē)間(Job Shops)；調(diào)度；啟發(fā)式算法；變鄰域搜索算法(RVNS)

柔性作業(yè)車(chē)間(Job Shops)是經(jīng)典Job Shops的擴(kuò)展,適合實(shí)際生產(chǎn)中多品種小批量的生產(chǎn)模式.近來(lái),柔性Job Shops中逐漸引入自動(dòng)化搬運(yùn)設(shè)備,提高了生產(chǎn)效率的同時(shí)也引發(fā)了復(fù)雜度更高的加工與搬運(yùn)集成調(diào)度問(wèn)題.但是,目前關(guān)于柔性Job Shops調(diào)度問(wèn)題的研究絕大多數(shù)僅考慮加工工序而未考慮搬運(yùn)工序.因此,對(duì)柔性作業(yè)車(chē)間中加工和搬運(yùn)工序的集成調(diào)度問(wèn)題進(jìn)行研究具有重要的現(xiàn)實(shí)與理論意義.

考慮搬運(yùn)的Job Shops調(diào)度問(wèn)題可分為2類(lèi).第一類(lèi)是帶一個(gè)搬運(yùn)設(shè)備Job Shops調(diào)度問(wèn)題,該問(wèn)題需要對(duì)機(jī)床和搬運(yùn)設(shè)備同時(shí)調(diào)度.Hurink等[1]將單個(gè)運(yùn)輸設(shè)備視作含Set-up時(shí)間的機(jī)床,提出了禁忌搜索算法對(duì)問(wèn)題求解.Brucker等[2]針對(duì)問(wèn)題建立混合整數(shù)規(guī)劃模型并用CPLEX求解.第二類(lèi)是帶多個(gè)搬運(yùn)設(shè)備的Job Shop調(diào)度問(wèn)題,該類(lèi)問(wèn)題與前類(lèi)問(wèn)題相比還需考慮搬運(yùn)設(shè)備指派問(wèn)題.針對(duì)該類(lèi)問(wèn)題目前文獻(xiàn)多采用元啟發(fā)式算法,如:改進(jìn)蜜蜂群算法[3]、改進(jìn)型遺傳算法[4]、局域搜索算法[5]、禁忌搜索算法[6]、模擬退火算法及局域搜索的混合算法[7]等求解問(wèn)題.Lacomme等[8]針對(duì)該問(wèn)題提出了調(diào)度框架并設(shè)計(jì)了文化基因算法.

考慮搬運(yùn)的柔性作業(yè)車(chē)間調(diào)度問(wèn)題的復(fù)雜度更高,其調(diào)度任務(wù)包括為加工工序和搬運(yùn)工序分別指派機(jī)床和搬運(yùn)設(shè)備、確定工件在機(jī)床及搬運(yùn)設(shè)備上的排序.Zhang等[9]針對(duì)該問(wèn)題提出改進(jìn)轉(zhuǎn)換瓶頸算法,實(shí)驗(yàn)結(jié)果表明算法能夠求得較優(yōu)解,但是算法采用隨機(jī)方式為加工工序指派機(jī)床,這致使運(yùn)算比較耗時(shí).Zhang等[10]針對(duì)該問(wèn)題設(shè)計(jì)的結(jié)合遺傳算法和禁忌搜索算法的混合算法求解效果較好,但其隨機(jī)生成的初始解的質(zhì)量有待提高.Liu等[11]針對(duì)該問(wèn)題設(shè)計(jì)了微型蜜蜂群算法并嘗試求解大規(guī)模算例.

本文在上述研究的基礎(chǔ)上,針對(duì)考慮搬運(yùn)的柔性作業(yè)車(chē)間調(diào)度問(wèn)題建立數(shù)學(xué)模型并分析問(wèn)題特點(diǎn)構(gòu)造基于貪婪策略的變鄰域搜索算法(greedy heuristic strategy-random variable neighborhood searchalgorithm, GRS-RVNS)(變鄰域搜索算法(RVNS)能較好地求解組合優(yōu)化問(wèn)題[12-14]),旨在嘗試綜合利用構(gòu)造型啟發(fā)式算法的快速求解優(yōu)勢(shì)與搜索算法的強(qiáng)尋優(yōu)能力優(yōu)勢(shì)求解所研究問(wèn)題,并通過(guò)仿真實(shí)驗(yàn)驗(yàn)證算法的有效性.

1問(wèn)題描述與建模

Oi,jOi,j+1…Oi,ni.

其中,Oi,jTi,j表示Oi,j在Ti,j之前.調(diào)度任務(wù)是在滿(mǎn)足各種資源約束和工藝路線(xiàn)關(guān)系約束的前提下,為每道加工工序和搬運(yùn)工序指派最合適的機(jī)床和搬運(yùn)設(shè)備,確定每臺(tái)機(jī)器和每個(gè)搬運(yùn)設(shè)備上各道工序的最佳加工順序以及開(kāi)工時(shí)間使總完工時(shí)間(Makespan)Cmax最小.

作如下假設(shè)：1)機(jī)床的輸入和輸出緩存區(qū)足夠大,不會(huì)引起阻塞；2)單個(gè)機(jī)床的加工能力和單個(gè)搬運(yùn)搬運(yùn)設(shè)備的搬運(yùn)能力均為1；3)同一工件一次只能占用一臺(tái)機(jī)床或一個(gè)搬運(yùn)設(shè)備；4)所有工件和資源在調(diào)度開(kāi)始時(shí)刻均處于可調(diào)度狀態(tài),不考慮宕機(jī).

據(jù)筆者所收集的文獻(xiàn)資料,該調(diào)度問(wèn)題的數(shù)學(xué)模型較為鮮見(jiàn).本文基于以上定義,分析問(wèn)題特點(diǎn)及約束關(guān)系,建立如下數(shù)學(xué)模型：

minCmax.

(1)

s.t.

(2)

(3)

?j∈[1,ni-1],?R∈{R1，R2，…，Rr}.

(4)

?i,i′∈[1,n],?j,j′∈[1,ni],

?j′∈[1,ni′],?M∈{M1,M2，…，Mm}.

(5)

?j′∈[1,ni′-1],?R∈{R1,R2，…，Rr}.

(6)

(7)

?i,i′∈[1,n],?j∈[1,ni],?j′∈[1,ni′],

?M∈{M1,M2，…，Mm}.

(8)

(9)

?i,i′∈[1,n],?j∈[1,ni-1],?j′∈[1,ni′-1],

?R∈{R1,R2，…，Rr}.

(10)

(11)

?j∈[1,ni-1].

(12)

其中,式(1)表示調(diào)度目標(biāo)最小化最大完工時(shí)間最優(yōu),式(2)表示最小化最大完工時(shí)間大于等于各工件的尾工序的結(jié)束時(shí)間,式(3)表示工件完成加工之后才能開(kāi)始搬運(yùn),式(4)表示工件運(yùn)輸?shù)綑C(jī)床之后才能開(kāi)始加工,式(5)表示一臺(tái)機(jī)床一次只能加工一個(gè)工件,式(6)表示一個(gè)搬運(yùn)設(shè)備一次只能搬運(yùn)一個(gè)工件,式(7)和(8)分別表示同一機(jī)床M上的2個(gè)加工工序之間的滿(mǎn)足先后順序關(guān)系,式(9)和(10)分別表示同一搬運(yùn)設(shè)備R完成的2個(gè)搬運(yùn)工序之間滿(mǎn)足先后順序關(guān)系,式(11)表示一個(gè)工件一次只能分配到一臺(tái)機(jī)床加工,式(12)表示一個(gè)工件一次只能由一臺(tái)搬運(yùn)設(shè)備完成搬運(yùn).

析取圖可直觀地表述可行解,一個(gè)包含3個(gè)工件、4臺(tái)機(jī)床、2個(gè)搬運(yùn)設(shè)備的柔性作業(yè)車(chē)間調(diào)度問(wèn)題的可行解用析取圖表示,如圖1所示.析取圖中從起點(diǎn)s到終點(diǎn)e的最長(zhǎng)路徑為關(guān)鍵路徑,其長(zhǎng)度可以利用圖論中的關(guān)鍵路徑算法[15]計(jì)算,關(guān)鍵路徑的長(zhǎng)度等于最小化最大完工時(shí)間.

圖1　可行解的析取圖表示Fig.1　Disjunctive graph for representation of feasible solutions

2算法構(gòu)建

為解決考慮搬運(yùn)的柔性作業(yè)車(chē)間調(diào)度問(wèn)題,設(shè)計(jì)一個(gè)基于貪婪啟發(fā)式策略的變鄰域搜索算法(GRS-RVNS).貪婪策略首先基于準(zhǔn)時(shí)化生產(chǎn)(just in time, JIT)生產(chǎn)和平衡生產(chǎn)思想定義機(jī)床和搬運(yùn)設(shè)備的復(fù)合指派系數(shù),同時(shí)為了使工序盡可能早地開(kāi)始加工且不影響其他工序,提出基于位置檢測(cè)的插入與追加綜合法計(jì)算工序的開(kāi)始時(shí)間.在貪婪策略求得初始解之后,用析取圖表示可行解并根據(jù)析取圖調(diào)度的性質(zhì)定理構(gòu)建有效的搜索鄰域,最后結(jié)合變鄰域搜索算法對(duì)初始解進(jìn)行優(yōu)化.

2.1貪婪啟發(fā)式策略

JIT生產(chǎn)能夠使工件盡早完成以縮短制造周期,而生產(chǎn)中資源利用越平衡越能削弱瓶頸資源對(duì)制造工期的不良影響,據(jù)此定義機(jī)床和搬運(yùn)設(shè)備的復(fù)合指派系數(shù).

定義1機(jī)床指派系數(shù)：

ΘM=w1ξ1+w2ξ2.

式中:

為JIT水平指標(biāo)(若機(jī)床M尚未分配加工任務(wù)則ξ1=0),該值越小表征工件越能及時(shí)加工；

表示當(dāng)前調(diào)度時(shí)刻機(jī)床的負(fù)載率,該值越小表征機(jī)床M的當(dāng)前負(fù)載率越低.w1和w2為權(quán)重系數(shù),滿(mǎn)足w1+w2=1.

定義2搬運(yùn)設(shè)備指派系數(shù)：

ΘR=w3ξ3+w4ξ4.

式中:

為JIT水平指標(biāo)(若搬運(yùn)設(shè)備R尚未分配搬運(yùn)任務(wù)則ξ3=0),該值越小表征工件越能及時(shí)被搬運(yùn)；

表示當(dāng)前調(diào)度時(shí)刻搬運(yùn)設(shè)備的負(fù)載率,該值越小表征機(jī)床R的當(dāng)前負(fù)載率越低.w3和w4為權(quán)重系數(shù),滿(mǎn)足w3+w4=1.

工序的開(kāi)始時(shí)間直接影響調(diào)度目標(biāo),為了使工序盡可能早地開(kāi)始加工且不影響其他工序,提出基于位置檢測(cè)的插入與追加綜合法計(jì)算工序的開(kāi)始時(shí)間.首先檢測(cè)同一機(jī)床或搬運(yùn)設(shè)備的已調(diào)度工序之間是否有合適的位置可以插入待調(diào)度工序,如果位置不存在,則利用追加法計(jì)算工序開(kāi)始時(shí)間,否則,利用插入法計(jì)算工序開(kāi)始時(shí)間.綜合方法定義如下.

定義3設(shè)OM中工序排序?yàn)閧O1,O2,…,Oλ,…,Oλe},appendOrInsert(Oi,j,M)定義如下.令

}.

否則用插入法計(jì)算,令

定義4設(shè)OR中工序排序?yàn)閧T1,T2…Tβ…Tβε},appendOrInsert(Tij,R)定義如下：令

否則用插入法計(jì)算,令

2.2鄰域結(jié)構(gòu)

變鄰域搜索算法在求解過(guò)程中根據(jù)某種優(yōu)化機(jī)制動(dòng)態(tài)地改變鄰域結(jié)構(gòu),從而避免陷入局部最優(yōu)而向全局最優(yōu)靠近,鄰域搜索結(jié)構(gòu)的優(yōu)劣是影響算法結(jié)果的重要因素.本文基于可行解的析取圖表示,定義機(jī)床塊MBlock為關(guān)鍵路徑Ps上連續(xù)的由同一臺(tái)機(jī)床加工的工序,搬運(yùn)塊RBlock為Ps上連續(xù)的由同一個(gè)搬運(yùn)設(shè)備完成的搬運(yùn)工序,基于文獻(xiàn)[1]提出的析取圖調(diào)度的性質(zhì)定理構(gòu)造以下4種鄰域.

定義5將SwapOnMBlock(s)記作N1(s),將MBlock內(nèi)的非首工序與前道工序交換直至其與首工序交換或者將非尾工序與后道工序交換直至其與尾工序交換.例如：若

MBlock=(Oi,j,Oi′,j′,Oi″,j″),則

N1(s)={(Oi′,j′,Oi,j,Oi″,j″),(Oi″,j″,Oi,j,Oi′,j′),(Oi,j,Oi″,j″,Oi′,j′),(Oi′,j′,Oi″,j″,Oi,j)}.

定義6將ExtraExchangeOnRBlock(s)記作N2(s),將RBlock內(nèi)非首工序與首工序交換或者將非尾工序與尾工序交換.例如,若

RBlock=(Ti,j,Ti′,j′,Ti″,j″),則

N2(s)={(Ti′,j′,Ti,j,Ti″,j″),(Ti″,j″,Ti′,j′,Ti,j),(Ti,j,Ti″,j″,Ti′,j′)}.

定義7將InnerExchangeOnRBlock(s)記作N3(s),隨機(jī)交換RBlock內(nèi)的2個(gè)非首尾工序.例如：若

RBlock=(Ti0,j0,Ti,j,Ti′,j′,Ti″,j″),則

N3(s)={(Ti0,j0,Ti′,j′,Ti,j,Ti″,j″)}.

定義8將Equilibrium(s)記作N4(s),為關(guān)鍵路徑上的加工工序重新指派負(fù)載率較低的可加工機(jī)床或?yàn)殛P(guān)鍵路徑上的搬運(yùn)工序重新指派負(fù)載率較低的可搬運(yùn)設(shè)備.

在鄰域搜索的過(guò)程中,遍歷當(dāng)前鄰域選出局部最優(yōu)解與初始解對(duì)比,若局部最優(yōu)解優(yōu)于初始解,則以該局部最優(yōu)解替換初始解,并以其作為出發(fā)點(diǎn)繼續(xù)在當(dāng)前鄰域進(jìn)行搜索；否則跳到下一個(gè)鄰域進(jìn)行搜索,直到滿(mǎn)足停止準(zhǔn)則.

2.3算法描述

基于以上定義,本文構(gòu)造的算法詳細(xì)描述如下.其流程圖如圖2所示.

步驟1確定可調(diào)度加工工序集：

步驟3令

步驟4執(zhí)行appendOrInsert(Oi*,j*,M*)

圖2　鄰域搜索算法流程圖Fig.2　Flow chart of neighborhood search algorithm

步驟8確定可調(diào)度搬運(yùn)工序集：

?i∈[1,n],?j∈[1,ni-1]}.

步驟10令

步驟11執(zhí)行appendOrInsert(Ti*,j*,R*).

步驟13更新相關(guān)加工工序的開(kāi)始時(shí)間.

步驟16變鄰域搜索(其中，k為領(lǐng)域結(jié)構(gòu)的序號(hào))：

1)初始化k=1；

2)若達(dá)到停止準(zhǔn)則,則轉(zhuǎn)步驟17；否則,執(zhí)行以下步驟；

3)隨機(jī)在Nk(s)中選擇x；

4)遍歷搜索x的鄰域Nk(x)中最好的解x′；

5)若Cmax(x′)

步驟17算法終止輸出所求解.

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

引入變量差距1：

引入變量差距2：

本文算法參數(shù)設(shè)置如下：w1、w3服從區(qū)間[0,1]上的均勻分布,w2和w4分別滿(mǎn)足w1+w2=1與w3+w4=1約束關(guān)系,在實(shí)驗(yàn)過(guò)程中根據(jù)算法流程對(duì)2組參數(shù)(w1,w2)和(w3,w4)分別隨機(jī)產(chǎn)生10組不同的參數(shù)組合,以局部結(jié)果最優(yōu)為依據(jù)確定最優(yōu)參數(shù)值.鄰域搜索順序也是影響變鄰域搜索算法的因素之一,為了避免重復(fù)某一個(gè)鄰域搜索順序,采用隨機(jī)變鄰域搜索策略,即在搜索過(guò)程中設(shè)置搜索步長(zhǎng)Step服從區(qū)間[1,kmax]的均勻分布,算法終止條件為連續(xù)10次迭代運(yùn)算結(jié)果無(wú)改善,實(shí)驗(yàn)結(jié)果如表1所示.其中INST4類(lèi)算例的第四列數(shù)據(jù)為利用文獻(xiàn)[9]中算法隨機(jī)指派機(jī)床的單次運(yùn)算結(jié)果,第六列數(shù)據(jù)為利用文獻(xiàn)[9]中算法多次運(yùn)算的最好結(jié)果.

表1本文算法與其他3種算法求解算例Makespan的結(jié)果對(duì)比

Tab.1Results comparison of Makespan by our algorithm and other three algorithms

算例MSB[9]GRSGTSGRS-RVNS1P01D1d115614998[10]1002P01D1t1939489[10]893P01T2t1939581[10]814P01T3t0959894[10]945P01D3d1224233220[10]2196P01D2d1158162158[10]1587PL01585854[5]568PL02656845[5]469PL03747045[5]4510PL04858645[5]4511EX119710096[10]9712EX12828682[10]8213EX13888884[10]8614EX14110112103[10]10615EX21109112103[10]10316EX22808376[10]7617EX23879186[10]8618EX24126129108[10]10819EX3111011299[10]9920EX32878985[10]8421EX33898986[10]8622EX34136135115[10]11523FJSP1173016901599[9]159424FJSP2167816521549[9]153225FJSP3109610991061[9]106026FJSP4111310961027[9]103127FJSP5141914031308[9]130828FJSP6140214171339[9]132529FJSP7141013661292[9]129130FJSP8146114501350[9]135031FJSP9158815911567[9]157432FJSP10201519981871[9]1871

3.1GRS運(yùn)算時(shí)間分析

在求解規(guī)模為100的算例用時(shí)約4 s,總體來(lái)看算法求解時(shí)間較短,適用于生產(chǎn)動(dòng)態(tài)中的實(shí)時(shí)調(diào)度.

3.2GRS運(yùn)算結(jié)果分析

根據(jù)表1統(tǒng)計(jì)各算例的Gap1值繪制圖3,觀察圖3可知對(duì)于前3類(lèi)算例Gap1值大多數(shù)為正值,而第4類(lèi)算例的多為非正值,4類(lèi)算例的Gap1均值依次為1.41%、0.10%、2.22%、-0.97%,表明對(duì)前3類(lèi)問(wèn)題GRS與文獻(xiàn)[9]中MSB算法相比求解結(jié)果沒(méi)有優(yōu)勢(shì),而對(duì)于INST4類(lèi)算例求解具有明顯優(yōu)勢(shì).這是因?yàn)榍?類(lèi)實(shí)例均為不含機(jī)床指派問(wèn)題,第四類(lèi)實(shí)例INST是包含機(jī)床指派的柔性作業(yè)車(chē)間調(diào)度問(wèn)題,而算法MSB采用的隨機(jī)指派機(jī)床的方式無(wú)法有效解決機(jī)床指派問(wèn)題,因此對(duì)結(jié)果造成不良影響.在運(yùn)算時(shí)間方面GRS和MSB的最長(zhǎng)用時(shí)約為15 s和600 s,綜合考慮運(yùn)算時(shí)間和求解結(jié)果,GRS能夠在較短的時(shí)間內(nèi)求解帶搬運(yùn)設(shè)備的作業(yè)車(chē)間調(diào)度問(wèn)題.

圖3　各算例差距1值對(duì)比分析Fig.3　Comparison of Gap1 values of each instance

圖4　ILS與GRS-VNS算法收斂性比較Fig.4　Convergence comparison for ILS and GRS-VNS algorithms

3.3GRS-RVNS算法收斂性分析

以算例9為例考察GRS-RVNS算法收斂性,并與文獻(xiàn)[5]中的ILS算法作對(duì)比如圖4所示.

可知本文算法在迭代約70次就得到最優(yōu)解,而ILS算法需要迭代約120次才得到最優(yōu)解,可見(jiàn)本文算法收斂速度較快,這說(shuō)明本文構(gòu)造鄰域結(jié)構(gòu)及變鄰域搜索方法是有效的.

3.4GRS-RVNS算法運(yùn)算結(jié)果分析

圖5　各類(lèi)算例非正差距2值比例Fig.5　Non-positive Gap2 values’proportion for each kind of instances

根據(jù)表1統(tǒng)計(jì)各算例的Gap2值繪制圖5,可知Gap2值在區(qū)間[-1.18%, 3.70%]內(nèi)變化,4類(lèi)算例的Gap2均值依次為0.26%、1.48%、0.43%、-0.18%,可見(jiàn)本文算法運(yùn)算結(jié)果與參照算法運(yùn)輸結(jié)果非常接近.但是Gap2正值和非正值的出現(xiàn)波動(dòng)較大,為進(jìn)一步分析運(yùn)算結(jié)果,統(tǒng)計(jì)各類(lèi)算例非正Gap2值所占比例繪制圖5.圖5表明4類(lèi)算例分別有83%、50%、75%、80%的運(yùn)算結(jié)果不比參照算法所求結(jié)果差.總體來(lái)看本文構(gòu)建的算法對(duì)求解帶搬運(yùn)設(shè)備的柔性作業(yè)車(chē)間調(diào)度問(wèn)題是有效的.

3.5搬運(yùn)設(shè)備數(shù)量對(duì)算法的影響

算例7、8、9、10所含的工件數(shù)和機(jī)床數(shù)相同(即搬運(yùn)任務(wù)數(shù)量相同),搬運(yùn)設(shè)備數(shù)依次為1、2、3、4,統(tǒng)計(jì)GRS-RVNS算法求解各算例結(jié)果繪制圖6.可知當(dāng)搬運(yùn)任務(wù)數(shù)量一定時(shí),隨著搬運(yùn)設(shè)備的增多總完工時(shí)間呈減小趨勢(shì).當(dāng)搬運(yùn)設(shè)備達(dá)到一定的數(shù)量之后,搬運(yùn)設(shè)備數(shù)目對(duì)總完工時(shí)間影響不大.據(jù)此可以利用本文算法為生產(chǎn)車(chē)間配置合理的搬運(yùn)設(shè)備數(shù)目提供理論依據(jù).

圖7　搬運(yùn)設(shè)備數(shù)量對(duì)GRS-VNS算法的影響Fig.7　Influence of number of handling equipment on GRS-VNS algorithm

4結(jié)語(yǔ)

本文建立了柔性作業(yè)車(chē)間的加工與搬運(yùn)集成調(diào)度問(wèn)題的數(shù)學(xué)模型,嘗試?yán)脴?gòu)造型啟發(fā)式算法與變鄰域搜索算法的綜合優(yōu)勢(shì)求解問(wèn)題,為此類(lèi)問(wèn)題的求解提供新思路.實(shí)驗(yàn)結(jié)果表明：基于JIT生產(chǎn)和均衡生產(chǎn)思想構(gòu)建的貪婪啟發(fā)式策略能夠快速有效地求解所研究問(wèn)題；基于可行解的析取圖表示方式構(gòu)建的搜索鄰域及隨機(jī)變鄰域搜索算法是有效的,且該算法有較好的收斂性.本文算法還可以為生產(chǎn)車(chē)間配置合理的搬運(yùn)設(shè)備數(shù)目提供理論依據(jù).

參考文獻(xiàn)(References)：

[1] HURINK J, KNUST S. Tabu search algorithms for job-shop problems with a single transport robot [J]. European Journal of Operational Research, 2005, 162(1): 99-111.

[2] BRUCKER P, BURKE E K, GROENEMEYER S. A mixed integer programming model for the cyclic job-shop problem with transportation [J]. Discrete Applied Mathematics, 2012, 160(13): 1924-1935.

[3] LEI D, GUO X. Scheduling job shop with lot streaming and transportation through a modified artificial bee colony [J]. International Journal of Production Research, 2013, 51(16): 4930-4941.

[4] CHAUDHRY I A, MAHMOOD S, SHAMI M. Simultaneous scheduling of machines and automated guided vehicles in flexible manufacturing systems using genetic algorithms [J]. Journal of Central South University of Technology, 2011, 18(5): 1473-1486.

[5] LACOMME P, LARABI M, TCHERNEV N. A disjunctive graph for the job-shop with several robot [C] ∥MISTA Conference. Paris: MISTA, 2007: 285-292.

[6] ZHENG Y, XIAO Y, SEO Y. A tabu search algorithm for simultaneous machine/AGV scheduling problem [J]. International Journal of Production Research, 2014,52(19): 5748-5763.

[7] DEROUSSI L, GOURGAND M, TCHERNEV N. A simple metaheuristic approach to the simultaneous scheduling of machines and automated guided vehicles [J]. International Journal of Production Research, 2008, 46(8): 2143-2164.

[8] LACOMME P, LARABI M, TCHERNEV N. Job-shop based framework for simultaneous scheduling of machines and automated guided vehicles [J]. International Journal of Production Economics, 2013, 143(1): 24-34.

[9] ZHANG Q, MANIER H, MANIER M A. A modified shifting bottleneck heuristic and disjunctive graph for job shop scheduling problems with transportation constraints [J]. International Journal of Production Research, 2014, 52(4): 985-1002.

[10] ZHANG Q, MANIER H, MANIER M A. A genetic algorithm with tabu search procedure for flexible job shop scheduling with transportation constraints and bounded processing times [J]. Computers and Operations Research, 2012, 39(7): 1713-1723.

[11]LIUZ,MAS,SHIY,etal.Solvingmulti-objectiveflexibleJobShopschedulingwithtransportationconstraintsusingamicroartificialbeecolonyalgorithm[C] ∥ 2013IEEE17thInternationalConferenceonComputerSupportedCooperativeWorkinDesign(CSCWD).Whistler：IEEE, 2013: 427-432.

[12]DRIESSELR,M?NCHL.Variableneighborhoodsearchapproachesforschedulingjobsonparallelmachineswithsequence-dependentsetuptimes,precedenceconstraints,andreadytimes[J].ComputersandIndustrialEngineering, 2011, 61(2): 336-345.

[13]MLADENOVIN,TODOSIJEVIR,UROEVID.TwolevelGeneralvariableneighborhoodsearchforAttractivetravelingsalesmanproblem[J].ComputersandOperationsResearch, 2014, 52(1): 341-348.

[14]MLADENOVIN,TODOSIJEVIR,UROEVID.Lessismore:Basicvariableneighborhoodsearchforminimumdifferentialdispersionproblem[J].InformationSciences, 2016, 326: 160-171.

[15] 嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu):C語(yǔ)言版 [M].北京：清華大學(xué)出版社有限公司,2002.

[16]BILGEü,ULUSOYG.AtimewindowapproachtosimultaneousschedulingofmachinesandmaterialhandlingsysteminanFMS[J].OperationsResearch, 1995, 43(6): 1058-1070.

收稿日期：2015-02-28.

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(71471135，61273035)；國(guó)家“863”高技術(shù)研究發(fā)展計(jì)劃資助項(xiàng)目(2009AA043000).

作者簡(jiǎn)介：周炳海(1965—), 男, 教授, 博導(dǎo)，從事離散制造系統(tǒng)維護(hù)、調(diào)度、建模與仿真研究.ORCID: 0000-0002-6599-9033. E-mail: bhzhou@#edu.cn

DOI:10.3785/j.issn.1008-973X.2016.06.009

中圖分類(lèi)號(hào)：TP 29

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1008-973X(2016)06-1073-07

Hybrid heuristic algorithm for integrated scheduling in flexible Job Shops

ZHOU Bing-hai, ZHAO Meng

(SchoolofMechanicalEngineering,TongjiUniversity,Shanghai201804,China)

Abstract:The non-linear programming model was developed with an objective of minimizing system Makespan to solve the integrated scheduling problem of processing and handling in flexible job shops effectively. A greedy heuristic strategy based variable neighborhood search algorithm (GRS-RVNS) was put forward. The greedy heuristic strategy was designed with the combination of the just in time (JIT) and balanced production ideas, in order to get initial solution rapidly. An effective neighbor was constructed based on the disjunctive graph representations of the feasible solutions and properties and theorems of the disjunctive graph scheduling. The neighbor was used in the random variable neighborhood search algorithm. Finally, the experiments were designed for the proposed algorithm. Results indicate that the computing time of the proposed algorithm is short and the scheduling method is promising.

Key words:handling, flexible job shops, scheduling, heuristic algorithm, variable neighborhood search algorithm