考慮工序序列動態時間緊迫度的逆序貪婪綜合調度算法

曹望成 謝志強 裴莉榕

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

②(牡丹江師范學院計算機科學與技術系 牡丹江 157011)

1 引言

調度優化問題的典型實例有制造車間中工序[1]的排序優化問題，網格計算中工作流[2–4]的費用優化問題和云計算中云服務工作流應用程序[5,6]或MapReduce任務[7]的排序優化問題。

智能制造已作為核心專項工程納入《中國制造2025》實施戰略。全國“兩會”政府工作報告[8]、《中國制造2025》和國務院關于積極推進“互聯網＋”行動的指導意見中均明確指出我國將大力發展產品個性化定制。消費者對產品多元化及個性化需求的不斷增加，促使產品類型趨向多品種、小批量。當制造多品種、小批量產品，特別是單件復雜結構產品時，如果按照傳統的先分步加工調度最后整體裝配調度的生產模式排產，必將割裂加工工序和裝配工序可并行處理的關系，降低復雜單產品生產效率。

謝志強等人[9–11]提出了第3類產品制造調度模式：加工工序和裝配工序一同處理的綜合調度，簡稱綜合調度。綜合調度是智能制造的核心組成部分，更是實現中國制造2025和工業4.0[12]的重要手段，學者針對綜合調度問題的算法優化做了大量研究工作。針對單車間一般綜合調度問題，謝志強等人[13,14]提出的考慮串行工序緊密度的擇時綜合調度算法[13]和考慮后續工序的擇時綜合調度算法[14]，存在以下缺點：

(1)文獻[13]的擇時綜合調度策略為每道工序選擇當前完工總用時最小的方案，忽略了該道工序對屬于同一工序序列的后續串行工序的影響，導致算法出現局部最優而影響產品調度結果的弊端；

(2)文獻[14]的工序排序策略與文獻[13]相同，在應用擇時綜合調度策略調度工序時不能總是優先處理對生產周期有較大影響的工序序列上的工序，必須回溯調整[15]，導致算法復雜度偏高。

綜上所述，本文提出串行工序序列的時間緊迫度(TUD)定義，應用所提工序排序策略得到工序隊列，再結合所提逆序貪婪調度策略，以工序為單位建立其工序調度方案，最后一道工序的調度方案即為產品調度方案。

2 問題模型描述

為便于綜合調度，將加工工序和裝配工序統一定義為工序，加工設備和裝配設備統一定義為設備。復雜單產品進行綜合調度時需滿足以下要求。(1)所有工序的加工時間已知而且與其加工順序無關，產品工序間的約束關系事先已知。(2)每道工序只能由一臺設備加工，某時刻每臺設備只能加工一道工序，工序一旦開始被加工則直至加工結束不能被間斷。(3)允許工序之間等待，允許設備在工序到達之前空閑。(4)當工序無緊前工序或其緊前工序均被加工完畢時，該工序才能被加工。(5)車間內不存在相同設備。

個性化定制復雜結構單產品(如飛行器)的加工工藝拓撲關系結構圖呈樹狀結構，結點間有向邊的方向與樹結構中相反，稱為產品加工工序樹，簡稱工序樹。為方便敘述，文中“結點”等價于他所表示的“工序”。

定義1 逆序工序樹。將工序樹中有向邊的方向取反之后所得到的樹型結構。

定義2 工序序列(Process Sequence, PS)。逆序工序樹中，從根結點或者某叉點孩子結點a開始，沿有向邊的方向遍歷結點，直到葉結點b為止，彼此之間具有串行偏序關系的結點序列，稱為工序a到 工序b的工序序列，記為P Sab。特別地，當工序序列只包含單個工序c時，此工序序列記為P Scc。

定義3 工序序列長度。工序序列中全部結點所代表工序的加工時間之和。

定義4 結點的路徑。逆序工序樹中，從根結點開始沿有向邊的方向遍歷到當前結點，所得到的有序結點序列稱為當前結點的路徑。

定義5 結點的路徑長度。結點的路徑上全部結點的加工時間之和。

定義6 關鍵路徑。當前逆序工序樹中，長度最長的葉結點的路徑，若不唯一，選擇包含工序數多的路徑為關鍵路徑，若仍不唯一，任選其一。

定義7 工序隊列。用于存放初始逆序工序樹中的全部結點按照工序排序策略所得到的排序結果，為方便描述，隊列中的結點簡寫為該結點所代表的工序名稱。

定義8 準調度時間點。根據工藝約束關系，某工序的緊前工序加工結束時間點之后其對應的設備上所有空閑時間段的開始時刻都是該工序的準調度時間點。

定義12 工序調度方案。設工序隊列中第k道工序試調度共產生X個準調度方案，它們構成準調度方案集Pk(X) ， 從Pk(X)中選擇完工時間最小的方案為工序調度方案，記為Pk，若不唯一，則從中選擇使該道工序盡早開始加工的方案。

定義13 產品調度方案。產品的全部n道工序試調度后產生的最佳調度方案，用P表示。

假設復雜單產品包含n道工序，需要m臺設備。Ai表 示編號為i(1≤i ≤n)的 工序，sij表 示Ai在設備Mj(1≤j ≤m) 上 的加工開始時間，tij表示其在設備Mj上的連續加工時間。工序隊列中第1道工序為根結點工序，其加工開始時刻為0，對應的工序調度方案為P1。 設工序隊列中第k道工序的工序調度方案為Pk，則Pn即 為P，一般綜合調度問題的目標函數及約束條件描述為

3 策略設計

本文中工序、設備和方案的結構描述如下。

(1)用鏈表存儲產品初始逆序工序樹，工序隊列存儲經排序后的全部結點，鏈表和隊列中元素的結構為：Node- Aid :{int} /Mid:int /T:int /L:int/F:Node*/Q:Node*[]/Tb:int /Te:int。A id是結點表示的工序名， M id 是工序對應的設備名，T是工序在機器M id 上的加工時間，L是結點的路徑長度，F是指向其緊前工序的指針，Q是指向結點緊后工序的指針集合， Tb 是工序實際開始加工時刻，Te是工序的加工結束時刻。

(2)調度方案的設備列表中設備結構為：M?Mid:int/NodeList:Node?/finishtime:int。

Mid 是設備名；N odeList 是設備上已試調度的工序鏈表，工序按加工開始時刻由小到大排序；finishtime是當前設備完工時間的最大值。

(3)調度方案結構為：P ?Pid:int/MachineList:M ?/totaltime:int。

Pid 是方案名；M achineList是方案對應的設備列表；t otaltime是方案中所有設備完工時間的最大值。

3.1 工序排序策略

3.1.1 工序排序策略分析

定義14 工序序列的時間緊迫度(Time Urgency Degree, TUD)。 Ai表示當前逆序工序樹關鍵路徑上的叉點，Li(j)表 示以 Ai的 第j個孩子為起點的唯一最長工序序列的長度，將Li(j)減 去以 Ai為緊前工序的最長工序序列的長度max(Li(x)),(x= 1,2,...,j,...)的差值定義為以 Ai為 緊前工序的第j個工序序列的時間緊迫度，記為T Pi(j) =Li(j)?max(Li(x))。

將 TPi(j)大 小作為判斷以第j個工序序列為關鍵路徑的子樹的完工時間對當前逆序工序樹完工時間影響程度的基本依據。工序序列時間緊迫度越大表明其所屬子樹對當前逆序工序樹的完工總時間影響越大，子樹上工序對設備的需求緊迫度越大，為縮短產品生產周期，優先調度該子樹上的工序。工序序列由若干加工時間不等的工序組成，隨著時間緊迫度值大的工序序列上的某道或某些工序加工完畢，由該工序序列剩余工序所組成的工序序列的時間緊迫度值將會發生變化，即工序序列的時間緊迫度是動態變化的。

3.1.2 工序排序策略的算法設計

設置一個工序隊列 Queue 、一個整型變量N、兩個鏈表L ist0 和L ist1。 Q ueue存放工序排序策略的結果；N是初始逆序工序樹的層數；L ist0存儲初始逆序工序樹，L ist1保 存排序前的工序樹L ist0。

算法1：工序排序策略算法

(1) 初始化L ist0 ， L ist1為空；

(2) 創建逆序工序樹L ist0：根據輸入產品工序的信息、工序間偏序關系和設備信息創建工序結點，輸入工序屬性值，插入逆序工序樹，屬性L，Tb和T e初值為0；

(3) 計算各結點的路徑長度和N，確定關鍵路徑的長度T′，更新各結點L屬性值：根結點的路徑長度為根結點的加工時間，其余結點的路徑長度為該結點的加工時間加上其緊前工序的路徑長度；

(4) 初始化Q ueue；

(5) i=0；

(6) 用L ist1備 份L ist0；

(7) 判斷工序樹中葉子結點個數是否為1，是轉步驟(8)，否則轉步驟(9)；

(8)i++， 將葉子結點入Q ueue，轉(11)；

(9) 調用算法2，對當前逆序工序樹中葉子結點排序并依次入Q ueue；

(10)L ist0 復制L ist1，在工序樹中刪除所有葉子結點，轉步驟(6)；

(11)判斷入隊列結點的指針F是否為空，是轉步驟(13)，否則轉步驟(12)；

(12)從工序樹中刪除所有葉子結點，轉步驟(7)；

(13)將Q ueue中的元素逆置；

(14)退出：返回Q ueue，N。

3.1.3 當前逆序工序樹中葉子結點排序算法設計

設置1個1維指針數組a[k](k=0,1,...,n ?2)，1個1維整型數組b[k](k=0,1,...,n ?2)， 堆棧Stack1和 S tack2 。排序過程中，a[k]存放指向以關鍵路徑上各叉點的孩子結點作為起點的唯一最長工序序列的指針，b[k]存 放a[k]元素所指向的各工序序列的時間緊迫度的數值，將a[k]中 元素按b[k]中對應數值由小到大排序；S tack1存放某工序序列所包含的全部叉點；S tack2 存放數組a[k]從前到后的各個元素。

算法2：當前逆序工序樹中葉子結點排序算法

(1) 初 始 化a[k]，b[k] ，S tack1 ，S tack2為 空，j=0；

(2) i++ ；

(3) 確定關鍵路徑，將其作為初始逆序工序樹中時間緊迫度最大的工序序列；

(4)j++，將關鍵路徑最后一個結點存入Queue，qj為指向該工序序列首結點的指針；

(5) 判斷指針qj指向的結點是否為叉點，是轉步驟(6)，否則轉步驟(7)；

(6) 叉點入S tack1；

(7) 指針后移指向下一結點；

(8) 判斷指針否為空，是轉步驟(9)，否則轉步驟(5)；

(9) 從工序樹中刪除此時間緊迫度最大的工序序列中的工序；

(10)判斷S tack1是否為空，是轉步驟(16)，否則轉步驟(11)；

(11) S tack1出棧，在逆序工序樹森林中，為出棧結點的各緊后工序找到以其為起點的一個長度最長的工序序列，若不唯一，選擇工序數多的，用a[k++]保存指向各最長工序序列的首結點的指針；

(12)依次計算各工序序列的時間緊迫度并存入b[k++]：為便于計算，方法是用各工序序列葉結點的路徑長度減去初始工序樹關鍵路徑長度；

(13)判斷S tack1是否為空，是轉步驟(14)，否則轉步驟(11)；

(14)將a[k]中 元素按b[k]中對應數值由小到大排序，數值相等時按工序序列所包含的工序數由小到大排序；

(15)將a[k]元 素從前到后依次入S tack2保存，清空a[k]和b[k]；

(16)判斷S tack2是否為空，是轉步驟(18)，否則轉步驟(17)；

(17) S tack2出棧，出棧指針所指工序序列作為其所屬子樹的時間緊迫度最大的工序序列，轉步驟(4)；

(18)退出。

3.2 逆序貪婪調度策略

3.2.1 逆序貪婪調度策略分析

工序隊列中第1個元素為根結點，安排其在所需設備上的“0”時刻試調度形成唯一的P1。試調度工序隊列中序號為i(i ≥2)的工序時，其緊前工序已被試調度完畢，因此序號為i的工序的準調度時間點已知，設Q T中 元素個數為X，可形成X個工序準調度方案，從中選擇結束時間最小的準調度方案，若不唯一，選擇使該工序最早開始加工的方案作為Pi，依次類推，直到序號為n的 工序試調度結束，Pn即 為P。

逆序貪婪調度的優點有3個：(1)因為是按由根到葉的順序試調度各工序，在試調度Q ueue中序號為i(i ≥2)的工序時，約束關系被破壞的已試調度工序數量少，只需考慮序號小于等于i?1的同設備工序；(2)當序號為i?1的 工序試調度結束，序號為i的工序的“準調度時間點”便隨之確定，算法效率高；(3)逆序貪婪調度以單個工序為單位進行試調度，形成Pi時 即實現了前i道工序的充分并行處理。

3.2.2 逆序貪婪調度策略算法設計

4 算法設計與復雜度分析

4.1 算法設計

首先應用算法1對全部工序進行排序，形成工序隊列；其次對工序隊列中序號為1的根結點進行調度，形成P1， 再對序號為i(2≤i ≤n)的工序應用算法3建立Pi；最后形成甘特圖并輸出。

算法4：考慮工序序列動態時間緊迫度的逆序貪婪綜合調度算法

(1) 應用算法1對工序排序，得到包含n(n ≥1)個工序的Q ueue；

(2) 試調度根結點工序，形成P1；

(3) i=2；

(4) 判斷i≤n是否成立，是轉步驟(5)，否則轉步驟(7)；

(5) 應用算法3建立Pi；

(6)i++，轉步驟步驟(4)；

(7) 形成甘特圖并輸出；

(8) 退出。

4.2 算法復雜度分析

假設產品的工序數為n， 有m臺設備，逆序工序樹的層數為N。

文中算法4是總算法，在算法4中調用1次算法1和循環n ?1次調用算法3。算法1調用了算法2。因而算法4的時間復雜度為總的時間復雜度，即算法1和循環n?1次調用算法3的時間復雜度之和。

4.2.1 算法1的時間復雜度

算法1主要包括以下4個操作：

(1)建立逆序工序樹

建立逆序工序樹是根據輸入的產品工序信息、工序間的偏序關系及設備信息建立鏈表的過程，為鏈表中的n個結點的屬性賦初值，時間復雜度為n的整數倍，時間復雜度為O(n)。

(2)計算工序路徑長度和工序樹的層數

計算工序路徑長度和工序樹的層數只需要對逆序工序樹由根開始進行1次遍歷，時間復雜度為O(n)。

(3)調用算法2

影響算法2時間復雜度的核心操作可簡單地描述為以下4個步驟：

(a)獲取當前逆序工序樹中的葉子結點；

(b)對步驟1中得到的葉子結點進行排序，將排序后的結點追加到工序隊列的末端；

(c)刪除當前逆序工序樹的葉子結點，得到新的當前逆序工序樹；

(d)重復步驟(a)，步驟(b)，步驟(c)，直到所有的結點都進入工序隊列。

4個步驟中對前3個步驟的循環次數為初始逆序工序樹的層數N，分析前3個步驟的時間復雜度。

步驟(a)只需要對當前逆序工序樹進行1次遍歷，設工序樹中結點個數為ni(i=1,2,...,N)，顯然有ni

步驟(b)每次進行排序的葉子結點數平均為n/N，進行排序的時間復雜度為O((n/N)2)，循環N次的時間復雜度為O(N×(n/N)2)=O(n2/N)。

步驟(c)刪除當前逆序工序樹的葉子結點只需要對當前工序樹進行1次遍歷，循環N次總的時間復雜度與步驟(a)相同，最大為O(n2)。

因此調用算法2的時間復雜度為O(n2)。

(4)將工序隊列Q ueue中的元素逆置

借助一個堆棧即可實現工序隊列 Q ueue 中n個元素的逆置，時間復雜度為O(n)。

綜合分析，算法1的時間復雜度為以上4個操作的時間復雜度之和，即為O(n2)。

4.2.2 循環調用算法3的時間復雜度

5 算法實例與對比分析

本文提出的算法是基于理論分析，不針對任何具體實例，具有普遍意義，為了方便讀者了解該算法，下面借助產品調度實例進一步說明。設制造企業的單件訂單產品 A包含37道工序，需要4臺設備，產品的逆序工序樹如圖1所示。逆序工序樹中結點用長方框表示，長方框內的信息是對應工序4個屬性的簡寫：工序名的編號i|設備名的編號j|工序的加工時間|結點的路徑長度，其中加工時間為單位時間(h)。

圖1 產品A的逆序工序樹

應用文獻[11]的策略確定產品 A中工序的調度次 序 為： A37 ，A 34 ，A 36 ，A 35 ，A 32 ，A 29，A33 ，A31 ，A30 ，A25 ，A26 ，A27 ，A24 ，A21，A20 ，A28 ，A22 ，A23 ，A19 ，A16 ，A15 ，A17，A18 ，A 12 ，A 9 ，A 13 ，A 14 ，A 10 ，A 11 ，A 8，A7 ，A 6 ， A2， A4 ，A 5，A 3 ， A1。同 設 備 工 序A17 與A 18的路徑長度分別為9和8，加工時間都是1 h，A 18所在的路徑為關鍵路徑，文獻[11] 只關注工序的路徑長度，忽略了工序所在分支對產品周期的整體影響，優先處理工序 A17造成調度結果欠佳，產品生產周期為26 h。

應用文獻[13]的工序序列排序策略將產品 A的10個工序序列按路徑長度由大到小排序。調度過程中，以關鍵路徑形成的初始調度方案為基礎，每調度1道工序形成多個準調度方案，從中選擇當前最佳調度方案，容易使算法陷入局部最優。比如在調度工序 A4 時， A4的4個準調度時間點分別為2，6，11，17，文獻[13]選擇在時間點11調度 A4，雖然當前方案總用時最少，但使得設備 M3上 A1與A 7,A7與A 23之 間出現了空閑時間段，且 A4所在工序序列的完成時間滯后，整體調度結果欠佳，產品生產周期為32 h。應用文獻[11]和文獻[13]，調度甘特圖如圖2和圖3所示。

圖2 使用文獻[11]算法調度產品A所得調度甘特圖

圖3 使用文獻[13]算法調度產品A所得調度甘特圖

應用本文所提算法調度產品 A。應用算法1對工序進行排序，其中排序第1層葉子結點時的工序序列劃分示意圖如圖4所示，工序排序結果為：A37 ，A34 ，A35 ，A24 ，A32 ，A31 ，A11 ，A21，A28，A 2。

圖4 排序第1層葉子結點時的工序序列劃分示意圖

全部工序排序后，將 Queue中的元素逆置，Queue 中 從 前 到 后 為： A1 ，A 3 ，A 7 ， A4 ，A 13，A6 ，A 9，A 18，A 12 ， A 15，A 23 ，A 5，A 17 ，A 8，A20 ，A27 ，A10 ，A22 ，A14 ，A25 ，A33 ，A16，A26 ，A 19 ，A 30 ，A 29 ，A 36 ， A2 ，A 28 ，A 21，A11 ，A31 ，A32 ，A24 ，A35 ，A34 ，A37。Queue 出隊列，試調度工序，只有試調度 A4，A12， A 16 ，A 24 建立P4，P9，P22，P34的過程中涉及準調度時間點的選取。 A4的準調度時間點為2和6，選擇2； A12的準調度時間點為5和8，選擇5；A16 的準調度時間點為8, 11和15，選擇8；A 24的準調度時間點為14和19，選擇19。4次試調度過程如圖5所示，灰色工序對應的方案作為工序調度方案。本文算法調度產品 A的調度甘特圖如圖6所示，生產周期為24 h。

圖5 4次試調度工序的過程示意圖

圖6 使用本文算法調度產品A所得調度甘特圖

應用文獻[14]和文獻[15]算法調度產品 A，調度結果與本文算法相同，產品生產周期為24 h，但因它們的工序排序策略與文獻[13]相同，不能優先調度時間緊迫度值大的工序序列上的工序，所以算法復雜度高于本文。

對比發現，應用本文算法調度產品 A 時，不但可以縮短產品的生產周期而且效率較高。

6 結束語

本文主要結論如下：

(1)工序排序策略，提出工序序列時間緊迫度的定義，將同層工序按所屬工序序列時間緊迫度值由大到小的順序確定調度順序，優化了調度結果；克服了文獻[13]的排序策略導致調度結果易于陷入局部最優的缺點；

(2)逆序貪婪調度策略，每道工序只需考慮在空閑的準調度時間點調度，算法復雜度不超過二次多項式。

綜上所述，本文算法優于目前典型的一般綜合調度算法，工序序列時間緊迫度概念的提出為進一步深入研究綜合調度問題拓展了思路，具有一定的理論和實際意義。該算法注重縮短橫向同層可調度工序并行調度結束時間的同時，更強調以動態時間緊迫度值大的工序序列為主的縱向調度優化思想，優化了綜合調度結果。