基于效率規則的混合作業車間調度算法應用研究

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

（三峽大學機械與材料學院，湖北宜昌 443002）

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

本文設計了基于效率函數初排排序再調節排序的方法，來解決混合作業車間調度，并將該方法應用到具體的實例.結果表明這種基于效率規則的調度方法可以有效地優化混合作業車間最大完工時間，從而可以推廣運用到混合車間調度問題的求解.

1 混合作業車間調度問題

1.1 問題描述

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

1.2 問題數學建模

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

2 基于效率規則的混合作業調度算法設計

2.1 建立隊列

對混合作業調度建立了3個隊列：

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

機器隊列.按實際加工順序，將每臺機器上加工的工件排列成隊列LMk（k＝1，2，…，m）.在此隊列中，每個工序的加工時間互不重疊，即工件在同一臺機器上，當一個加工任務完成之后才能開始另一個加工任務［7］.

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

2.2 初始化

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

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

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

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

2.3 初排算法的設計

混合作業車間初排算法流程如下：

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

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

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

Step5：分別依據式（3）、（4）和（5）計算工序Jij的開始時間STij、結束時間FTij和等待時間WTij；

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

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

Step9：判斷緊前工序隊列數值是否全部為1，是則算法結束，否則，跳轉Step2.

2.4 調節算法的設計

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

調節算法的目標為

具體調節算法流程為：

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

Step3：遍歷機器隊列中LMk（k＝1，2，…，m）對任意一個i，若Wil＝0（l＝1，2，…，ni）則排序結果最優，不需調節.此時，關鍵路徑上的各個工序均無等待時間，排序結果最優，跳轉Step9；

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

Step5：設計器Mi上第j 次加工的工序為Jpq，j＋1次加工的工序為Jp′q′，如果工序Jp′q′的前一道工序Jp′q′－1的結間束時FTp′q′－1＜STpq，則交換Jp′q′和Jpq在機器Mi上的加工順序；

Step9：算法結束.

3 實例計算與分析

某車間有4個工件在4臺機床上加工，每個工件有4道工序，假定每個工件在每臺機床上各加工一次，并且每道工序的加工時間和每個工件的加工路線已知，詳細數據見以下3個矩陣：

運用上文中效率規則算法，對實例問題進行計算求解，并在開發的調度系統中以甘特圖的形式進行調度結果輸出，初排算法計算后輸出結果和調節算法輸出結果分別如圖1～2 所示.圖中，縱軸表示機器編號，橫軸表示時間.

圖1 初排結果輸出界面

圖2 調節結果輸出界面

通過以上調度甘特圖可以看出，進行初排算法計算后最長時間為17個工作時，再采用調節算法計算最終的調度結果為16個工作時.通過初排算法計算再調節計算后，整批工件的排產時間得到了很好的優化.證明了這種基于效率規則的調度算法可以很好地解決混合作業車間的調度問題，可以很好地應用于混合作業車間調度.

4 結 語

基于效率規則的混合車間調度算法，基本思想是在工件效率函數的基礎上，設計初排排序再調節排序，最終得出調度結果.這種算法在混合作業車間調度問題中研究得比較少，可能還存在進一步的改進可能，但可以作為混合作業車間調度問題的一個新的研究方向，開展相應有意義的研究工作.

［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］ 胡雅麗，楊建軍.基于約束規則的作業車間調度研究［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］ 曾利軍，易理威，劉玲華，等.求解車間調度問題的離散粒子群優化算法［J］.電腦知識與技術，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］ 王 冰，李巧云，羊曉飛.模糊車間作業調度的三點滿意度模型［J］.控制與決策，2012，27（7）：1082－1086.

［8］ 張 博.流水車間成組作業調度的仿真研究［D］.天津：天津工業大學，2008.

［9］ 崔雪麗.基于混合遺傳算法的車間生產計劃調度［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.