基于動(dòng)態(tài)調(diào)整葉節(jié)點(diǎn)工序的綜合調(diào)度算法

劉顯超，趙 男，楊 茁，蘇艷會(huì)，周 偉

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

0 引言

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

隨著互聯(lián)網(wǎng)技術(shù)和計(jì)算機(jī)技術(shù)的發(fā)展，制造行業(yè)的產(chǎn)品需求和社會(huì)需求也發(fā)生了變化［1-5］。但是，人們對(duì)復(fù)雜產(chǎn)品的需求日趨個(gè)性化和多樣化［6-7］，因而亟需解決多品種、小批量復(fù)雜工藝的產(chǎn)品調(diào)度問題。為此，有專家學(xué)者提出了將“產(chǎn)品的加工和裝配同步處理”的綜合調(diào)度［8］并開展了一系列的研究［9-12］，提出了諸多調(diào)度算法，也拓展出很多新的研究領(lǐng)域［12-18］。

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

為解決上述問題，本文以優(yōu)化綜合調(diào)度時(shí)間成本為目標(biāo)，提出了基于動(dòng)態(tài)調(diào)整葉節(jié)點(diǎn)工序的綜合調(diào)度算法。算法以復(fù)雜產(chǎn)品工藝樹的葉節(jié)點(diǎn)工序和對(duì)應(yīng)的加工設(shè)備作為研究對(duì)象，首先以復(fù)雜產(chǎn)品工藝樹原始樹圖構(gòu)建葉節(jié)點(diǎn)工序和對(duì)應(yīng)加工設(shè)備的工序組，在工序組中優(yōu)先調(diào)度層優(yōu)先級(jí)較高的葉節(jié)點(diǎn)工序；其次，在工藝樹中刪除已調(diào)度的葉節(jié)點(diǎn)工序，重構(gòu)復(fù)雜產(chǎn)品工藝樹和葉節(jié)點(diǎn)工序，更新葉節(jié)點(diǎn)工序和對(duì)應(yīng)加工設(shè)備的工序組；如此循環(huán)分解，直到原始工藝樹中所有工序全部調(diào)度完畢的綜合調(diào)度方法。

1 相關(guān)定義

假設(shè)綜合調(diào)度系統(tǒng)有m臺(tái)加工設(shè)備，需要加工完成復(fù)雜產(chǎn)品的n道工序，要求如下：

（1）在加工的某個(gè)時(shí)刻，加工設(shè)備只能連續(xù)加工對(duì)應(yīng)的工序。

（3）不存在相同設(shè)備。

定義1 葉節(jié)點(diǎn)工序在復(fù)雜產(chǎn)品工藝樹中，將沒有緊前工序約束、但是具有緊后約束工序的工序定義為葉節(jié)點(diǎn)工序，且葉節(jié)點(diǎn)工序數(shù)量必須大于等于1。

定義2 工序?qū)觾?yōu)先級(jí)根據(jù)文獻(xiàn)［20］首次提出的層優(yōu)先級(jí)問題，描述為：對(duì)于具有n層結(jié)構(gòu)的復(fù)雜產(chǎn)品，首先將根節(jié)點(diǎn)工序的優(yōu)先級(jí)設(shè)為最低，定義為1，根節(jié)點(diǎn)工序的所有后裔節(jié)點(diǎn)工序的優(yōu)先級(jí)定義為2，以此類推，直到第n層的所有節(jié)點(diǎn)的優(yōu)先級(jí)設(shè)為最高，定義為n［19］。

定義3 工序組在綜合調(diào)度中，處于當(dāng)前復(fù)雜產(chǎn)品工藝樹中的葉節(jié)點(diǎn)工序和其對(duì)應(yīng)的加工設(shè)備組成的加工組合定義為工序組。在工序組中，一臺(tái)設(shè)備至少對(duì)應(yīng)一道葉節(jié)點(diǎn)工序。

2 算法設(shè)計(jì)

復(fù)雜產(chǎn)品加工的全過程中，所有加工設(shè)備彼此獨(dú)立，設(shè)備間不存在優(yōu)先順序的問題。本文分別從橫縱兩個(gè)方面優(yōu)化了復(fù)雜產(chǎn)品的綜合調(diào)度效果，其中縱向優(yōu)化是通過在工序組調(diào)度的葉節(jié)點(diǎn)工序?qū)崿F(xiàn)的，達(dá)到縮短整體加工用時(shí)的優(yōu)化目標(biāo)；橫向優(yōu)化是通過循環(huán)產(chǎn)生新葉節(jié)點(diǎn)工序?qū)崿F(xiàn)的，即通過提高串行工序的緊密銜接度，減少對(duì)應(yīng)設(shè)備上工序加工的間隔時(shí)間，達(dá)到提高各個(gè)設(shè)備利用率的優(yōu)化效果。算法流程如圖1 所示，具體闡述如下：

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

Step 1以復(fù)雜產(chǎn)品工藝樹原始樹圖為基礎(chǔ)，查找所有葉節(jié)點(diǎn)工序。

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

Step 2建立葉節(jié)點(diǎn)工序組。

Step 3判斷工序組中待調(diào)度葉節(jié)點(diǎn)工序是否唯一，是則調(diào)度；否則轉(zhuǎn)Step4。

Step 4按照層優(yōu)先級(jí)由高到低的順序依次調(diào)度組內(nèi)葉節(jié)點(diǎn)工序。

Step 5在復(fù)雜產(chǎn)品工藝樹原始樹圖中刪除已經(jīng)調(diào)度完成的葉節(jié)點(diǎn)工序，形成新的工藝樹。

Step 6重復(fù)Step1，直到根節(jié)點(diǎn)工序調(diào)度完畢。

3 調(diào)度實(shí)例演示

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

圖2 復(fù)雜產(chǎn)品A 工藝樹圖Fig. 2 Complex product A process tree

Step 1以復(fù)雜產(chǎn)品工藝樹原始樹圖為基礎(chǔ)，確定原始工藝樹圖葉節(jié)點(diǎn)工序，共計(jì)9 道，如圖3 所示。

圖3 復(fù)雜產(chǎn)品A 工藝樹圖初始葉節(jié)點(diǎn)工序圖Fig. 3 Initial leaf node process diagram of complex product A process tree diagram

Step 2建立葉節(jié)點(diǎn)工序和對(duì)應(yīng)加工設(shè)備工序組，可表示為：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設(shè)備M1工序組中待調(diào)度葉節(jié)點(diǎn)工序只有A26，直接調(diào)度；設(shè)備M2、M3、M4對(duì)應(yīng)的工序組中，葉節(jié)點(diǎn)工序不唯一，則按照層優(yōu)先級(jí)由高到低的順序依次調(diào)度組內(nèi)葉節(jié)點(diǎn)工序，得到各工序組調(diào)度順序?yàn)镸1：｛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在復(fù)雜產(chǎn)品工藝樹原始樹圖中刪除已經(jīng)調(diào)度完成的葉節(jié)點(diǎn)工序，形成新的工藝樹，得到新的葉節(jié)點(diǎn)工序3 道，如圖4 所示。

圖4 第一次調(diào)度結(jié)束后的新樹圖Fig. 4 New tree after the first scheduling

Step 5重復(fù)上述步驟，直到根節(jié)點(diǎn)工序A1調(diào)度完畢，調(diào)度過程見表1。

表1 復(fù)雜產(chǎn)品A 調(diào)度過程表Tab.1 Scheduling process of complex product A

復(fù)雜產(chǎn)品A按照動(dòng)態(tài)調(diào)整葉節(jié)點(diǎn)工序方法，調(diào)度順序?yàn)椋海鸄26，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｝，調(diào)度甘特圖如圖5 所示，共計(jì)27個(gè)加工用時(shí)。

圖5 本文算法加工復(fù)雜產(chǎn)品A 甘特圖Fig. 5 Gantt chart of complex product A processed by this algorithm

4 算法對(duì)比分析

4.1 與文獻(xiàn)［13］的算法對(duì)比

文獻(xiàn)［13］的算法，按照緊密程度將復(fù)雜產(chǎn)品的所有工序分為2 類，對(duì)于緊密度較高的工序組采用“首次適應(yīng)調(diào)度”算法，對(duì)于緊密度較弱的工序組使用“擬關(guān)鍵路徑法”，調(diào)度順序?yàn)椋鸄24、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 所示，總用時(shí)28 工時(shí)。

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

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

4.2 與文獻(xiàn)［14］算法對(duì)比

文獻(xiàn)［14］算法在復(fù)雜產(chǎn)品工藝樹的整體結(jié)構(gòu)的基礎(chǔ)上，首先將工藝樹按照排序策略劃分為只具有串行關(guān)系的工序序列，然后從調(diào)度方案集合中按照擇時(shí)策略依次選擇加工總用時(shí)最小和最早的方案進(jìn)行調(diào)度。

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

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

對(duì)比分析本文算法和文獻(xiàn)［14］的算法對(duì)應(yīng)的加工甘特圖5 和圖7 可知，本文算法所有設(shè)備均從t＝0 時(shí)刻的始點(diǎn)開始加工，整體上比文獻(xiàn)［14］算法中的各工序銜接度要高。

在設(shè)備M4上，圖5 在t ＝20 時(shí)刻完成了對(duì)應(yīng)所有工序的加工，而圖7 中在設(shè)備M4上所有工序加工結(jié)束前在t ＝0 至t ＝8 時(shí)刻、t ＝9 至t ＝10 時(shí)刻、t ＝16 至t ＝19 時(shí)刻、t ＝20 至t ＝22 時(shí)刻出現(xiàn)共計(jì)14 個(gè)工時(shí)的設(shè)備空閑時(shí)間段，明顯多于圖5 中的9 個(gè)工時(shí)的空閑時(shí)間段，設(shè)備M4利用率提高了11%。

在設(shè)備M3上，圖5 在t ＝25 時(shí)刻完成了對(duì)應(yīng)所有工序的加工，而圖7 中在設(shè)備M3上所有工序加工結(jié)束前在t ＝3 至t ＝4 時(shí)刻、t ＝5 至t ＝14 時(shí)刻、t ＝16 至t ＝20 時(shí)刻、t ＝27 至t ＝28 時(shí)刻出現(xiàn)共計(jì)15 個(gè)工時(shí)的設(shè)備空閑時(shí)間段，多于圖5 中的11 個(gè)工時(shí)的空閑時(shí)間段，設(shè)備M3利用率提高了7.7%。

在設(shè)備M2上，圖5 在t ＝22 時(shí)刻完成了對(duì)應(yīng)所有工序的加工，而圖7 中在設(shè)備M2上所有工序加工結(jié)束前在t ＝0 至t ＝2 時(shí)刻、t ＝5 至t ＝7 時(shí)刻、t ＝14至t ＝18 時(shí)刻、t ＝19 至t ＝24 時(shí)刻出現(xiàn)共計(jì)13 個(gè)工時(shí)的設(shè)備空閑時(shí)間段，明顯多于圖5 中t ＝13 至t ＝14 時(shí)刻、t ＝15 至t ＝21 時(shí)刻共計(jì)7 個(gè)工時(shí)的空閑時(shí)間段，設(shè)備M2利用率提高了14.6%。

在設(shè)備M1上，圖5 在t ＝27 時(shí)刻完成了對(duì)應(yīng)所有工序的加工，而圖7 中在設(shè)備M1上所有工序加工結(jié)束前在t ＝0 至t ＝5 時(shí)刻、t ＝19 至t ＝29 時(shí)刻出現(xiàn)共計(jì)15 個(gè)工時(shí)的設(shè)備空閑時(shí)間段，多于圖5 中t ＝6 至t ＝10 時(shí)刻、t ＝18 至t ＝25 時(shí)刻共計(jì)11 個(gè)工時(shí)的空閑時(shí)間段，設(shè)備M1利用率提高7.7%。

綜上，從各個(gè)設(shè)備利用率的角度分析，本文算法采用將對(duì)應(yīng)設(shè)備與動(dòng)態(tài)調(diào)整產(chǎn)生的葉節(jié)點(diǎn)工序進(jìn)行組合的方法，是從工序和設(shè)備兩個(gè)角度進(jìn)行優(yōu)化，對(duì)比分析表明本文算法不僅減少了各個(gè)設(shè)備的空閑時(shí)間段，而且提高了所有加工設(shè)備的利用率，進(jìn)而提高了復(fù)雜產(chǎn)品加工的設(shè)備總體利用率。3 種算法的調(diào)度過程時(shí)間對(duì)比和設(shè)備利用率對(duì)比見表2。

表2 3 種算法的調(diào)度過程時(shí)間對(duì)比和設(shè)備利用率對(duì)比Tab.2 Comparison of scheduling process time and equipments utilization of three algorithms

4.3 3 種算法調(diào)度結(jié)果對(duì)比分析

對(duì)圖1 中的復(fù)雜產(chǎn)品A，文獻(xiàn)［13］的算法總加工用時(shí)為28 工時(shí)、文獻(xiàn)［14］的算法總加工用時(shí)為31 工時(shí)，而本文算法總加工用時(shí)為27 工時(shí)。由此可知，本文算法更優(yōu)，主要是因?yàn)椋?/p>

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

文獻(xiàn)［14］ 中考慮串行工序緊密度的擇時(shí)算法與緊密銜接工序組聯(lián)動(dòng)的算法相似，也是只以工序?yàn)橹饕獌?yōu)化對(duì)象，通過擇時(shí)調(diào)度策略確定串行工序加工開始時(shí)間點(diǎn)，同樣沒有充分考慮到設(shè)備的利用率問題，忽略了設(shè)備因素在綜合調(diào)度中的重要作用。例如設(shè)備M1在t ＝18 至t ＝29 時(shí)刻、設(shè)備M3在t ＝5 至t ＝14 時(shí)刻、設(shè)備M4在t ＝1 至t ＝8 時(shí)刻這些時(shí)間段一直處于空閑狀態(tài)，沒有加工工序，因此就給復(fù)雜產(chǎn)品加工過程造成一定的整體影響。

相對(duì)于緊密銜接工序組聯(lián)動(dòng)算法、考慮串行工序緊密度的擇時(shí)算法，本文算法的設(shè)備利用率分別提高了0.8%、10.5%，實(shí)驗(yàn)表明本文算法在復(fù)雜產(chǎn)品的綜合調(diào)度中效果更優(yōu)，不僅為解決一般復(fù)雜產(chǎn)品的綜合調(diào)度提供了一種新的方法，而且為進(jìn)一步深入研究綜合調(diào)度拓展了思路，具有一定的理論和實(shí)際意義。

5 結(jié)束語

綜上所述，本文以優(yōu)化復(fù)雜產(chǎn)品綜合調(diào)度的時(shí)間成本目標(biāo)，以復(fù)雜產(chǎn)品工藝樹結(jié)構(gòu)中具有重要作用的葉節(jié)點(diǎn)工序?yàn)閮?yōu)化對(duì)象，提出了基于動(dòng)態(tài)調(diào)整葉節(jié)點(diǎn)工序的算法。實(shí)驗(yàn)對(duì)比分析表明，本文算法有效地提高了設(shè)備的利用率，為綜合調(diào)度提供了一種新的研究方法。