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

1、一種改進(jìn)的關(guān)鍵工序算法劉智勇 徐昕江蘇科技大學(xué)經(jīng)濟(jì)管理學(xué)院，江蘇 鎮(zhèn)江 212003摘要：針對(duì)問題，改進(jìn)了關(guān)鍵工序法法，該算法同時(shí)注重關(guān)鍵工件與關(guān)鍵工序，通過對(duì)關(guān)鍵工件與非關(guān)鍵工件在關(guān)鍵工序前后的加工時(shí)間計(jì)算、比較來獲得各工件加工的先后順序，縮短最長(zhǎng)流程時(shí)間。并將該啟發(fā)式算法與關(guān)鍵工序法進(jìn)行了對(duì)比分析，最后利用仿真的方法來驗(yàn)證所提出的方法的可行性。關(guān)鍵詞：Flow-shop 關(guān)鍵工件 關(guān)鍵工序 啟發(fā)式算法 最長(zhǎng)流程時(shí)間0引言Flow-shop調(diào)度問題（flow shop scheduling problem,FSP）是許多實(shí)際流水線生產(chǎn)調(diào)度問題的簡(jiǎn)化模型，它無論是在離散制造工業(yè)還是在流程工業(yè)中

2、都具有廣泛的應(yīng)用，因此其研究具有重要的理論意義和工程價(jià)值。n/m/p/Fmax問題是Flow-shop調(diào)度問題中的一種特殊情況，即所有工件在各臺(tái)機(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ī)模問題，對(duì)于大規(guī)模問題幾乎被認(rèn)為是無效算法，智能搜索法在求解上

3、雖比啟發(fā)式算法更接近最有解，但由于設(shè)計(jì)針對(duì)具體問題的智能搜索法對(duì)于許多人來說比較困難，特別是對(duì)于實(shí)際工程人員更是如此。所以啟發(fā)式算法仍是用的很多的方法。主要的啟發(fā)式算法有Palmer算法、關(guān)鍵工序法和最小排序系數(shù)法等。其中，關(guān)鍵工序法貫穿著當(dāng)前先進(jìn)的管理思想，能夠很好的對(duì)現(xiàn)實(shí)情況進(jìn)行解釋和分析。然而關(guān)鍵工序法所求的可行解很可能與最優(yōu)解相差甚遠(yuǎn)，鑒于此，本文對(duì)其進(jìn)行了改進(jìn)。1 問題描述問題可以描述為：有個(gè)工件在臺(tái)機(jī)器上加工，各工件有完全相同的工藝路線，每一臺(tái)機(jī)器上加工工件的先后順序也完全相同；一個(gè)工件不能同時(shí)在不同的機(jī)器上加工；每臺(tái)機(jī)器同時(shí)只能加工一個(gè)工件；各工件在加工完后立即送下一道工序；工件

4、在機(jī)器上開始加工，必須一直進(jìn)行到該工序完工，中途不允許停下來插入其它工件；所有工件在0時(shí)刻已準(zhǔn)備就緒，機(jī)器調(diào)整時(shí)間包括在加工時(shí)間內(nèi)；允許工件在工序之間等待，允許機(jī)器在任務(wù)未到達(dá)時(shí)閑置；優(yōu)化目標(biāo)是求出這n個(gè)任務(wù)的一個(gè)全排列，使其最長(zhǎng)流程時(shí)間（也稱加工周期）最短，則的計(jì)算方法如下：上式中代表工件在機(jī)器上的完工時(shí)間，代表工件在機(jī)器上的加工時(shí)間。2改進(jìn)的關(guān)鍵工序法改進(jìn)的關(guān)鍵工序法要求抓住關(guān)鍵工序和關(guān)鍵工件，定義關(guān)鍵工序?yàn)楦鞯拦ば蛏霞庸じ鱾€(gè)工件總時(shí)間最長(zhǎng)的工序；定義關(guān)鍵工件為各個(gè)工件在各道工序加工總時(shí)間最長(zhǎng)的工件。若關(guān)鍵工件都多個(gè)，則按照各關(guān)鍵工件首道工序加工時(shí)間與尾道工序加工時(shí)間的大小分組，首道工序加

5、工時(shí)間小于尾道的工件為第一組，首道工序加工時(shí)間等于尾道的工件第二組，首道工序加工時(shí)間大于尾道的工件為第三組，優(yōu)先順序?yàn)榈谝唤M，第二組，第三組，對(duì)于第一組中的各關(guān)鍵工件之間的排序則按關(guān)鍵工序前各道工序總加工時(shí)間從小到大排序，對(duì)于第三組的各關(guān)鍵工件之間的排序則按關(guān)鍵工序后各道工序總加工時(shí)間從大到小排序，第二組的各關(guān)鍵工件的排序時(shí)需先比較第一組與第三組內(nèi)的工件個(gè)數(shù)，當(dāng)?shù)谝唤M的工件個(gè)數(shù)少于或等于第三組時(shí)，第二組內(nèi)工件按第一組規(guī)則排，否則按第三組的規(guī)則排。對(duì)關(guān)鍵工件以外的所有工件同樣比較首道工序加工時(shí)間與尾道工序加工時(shí)間，按小于、等于、大于分為三組，其組內(nèi)排序規(guī)則與關(guān)鍵工件個(gè)組內(nèi)排序規(guī)則相同。最后按非關(guān)

6、鍵工件第一組，非關(guān)鍵工件第二組，關(guān)鍵工件第一組，關(guān)鍵工件第二組，關(guān)鍵工件第三組，非關(guān)鍵共建第三組的順序進(jìn)行總排序，即可獲得滿意的。對(duì)于關(guān)鍵工序?yàn)槭椎拦ば虻那樾?，就把次關(guān)鍵工序看成是上述的關(guān)鍵工序，排序步驟不變。用數(shù)學(xué)語言表示如下：Step1: 對(duì)，計(jì)算，對(duì)，計(jì)算，定義為關(guān)鍵工件，定義 為關(guān)鍵工序。Step2:：若（其中表示括號(hào)中集合包含元素的個(gè)數(shù)），則，則計(jì)算的值，按該值從小到大排列獲得一個(gè)排序優(yōu)先。，則計(jì)算的值，按該值從大到小排列獲得一個(gè)排序優(yōu)先序列。，則當(dāng)時(shí)，那么按的規(guī)則獲得中元素的排序；當(dāng)時(shí)，那么按的規(guī)則獲得中元素的排序；設(shè)中元素的排序優(yōu)先序列為。將Step2:中的各種排序優(yōu)先序列一起排

7、序，得到。Step3:：若，則，則計(jì)算的值，按該值從小到大排列獲得一個(gè)排序優(yōu)先。，則計(jì)算的值，按該值從大到小排列獲得一個(gè)排序優(yōu)先序列。，則當(dāng)時(shí)，那么按Step3中的規(guī)則獲得中元素的排序；當(dāng)時(shí)，那么按Step3中的規(guī)則獲得中元素的排序；設(shè)中元素的排序優(yōu)先序列為。Step4:：將上述結(jié)果進(jìn)行總排序優(yōu)先級(jí)：。經(jīng)過上述四步，獲得的結(jié)果就是滿意解。3算法示例設(shè)有8個(gè)零件A、B、C、D、E、F、G、H在8臺(tái)機(jī)器M1、M2、M3、M4、M5、M6、M7、M8上同順序加工，其工藝過程及工時(shí)定額見表1，試求出最長(zhǎng)流程時(shí)間Fmax.表1 工藝過程及工時(shí) 零件工序ABCDEFGH各工件加工總時(shí)間M138691287

8、44M213224756746M3716109607459M415781011148982M5647125115555M666821083245M72107215102351M8871010156451各工件總加工時(shí)間6060585856554541現(xiàn)利用改進(jìn)的關(guān)鍵工序法求解:計(jì)算每個(gè)工件的總加工時(shí)間以及每個(gè)工序總加工時(shí)間，見表，可知關(guān)鍵工件有兩個(gè)A、B，關(guān)鍵工序有一個(gè)M4。針對(duì)A工件，首道工序加工時(shí)間大于尾道工序加工時(shí)間，B工件，首道工序加工時(shí)間小于尾道工序加工時(shí)間，自然A排B的前面，即AB。對(duì)剩余工件，按首道工序加工時(shí)間大于、等于、小于尾道工序加工時(shí)間分成三類，可得首道工序加工時(shí)間大于尾道

9、工序加工時(shí)間的工件有C、D、F；首道工序加工時(shí)間等于尾道工序加工時(shí)間的工件E；首道工序加工時(shí)間小于尾道工序加工時(shí)間的工件有G、H。 對(duì)C、D、E、F按關(guān)鍵工序前的各道工序時(shí)間相加（M1+M2+M3），得到TC=6+2+10=18，TD=9+4+9=22， TF=2+5+0=4，則C、D、F的排序按T值從小到大為FCD； 對(duì)G、H按按關(guān)鍵工序后的各道工序時(shí)間相加（M5+M6+M7），得到TG=5+3+2+6=16，TH=5+2+3+4=14，則G、H的排序按T值從大到小為GH。按首道工序加工時(shí)間大于尾道工序加工時(shí)間的工件，首道工序加工時(shí)間等于尾道工序加工時(shí)間的工件，關(guān)鍵工件，首道工序加工時(shí)間小于

10、尾道工序加工時(shí)間的工件的順序進(jìn)行全排，獲得FCDEABGH。 表2 總流程時(shí)間計(jì)算結(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

11、(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)表示流程時(shí)間計(jì)算情況表3 與關(guān)鍵工序法求解結(jié)果比較算法排序最大流程時(shí)間Fmax改進(jìn)后算法FCDEABGHFmax=111關(guān)鍵工序法FCDAEBGHFmax=1234算法測(cè)試與比較通過MATLAB程序?qū)栴}進(jìn)行100次仿真，將關(guān)鍵工序法和文中提出的改進(jìn)方法進(jìn)行了對(duì)比。結(jié)果如圖1所示：圖1 不同規(guī)模Flow-shop求解結(jié)果比較a) m=50,n=50b) m=100,n=1

12、00c) m=150,n=150d) m=200, n=200可見，本文所提出的改進(jìn)方法普遍優(yōu)于原本的關(guān)鍵工序方法。當(dāng)所要求解的Flow-shop問題規(guī)模較小時(shí),如圖1中 a）所示，改進(jìn)方法不略于關(guān)鍵工序法。但兩條曲線幾乎重合，優(yōu)勢(shì)比較小。這說明在規(guī)模較小的Flow-shop問題中，關(guān)鍵工序法依然十分有效。然而，當(dāng)問題規(guī)模較大時(shí)，如圖1中b）所示，本文中的改進(jìn)方法明顯優(yōu)于關(guān)鍵工序法。這說明關(guān)鍵工序法在大規(guī)模問題中，相對(duì)于最優(yōu)解將產(chǎn)生明顯偏差，并且這種偏差是隨著問題規(guī)模的擴(kuò)大而增大的。而本文所提出的改進(jìn)算法，恰恰彌補(bǔ)了關(guān)鍵工序法在大規(guī)模Flow-shop問題中表現(xiàn)較差這一問題。5參考文獻(xiàn)1 Li

13、u 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)計(jì)劃與控制M，北京：高等教育出版社，2005：391-400。5WOO H S, YIM D S. A heuristic algorithm for mean flowtime objective in flowshop shcdulingJ. Com