作業(yè)車間調(diào)度問題的隨機鄰域交換算法

1、第25卷第1期2010年2月系統(tǒng)工程學報JOURN AL OF SY STE M S E NGI N EER I N G Vol .25No .1Feb .2010作業(yè)車間調(diào)度問題的隨機鄰域交換算法崔健雙,李鐵克(北京科技大學經(jīng)濟管理學院,北京100083摘要:針對作業(yè)車間調(diào)度問題提出了一種隨機鄰域交換算法RNSA (rando m ne ighborhood s wapp ing algorith m .算法由幾個緊密銜接的執(zhí)行階段組成,其核心思想是如何設(shè)計生成多樣性調(diào)度以及如何判斷新調(diào)度的可行性.為此,采用了一種組合隨機鄰域交換策略并證明了一個調(diào)度可行性判定定理.為了驗證算法的有效性,對一

2、批Bench m ark 算例進行了測試并與國內(nèi)外現(xiàn)有研究結(jié)果做出了比較.關(guān)鍵詞:作業(yè)車間調(diào)度問題;隨機鄰域交換;關(guān)鍵路徑算法中圖分類號:TP273.1文獻標識碼:A 文章編號:1000-5781(201001-0111-05Rando m nei ghbor hood sw a pp i n g a lgor ith m for job shop scheduli n g pr oble mC U I J i an 2shuang,L I T ie 2ke(School of Econom ics and Manage ment,University of Science &Technol

3、ogy Beijing,Beijing 100083,China Ab stra ct:A r ando m neighborhood s wapping algorith m (RNS A is presented.The algorithm is co m 2posed of several interr e lated phases .Its key ideas a r e how to generate diversified s oluti ons and how t o judge if the ne w solutions a r e f easible .For doing t

4、hat,we put f or ward a random neighborhood s wapp ing policy and pr ove a theore m which indicates the calculability of a s olution is the sufficient and necessary conditi on f or its f easibility .F inally,the algorith m was tested with a batch of B ench 2m ark p r oble m s and compared w ith exist

5、ing a lgorithm s .Key word s:j ob shop scheduling pr oblem;random ne ighborhood s wapp ing;c ritica l path algorith m0引言作業(yè)車間調(diào)度問題是關(guān)于多類機調(diào)度問題的一類重要組合優(yōu)化問題.文獻1系統(tǒng)地總結(jié)了這類問題的研究進展.其中,采用遍歷搜索的方法由于受時間和資源的限制難以有大的突破,而通過諸如鄰域搜索2、混合遺傳3-5、轉(zhuǎn)移瓶頸加禁忌搜索6-7等近優(yōu)求解算法是目前研究熱點.本文提出的算法就屬于一種近優(yōu)求解算法.算法的核心思想是如何設(shè)計生成多樣性調(diào)度以及如何判斷新調(diào)度的可行性,為此

6、,采用了一種組合隨機鄰域交換策略來生成新的調(diào)度并證明了一個可行性判定定理來剔除不可行調(diào)度.對于不可行調(diào)度立即予以淘汰,以節(jié)省計算時間;對于可行調(diào)度則再利用關(guān)鍵路徑算法做反復(fù)地局部優(yōu)化,逐步逼近最優(yōu)值.1問題模型設(shè)J =J i n i =1、M =M k mk =1分別代表由n 個工件和m 臺機器組成的有限集合.工件J i 必須按照預(yù)先指定的順序O i1,O i2,O im (優(yōu)先順序約收稿日期;修訂日期5基金項目國家自然科學基金資助項目(:2007-10-27:2009-11-1.:70771008.束在各臺機器上依序加工.其中,Oik 表示工件Ji在機器M k上一次不可中斷加工且加工時間p

7、ik是已知的.同一個工件同時只能被一臺機器加工,而同一時間一臺機器只能加工一個工件(資源約束.若以C ik代表工件J i在機器M k上加工完成的時間,則最后一個工件在最后一臺機器上加工完成的時間稱為最大完工時間Cmax,即m akespan.設(shè)A代表受優(yōu)先順序約束限制的相鄰工序?qū)Φ募?E k代表在機器k上加工并且受資源約束限制的工序?qū)Φ募?要求在滿足優(yōu)先順序和資源約束條件下,對各個工件加工順序進行調(diào)度排序并確定這些工件在各臺機器上的開工時間rt ik0,以使得Cmax最小化,數(shù)學模型如下.M inCmax =M inm ax(rtik+pik(1s.t.rt jk-rt ikp ik,(i

8、,jA(2rt jk -rtikpik或rtik-rtjkpjk,(i,jEk(3rt ik0(4其中,式(2表示J j必須在J i之后加工(優(yōu)先順序約束;式(3要求同一臺機器同時只能加工一個工件(資源約束;式(4說明準備時間為0.2初始調(diào)度計算開始于一個初始調(diào)度.首先對每個工件按照其加工工序從小到大依次編號.在不考慮機器資源沖突的前提下,每個工件的第0道工序開工時間為0,其它后繼工序的開工時間等于其前道工序結(jié)束時間,得到各道工序的開工時間,即無資源約束的最早開工時間.然后利用下述規(guī)則獲得一個初始調(diào)度.定義1開工順序優(yōu)先指派規(guī)則把需要在同臺機器上加工的工件放在一起進行開工順序優(yōu)先指派,規(guī)則如下

9、:1無機器約束最早開工時間小的優(yōu)先;2若1相同,加工工序編號小的優(yōu)先;3若1、2都相同則工件序號小的優(yōu)先. 3計算m a ke span并做可行判斷Make span的計算原則是:在給定調(diào)度下,根據(jù)當前機器和工件的空閑狀態(tài),選擇最早可能被加工的工件立即開始加工在滿足問題所有約束條件的前提下,當前機器上當前工件的最早開工及完工時間可按照如下公式計算對m,mM;q,kN,有rt m q=m axet m k,e t mqe t m q=rt m q+p m q(5式中,m、m代表兩臺不同的機器,q、k代表兩個不同的工件.rt mq表示當前工件q在機器m上最早開工時間,e t m q表示最早完工時間

10、,p m q是加工時間.若給定的調(diào)度可行,則利用公式(5可以依次計算出每道工序的開、完工時間并最終得到m ake s pan.式(5稱為m ake s p an計算公式.定義2對于給定調(diào)度,若能夠按照公式(5計算得到所有操作的開工、完工時間,則該調(diào)度是可計算調(diào)度.引理1一個可計算調(diào)度是可行調(diào)度.證明因給定調(diào)度是可計算的,按照定義2,只需遵循公式(5即可得到所有操作的開、完工時間,包括m akespan.當在計算過程中由于e t m k或e t mq未知而影響到不能計算rt mq時,即轉(zhuǎn)向下一臺機器的當前工件繼續(xù)進行計算,直到完成為止.引理2一個可行調(diào)度是可計算的.證明使用反證法,假定可行調(diào)度不

11、可計算,則意味著或者et m k或者e t mq是未知的,于是對某些操作來說不能獲得它們的開工時間,影響到最終不能計算出makespan,而這與調(diào)度可行相矛盾.由引理1和引理2有下列結(jié)論.定理一個給定調(diào)度的可計算性是其可行的充要條件.由此,僅需要判斷一個給定調(diào)度是否能夠計算出所有操作的開工時間,即可知曉該調(diào)度是否可行.下面對于有M臺機器N個工件的作業(yè)車間調(diào)度問題,給出具體實現(xiàn)步驟:步驟0在M臺機器中選擇第m臺作為當前機器;步驟1從m中選擇當前工件q;步驟2判斷et m k和e t mq是否都已知:若已知,令rt m q=m axe t m k,et mq,e t m q=rt m q+p m

12、q,qq+1,轉(zhuǎn)步驟1;否則,轉(zhuǎn)步驟3;步驟3判斷m=M?若是,m0,轉(zhuǎn)步驟4;否則,mm+1,轉(zhuǎn)步驟1;步驟4通過對M臺機器一輪循環(huán)計算后,比較是否每臺機器當前工件編號都無變化若是,做調(diào)度不可行標記,算法結(jié)束;否則,轉(zhuǎn)步驟5;步驟5判斷各機器所有工件是否全部計算211系統(tǒng)工程學報第25卷.完成.若是,返回最大完工時間m ake span;否則,轉(zhuǎn)步驟0.4產(chǎn)生新調(diào)度并做局部優(yōu)化搜索隨機鄰域交換產(chǎn)生新調(diào)度的規(guī)則如下:1交換可發(fā)生在同臺機器任意兩個相鄰操作之間,這樣可避免產(chǎn)生過多的不可行調(diào)度,減少無效交換;2每臺機器每次僅允許發(fā)生一次交換;3考慮到多個操作之間存在的隱性耦合關(guān)系,以工件號、操作位

13、置和加工步驟等已知參數(shù)對交換條件進行限制,滿足條件的操作才與其后繼操作發(fā)生交換.表1Ben chm a rk測試用例TA01TA50測試結(jié)果比較Table1Test res u lts and comparis on on Benchmark p roble m s TA01T A50問題規(guī)模最優(yōu)(上界TSS B6RE(%TS AB7RE(%S B2G LS59R E(%HPS O10RE(%R NS A R E(%注TSS B、TS B、S B2G L S S,S O為相應(yīng)文獻提出方法的最優(yōu)值或上界,其相鄰列的R為其平均相對誤差311第1期崔健雙等:作業(yè)車間調(diào)度問題的隨機鄰域交換算法12A

14、H P E.根據(jù)上述規(guī)則,當問題的相關(guān)參數(shù)滿足如下邏輯關(guān)系時發(fā)生交換:I F (seq_num =r Op rt AND(p r o_o rde r=rStep OR (job_num=sJob THENOr O p rtOr Op rt+1其中,seq_num 是當前機器上加工工序位置;p r o_orde r 是加工工序編號;job_num 是工件編號.后兩個參數(shù)都是確知值.r Op rt (N -1、rStep (M 和s Job (N 是約定范圍的三個隨機數(shù).如果說產(chǎn)生新調(diào)度是全局范圍內(nèi)的調(diào)整變化,局部優(yōu)化搜索就是小幅調(diào)整.本文采用的局部優(yōu)化搜索策略是對文獻8中的關(guān)鍵路徑算法(C P

15、A 的改進.改進的C P A 增加了對一個關(guān)鍵塊有3個操作的處理方法,即如果一個塊中有3個操作,單獨做兩兩交換并選用二者中較好的結(jié)果.5算法實現(xiàn)步驟步驟0利用優(yōu)先指派規(guī)則產(chǎn)生初始調(diào)度,計算m akespan 作為當前目標函數(shù)最優(yōu)值B estValue;步驟1產(chǎn)生一個新調(diào)度;步驟2判斷新調(diào)度的可行性:若可行,轉(zhuǎn)步驟3;否則,恢復(fù)原調(diào)度并判斷是否達到設(shè)定循環(huán)次數(shù);若是,停止計算并輸出最終結(jié)果;若否,轉(zhuǎn)步驟1;步驟3利用改進的C P A 對新調(diào)度作局部優(yōu)化搜索,此時B est Va lue 總是保留最優(yōu)值,轉(zhuǎn)步驟1.算法中間臨時產(chǎn)生的調(diào)度都會經(jīng)過比較后被淘汰,每次僅保留最優(yōu)調(diào)度,因此空間復(fù)雜度可忽略

16、不計.算法的計算量,即時間復(fù)雜度主要在步驟2、步驟 3.針對此類問題的算法一般采用B enchm ark 問題計算結(jié)果的比較來做出評價.6算法效果分析與比較選擇了不同規(guī)模的80個B enchm ark 算例TA01TA80對算法的效果進行測試.使用C 語言編程、主頻1.5G H z 的I B M ThinkPad T40進行計算.因計算結(jié)果中T A51T A80(除T A55外都達到了目標函數(shù)最優(yōu)值,表1中僅列出了T A01TA50的計算結(jié)果.由T A 系列算例計算結(jié)果分析可知:1近44%的算例可獲最優(yōu)值,前50個算例的平均相對誤差為0.82%,是參與比較的所有算法中最低的.2為了體現(xiàn)普遍性和

17、公平性,表1數(shù)據(jù)是在相同環(huán)境下對每個算例進行了5遍測試的平均值.3算法也曾對較容易計算的算例做過計算.例如,對于LA01LA15和LA31LA35,在既有環(huán)境下,每5個算例一組連續(xù)進行計算,每組總計算時間都不超過1s .4對于規(guī)模超過2000(N =100,M =20的10個算例T A71TA80,都能夠在較短時間內(nèi)(平均4.3m in得到最優(yōu)值.5與文獻4-6中提出的算法計算結(jié)果的比較也表明,RNS A 算法有明顯優(yōu)勢.7結(jié)束語本文提出了一種組合條件隨機鄰域交換算法并證明和編程實現(xiàn)了調(diào)度可行判定準則,指出可計算性是調(diào)度可行的充要條件.可行判定及時淘汰了無效調(diào)度,提高了計算效率.算法還成功地引

18、入了改進的CA P,實現(xiàn)了局部鄰域優(yōu)化搜索,對提高算法的搜索深度起到了重要作用.B enchm a rk 測試用例的計算結(jié)果證明了算法的有效性和可靠性.參考文獻:S,M S D j ,f f O R 2,3(33王磊,黃文奇求解工件車間調(diào)度問題的一種新的鄰域搜索算法計算機學報,5,(56411系統(tǒng)工程學報第25卷1Ja i n A eeran .ete r m in istic ob shop sch ed u ling:Past p re sent an d u t u re J .E u r op ean Jo u rna l o p e ra ti o na l e search 199

19、9112:90-44.2.J .20028:809-81.Wang Lei,HuangWenqi .A ne w l ocal sea rch a l gorith m for j ob shop scheduling p roblem J .Chine s e Journal of Co mputers,2005,28(5:809-816.(in Chine se 3Jo s F G,Jorge J M M ,Maor c i o G C R.A hybrid geneti c algorith m for the j ob sh op s cheduling p roblem sJ .Eu

20、ro peanJournal of Operati on R esearch,2005,167(1:77-95.4B yung J P,Hyung R C,Hyun S K .A hybrid genetic a lg orith m for the j ob shop scheduling problem sJ .Compute rs &In 2dustri a l Enginee ri ng,2003,45(3:597-613.5Federico D C ,Robe rto T,Guiseppe V.A gene tic a lg orith m for the j ob s hop pr

21、oblem J .Co mputers Operati on R esearch,1995,22(1:15-24.6A dam s J,B a l a s E,Za wack D .The s hifting bottl eneck p rocedure for j ob 2s hop schedulingJ .Manag em ent Science,1988,34(3:391-401.7Fe rdinand o P,E manuela M.A taboo search me th od guided by shifting bottleneck for the job shop scheduli ng problem J .Euro