求解調(diào)度問題的啟發(fā)式算法

一種改進(jìn)的關(guān)鍵工序算法劉智勇 徐昕江蘇科技大學(xué)經(jīng)濟(jì)管理學(xué)院，江蘇 鎮(zhèn)江 摘要：針對問題，改進(jìn)了關(guān)鍵工序法法，該算法同時注重關(guān)鍵工件與關(guān)鍵工序，通過對關(guān)鍵工件與非關(guān)鍵工件在關(guān)鍵工序前后的加工時間計算、比較來獲得各工件加工的先后順序，縮短最長流程時間。并將該啟發(fā)式算法與關(guān)鍵工序法進(jìn)行了對比分析，最后利用仿真的方法來驗證所提出的方法的可行性。關(guān)鍵詞：Flow-shop 關(guān)鍵工件 關(guān)鍵工序 啟發(fā)式算法 最長流程時間0引言Flow-shop調(diào)度問題（flow shop scheduling problem,FSP）是許多實際流水線生產(chǎn)調(diào)度問題的簡化模型，它無論是在離散制造工業(yè)還是在流程工業(yè)中都具有廣泛的應(yīng)用，因此其研究具有重要的理論意義和工程價值。n/m/p/Fmax問題是Flow-shop調(diào)度問題中的一種特殊情況，即所有工件在各臺機(jī)器上的加工順序都相同，也稱流水作業(yè)排列排序問題或同順序排序問題。其求解方法有精確方法1（分支定界法、窮舉法等）、智能搜索法2,3,4（神經(jīng)網(wǎng)絡(luò)法、遺傳算法、蟻群算法等）、啟發(fā)式算法4,5,6,7（Palmer算法、C-D-S法、關(guān)鍵工序法、最小排序系數(shù)法等）等等。由于Flow-shop調(diào)度問題一般都屬于NP難題(nondeterministic polynomial)。精確方法只能求解小規(guī)模問題，對于大規(guī)模問題幾乎被認(rèn)為是無效算法，智能搜索法在求解上雖比啟發(fā)式算法更接近最有解，但由于設(shè)計針對具體問題的智能搜索法對于許多人來說比較困難，特別是對于實際工程人員更是如此。所以啟發(fā)式算法仍是用的很多的方法。主要的啟發(fā)式算法有Palmer算法、關(guān)鍵工序法和最小排序系數(shù)法等。其中，關(guān)鍵工序法貫穿著當(dāng)前先進(jìn)的管理思想，能夠很好的對現(xiàn)實情況進(jìn)行解釋和分析。然而關(guān)鍵工序法所求的可行解很可能與最優(yōu)解相差甚遠(yuǎn)，鑒于此，本文對其進(jìn)行了改進(jìn)。1 問題描述問題可以描述為：有個工件在臺機(jī)器上加工，各工件有完全相同的工藝路線，每一臺機(jī)器上加工工件的先后順序也完全相同；一個工件不能同時在不同的機(jī)器上加工；每臺機(jī)器同時只能加工一個工件；各工件在加工完后立即送下一道工序；工件在機(jī)器上開始加工，必須一直進(jìn)行到該工序完工，中途不允許停下來插入其它工件；所有工件在0時刻已準(zhǔn)備就緒，機(jī)器調(diào)整時間包括在加工時間內(nèi)；允許工件在工序之間等待，允許機(jī)器在任務(wù)未到達(dá)時閑置；優(yōu)化目標(biāo)是求出這n個任務(wù)的一個全排列，使其最長流程時間（也稱加工周期）最短，則的計算方法如下：上式中代表工件在機(jī)器上的完工時間，代表工件在機(jī)器上的加工時間。2改進(jìn)的關(guān)鍵工序法改進(jìn)的關(guān)鍵工序法要求抓住關(guān)鍵工序和關(guān)鍵工件，定義關(guān)鍵工序為各道工序上加工各個工件總時間最長的工序；定義關(guān)鍵工件為各個工件在各道工序加工總時間最長的工件。若關(guān)鍵工件都多個，則按照各關(guān)鍵工件首道工序加工時間與尾道工序加工時間的大小分組，首道工序加工時間小于尾道的工件為第一組，首道工序加工時間等于尾道的工件第二組，首道工序加工時間大于尾道的工件為第三組，優(yōu)先順序為第一組，第二組，第三組，對于第一組中的各關(guān)鍵工件之間的排序則按關(guān)鍵工序前各道工序總加工時間從小到大排序，對于第三組的各關(guān)鍵工件之間的排序則按關(guān)鍵工序后各道工序總加工時間從大到小排序，第二組的各關(guān)鍵工件的排序時需先比較第一組與第三組內(nèi)的工件個數(shù)，當(dāng)?shù)谝唤M的工件個數(shù)少于或等于第三組時，第二組內(nèi)工件按第一組規(guī)則排，否則按第三組的規(guī)則排。對關(guān)鍵工件以外的所有工件同樣比較首道工序加工時間與尾道工序加工時間，按小于、等于、大于分為三組，其組內(nèi)排序規(guī)則與關(guān)鍵工件個組內(nèi)排序規(guī)則相同。最后按非關(guān)鍵工件第一組，非關(guān)鍵工件第二組，關(guān)鍵工件第一組，關(guān)鍵工件第二組，關(guān)鍵工件第三組，非關(guān)鍵共建第三組的順序進(jìn)行總排序，即可獲得滿意的。對于關(guān)鍵工序為首道工序的情形，就把次關(guān)鍵工序看成是上述的關(guān)鍵工序，排序步驟不變。用數(shù)學(xué)語言表示如下：Step1: 對，計算，對，計算，定義為關(guān)鍵工件，定義 為關(guān)鍵工序。Step2:：若（其中表示括號中集合包含元素的個數(shù)），則，則計算的值，按該值從小到大排列獲得一個排序優(yōu)先。，則計算的值，按該值從大到小排列獲得一個排序優(yōu)先序列。，則當(dāng)時，那么按的規(guī)則獲得中元素的排序；當(dāng)時，那么按的規(guī)則獲得中元素的排序；設(shè)中元素的排序優(yōu)先序列為。將Step2:中的各種排序優(yōu)先序列一起排序，得到。Step3:：若，則，則計算的值，按該值從小到大排列獲得一個排序優(yōu)先。，則計算的值，按該值從大到小排列獲得一個排序優(yōu)先序列。，則當(dāng)時，那么按Step3中的規(guī)則獲得中元素的排序；當(dāng)時，那么按Step3中的規(guī)則獲得中元素的排序；設(shè)中元素的排序優(yōu)先序列為。Step4:：將上述結(jié)果進(jìn)行總排序優(yōu)先級：。經(jīng)過上述四步，獲得的結(jié)果就是滿意解。3算法示例設(shè)有8個零件A、B、C、D、E、F、G、H在8臺機(jī)器M1、M2、M3、M4、M5、M6、M7、M8上同順序加工，其工藝過程及工時定額見表1，試求出最長流程時間Fmax.表1 工藝過程及工時 零件工序ABCDEFGH各工件加工總時間213224756746M3716109607459M415781011148982M5647125115555M666821083245M72107215102351M8871010156451各工件總加工時間6060585856554541現(xiàn)利用改進(jìn)的關(guān)鍵工序法求解:計算每個工件的總加工時間以及每個工序總加工時間，見表，可知關(guān)鍵工件有兩個A、B，關(guān)鍵工序有一個M4。針對A工件，首道工序加工時間大于尾道工序加工時間，B工件，首道工序加工時間小于尾道工序加工時間，自然A排B的前面，即AB。對剩余工件，按首道工序加工時間大于、等于、小于尾道工序加工時間分成三類，可得首道工序加工時間大于尾道工序加工時間的工件有C、D、F；首道工序加工時間等于尾道工序加工時間的工件E；首道工序加工時間小于尾道工序加工時間的工件有G、H。 對C、D、E、F按關(guān)鍵工序前的各道工序時間相加（M1+M2+M3），得到TC=6+2+10=18，TD=9+4+9=22， TF=2+5+0=4，則C、D、F的排序按T值從小到大為FCD； 對G、H按按關(guān)鍵工序后的各道工序時間相加（M5+M6+M7），得到TG=5+3+2+6=16，TH=5+2+3+4=14，則G、H的排序按T值從大到小為GH。按首道工序加工時間大于尾道工序加工時間的工件，首道工序加工時間等于尾道工序加工時間的工件，關(guān)鍵工件，首道工序加工時間小于尾道工序加工時間的工件的順序進(jìn)行全排，獲得FCDEABGH。 表2 總流程時間計算結(jié)果 零件工序FCDEABGHM12(2)6(8)9(17)1(18)3(21)8(29)8(37)7(44)M25(7)2(10)4(21)7(28)13(41)2(43)6(49)7(56)M30(7)10(20)9(30)6(36)7(48)16(64)7(71)4(75)M414(21)8(29)10(40)11(51)15(66)7(73)8(81)9(90)M511(32)7(39)12(52)5(57)6(72)4(77)5(86)5(95)M68(40)8(48)2(54)10(67)6(78)6(84)3(89)2(97)M710(50)7(57)2(59)15(82)2(84)10(94)2(96)3(100)M85(55)10(67)10(77)1(83)8(92)7(101)6(107)4(111)注：（ ）內(nèi)表示流程時間計算情況表3 與關(guān)鍵工序法求解結(jié)果比較算法排序最大流程時間Fmax改進(jìn)后算法FCDEABGHFmax=111關(guān)鍵工序法FCDAEBGHFmax=1234算法測試與比較通過MATLAB程序?qū)栴}進(jìn)行100次仿真，將關(guān)鍵工序法和文中提出的改進(jìn)方法進(jìn)行了對比。結(jié)果如圖1所示：圖1 不同規(guī)模Flow-shop求解結(jié)果比較a) m=50,n=50b) m=100,n=100c) m=150,n=150d) m=200, n=200可見，本文所提出的改進(jìn)方法普遍優(yōu)于原本的關(guān)鍵工序方法。當(dāng)所要求解的Flow-shop問題規(guī)模較小時,如圖1中 a）所示，改進(jìn)方法不略于關(guān)鍵工序法。但兩條曲線幾乎重合，優(yōu)勢比較小。這說明在規(guī)模較小的Flow-shop問題中，關(guān)鍵工序法依然十分有效。然而，當(dāng)問題規(guī)模較大時，如圖1中b）所示，本文中的改進(jìn)方法明顯優(yōu)于關(guān)鍵工序法。這說明關(guān)鍵工序法在大規(guī)模問題中，相對于最優(yōu)解將產(chǎn)生明顯偏差，并且這種偏差是隨著問題規(guī)模的擴(kuò)大而增大的。而本文所提出的改進(jìn)算法，恰恰彌補(bǔ)了關(guān)鍵工序法在大規(guī)模Flow-shop問題中表現(xiàn)較差這一問題。5參考文獻(xiàn)1 Liu Lili Tang Guochun. A Branch and Bound Approach and Heuristic Algorithms for Scheduling a Batching MachineJ.2004,8(3):39-44.2REEVES C R. A genetic algorithm for flowshop sequencingJ.Computer and Operations Research,1995,22(1):5-23.3RAJENDRAN C,ZIEGLER H. Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime jobsJ. European Journal of Operational Research,2004,155(2):426-4384 葉春明 生產(chǎn)計劃與控制M，北京：高等教育出版社，2005：391-400。5WOO H S, YIM D S. A heuristic algorithm for mean flowtime objective in flowshop shcdulingJ. Com