基于效率規(guī)則的混合作業(yè)車間調(diào)度算法應(yīng)用研究

吳正佳 林 攀 張 成 祝小琴 羅月勝

（三峽大學(xué)機(jī)械與材料學(xué)院，湖北宜昌 443002）

在混合作業(yè)車間調(diào)度問題中，其中一部分工序是沒有嚴(yán)格的先后順序的；另一部分工序又具有嚴(yán)格的順序，也就是說會(huì)有一些工序具有一個(gè)或多個(gè)緊前或緊后工序［1］.混合作業(yè)調(diào)度問題具有作業(yè)方式多樣化、規(guī)模龐大、系統(tǒng)復(fù)雜等特點(diǎn).應(yīng)用傳統(tǒng)的函數(shù)分析方法，又很難將所研究的問題抽象為相應(yīng)的數(shù)學(xué)問題，且計(jì)算量極其龐大，步驟過程也較為繁瑣，故難以順利完成［2］.

本文設(shè)計(jì)了基于效率函數(shù)初排排序再調(diào)節(jié)排序的方法，來解決混合作業(yè)車間調(diào)度，并將該方法應(yīng)用到具體的實(shí)例.結(jié)果表明這種基于效率規(guī)則的調(diào)度方法可以有效地優(yōu)化混合作業(yè)車間最大完工時(shí)間，從而可以推廣運(yùn)用到混合車間調(diào)度問題的求解.

1 混合作業(yè)車間調(diào)度問題

1.1 問題描述

假設(shè)有m 臺(tái)機(jī)器M1，M2，…，Mm需要加工n 個(gè)工件J1，J2，…，Jn.混合作業(yè)車間需要解決的兩個(gè)關(guān)鍵問題：一是如何安排工序的順序；二是如何確定工序在機(jī)器上的加工時(shí)間，并保持每個(gè)加工工件的工藝約束.和傳統(tǒng)的車間作業(yè)調(diào)度問題相似，對(duì)此類混合作業(yè)車間調(diào)度問題也存在以下假設(shè)：1）一個(gè)工件同一時(shí)間只能在一臺(tái)機(jī)器上加工；2）正在加工的工序不允許中斷；3）同一時(shí)間一臺(tái)機(jī)器只允許加工一個(gè)工件；4）每道工序只允許在一臺(tái)機(jī)器上完成；5）工件在工序間可以等待，工件未到達(dá)前機(jī)器可以閑置；6）工件與機(jī)器的相關(guān)參數(shù)均一致，包括：工序在機(jī)器上的加工時(shí)間，工件的工藝路線；7）每個(gè)工件的第一道工序開始加工時(shí)間大于等于零［3－5］.

1.2 問題數(shù)學(xué)建模

對(duì)加工效率r（i，j）作如下解釋：假設(shè)r（i′，j′）是工件Ji′在加工工序Ji′i′時(shí)的加工“效率”，r（i″，j″）是工件Ji″在加工工序Ji″，i″時(shí)的加工“效率”，（1＜i′，i′＜n；1＜j′＜Q1，1＜j″＜Q2）.若r（i′，j′）＜r（i″，j″），則表明工件Ji′在加工工序Ji′i′時(shí)，其“效率”比工件Ji″在加工工序Ji″i″的“效率”低.

2 基于效率規(guī)則的混合作業(yè)調(diào)度算法設(shè)計(jì)

2.1 建立隊(duì)列

對(duì)混合作業(yè)調(diào)度建立了3個(gè)隊(duì)列：

工件隊(duì)列.按其次序約束，出現(xiàn)多道緊前工序時(shí)，任意初始順序，將每個(gè)工件的加工工序排列成隊(duì)列LJi（i＝1，2，…，n）［6］.在此隊(duì)列中，每個(gè)工序的加工時(shí)間不能重疊，即工件的前一道工序加工完成后才能進(jìn)行后一道工序的加工.

機(jī)器隊(duì)列.按實(shí)際加工順序，將每臺(tái)機(jī)器上加工的工件排列成隊(duì)列LMk（k＝1，2，…，m）.在此隊(duì)列中，每個(gè)工序的加工時(shí)間互不重疊，即工件在同一臺(tái)機(jī)器上，當(dāng)一個(gè)加工任務(wù)完成之后才能開始另一個(gè)加工任務(wù)［7］.

工序多道緊前和緊后工序隊(duì)列.建立工件每道工序的緊前隊(duì)列LJibs（s＝Ok，b＝Qi，i＝1，2，…，n），b代表某個(gè)工件的第幾道工序，s表示工序b 的緊前工序的個(gè)數(shù)［8］.因此，計(jì)算各工序的實(shí)際開工時(shí)間與完工時(shí)間時(shí)，必須保證3個(gè)隊(duì)列的完整性.即調(diào)度問題就變成如何根據(jù)隊(duì)列LJibs和LJi來確定工件隊(duì)列的最終順序，然后把LJi中的各工序如何插入到LMk中，并且保證目標(biāo)函數(shù)值最優(yōu)或近似最優(yōu).

2.2 初始化

1）工件隊(duì)列：按照工件的每一道工序的次序約束，出現(xiàn)多道緊前工序時(shí)，初始順序任意，建立各個(gè)工件的一個(gè)工件隊(duì)列LJi（i＝1，2，…，n）.

2）根據(jù)式（1）計(jì)算每道工序的r（i，j），則對(duì)于各個(gè)工件Ji（i＝1，2，…，n）滿足max（1－r（i，j））的工序必在隊(duì)首，出現(xiàn)多道緊前工序時(shí)都按照先加工計(jì)算效率.

3）機(jī)器隊(duì)列：初始時(shí)各機(jī)器都未被分配，即每個(gè)機(jī)器隊(duì)列LMk（k＝1，2，…，m）均置空Null，而且每個(gè)機(jī)器Mk加工的工件數(shù)nk均置0，Mk0也置0.

4）建立多道緊前工序隊(duì)列：依據(jù)各個(gè)工件的每道工序的緊前工序個(gè)數(shù)，建立各個(gè)工件的一個(gè)緊前工序隊(duì)列LJibs（s＝Ok，b＝Qi，i＝1，2，…，n）［9－10］.

2.3 初排算法的設(shè)計(jì)

混合作業(yè)車間初排算法流程如下：

Step1：nk＝0（k＝1，2，…，m），W ＝｛Jij｜j＝1，2，…，Qi；k＝1，2，…，i＝1，2，…，n｝；

Step3：在各個(gè)工序中選擇滿足加工效率值為max（1－r（i，j））（j＝1，2，…，Qi；i＝1，2，…，n）的工序Jij.如果不唯一，則取滿足max｛Ti－TSie｝的工序Jij.然后循環(huán)到下一道工序Jij＋1；

Step4：如果Pij＝Mk，則將工序Jij插入到機(jī)器列隊(duì)LMk的隊(duì)尾；

Step5：分別依據(jù)式（3）、（4）和（5）計(jì)算工序Jij的開始時(shí)間STij、結(jié)束時(shí)間FTij和等待時(shí)間WTij；

Step6：更新nk＝nk＋1，并Eknk＝FTij；

Step7：判斷工件隊(duì)列LJi（i＝1，2，…，n）是否遍歷完畢，是則跳轉(zhuǎn)Step8，否則，跳轉(zhuǎn)Step3；

Step9：判斷緊前工序隊(duì)列數(shù)值是否全部為1，是則算法結(jié)束，否則，跳轉(zhuǎn)Step2.

2.4 調(diào)節(jié)算法的設(shè)計(jì)

設(shè)Wkl為第K 臺(tái)機(jī)器完成第L－1次加工Jij后要進(jìn)行第l 次加工Ji′j′的等待時(shí)間，即：Wkl＝WTi′j′（k＝1，2，…，n；l＝1，2，…nk），則

調(diào)節(jié)算法的目標(biāo)為

具體調(diào)節(jié)算法流程為：

Step1：計(jì)算Wkl（k＝1，2，…，m；l＝1，2，…，nk）；

Step3：遍歷機(jī)器隊(duì)列中LMk（k＝1，2，…，m）對(duì)任意一個(gè)i，若Wil＝0（l＝1，2，…，ni）則排序結(jié)果最優(yōu)，不需調(diào)節(jié).此時(shí)，關(guān)鍵路徑上的各個(gè)工序均無等待時(shí)間，排序結(jié)果最優(yōu)，跳轉(zhuǎn)Step9；

Step4：求wij＝｛Wij｝，但wil≠0的工序Jpq；

Step5：設(shè)計(jì)器Mi上第j 次加工的工序?yàn)镴pq，j＋1次加工的工序?yàn)镴p′q′，如果工序Jp′q′的前一道工序Jp′q′－1的結(jié)間束時(shí)FTp′q′－1＜STpq，則交換Jp′q′和Jpq在機(jī)器Mi上的加工順序；

Step9：算法結(jié)束.

3 實(shí)例計(jì)算與分析

某車間有4個(gè)工件在4臺(tái)機(jī)床上加工，每個(gè)工件有4道工序，假定每個(gè)工件在每臺(tái)機(jī)床上各加工一次，并且每道工序的加工時(shí)間和每個(gè)工件的加工路線已知，詳細(xì)數(shù)據(jù)見以下3個(gè)矩陣：

運(yùn)用上文中效率規(guī)則算法，對(duì)實(shí)例問題進(jìn)行計(jì)算求解，并在開發(fā)的調(diào)度系統(tǒng)中以甘特圖的形式進(jìn)行調(diào)度結(jié)果輸出，初排算法計(jì)算后輸出結(jié)果和調(diào)節(jié)算法輸出結(jié)果分別如圖1～2 所示.圖中，縱軸表示機(jī)器編號(hào)，橫軸表示時(shí)間.

圖1 初排結(jié)果輸出界面

圖2 調(diào)節(jié)結(jié)果輸出界面

通過以上調(diào)度甘特圖可以看出，進(jìn)行初排算法計(jì)算后最長(zhǎng)時(shí)間為17個(gè)工作時(shí)，再采用調(diào)節(jié)算法計(jì)算最終的調(diào)度結(jié)果為16個(gè)工作時(shí).通過初排算法計(jì)算再調(diào)節(jié)計(jì)算后，整批工件的排產(chǎn)時(shí)間得到了很好的優(yōu)化.證明了這種基于效率規(guī)則的調(diào)度算法可以很好地解決混合作業(yè)車間的調(diào)度問題，可以很好地應(yīng)用于混合作業(yè)車間調(diào)度.

4 結(jié) 語

基于效率規(guī)則的混合車間調(diào)度算法，基本思想是在工件效率函數(shù)的基礎(chǔ)上，設(shè)計(jì)初排排序再調(diào)節(jié)排序，最終得出調(diào)度結(jié)果.這種算法在混合作業(yè)車間調(diào)度問題中研究得比較少，可能還存在進(jìn)一步的改進(jìn)可能，但可以作為混合作業(yè)車間調(diào)度問題的一個(gè)新的研究方向，開展相應(yīng)有意義的研究工作.

［1］ Amit Kumar Gupta，Appa Iyer Sivakulllar.Job Shop Scheduling Techniques in Semiconductor Manufacturing［J］.Int J Adv Manuf Technol，2006，27：1163－1169.

［2］ 胡雅麗，楊建軍.基于約束規(guī)則的作業(yè)車間調(diào)度研究［J］.工業(yè)控制計(jì)算機(jī)，2012，48（5）：43－46.

［3］ Ling Wang，Da－Zhong Zheng.A Modified Evolutionary Programming for Row Shop Scheduling［J］.Int J Adv Manuf Technol，2003，22：522－527.

［4］ 曾利軍，易理威，劉玲華，等.求解車間調(diào)度問題的離散粒子群優(yōu)化算法［J］.電腦知識(shí)與技術(shù)，2012，38（28）：6787－6789.

［5］ Tai，Tsu Ta，Boucher，Thomas O.An Architecture for Scheduling and Control in Flexible Manufacturing Systems Using Distributed Objects［J］.IEEE Transactions on Robotics and Automation，2002，18（4）：45－49.

［6］ 王 冰，李巧云，羊曉飛.模糊車間作業(yè)調(diào)度的三點(diǎn)滿意度模型［J］.控制與決策，2012，27（7）：1082－1086.

［8］ 張 博.流水車間成組作業(yè)調(diào)度的仿真研究［D］.天津：天津工業(yè)大學(xué)，2008.

［9］ 崔雪麗.基于混合遺傳算法的車間生產(chǎn)計(jì)劃調(diào)度［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2011，36（7）：25－29.

［10］Laguna M，Barnes J W，Glover F W.Intelligent Scheduling with Tabu Search：an Application to Jobs With Linear Delay Penalties and Sequence－dePendent Set up Cost and Times［J］.Applied Intelligence，2003，56（3）：159.