基于動態調整葉節點工序的綜合調度算法

劉顯超，趙 男，楊 茁，蘇艷會，周 偉

（1 吉林師范大學 計算機學院，吉林 四平 136000；2 四平市第二十五中學，吉林 四平 136000；3 吉林師范大學附屬學校，吉林 四平 136000；4 長春市第十六中學，長春 130000）

0 引言

產品的生產制造作為影響企業生產效率的主要因素，一直都是相關學科研究的熱點。在人力資源、設備資源等有限的前提下，如何更好地提高生產加工的時間效率和設備的利用效率直接決定了企業的生產效率，也是制造業致力解決的重要問題。

隨著互聯網技術和計算機技術的發展，制造行業的產品需求和社會需求也發生了變化［1-5］。但是，人們對復雜產品的需求日趨個性化和多樣化［6-7］，因而亟需解決多品種、小批量復雜工藝的產品調度問題。為此，有專家學者提出了將“產品的加工和裝配同步處理”的綜合調度［8］并開展了一系列的研究［9-12］，提出了諸多調度算法，也拓展出很多新的研究領域［12-18］。

雖然現有的綜合調度算法已經取得了較好的研究成果，但是仍然存在橫縱雙向優化中兼顧性不完善的問題。例如以“工序”為研究對象的算法中，文獻［13］雖然提出了以工序數量總量來確定調度路徑和次序的算法，但是忽略了葉節點工序的重要作用。文獻［14］雖然提出了以串行工序數量為排序策略的算法，但是忽略了設備利用率對整體調度效果的影響等等。

為解決上述問題，本文以優化綜合調度時間成本為目標，提出了基于動態調整葉節點工序的綜合調度算法。算法以復雜產品工藝樹的葉節點工序和對應的加工設備作為研究對象，首先以復雜產品工藝樹原始樹圖構建葉節點工序和對應加工設備的工序組，在工序組中優先調度層優先級較高的葉節點工序；其次，在工藝樹中刪除已調度的葉節點工序，重構復雜產品工藝樹和葉節點工序，更新葉節點工序和對應加工設備的工序組；如此循環分解，直到原始工藝樹中所有工序全部調度完畢的綜合調度方法。

1 相關定義

假設綜合調度系統有m臺加工設備，需要加工完成復雜產品的n道工序，要求如下：

（1）在加工的某個時刻，加工設備只能連續加工對應的工序。

（3）不存在相同設備。

定義1 葉節點工序在復雜產品工藝樹中，將沒有緊前工序約束、但是具有緊后約束工序的工序定義為葉節點工序，且葉節點工序數量必須大于等于1。

定義2 工序層優先級根據文獻［20］首次提出的層優先級問題，描述為：對于具有n層結構的復雜產品，首先將根節點工序的優先級設為最低，定義為1，根節點工序的所有后裔節點工序的優先級定義為2，以此類推，直到第n層的所有節點的優先級設為最高，定義為n［19］。

定義3 工序組在綜合調度中，處于當前復雜產品工藝樹中的葉節點工序和其對應的加工設備組成的加工組合定義為工序組。在工序組中，一臺設備至少對應一道葉節點工序。

2 算法設計

復雜產品加工的全過程中，所有加工設備彼此獨立，設備間不存在優先順序的問題。本文分別從橫縱兩個方面優化了復雜產品的綜合調度效果，其中縱向優化是通過在工序組調度的葉節點工序實現的，達到縮短整體加工用時的優化目標；橫向優化是通過循環產生新葉節點工序實現的，即通過提高串行工序的緊密銜接度，減少對應設備上工序加工的間隔時間，達到提高各個設備利用率的優化效果。算法流程如圖1 所示，具體闡述如下：

圖1 算法流程圖Fig. 1 Flow chart of the algorithm

Step 1以復雜產品工藝樹原始樹圖為基礎，查找所有葉節點工序。

隨著我國經濟不斷發展，各種新科學、新技術層出不窮，各個行業都取得了一定程度上的發展，電力行業也是如此，它們抓住機遇，不斷引進新技術，加之自己的創新，取得了不錯的成績，為我國國民經濟的發展以及人民生活水平的提高做出重要貢獻。輸電線路是電力系統的重要組成部分，其安全性與穩定性直接影響到電力的有效供應。電力企業如何做好輸電線路管理工作，已成為業內人士關注的重要問題。

Step 2建立葉節點工序組。

Step 3判斷工序組中待調度葉節點工序是否唯一，是則調度；否則轉Step4。

Step 4按照層優先級由高到低的順序依次調度組內葉節點工序。

Step 5在復雜產品工藝樹原始樹圖中刪除已經調度完成的葉節點工序，形成新的工藝樹。

Step 6重復Step1，直到根節點工序調度完畢。

3 調度實例演示

現假設復雜產品A加工工藝樹如圖2 所示。需要說明的是，此算例不特指某一類產品，對于其他小批量、多品種的復雜產品亦適用。對實例流程擬做闡釋分述如下。

圖2 復雜產品A 工藝樹圖Fig. 2 Complex product A process tree

Step 1以復雜產品工藝樹原始樹圖為基礎，確定原始工藝樹圖葉節點工序，共計9 道，如圖3 所示。

圖3 復雜產品A 工藝樹圖初始葉節點工序圖Fig. 3 Initial leaf node process diagram of complex product A process tree diagram

Step 2建立葉節點工序和對應加工設備工序組，可表示為：M1：｛A26／1／4｝；M2：｛A6／2／3、A21／2／1、A27／2／2｝；M3：｛A17／3／1、A24／3／3｝；M4：｛A14／4／1、A19／4／3、A22／4／1｝。

Step 3設備M1工序組中待調度葉節點工序只有A26，直接調度；設備M2、M3、M4對應的工序組中，葉節點工序不唯一，則按照層優先級由高到低的順序依次調度組內葉節點工序，得到各工序組調度順序為M1：｛A26／1／4｝；M2：｛A27／2／2、A21／2／1、A6／2／3｝；M3：｛A24／3／3、A17／3／1｝；M4：｛A22／4／1、A19／4／3、A14／4／1｝。

Step 4在復雜產品工藝樹原始樹圖中刪除已經調度完成的葉節點工序，形成新的工藝樹，得到新的葉節點工序3 道，如圖4 所示。

圖4 第一次調度結束后的新樹圖Fig. 4 New tree after the first scheduling

Step 5重復上述步驟，直到根節點工序A1調度完畢，調度過程見表1。

表1 復雜產品A 調度過程表Tab.1 Scheduling process of complex product A

復雜產品A按照動態調整葉節點工序方法，調度順序為：｛A26，A27，A21，A6，A24，A17，A22，A19，A14，A13，A25，A20，A16，A10，A23，A18，A8，A12，A15，A5，A3，A11，A9，A7，A4，A2，A1｝，調度甘特圖如圖5 所示，共計27個加工用時。

圖5 本文算法加工復雜產品A 甘特圖Fig. 5 Gantt chart of complex product A processed by this algorithm

4 算法對比分析

4.1 與文獻［13］的算法對比

文獻［13］的算法，按照緊密程度將復雜產品的所有工序分為2 類，對于緊密度較高的工序組采用“首次適應調度”算法，對于緊密度較弱的工序組使用“擬關鍵路徑法”，調度順序為｛A24、A21、A26、A27、A25、A23、A22、A19、A18、A15、A11、A20、A16、A12、A9、A17、A14、A13、A10、A8、A5、A6、A3、A7、A4、A2、A1｝，如圖6 所示，總用時28 工時。

圖6 文獻［13］算法甘特圖Fig. 6 Gantt chart of the algorithm in Ref.［13］

對比分析本文算法和文獻［13］的算法對應的加工甘特圖5 和圖6 可知，本文算法中各個加工設備不相同且彼此獨立，所以在滿足緊前工序（組）約束前提下，設備M3在t ＝16 時刻調度工序A9，充分利用了設備M3在t ＝16 到t ＝18 時刻的空閑段。同時，因工序A5在圖5 中比在圖6 中早3 個工時開始加工，其緊后工序（組）A3、A2、A6的加工時間比在圖6中分別提前了3、1、1 個工時開始加工。在設備M2上，本文算法從t ＝0 到t ＝13 時刻一直連續加工，處于“設備忙” 的狀態，提高了M2的設備利用率。在設備M1上本文算法因工序A13從t ＝4 時刻開始加工，比圖6 中的t ＝12 時刻提前了8 個工時開始加工，其后續工序A8、A3分別提前了3 個工時開始加工。對比分析表明，本專利方法能夠有效減少對應加工設備的空閑時間，并提高了加工工序的緊密銜接度，進而優化了復雜產品整體調度效果。

4.2 與文獻［14］算法對比

文獻［14］算法在復雜產品工藝樹的整體結構的基礎上，首先將工藝樹按照排序策略劃分為只具有串行關系的工序序列，然后從調度方案集合中按照擇時策略依次選擇加工總用時最小和最早的方案進行調度。

針對復雜產品A的加工工藝樹，采用文獻［14］算法形成初始調度方案為｛A1、A2、A4、A7、A9、A11、A15、A18、A18、A25、A26｝，在此基礎上按照｛A3、A11、A9、A13、A17、A19、A16、A20、A24、A6、A19、A27、A21、A14、A22、A26｝ 的順序進行調整，結果甘特圖如圖7 所示，總加工用時為31 工時。

圖7 文獻［14］算法甘特圖Fig. 7 Gantt chart of the algorithm in Ref.［14］

對比分析本文算法和文獻［14］的算法對應的加工甘特圖5 和圖7 可知，本文算法所有設備均從t＝0 時刻的始點開始加工，整體上比文獻［14］算法中的各工序銜接度要高。

在設備M4上，圖5 在t ＝20 時刻完成了對應所有工序的加工，而圖7 中在設備M4上所有工序加工結束前在t ＝0 至t ＝8 時刻、t ＝9 至t ＝10 時刻、t ＝16 至t ＝19 時刻、t ＝20 至t ＝22 時刻出現共計14 個工時的設備空閑時間段，明顯多于圖5 中的9 個工時的空閑時間段，設備M4利用率提高了11%。

在設備M3上，圖5 在t ＝25 時刻完成了對應所有工序的加工，而圖7 中在設備M3上所有工序加工結束前在t ＝3 至t ＝4 時刻、t ＝5 至t ＝14 時刻、t ＝16 至t ＝20 時刻、t ＝27 至t ＝28 時刻出現共計15 個工時的設備空閑時間段，多于圖5 中的11 個工時的空閑時間段，設備M3利用率提高了7.7%。

在設備M2上，圖5 在t ＝22 時刻完成了對應所有工序的加工，而圖7 中在設備M2上所有工序加工結束前在t ＝0 至t ＝2 時刻、t ＝5 至t ＝7 時刻、t ＝14至t ＝18 時刻、t ＝19 至t ＝24 時刻出現共計13 個工時的設備空閑時間段，明顯多于圖5 中t ＝13 至t ＝14 時刻、t ＝15 至t ＝21 時刻共計7 個工時的空閑時間段，設備M2利用率提高了14.6%。

在設備M1上，圖5 在t ＝27 時刻完成了對應所有工序的加工，而圖7 中在設備M1上所有工序加工結束前在t ＝0 至t ＝5 時刻、t ＝19 至t ＝29 時刻出現共計15 個工時的設備空閑時間段，多于圖5 中t ＝6 至t ＝10 時刻、t ＝18 至t ＝25 時刻共計11 個工時的空閑時間段，設備M1利用率提高7.7%。

綜上，從各個設備利用率的角度分析，本文算法采用將對應設備與動態調整產生的葉節點工序進行組合的方法，是從工序和設備兩個角度進行優化，對比分析表明本文算法不僅減少了各個設備的空閑時間段，而且提高了所有加工設備的利用率，進而提高了復雜產品加工的設備總體利用率。3 種算法的調度過程時間對比和設備利用率對比見表2。

表2 3 種算法的調度過程時間對比和設備利用率對比Tab.2 Comparison of scheduling process time and equipments utilization of three algorithms

4.3 3 種算法調度結果對比分析

對圖1 中的復雜產品A，文獻［13］的算法總加工用時為28 工時、文獻［14］的算法總加工用時為31 工時，而本文算法總加工用時為27 工時。由此可知，本文算法更優，主要是因為：

文獻［13］的緊密銜接工序組聯動的算法雖然注重銜接緊密的工序組，但工序組中只由工序組成，不僅忽略了緊密銜接度不高的其他工序的相對位置等因素對調度結果的整體影響，而且沒有充分利用設備的空閑時間段。例如，設備M2在t ＝17 至t ＝23時刻、設備M3在t ＝8 至t ＝14 時刻和設備M4在t ＝5 至t ＝11 時刻出現較長時間的空閑。

文獻［14］ 中考慮串行工序緊密度的擇時算法與緊密銜接工序組聯動的算法相似，也是只以工序為主要優化對象，通過擇時調度策略確定串行工序加工開始時間點，同樣沒有充分考慮到設備的利用率問題，忽略了設備因素在綜合調度中的重要作用。例如設備M1在t ＝18 至t ＝29 時刻、設備M3在t ＝5 至t ＝14 時刻、設備M4在t ＝1 至t ＝8 時刻這些時間段一直處于空閑狀態，沒有加工工序，因此就給復雜產品加工過程造成一定的整體影響。

相對于緊密銜接工序組聯動算法、考慮串行工序緊密度的擇時算法，本文算法的設備利用率分別提高了0.8%、10.5%，實驗表明本文算法在復雜產品的綜合調度中效果更優，不僅為解決一般復雜產品的綜合調度提供了一種新的方法，而且為進一步深入研究綜合調度拓展了思路，具有一定的理論和實際意義。

5 結束語

綜上所述，本文以優化復雜產品綜合調度的時間成本目標，以復雜產品工藝樹結構中具有重要作用的葉節點工序為優化對象，提出了基于動態調整葉節點工序的算法。實驗對比分析表明，本文算法有效地提高了設備的利用率，為綜合調度提供了一種新的研究方法。