基于逆序層優先的柔性綜合調度算法

謝志強 王 茜

(哈爾濱理工大學計算機科學與技術學院 哈爾濱 150000)

1 引言

傳統的生產制造過程，將加工[1,2]和裝配[3,4]作為兩個獨立的階段，對問題的研究主要針對零部件的批量加工，例如針對大批量生產環境的flow shop調度問題[5,6]和針對多品種小批量生產環境的job-shop調度問題[7,8]。隨著社會多元化需求的增加，多品種小批量的訂單逐漸增多，在這種多元化需求環境的驅動下，需要一種新的生產調度模式，滿足人民個性化定制型產品的需求。這樣，綜合調度[9]應運而生，它將產品的加工過程和裝配過程統一為加工過程，將復雜產品映射為虛擬加工樹。由于同時考慮了工序間的順序約束和裝配約束，綜合調度問題在縮短產品制造周期、提高生產系統效率方面，具有重要的研究意義和實際應用價值。另外，隨著加工技術、自動化技術的發展，柔性制造系統和數控加工中心等帶有一定柔性的生產系統在實際企業生產中扮演著越來越重要的角色，柔性作業車間調度問題更加符合實際生產問題。因此，本文研究具有柔性設備選擇的樹狀結構產品綜合調度問題。

柔性綜合調度問題較傳統的車間調度問題和一般的綜合調度問題更為復雜，也是一類典型的NP難問題[10]。目前，對綜合調度問題研究的文獻還相對較少，且主要求解單車間一般綜合調度問題[11,12]等。 針對柔性綜合調度問題，在基于啟發式規則的相關解決方案中，謝志強等人[13]提出了一種考慮設備無關延遲約束的綜合柔性調度算法。謝志強等人[14]從設備找工序的角度出發，提出了一種基于設備驅動的綜合柔性調度沖突調解算法。Birgin等人[15]提出了一種基于鏈表的柔性綜合調度算法，并且在此基礎上進一步提出了一種基于集束搜索的柔性綜合調度算法。謝志強等人[16]提出了一種設備驅動和實質路徑的動態并行綜合柔性調度算法，該算法兼顧了設備驅動和動態實質短路徑策略的優點，提高了設備利用率和并行處理效率。針對柔性綜合調度問題，在基于智能優化算法的相關解決方案中，趙詩奎等人[17]提出了一種基于虛擬零部件級別分區編碼的產品綜合調度算法。該算法將產品的各零部件設置級別，按級別進行分區編碼，該種編碼方式保證了初始解的可行性，但其編碼方式存在缺點，即有遺漏最優解的風險。Lei等人[18]提出了一種基于工序關系矩陣表的綜合調度算法，該算法首先為產品建立一個工序關系矩陣表，隨后基于該表設計了相應的編碼規則和進化算子。由于綜合調度問題中復雜優先順序約束條件的存在，導致已有的各種編碼方法和進化算子均已失效，進而使得智能優化算法在綜合調度問題中的應用受限。總體來說，研究柔性綜合調度問題的相關文獻還相對較少。

在上述求解柔性綜合調度問題的相關算法中，均考慮正向調度，即從葉節點開始調度，直至根節點調度完畢，則代表產品調度加工完成。在正向調度的解決方案中，當某一工序有多個緊前工序時，難以合理安排這些相關工序，進而影響產品總加工時間。因此，本文采用逆序調度的思想，從根節點開始調度，這樣可以簡化某一工序存在多緊前工序的約束條件，便于合理安排各工序。最終將調度產生的逆序調度方案轉換為正序調度方案。

2 問題描述

在傳統的柔性Job-shop調度問題中，工序間的總體約束結構呈線狀，而柔性綜合調度問題中調度對象的總體工藝結構圖呈樹狀結構，這使得在樹狀結構產品柔性綜合調度問題的調度過程中，需要考慮工序間的協調和同步問題，從而使問題的目標函數得到優化。在該問題中，某產品的工藝加工樹如圖1所示，每個工序由3部分構成，即工序名、加工設備集以及對應的加工時間，箭頭的指向規定了工序間的加工順序。樹狀結構產品柔性綜合調度問題的數學模型可以描述為：由n道工序 {oi}1≤i≤n構成的樹狀結構復雜單產品，需要在m臺設備上進行加 工，工 序oi的 可 加 工 設 備 集 為{Mi}1≤i≤n ?{1,2,...,m}并 且Mi ?=?，pik為 工 序oi在 設 備k ∈Mi上的加工時間。si和ci分別表示工序oi的開始加工時間和完工時間。xli=1表示工序ol是工序oi的工藝緊前工序；yik=1表示工序oi在設備k∈Mi上進行加工；zij=1表示在同設備上加工的工序oi和oj，工序oi為工序oj的設備緊前工序，即工序oj在工序oi加工完成之后才開始加工。因此本問題的數學描述為

圖1 產品A加工工藝樹

其中，本問題的調度目標是合理安排各工序以使產品的完工時間盡可能短，目標函數如式(1)所示。式(2)表示每道工序要被分配到某1臺且只能1臺機器上進行加工；式(3)表示工序oi的加工時間，式(4)為工序oi的開工時間，即工序oi要在合理的條件下盡早開始加工；式(5)為工序oi的完工時間。式(6)表示同一臺設備上連續加工的兩道工序，后一道工序的開工時間不能早于前一道工序的完工時間。

3 算法設計

對于一棵產品工藝加工樹，由于根節點加工完畢代表整個產品加工完畢，即根節點工序加工完成為最終加工目的。首先加工葉節點最后加工根節點會導致加工過程中工序有多個緊前約束條件，而首先加工根節點，可減少相關工序節點的加工約束。本文采用逆序調度的思想，即首先加工根節點，直到葉節點加工完畢，該產品調度結束。為了便于算法描述以及后續相關策略的設計，本文首先給出如下定義：

定義1 目標工序：調度過程中，將當前正在安排的某一工序稱為目標工序。

定義2 待調度工序集：即將調度的某一層工序組成的集合。

定義3 擬加工時間：對于可在超過3臺設備上加工的工序，本文去掉最長加工時間和最短加工時間，然后計算剩余加工時間的平均加工時間作為該工序的擬加工時間；對于可在少于兩臺設備上加工的工序，直接計算該時間集的平均加工時間作為該工序的擬加工時間。

定義4 偽緊前工序：由于本文采用逆序調度，原本某一工序的緊后工序成為該工序的緊前工序，稱為偽緊前工序。

定義5 偽緊后工序：由于本文采用逆序調度，原本某一工序的緊前工序成為該工序的緊后工序，稱為偽緊后工序。

定義6 偽緊后路徑長度：按擬加工時間計算時，由目標工序的所有偽緊后工序加工到葉節點的總時間的最大值。

定義7 偽緊前路徑長度：由根節點工序開始加工，目標工序的偽緊前工序的實際完工時間。

定義8 總路徑長度：目標工序的偽緊前路徑長度，偽緊后路徑長度以及擬加工時間之和。

定義9 子孫節點：工序的后代子孫節點，例如工序A15的子孫節點為工序A9，A10，A3，A4，A1。

對于圖1所示的復雜產品柔性工藝加工樹，按照上述定義，我們計算其擬加工時間和偽緊后路徑長度如圖2所示，例如對于工序A15，其擬加工時間為20，偽緊后路徑長度為70。

圖2 圖1所示產品各工序擬加工時間和偽緊后路徑長度

3.1 逆序層優先策略

本文提出逆序層優先的策略，對各工序按層進行調度。首先，為每個工序設置其所在的層數，即規定根節點所在的層為第1層，隨著后續工序其深度每增加1層，所在層數加1。然后，將第i層上的所有工序放入工序集合Oi中作為第i層的待調度工序集，例如O4={A8, A9, A10, A11, A12, A13}。最后，按照層數遞增的順序，依次對各層工序集進行調度。由于本文采用逆序調度加工的思想，緩解了正序調度時，某一工序存在多個緊前工序，難以確定目標工序開工時間的問題。另外，同層工序優先調度，可以最大化的使同層工序并行加工。

3.2 動態擬長路徑策略

對于某層待調度工序集Oi={o1, o2, ···, on}，設其偽緊前工序集為Pi={p1, p2, ···, pn}，偽緊前工序的結束時間即偽緊前路徑長度為PEi={pe1, pe2,···, pen}，擬加工時間集合為A_Ti={a_t1, a_t2,···, a_tn}，偽緊后工序集為Si={s1, s2, ···, sn}，偽緊后路徑長度Ri={r1, r2, ···, rn}，計算第i層待調度工序集中各工序的總路徑長度Ti=PEi+A_Ti+Ri，例如第j個工序的總路徑長度為pej+a_tj+rj。

由于本文采用逆序調度的思想，目標工序的偽緊前工序的結束時間，為目標工序最早可加工時間，在不考慮設備占用的情況下，本文以各工序的總路徑長度，來估計目標工序子孫節點的最終完工時間，路徑長度越大，說明其對應的子孫節點的完工時間越晚，所對應的產品完工時間越晚。因此，本文優先調度路徑長度大的目標工序，由于目標工序的偽緊前工序的結束時間不同，導致每次計算總路徑長度時所得結果不同，因此稱該策略為動態擬長路徑策略。

該策略的主要思想是，按待調度工序集中各工序的總路徑長度對各工序進行降序排列，優先調度總路徑長度值大的目標工序；當總路徑長度值相同時，優先調度擬緊后路徑長度大的工序；當擬緊后路徑長度值相同時，優先調度擬緊后工序個數多的工序；當緊后工序個數相同時，優先調度擬加工時間值大的工序；再相同時，隨機選擇某一工序調度。

3.3 設備選擇策略

對于一棵柔性工藝加工樹，某一工序可能可以在多個設備上加工，但不同加工設備所需加工時間可能不同。為了盡可能地減少總加工時間，本文盡量為目標工序選擇加工用時短的設備進行加工。即針對目標工序oj，獲取該工序的偽緊前工序完工時間，獲取該工序的可加工設備集并按加工時間從小到大排序，若可最短加工時間所對應的設備在目標工序的偽緊前工序完工時刻空閑，則將目標工序分配至該設備上加工；否則，按序選擇將目標工序安排至完工時間最早的設備上加工。 若存在多個設備加工時間相同，則優先選擇目標工序完工時間早的設備進行加工。由于目標工序偽緊后工序是在目標工序的基礎上進行加工，其偽緊后工序的開工時間由該工序的結束加工時間決定，則選擇早結束方案所對應的設備加工對縮短整體加工時間有利。

3.4 設備搶占策略

本文采用逆序調度的思想，從根節點開始，按層序依次調度每層待調度工序集中的工序。由于同層工序間，不存在緊前緊后約束關系，為了充分提高設備占用率，縮短產品完工時間，本文考慮設備搶占情況，以優先加工可早加工的目標工序。

由于首先調度根節點工序，因此，其開工時間我們規定為0。對于目標工序oj，在確定了加工設備進行調度時，若其最早可加工時刻設備空閑，則考慮將該工序放置該時刻進行加工，若該時刻有后續加工工序，則將其移至目標工序完工時刻進行加工。

3.5 基于完工時間翻轉的調度方案轉換策略

由于本文采用逆序調度的思想，所產生的調度方案為逆序調度方案。為了將逆序調度方案轉換為正序調度方案，即產品的調度從葉節點開始，本文給出了一種基于完工時間翻轉的調度方案轉換策略。假設已知待轉換方案的產品最終完工時間，各工序的逆序開工時間和逆序完工時間。則本文所述的轉換策略的具體方法為：首先，將各工序在逆序調度時的開工時間和完工時間分別減去當前方案的產品完工時間；然后，將各工序所對應的結果取反，即將各個開工時間和完工時間值變成非負數；最后將各工序對應的開工時間和完工時間交換即可獲得正序調度時各工序的調度時刻表。注意，在轉變為正序調度方案后，若某一工序的所有緊前工序已加工完成，且當前工序開始加工時刻之前存在空閑時間段，則該工序可以向前移動。但是，無論是在正序調度方案中還是逆序調度方案中，產品的最終完工時間是不變的。因此，本文并沒有考慮工序的移動情況。

3.6 算法總體設計

本文所述的基于逆序層優先的柔性綜合調度算法具體執行步驟如下所述，算法總體流程圖如圖3所示。

圖3 算法總體流程圖

步驟1 輸入設備和產品加工信息，計算工序擬加工時間，偽緊后路徑長度等屬性信息。

步驟2 執行逆序層優先策略，為各工序設計層優先級，并按其所在的層數將其加入至不同的層待調度工序集，并將集合按層序升序排列，假設一共有m層工序，則最終一共產生m個工序集，i=1。

步驟3 判斷i是否大于m，若是則執行步驟4；否則，執行步驟5。

步驟4 執行基于完工時間翻轉的調度方案轉換策略，將逆序調度方案，轉換為正序調度方案，算法結束。

步驟5 假設當前待調度工序集為Oi，則執行動態擬長路徑策略，將待調度工序集中各工序排序。

步驟6 判斷待調度工序集是否為空，若為空，則i=i+1，跳轉至步驟3；否則，執行步驟7。

步驟7 獲取待調度工序中的首個工序作為目標工序，并將其在待調度工序集中移除。

步驟8 按設備選擇策略為目標工序確定加工設備。

步驟9 按設備搶占策略確定目標工序開工時間，跳轉至步驟6。

4 復雜度分析

設工序總數為n，可加工設備總數為m。初始時，算法需要計算工序擬加工時間以及其偽緊后路徑長度，在計算目標工序擬加工時間時，需要執行m次操作，一共有n道工序，因此其時間復雜度為O(n×m)。計算工序偽緊后路徑長度時，首先獲取其偽緊后工序的路徑長度，然后加上當前工序的擬加工時間，共有n道工序，因此，其時間復雜度為O(n)。本算法主要執行以下操作：

(1) 逆序層優先策略。該操作需要遍歷所有工序，將各工序加入不同的逆序待調度工序集，需要執行n次操作，因此，逆序層優先策略的時間復雜度為O(n)。

(2) 動態擬長路徑策略。對于當前逆序層待調度工序集Oi，設其工序個數為ni，對于每道工序我們需要計算其總路徑長度，即執行兩次加法操作，總共執行2×ni次操作，時間復雜度為O(ni)。然后需要按總路徑長度對當前工序集工序進行排序，時間復雜度為O(nilog2ni)。最壞情況下，ni=n，因此，動態擬長路徑策略的時間復雜度為O(nlog2n)。

(3) 設備選擇策略。對目標工序來說，在為其選擇加工設備時，最壞情況下需要考慮所有可加工設備，即執行m次操作。因此設備選擇策略的時間復雜度為O(n×m)。

(4) 設備搶占策略。確定目標工序開工時刻的時候需要確定其最早可加工時刻是否空閑，若空閑則搶占至該時刻進行加工，總共需要判斷n次，因此時間復雜度為O(n)。

(5) 基于完工時間翻轉的調度方案轉換策略。在轉換過程中，需要將各工序在逆序調度時的開工時間和完工時間分別減去當前方案的產品完工時間；然后，將各工序所對應的結果取反變成非負數；最后將各工序對應的開工時間和完工時間交換即可獲得正序調度時各工序的調度時刻表。因此，該策略的時間復雜度為O(n)。

綜上所述，本文所提算法的時間復雜度取上述各項操作的最大值，即所提算法的時間復雜度為O(nlog2n)。

5 實例對比分析

本文所述算法不針對任何具體產品，對所有算例均實用。為了進一步闡述上述算法的執行步驟，本節對圖1所示產品工藝加工樹進行調度加工，并將調度方案與已有的主流的解決柔性綜合調度問題的算法進行對比。

計算各工序相關屬性信息，例如擬加工時間、偽緊后工序徑長度等。

初始時，第1層待調度工序集為O1={A21}，僅包含一個元素，即根節點工序A21，其偽緊前工序集P1={}為空，因此，該層工序最早可加工時刻為PE1={0}，加工時間為t1={(M1,M2,M4)/(20,25, 15)}，擬加工時間集合A_T1={20}，由設備選擇策略為其選擇用時最短的設備M4進行加工，其完工時間為時刻15，第1層待調度工序集調度結束，第1層工序結束時間為e1={A21/15}。

第2層待調度工序集為O2={A18, A19, A20}，其偽緊前工序集P2={A21, A21, A21}，最早可開始加工時刻為PE2={15, 15, 15}，其加工時間集t2={(M1, M3, M4)/(20, 15, 25), (M2, M3,M4)/(15, 20, 25), (M3, M4)/(20, 20)}，擬加工時間集合A_T2={20, 20, 20}，偽緊后工序集合為S2={(A14, A15), (A16), (A17)}，當前層待調度工序集的偽緊后路徑長度集為R2={90, 77.5, 62.5}，則當前待調度工序集各工序所對應總路徑長度為O2= PE2+A_T2+R2={A18/125, A19/112.5,A20/97.5}，對O2按其所對應的總路徑長度按降序進行排列的并按序進行調度，最終調度順序為{A18, A19, A20}。對于工序A18，按設備選擇策略中短用時優先原則，將其分配至設備M3進行加工；對于工序A19，按設備選擇策略中短用時優先原則，將其分配至設備M2上進行加工；對于工序A20，按設備選擇策略中最早結束時間原則，確定其加工設備為M4。第2層待調度工序調度完成，其結束時間集e2={ A18/30, A19/30, A20/35}。

第3層待調度工序集為O3={A14, A15, A16,A17}，其偽緊前工序集P3={A18, A18, A19,A20}，最早可開始加工時刻為PE3={30, 30, 30,35}，其加工時間集t3={(M1, M3, M4)/(20, 20,15), (M1, M3, M4)/(20, 15, 25), (M2, M4)/(20,40), (M2, M4)/(15, 20)}，擬加工時間集合A_T3={20, 20, 30, 17.5}，偽緊后工序集合為S3={(A8), (A9, A10), (A11), (A12, A13)}，當前待調度工序層的偽緊后路徑長度為R3={25, 70,47.5, 45}，則當前待調度工序集各工序所對應總路徑長度為O3= PE3+A_T3+R3={A14/75,A15/120, A16/107.5, A17/97.5}，對O3按其所對應的總路徑長度按降序排列并按序進行調度，最終調度順序為{A15, A16, A17, A14}。對于工序A15，按設備選擇策略中短用時優先原則，確定其加工設備為M3；對于工序A16，按設備選擇策略中短用時優先原則，確定其加工設備為M2；對于工序A17，按設備選擇策略中最早結束時間原則，其加工設備為M4；對于工序A14，按設備選擇策略中最早結束時間策略，其加工設備為M1。第3層待調度工序調度完成，其結束時間集e3={A14/50,A15/45, A16/50, A17/55}。

第4層待調度工序集為O4={A8, A9, A10, A11,A12, A13}，其偽緊前工序集P4={A14, A15, A15,A 1 6, A 1 7, A 1 7}，最早可開始加工時刻為PE4={50, 45, 45, 50, 55, 55}，其加工時間集t4={(M1, M2, M3, M4)/(25, 25, 30, 25), (M1, M3,M4)/(20, 20, 45), (M2, M3, M4)/(25, 20, 20),(M1, M2, M4)/(10, 15, 25), (M1, M3, M4)/(15,15, 35), (M1, M2, M4)/(15, 20, 40)}，擬加工時間集合A_T4={25, 20, 20, 15, 15, 20}，偽緊后工序集合為S4={(), (A3), (A4), (A5), (A6), (A7)}，當前待調度工序層的偽緊后路徑長度為R4={0, 50,20, 32.5, 20, 25}，當前待調度工序集各工序所對應總路徑長度為O4= PE4+A_T4+R4={A8/75,A9/115, A10/85, A11/97.5, A12/90, A13/100}，對O4按其所對應的總路徑長度按降序排列并按序進行調度，最終調度順序為{A9, A13, A11, A12,A10, A8}。對于工序A9，按設備選擇策略，確定其加工設備為M3；對于工序A13，按設備選擇策略中短用時優先原則確定其加工設備為M1；對于工序A11，按設備選擇策略中短用時優先原則，確定其加工設備為M1，由于在先調度A13時，設備M1上將產生5時間段的空隙，因此，根據設備搶占策略，前移調整工序A11；對于工序A12，按設備選擇策略，將其安排至設備M3上加工；對于工序A10，按設備選擇策略，其加工設備為M4；對于工序A8，按設備選擇策略中短用時優先原則，其加工設備為M2。第4層待調度工序調度完成，其結束時間集e4={A8/75, A9/65, A10/75, A11/60,A12/80, A13/75}。

第5層待調度工序集為O5={A3, A4, A5, A6,A7}，其偽緊前工序集P5={A9, A10, A11, A12,A13}，最早可開始加工時刻為PE5={65, 75, 60,80,75}，其加工時間集t5={( M2, M4)/(30, 30), (M2,M3, M4)/(30, 15, 20), (M1, M2, M4)/(15, 20, 25),(M1, M3, M4)/(20, 20, 20), (M1, M2, M3,M4)/(20, 25, 25, 35) }，擬加工時間集合A_T5={30, 20, 20, 20, 25}，偽緊后工序集合為S5={ (A1), (), (A2), (), ()}，當前待調度工序層的偽緊后路徑長度為R5={20, 0, 12.5, 0, 0 }，當前待調度工序集各工序所對應總路徑長度為O5= PE5+A_T5+R5={A3/115, A4/95, A5/92.5, A6/100,A7/100}，對O5按其所對應的總路徑長度按降序排列并按序進行調度，最終調度順序為{A3, A7, A6,A4, A5}。對于工序A3，按設備選擇策略，確定其加工設備為M2；對于工序A7，按設備選擇策略中短用時優先原則，其加工設備為M1；對于工序A6，按設備選擇策略中短用時優先原則，確定其加工設備為M3；對于工序A4，按短用時原則及最早結束時間原則，其加工設備為M4；對于工序A5，按設備選擇策略中短用時優先原則，確定其加工設備為M1。第5層待調度工序調度完成，其結束時間集e5={A3/105, A4/95, A5/110, A6/100,A7/95}。

第6層待調度工序集為O6={A1, A2}，其偽緊前工序集P6={A3, A5}，最早可開始加工時刻為PE6={105, 110}，其加工時間集t6={ (M1, M2,M4)/(15, 20, 35),(M1, M2)/(10, 15) }，擬加工時間集合A_T6={20, 12.5}，偽緊后工序集合為S6={(), ()}，當前待調度工序層的偽緊后路徑長度R6={0, 0 }，當前待調度工序集各工序所對應總路徑長度為O6= PE6+A_T6+R6={A1/125,A2/112.5}，對O6按其所對應的總路徑長度按降序排列并按序進行調度，最終調度順序為{A1, A2}。對于工序A1，按設備選擇策略中短用時原則，確定其加工設備為M1；對于工序A2，按設備選擇策略中最早結束時間原則，確定其加工設備為M2。第6 層待調度工序調度完成，其結束時間集e6={A1/125, A2/125 }。

針對圖1所示產品工藝加工樹，經過本文所述算法，逆序調度甘特圖如圖4所示，產品完工時間為125工時，經本文所述的基于完工時間翻轉的調度方案轉換策略，正序調度方案如圖5所示。

圖4 應用本文所提算法產生的逆序調度方案

圖5 應用本文所提算法產生的正序調度方案

為了驗證所求調度方案的優越性，本文采用主流的解決柔性綜合調度問題的算法對圖1所示產品進行調度加工，其中，采用基于設備驅動的綜合柔性調度沖突調解算法[14]所得到的調度結果如圖6所示，總加工時間為140工時；采用基于設備驅動和實質路徑的動態并行綜合柔性調度算法[16]所得到的調度結果如圖7所示，總加工時間為135工時。采用基于鏈表調度的柔性綜合調度算法[15]所得到的調度結果如圖8所示，總加工時間為155工時。經過對比可以發現本文所得完工時間均優于上述算法所得結果。

圖6 基于設備驅動的綜合柔性調度沖突調解算法調度結果甘特圖

圖7 基于設備驅動和實質路徑的動態并行綜合柔性調度算法調度結果甘特圖

圖8 基于鏈表調度的柔性綜合調度算法調度結果甘特圖

6 結束語

本文針對解決復雜產品柔性綜合調度問題時，正向調度導致調度結果不理想的問題，提出了一種基于逆序層優先的柔性綜合調度算法。首先提出了逆序層優先策略，從根節點開始調度，減少了多緊前工序的約束條件；其次提出了動態擬長路徑策略，優先調度對產品完工時間影響大的工序；然后提出了設備選擇策略和設備搶占策略，盡量為目標工序選擇加工用時短的工序且盡量提前加工，有利于縮短產品完工時間；最后提出了基于完工時間翻轉的調度方案轉換策略，將逆序調度方案轉換為正序調度方案，便于實際調度。該算法在不提高算法復雜度的前提下，提高了設備利用率，縮短了產品完工時間。