基于改進(jìn)定向搜索算法的作業(yè)車間瓶頸控制研究

,

(浙江工業(yè)大學(xué) 工業(yè)工程研究所，浙江 杭州 310014)

隨著市場(chǎng)經(jīng)濟(jì)的發(fā)展，使得企業(yè)生產(chǎn)受到越來越多不確定性因素的影響，如訂單需求的減少、產(chǎn)品生命周期的縮短、生產(chǎn)異常等.這些不確定因素導(dǎo)致了生產(chǎn)過程的不穩(wěn)定，形成了生產(chǎn)瓶頸，如何在這種復(fù)雜多變的制造環(huán)境下對(duì)作業(yè)車間瓶頸進(jìn)行控制，已經(jīng)成為當(dāng)前車間控制技術(shù)研究的一個(gè)重點(diǎn)[1-2].近年來，有很多學(xué)者對(duì)其進(jìn)行了不同方向的探索，文獻(xiàn)[3]以設(shè)備利用率最大為生產(chǎn)物流瓶頸定義，同時(shí)在采用工藝路徑和工序分割的方法基礎(chǔ)上，應(yīng)用遺傳算法對(duì)生產(chǎn)系統(tǒng)進(jìn)行排程.文獻(xiàn)[4]利用改進(jìn)的微粒群算法構(gòu)建一個(gè)加權(quán)工期和最小的初始調(diào)度計(jì)劃，并基于關(guān)鍵鏈管理方法對(duì)初始調(diào)度計(jì)劃進(jìn)行合理地緩沖設(shè)置，消除了車間內(nèi)瓶頸的影響.文獻(xiàn)[5-6]采用啟發(fā)式規(guī)則和遺傳算法相結(jié)合的方法對(duì)車間進(jìn)行了重調(diào)度的研究.這些研究在車間重調(diào)度方面有很大的優(yōu)勢(shì)，但往往存在原調(diào)度方案破壞程度大，作業(yè)調(diào)整范圍廣的問題，并且在重調(diào)度中并未考慮設(shè)備完成任務(wù)的能力指標(biāo).在此基礎(chǔ)上，以柔性作業(yè)車間為研究對(duì)象，采用改進(jìn)的過濾定向搜索算法，以瓶頸產(chǎn)生觸發(fā)重調(diào)度，可以最小程度影響原調(diào)度方案，大大降低重調(diào)度實(shí)施難度，具有重要研究意義.

1 作業(yè)車間瓶頸問題模型

為確定作業(yè)車間瓶頸，建立基于瓶頸的動(dòng)態(tài)調(diào)度模型，需要對(duì)作業(yè)車間進(jìn)行數(shù)學(xué)描述.對(duì)于一作業(yè)車間S，有n個(gè)作業(yè)在m臺(tái)設(shè)備上加工，并且每個(gè)作業(yè)Ji有s道工序需要加工.令J為作業(yè)集合，并有J={Ji|0

選擇以完工時(shí)間和設(shè)備利用率雙目標(biāo)因素作為優(yōu)化目標(biāo)，并進(jìn)行以下符號(hào)定義：cijk為工件j的i工序在設(shè)備k上的完工時(shí)間；sijk為工件j的i工序在設(shè)備k上的開始加工時(shí)間；pijk為工件j的i工序在設(shè)備k上的加工時(shí)間；W為優(yōu)化目標(biāo)；Fm為完工時(shí)間目標(biāo)因素；Fe為關(guān)鍵設(shè)備負(fù)荷因素；wm為完工時(shí)間目標(biāo)因素加權(quán)值；we為關(guān)鍵設(shè)備負(fù)荷因素加權(quán)值.定義變量為

則作業(yè)車間瓶頸優(yōu)化模型為

W=min(wmFm+weFe)

(1)

其中

(2)

(3)

s.t.wm+we=1

(4)

∑αijk=1,?Mk∈Mij

(5)

sijk≥cljk，且i>l

(6)

sijk≥cghk，且βijghk=1

(7)

i,j,k,g,h,l≥1

(8)

式(4)表示了雙約束的加權(quán)值和為1；式(5)表示了同一個(gè)工序只能在一臺(tái)設(shè)備上加工；式(6)表示了每個(gè)工件中各工序的順序約束；式(7)表示了每臺(tái)設(shè)備中加工的各工序的順序約束.

2 作業(yè)車間瓶頸的控制方法

2.1 作業(yè)車間瓶頸控制模型

為了描述作業(yè)車間瓶頸控制的動(dòng)態(tài)特征，采用Petri網(wǎng)建模技術(shù)進(jìn)行建模.黑色粗線表示變遷(transition)，以t表示，代表各個(gè)車間活動(dòng)，圓圈表示庫所(place)，以p表示，代表作業(yè)車間活動(dòng)的狀態(tài).作業(yè)車間瓶頸控制模型見圖1.

圖1 作業(yè)車間瓶頸控制模型

2.2 作業(yè)車間瓶頸控制策略

當(dāng)瓶頸產(chǎn)生時(shí)，會(huì)導(dǎo)致原有調(diào)度策略發(fā)生不可逆的破壞，并且隨著設(shè)備數(shù)量、工件數(shù)量以及擾動(dòng)影響工序數(shù)量的增加，作業(yè)車間的瓶頸問題模型會(huì)呈指數(shù)級(jí)增長(zhǎng)，一般的車間管理辦法無法解決，所以提出應(yīng)用過濾定向搜索算法的基于不可預(yù)測(cè)瓶頸的控制策略.

2.2.1 算法描述

過濾定向搜索算法(Filtered-beam-search,FBS)是分支定界法的一種改進(jìn)方法，其原理是對(duì)問題進(jìn)行逐層搜索，并從搜索樹中選取最有優(yōu)勢(shì)f(定向過濾寬度)個(gè)節(jié)點(diǎn)作為候選節(jié)點(diǎn)，其余節(jié)點(diǎn)在本層搜索中將永久刪除，再從候選節(jié)點(diǎn)中選取b(定向搜索寬度)個(gè)節(jié)點(diǎn)(定向搜索節(jié)點(diǎn))作為調(diào)度節(jié)點(diǎn)，其他沒被選中的節(jié)點(diǎn)在本層搜索中也將被永久刪除，最后以定向搜索節(jié)點(diǎn)為調(diào)度節(jié)點(diǎn)應(yīng)用分支策略進(jìn)行可調(diào)度節(jié)點(diǎn)分支，形成新的一層調(diào)度方案.為了能夠從全局中搜索到定向搜索節(jié)點(diǎn)，需要引用局部評(píng)價(jià)函數(shù)(Local evaluation function)和全局評(píng)價(jià)函數(shù)(Global evaluation function).局部評(píng)價(jià)函數(shù)用來在可行節(jié)點(diǎn)中選取f個(gè)候選節(jié)點(diǎn)，而全局評(píng)價(jià)函數(shù)用來在f個(gè)候選節(jié)點(diǎn)中選取b個(gè)定向搜索節(jié)點(diǎn).

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

1) 分支策略.每一層的節(jié)點(diǎn)包含兩方面的信息，一是該節(jié)點(diǎn)必須是該層可調(diào)度的節(jié)點(diǎn)，二是每個(gè)節(jié)點(diǎn)需確定加工設(shè)備和加工開始時(shí)間.為此，采用改進(jìn)的可調(diào)度工序優(yōu)先策略.作為分支策略.假設(shè)Dl是一個(gè)已經(jīng)有l(wèi)層的局部調(diào)度集合，Pl為第l層可調(diào)度工序集合，sij為工序Oij∈Dl的加工開始時(shí)間，有sij=s(i-1)j+p(i-1)jk.令時(shí)間TMijk為可加工工序Oij的機(jī)床Mk最早可使用時(shí)間，TM*=min{TMijk}，且Oij∈pl+1，Mk∈Mij則有TMijk∈TM*的工序Oijk形成集合O*，l+1層的可調(diào)度工序?yàn)镺*∈pl+1，sijk=max(sij，TMijk).

2) 評(píng)價(jià)函數(shù).為了在不可預(yù)測(cè)瓶頸的擾動(dòng)下盡可能快的恢復(fù)生產(chǎn)，以及能夠在多個(gè)選擇中平衡資源負(fù)載，采用最小加工時(shí)間規(guī)則(Shortest processing time，SPT)[7]和機(jī)床負(fù)載平衡規(guī)則(Machine load balance，MLB)[8]雙層調(diào)度規(guī)則作為全局評(píng)價(jià)函數(shù)，而為保證加工設(shè)備完成生產(chǎn)任務(wù)的可靠性，采用SPT、信用能力評(píng)價(jià)指標(biāo)Ejt和MLB雙層調(diào)度規(guī)則作為局部評(píng)價(jià)函數(shù)，即首先應(yīng)用SPT和Ejt加權(quán)評(píng)價(jià)指標(biāo)LE對(duì)節(jié)點(diǎn)進(jìn)行局部評(píng)價(jià)，選取f個(gè)局部調(diào)度節(jié)點(diǎn)，若有大于f個(gè)節(jié)點(diǎn)，再應(yīng)用MLB對(duì)剩下節(jié)點(diǎn)的選擇進(jìn)行過濾.為了對(duì)局部調(diào)度節(jié)點(diǎn)進(jìn)行全局評(píng)價(jià)，首先應(yīng)用SPT形成全局調(diào)度，選取b個(gè)定向搜索節(jié)點(diǎn)，若有大于b個(gè)節(jié)點(diǎn)，再應(yīng)用MLB對(duì)剩下的節(jié)點(diǎn)進(jìn)行第二次篩選.其公式為

LE=θSPTESPT+θEEjt+N

(9)

其中

(10)

ξk為該加工設(shè)備完成第k次任務(wù)的信用質(zhì)量獎(jiǎng)勵(lì)因子；ρk為該加工設(shè)備完成第k次任務(wù)的信用質(zhì)量懲罰因子，并且ρk>ξk，θSPT和θE為加權(quán)系數(shù)，且θSPT>0，θE<0，N為足夠大的正數(shù).

2.2.3 算法流程

圖2為改進(jìn)的過濾定向搜索算法流程，具體描述為：

Step1初始化算法，設(shè)定算法參數(shù)b，f，工序數(shù)q，調(diào)度層標(biāo)識(shí)l，解數(shù)量標(biāo)識(shí)m，以及瓶頸問題模型參數(shù).

Step2應(yīng)用分支策略生成子節(jié)點(diǎn)，確定pl初始值，節(jié)點(diǎn)數(shù)量n，并且層標(biāo)識(shí)l+1.

Step3判斷節(jié)點(diǎn)數(shù)是否大于定向搜索寬度b，若大于或等于執(zhí)行下一步，若小于則返回上一步.

Step4為保證調(diào)度全局最優(yōu)，首先對(duì)初始調(diào)度節(jié)點(diǎn)進(jìn)行全局評(píng)價(jià)，并更新pl.

Step5可行解數(shù)量循環(huán).可行解數(shù)量標(biāo)識(shí)m+1，判斷可行解的數(shù)量是否大于b，若是則執(zhí)行Step11，若否執(zhí)行下一步.

Step6調(diào)度層循環(huán).調(diào)度層標(biāo)識(shí)l+1，判斷層標(biāo)識(shí)是否大于工序數(shù)量，若是執(zhí)行Step10，若否執(zhí)行下一步.

Step7應(yīng)用分支策略生成子節(jié)點(diǎn)，節(jié)點(diǎn)數(shù)量為n′.

Step8對(duì)節(jié)點(diǎn)進(jìn)行局部評(píng)價(jià)，局部評(píng)價(jià)函數(shù)為L(zhǎng)E.

Step9對(duì)局部調(diào)度節(jié)點(diǎn)進(jìn)行全局評(píng)價(jià)，評(píng)價(jià)策略為SPT和MLB，并更新pl.

Step10形成調(diào)度解.

Step11對(duì)所有調(diào)度解計(jì)算目標(biāo)函數(shù)W，選擇最優(yōu)解.

圖2 過濾定向搜索算法流程

3 實(shí)例應(yīng)用

3.1 實(shí)例選取

3.1.1 基本加工信息

為了驗(yàn)證瓶頸控制策略的有效性，選取了某千斤頂生產(chǎn)企業(yè)作為應(yīng)用實(shí)例.該企業(yè)作業(yè)車間共有8臺(tái)設(shè)備資源，分別為M1，M2，M3，…，M8，其自制件共有8種，分別為：J1,J2,J3,…，J8,每種工件有3—4個(gè)工序，每種工序可由不同的設(shè)備進(jìn)行加工，屬于較典型的離散型制造系統(tǒng).表1工序加工時(shí)間和信用能力評(píng)價(jià)指標(biāo)表，表2為各工件的交貨期.

表1 工序加工時(shí)間和信用能力評(píng)價(jià)指標(biāo)表1)

表2 工件交貨期

3.1.2 初始調(diào)度

該企業(yè)根據(jù)內(nèi)部生產(chǎn)計(jì)劃生成作業(yè)車間初始調(diào)度方案，如圖3所示.初始調(diào)度方案為靜態(tài)調(diào)度，并未考慮系統(tǒng)中可能發(fā)生的動(dòng)態(tài)事件.圖中任務(wù)矩形標(biāo)識(shí)格式為“工件-工序”，如圖3中“3-1”表示了作業(yè)3的第一個(gè)工件O13.矩形下方為該任務(wù)的開始時(shí)間和結(jié)束時(shí)間.

圖3 初始調(diào)度甘特圖

3.1.3 動(dòng)態(tài)事件

為了評(píng)價(jià)瓶頸控制策略對(duì)系統(tǒng)中動(dòng)態(tài)事件的處理能力，選取在日常生產(chǎn)中發(fā)生頻率較高的設(shè)備故障事件進(jìn)行仿真，在時(shí)間t=5的時(shí)刻，設(shè)備M6發(fā)生故障，并在當(dāng)前生產(chǎn)周期中無法恢復(fù)投產(chǎn).

3.2 瓶頸控制策略驗(yàn)證及評(píng)價(jià)

根據(jù)企業(yè)歷史數(shù)據(jù)，設(shè)置算法的參數(shù)值如表3所示.

表3 算法參數(shù)

采用2.2中提到控制策略進(jìn)行重新調(diào)度.根據(jù)表3中的算法參數(shù)，進(jìn)行過濾定向搜索算法計(jì)算，得出設(shè)備M6故障下的重調(diào)度甘特圖，如圖4所示.

圖4 M6故障下的重調(diào)度甘特圖

由瓶頸控制策略對(duì)動(dòng)態(tài)事件的控制，可以得出初始調(diào)度、動(dòng)態(tài)事件下的重調(diào)度完工時(shí)間對(duì)比結(jié)果，如表4所示，以及重調(diào)度設(shè)備負(fù)荷對(duì)比結(jié)果，如表5所示.

表4 重調(diào)度完工時(shí)間對(duì)比

表5 重調(diào)度設(shè)備負(fù)荷對(duì)比

由表4可知：在動(dòng)態(tài)調(diào)度下的最大完工時(shí)間均為15，較擾動(dòng)前增加了1 h，但并未超出各工件的交貨期，可以接受.由表5可知：經(jīng)過重調(diào)度設(shè)備負(fù)荷極差僅為5，具有較大幅度的提升.由此可見，在動(dòng)態(tài)事件的影響下，瓶頸控制策略能夠很好的處理作業(yè)車間中的擾動(dòng)，具有有效性.

4 結(jié) 論

為了對(duì)作業(yè)車間瓶頸進(jìn)行控制，并減少瓶頸對(duì)系統(tǒng)的影響，提出了基于改進(jìn)的過濾定向搜索算法的離散車間瓶頸控制研究.結(jié)果表明：給出了作業(yè)車間瓶頸問題模型，以完工時(shí)間和設(shè)備利用率作為優(yōu)化目標(biāo)建立了目標(biāo)函數(shù)；給出了作業(yè)車間瓶頸控制方法，建立了瓶頸控制模型，給出了基于改進(jìn)的過濾定向搜索算法的瓶頸控制策略；進(jìn)行了實(shí)例驗(yàn)證.選取某千斤頂生產(chǎn)企業(yè)作為實(shí)例，說明了基于改進(jìn)的過濾定向搜索算法的瓶頸控制策略有效性.但研究中未考慮瓶頸對(duì)生產(chǎn)系統(tǒng)的影響程度，只對(duì)具有破壞性影響的瓶頸進(jìn)行控制，還可以針對(duì)瓶頸的影響程度做進(jìn)一步研究.

參考文獻(xiàn)：

[1] JIN Feng, WU Cheng. Research status and prospects for massive production scheduling[J]. Computer Integrated Manufacturing Systems,2006,12(2):161-168．

[2] BASSETT M H, PEKNY J F, REKLAITIS G V. Decomposition techniques for the solution of large-scale scheduling problems[J].AIChE Journal,1996,42(12):3373-3387．

[3] 何文錦,魯建廈,李修琳.基于生產(chǎn)物流瓶頸的生產(chǎn)排程研究[J].輕工機(jī)械,2013,2(1):101-110.

[4] 張沙清,陳新度,陳慶新,等.基于改進(jìn)微粒群算法的模具多項(xiàng)目動(dòng)態(tài)調(diào)度[J].計(jì)算機(jī)集成制造,2011,17(3):622-629.

[5] 肖志嬌,常會(huì)友,衣楊.啟發(fā)式規(guī)則與GA結(jié)合的優(yōu)化方法求解工作流動(dòng)態(tài)調(diào)度優(yōu)化問題[J].計(jì)算機(jī)科學(xué),2007,34(2):157-191.

[6] 魏英姿,谷侃鋒.基于性能預(yù)測(cè)的遺傳強(qiáng)化學(xué)習(xí)動(dòng)態(tài)調(diào)度方法[J].系統(tǒng)仿真學(xué)報(bào)2010,22(12):2809-2820.

[7] 應(yīng)晨,魯建廈,湯洪濤.一種基于加工優(yōu)先級(jí)的在制品控制方法[J].浙江工業(yè)大學(xué)學(xué)報(bào),2012，40(6):679-684.

[8] 陸漢東,何衛(wèi)平,周旭.基于禁忌搜索的柔性作業(yè)車間分批調(diào)度[J].上海交通大學(xué)學(xué)報(bào),2012,46(12):2003-2008.

[9] 王世進(jìn),周炳海,奚立峰.基于過濾定向搜索的柔性制造系統(tǒng)動(dòng)態(tài)調(diào)度優(yōu)化[J].上海交通大學(xué)學(xué)報(bào),2007(1):94-101.

[10] 黃卓平,魯建廈,李修琳.基于延遲懲罰成本的生產(chǎn)物流瓶頸辨識(shí)研究[J].浙江工業(yè)大學(xué)學(xué)報(bào),2012,40(5):57-573.

[11] 孔令革,魯建廈,詹燕.基于排隊(duì)網(wǎng)絡(luò)的生產(chǎn)物流瓶頸轉(zhuǎn)移研究[J].浙江工業(yè)大學(xué)學(xué)報(bào),2011,39(6):644-647.