,

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

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

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

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

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

則作業(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)表示了雙約束的加權值和為1；式(5)表示了同一個工序只能在一臺設備上加工；式(6)表示了每個工件中各工序的順序約束；式(7)表示了每臺設備中加工的各工序的順序約束.

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

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

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

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

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

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

2.2.1 算法描述

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

2.2.2 算法設計

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

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

LE=θSPTESPT+θEEjt+N

(9)

其中

(10)

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

2.2.3 算法流程

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

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

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

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

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

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

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

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

Step8對節(jié)點進行局部評價，局部評價函數(shù)為LE.

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

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

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

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

3 實例應用

3.1 實例選取

3.1.1 基本加工信息

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

表1 工序加工時間和信用能力評價指標表1)

表2 工件交貨期

3.1.2 初始調(diào)度

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

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

3.1.3 動態(tài)事件

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

3.2 瓶頸控制策略驗證及評價

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

表3 算法參數(shù)

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

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

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

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

表5 重調(diào)度設備負荷對比

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

4 結 論

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

參考文獻：

[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].輕工機械,2013,2(1):101-110.

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

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

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

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

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

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

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

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