兩車間可調度工序均衡處理的綜合調度算法

謝志強，鄭付萍，朱天浩，周含笑

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

1 概述

產品制造調度問題是NP難問題[1]，目標是在滿足約束條件的前提下，使產品的加工時間盡可能少。以往對大批量相同產品采用流水線方式生產制造的調度方法主要是純加工調度[2-3]和純裝配調度[4-5]，但隨著社會對產品多樣化的需求，多產品小批量的生產計劃越來越多。對多品種小批量產品，特別是單件復雜產品，如果按以往先加工后裝配的方式制造，必然要割裂產品內在的加工與裝配的并行關系，文獻[6]提出產品制造的第3種調度方式：加工和裝配一同處理的綜合調度。隨著綜合調度研究的深入，目前有關綜合調度的研究已解決了一般綜合調度問題[7]、工序間存在特殊約束關系[8]、柔性產品[9]、存在相同設備[10]和存在批處理設備[11]等的綜合調度問題，但所解決的綜合調度問題僅限于設備資源在單車間的情況，目前還無人考慮單件復雜產品在相同設備資源兩車間制造的分布式綜合調度的實際問題。

對于單件復雜產品在兩車間分布式制造的調度問題，主要的研究目標是設計使產品盡早完成的調度方案。為了使產品盡早完成，需要解決以下問題：(1)兩車間充分并行處理，即讓兩車間工序加工的時間差盡量小；(2)工序在兩車間移動的次數盡量少。

對于問題(1)，考慮到葉節點工序為可同時加工工序[12]，即葉節點工序可充分并行處理，本文首先將原始葉節點工序成批調度處理，再將每次動態生成的葉節點工序分批處理，即可調度工序分批處理。考慮到兩車間充分并行處理，即減少在兩車間形成的工序加工時間差，將每批工序按加工時間盡量均衡地分為 2組。借鑒單車間綜合調度中的設備均衡策略[13]，在相同設備的兩車間上，提出使得分配工序時間之和盡量相等的可調度工序車間均衡策略。對于問題(2)，采取將已分組的工序分配到其緊前工序個數較多車間的方法，以降低工序的位移次數，為此提出分組工序車間確定策略。

2 問題描述

對于樹狀結構的單件復雜產品，葉節點工序為初始時可加工的工序，根節點工序為最后加工的工序。由于產品加工過程中形成的緊前工序集為空的動態葉節點工序為可調度工序，于是設動態葉節點工序集為可調度工序集。為了減少產品完成時間，計劃將每批可調度工序進行適當合理的分組并分配到兩車間，為此定義可調度工序分組的相關概念：工序設備分組，車間均衡和設備均衡組。

定義 1(工序設備分組) 對于動態形成的一批可調度工序，按設備種類進行分組稱為工序設備分組。

定義 2(車間均衡) 將按設備形成的分組再按車間均衡分配，使分配到兩車間的工序占用設備的時長差△T相對較小。

定義 3(設備均衡組) 通過車間均衡處理產生的車間分組稱為設備均衡組。

根據定義 2與可調度工序集的特征，通過對可調度工序集均衡處理可使產品在兩車間分布式加工充分并行，達到減少產品加工時間的目的，于是提出了兩車間可調度工序分組均衡處理的綜合調度算法，并建立相關的數學模型。

由于綜合調度是將產品加工工序和裝配工序統一為加工工序，加工設備和裝配設備統一為設備一同處理的調度方式，于是一個有n道工序的產品在m臺設備上進行分批綜合調度的約束條件如下：

(1)一臺設備在某一時刻只能加工一道工序，且一旦加工某道工序，必須滿足該工序加工完畢后，這臺設備才可以加工其他工序。

(2)某道工序在某一時刻只可以占用兩車間中相同設備中的一臺設備進行加工。

(3)可調度工序集加工完畢才可以開始下批可調度工序加工。

(4)允許工序之間等待，允許設備在工序到達之前閑置。

由于本文討論的綜合調度算法是在滿足上述約束條件下，按動態形成的可調度工序集分批調度，每批可調度工序加工開始的時間為上一批可調度工序加工完畢的時間，每批可調度工序加工完畢的時間為按工序設備分組后在兩車間中設備完工的最大時間值，于是本問題的數學描述為：

其中，w代表a、b兩車間，可調度工序批次為j=1,2,…,k；Ewj是每批的完成時間；Ewk為產品完成時間；Sj為每批可調度工序的開始加工時間，即上批可調度工序的完成時間，第1批可調度工序的開始加工時間為S1=0；Cwjf為第j批可調度工序在 w車間的設備 f上組合工序的加工時間和；tjf是設備均衡組工序加工時間差；式(5)表示第 j批可調度工序在w車間各設備完工的最大值。

3 分配方案設計與分析

為減少產品兩車間分布式綜合制造的時間，可從 2個方面考慮：(1)使產品在兩車間充分并行制造；(2)減少兩車間工序移動占用的時間。于是研究使產品工序在兩車間加工時間差相對小和工序在兩車間移動次數少的調度方案。

由于每批可調度工序可并行處理，為了減少兩車間加工時間差和工序移動次數，設計了可調度工序車間均衡策略和分組工序車間確定策略。

為方便按批調度工序，本文設置工序的屬性：qi|Mwi|ti|Fi|ei|Li，其中，qi為工序名；Mwi為工序 qi所在車間 w(a或b)的加工設備；ti為工序qi的加工時間；Fi為工序qi的緊前工序集；ei為集合 Fi中工序的個數；Li為工序 qi的緊后工序，i∈{1,2,…,n}。一般情況下，工序屬性只需前3項就可以實現產品加工的策略和方案，本文添加了緊前工序集、緊前工序個數和緊后工序，可根據緊前工序個數為空動態生成可調度工序。

3.1 可調度工序車間均衡策略

一般產品充分并行制造要求設備均衡加工，根據文獻[13]，設備均衡是指工序的加工設備不唯一時，選擇已加工時間和最小的設備作為該工序的加工設備。對于相同設備兩車間的產品制造，當要求兩車間所有相同設備對每批可調度工序都均衡加工時為車間均衡，因此，車間均衡是基于設備均衡提出的。由定義2，車間均衡與設備均衡區別如下：

(1)相同點：2個均衡都是針對設備的。

(2)不同點：設備均衡是針對一種設備且考慮以往工序加工情況，車間均衡是針對兩車間中所有的相同設備且只考慮同批可調度工序。

對每批可調度工序進行分配時，根據定義 1對設備進行分組，針對每個工序設備分組采用本文設計的車間均衡策略達到車間均衡。下面詳細說明車間均衡策略：

(1)當某工序設備分組中工序唯一，此時該設備無需考慮均衡；

(2)當某工序設備分組中僅有 2個可調度工序，將這2個工序分別分配到兩車間；

(3)當某工序設備分組中可調度工序數大于等于3時，有以下2種方案。

方案1 工序動態調整。

因為兩車間工序設備分組中設備m上工序均衡分組的重要指標是該工序設備分組中所有工序的加工時間和除以車間數2的值Pm，即在本文中為該工序設備分組中所有工序的加工時間和的一半，所以該均衡方案的目標是讓設備均衡組的2個組合工序加工時間值與Pm的差值盡量小。具體實現步驟如下：

步驟1 分組時考慮有序序列比無序序列針對工序調整的確定性強、對后續的工序調整的操作便捷以及時間復雜度小，于是先將工序設備分組中的工序按加工時間ti升序排序得序列H。

步驟2 按序將H中的值累加到D中，直到首次滿足均衡差△T=D–Pm≥0，記錄累加的工序序列為 G，將其他工序存放到升序序列B中。

步驟3 對均衡差△T進行處理。若△T=0或△T值小于H中的第1個工序的加工時間，已達到最優均衡，記錄設備均衡組；否則將△T與 G中的其他項進行比較，若△T等于G中某項，則將此項調整到序列B；若△T介于G中某相鄰兩項值之間，則將G中與△T接近的工序調整到B中。

方案1可調度工序車間均衡策略實現流程如圖1所示。

圖1 可調度工序車間均衡策略實現流程

方案2 根據冪集值確定。

具體方法是：首先確定設備m的最優均衡時間Pm；然后求該工序設備分組的冪集；其次計算每個冪集中的工序按屬性ti累加和D并計算均衡差△T=D–Pm，記錄△T最小的值；最后將△T值最小的冪集作為設備均衡組的一部分。

由于方案2在確定均衡差△T時比方案1考慮的情況多，因此方案2的結果可能優于方案1。但由于方案2的時間復雜度是指數級的，而方案 1的時間復雜度在二次多項式內，考慮調度方法的實用性和時效性，針對工序設備分組中可調度工序大于等于3的情況時，選擇方案1進行車間均衡。

3.2 工序車間確定策略

產品在兩車間分布式加工制造，存在工序在兩車間移動的情況，關于工序的移動提出以下相關概念：

定義 4(工序移動) 產品加工時，當工序 qi的緊前工序Fi與其不在同一車間，需將Fi的加工結果移動到qi所在的車間，稱其為工序移動。

定義5(位移數) 由工序移動產生的次數稱為位移數。

由于工序移動會增加產品完工的時間，當確定設備均衡組后，需確定設備均衡組 2個組合的加工車間，以減少位移數，于是根據工序相關性[14]提出分組工序車間確定策略。工序車間策略實現流程如圖2所示。

圖2 工序車間策略實現流程

工序車間確定策略描述如下：

設第j批可調度工序中設備f均衡組的2個組合為C1jf和C2jf，對C1jf和C2jf中工序的緊前工序所在車間進行統計。設組合C1jf中工序的緊前工序在a、b車間的總數分別為x、y，組合C2jf中工序的緊前工序在a、b車間的總數分別為p、q。若C1jf組合中的工序在a車間加工，C2jf組合中的工序在b車間加工，則產生的位移數為y+p，反之產生的位移數為x+q。于是工序車間確定策略是選擇產生位移數較少的將兩組合分配到兩車間的方式。即通過min{x + q, y + p}確定C1jf和C2jf所在車間；若x+q和y+p相等，即工序的緊前工序在兩車間分布數相同，則任意分配兩組合到兩車間。

4 可調度工序分組處理的實現與分析

4.1 算法實現

為了實現產品在兩車間分布式加工縮短產品完成時間和減少工序移動次數的目標，提出兩車間可調度工序分組均衡處理的綜合調度算法。該算法的主要思想是將原始葉節點工序和每次動態生成的葉節點工序分批處理，再將每批工序按設備加工時間盡量均衡地分為 2組，再將已分組的工序分配到其緊前工序個數較多的車間，對分組中的工序依次按序調度并在相應設備上確定盡早開始加工時間，最后修改當前已調度工序的緊后工序、緊前工序個數屬性。

對可調度工序按批進行分配調度時，既考慮了可調度工序車間均衡又考慮了減少位移數，因此該算法可使產品盡早完成且控制工序位移次數。算法的描述如下：

(1)輸入設備數和產品信息。

(2)根據工序 qi緊前工序個數屬性 ei為 0確定可調度工序。

(3)根據上一批可調度工序在a、b車間中各設備完成時間 Ea(j–1)、Eb(j–1)的最大值，即 Sj=(Ea(j–1)≤Eb(j–1)?Eb(j–1)：Ea(j–1))，確定每批可調度工序的開始加工時間Sj。

(4)可調度工序按設備進行分組。

(5)如果工序設備分組中工序數小于等于 2，將工序依次存入兩組合，此時組合可以為空集；若分組中工序數大于2，依據車間均衡策略進行均衡分組。

(6)判斷所有的工序設備分組是否達到車間均衡，不均衡則執行步驟(5)。

(7)判斷可調度工序的批次j是否為1，若為1則轉到步驟(9)。

(8)根據分組工序車間確定策略確定設備均衡組的加工車間，方法是對設備均衡組中的工序，根據已加工工序緊后工序屬性 Li，依次尋找緊前工序并確定緊前工序所在車間 w，同時累加對應車間工序數，并根據工序數的多少確定設備均衡組的加工車間。

(9)各設備均衡組中的工序按序調度，且開始加工時間為Sj。

(10)判斷此批可調度工序的緊后工序Li是否為空，為空轉到步驟(14)。

(11)計算此批工序在兩車間的結束時間Eaj和Ebj。方法是由問題描述中的式(3)有：Eaj=Sj–1+Taj或 Ebj=Sj–1+Tbj；根據式(6)有：Taj=max{Caj1,Caj2,…,Cajf,…,Cajm}或 Tbj=max{Cbj1,Cbj2,…,Cbjf,…,Cbjm}。

(12)修改此批可調度工序的緊后工序、緊前工序個數屬性，配合完成下批可調度工序的確定。方法是對當前批次可調度工序的緊后工序、緊前工序個數依次進行減1操作。

(13)刪除此批可調度工序，并將可調度工序的批次j值加1且轉到步驟(2)。

(14)輸出甘特圖。

(15)結束。

算法流程如圖3所示。

圖3 本文算法流程

4.2 算法復雜度分析

本文算法特點是動態生成可調度工序，并按批進行調度處理，所以，下面針對一批可調度工序調度處理的復雜度進行分析。

(1)可調度工序確定。根據工序qi緊前工序個數的屬性ei確定可調度工序，方法是當ei=0，qi為可調度工序。對n個工序需進行n次判斷處理，所以，可調度工序確定的復雜度為O(n)。

(2)工序設備分組及排序。根據工序qi加工設備屬性Mwi先進行工序設備分組，此時需判斷 n次；然后進行工序設備分組中工序排序，設工序設備分組中每個設備工序數平均為 n/m，于是每個設備上工序升序排序的操作次數是，所有工序設備分組并排序的操作次數是 n+，由于1 ≤ m＜＜n，因此工序設備分組并排序的復雜度為O(n2)。

(3)車間均衡。工序設備分組中工序要達到車間均衡，對每個工序設備分組工序加工時間求和，再除以 2求得平均時間Pm，需運算n/m次；工序設備分組中的工序依次累加到D且與Pm比較，最多需計算和判斷2n/m次；均衡差△T與G中工序，最多進行比較和調整次數為n/m+1。每個工序設備分組達到車間均衡的操作次數是4n/m+1。所有工序設備分組處理的次數為m(4n/m+1)，因此，車間均衡的復雜度為O(n)。

(4)分組工序車間確定。若工序qi已加工調度，可通過工序屬性Mwi確定其加工設備和加工車間。一批可調度工序得到的某設備均衡組中的工序數平均小于n/m，已加工工序最壞情況下為n。

確定設備均衡組中一個工序的緊前工序及緊前工序所在車間，需判斷已加工的n個工序緊后工序屬性n次，再確定其所在的車間最多n次，在累加車間工序數最多n次，所以確定設備均衡組中一個工序的緊前工序及緊前工序所在車間最多需處理3n次。

確定設備均衡組的組合中 n/m個工序的緊前工序及緊前工序所在車間最多需處理3n2/m次，于是一個設備均衡組分組工序車間確定的次數為6n2/m，所有設備均衡組確定車間的次數為6n2。因此，分組工序車間確定的復雜度為O(n2)。

(5)分組中工序的依序調度。設備均衡組的一個組中工序按序調度，由于平均每個組中工序個數小于n/m，組中工序需要比較的次數為，一個設備均衡組工序按序調度需比較次數為。因此所有分組中工序依序調度的比較次數為，即復雜度為O(n2)。

(6)工序緊后工序屬性的修改。當前批次可調度工序個數最多為n，每個工序查找其緊后工序且緊后工序的緊前工序個數屬性進行一次減 1操作。由于被查找的工序數最多為n，因此查找緊后工序的操作最多為n×n次，修改一批可調度工序的緊后工序緊前工序個數屬性的修改次數最多為n。因此，修改一批可調度工序的緊后工序緊前工序個數屬性的操作次數的數量級最多為O(n2)。

綜上所述，在最壞情況下，對一批可調度工序調度處理的時間復雜度為O(n2)。設產品分k批調度，因此，本文算法復雜度應為O(kn2)。

5 調度實例

若有單件復雜產品A，其加工工藝樹如圖4所示，框內符號分別表示：產品的工序名|加工設備名|工序加工時間。

圖4 產品A的加工工藝樹

由工序緊前工序個數屬性為0確定第1批可調度工序{A13, A14, A15, A22, A17, A18, A19, A9, A20, A21}；根據定義 1進行工序設備分組且分組中工序 qi按加工時間屬性 ti升序排序(Mf表示工序設備分組的工序組)：M1{A18, A21},M2{A9, A19, A20}, M3{A13, A22, A15, A17}, M4{A14}。

M1組中兩工序依次分配到兩車間；M2組工序數大于2，需進行車間均衡，A9與A19的加工時間和與平均值Pm相等，所以設備均衡組兩組合C112{A9, A19}、C212{A20}；M3組工序(A13, A22, A15)累加和D首次滿足大于Pm，即15>11時，兩組合C113{A13, A22, A15}、C213{A17}，均衡差值△T=D –Pm=4，△T與累加工序A13的加工時長相等，于是應調整到C213中，所以C213改為{A13, A17}，C113改為{A22, A15}，M4{A14}任意分配。

最后分到 a車間加工調度的工序{A18, A9, A19, A13,A17, A14}，b車間加工調度的工序{A21, A20, A22, A15}。由于此批可調度工序無緊前工序，因此開始加工時間S1為0，對此批可調度工序進行加工調度。根據已加工工序可知此批可調度工序在a、b車間加工結束時間均為11個單位。

修改此批可調度工序的緊后工序、緊前工序個數屬性，并刪除此批可調度工序。根據工序、緊前工序個數屬性 ei為0確定下一批可調度工序{A6, A16, A8, A10, A11, A12}，按工序設備分組，分組中工序按加工時長升序排序M2{A6,A16, A8}、M4{A10, A11, A12}。

M2組進行車間均衡，A6和A16的加工時間和D與Pm的關系9>8，△T =D–Pm=1，△T小于累加工序中第1項，所以不需調整，最后組合C122{A6, A16}、C222{A8}；M4組車間均衡后均衡組的兩組合C124{A10, A11}、C224{A12}。

由于此批工序有緊前工序，因此需根據分組工序車間確定策略進行車間選擇。首先統計兩組合C122、C222中緊前工序在兩車間的個數。C122、C222在a車間的個數分別為x=2、p=2，在 b車間的個數分別為 y=1、q=0；若組合 C122在a車間加工產生的位移數為1，C222在b車間加工產生的位移數為2，總位移數3；反之產生的總位移數2；選擇位移數少的方式進行分配，即選擇位移數為2的方式將C122分配到b車間，C222分配到a車間；同理C124分配到a車間，C224分配到b車間。

于是，此批分到 a車間加工的工序{A8, A10, A11}，b車間加工的工序{A6, A16, A12}。此批工序的開始加工時間為上一批工序加工結束時間即11，調度此批可調度工序。由于Ta2為13、Tb2為9，因此Ea2為24、Eb2為20。

按照上面的處理方法對每批工序分配和調度直到最后一個工序處理結束，產品在a、b車間調度的甘特圖如圖5和圖6所示。

圖5 車間a所得甘特圖

圖6 車間b所得甘特圖

若對每批可調度工序處理時不采用上文提出的策略，即先進行設備均衡處理，而是將工序降序排序后通過考慮設備均衡進行工序車間分配。

對第 1批可調度工序并按路徑長度降序排序為{A20,A21, A17, A18, A22, A19, A13, A15, A14, A9}。依次將工序按盡早加工要求分配到兩車間，分到 a車間的工序為{A14,A17, A15, A19, A9, A21}、b車間的工序為{A22, A13, A20,A18}。

依次類推得到該方法a和b車間產品調度甘特圖如圖7和圖8所示。

圖7 對比方法所得a車間甘特圖

圖8 對比方法所得b車間甘特圖

由圖5、圖6與圖7、圖8對比可以看出，采用本文的算法產品加工完成時間是38工時，產生的位移數為6，采用另外一種方案的加工時間是40工時，產生的位移數為8。

之所以第1個方案效果更好，是因為第2個方案既沒有真正地實現設備均衡，也沒有考慮工序移動次數。例如，第1批結束時間方案1是11，而方案2是13。

6 結束語

針對單件復雜產品在兩車間分布式制造問題，本文根據動態生成可并行處理的可調度工序和兩車間的資源屬性提出了 2個方案：設備均衡策略和工序確定車間策略，通過 2個策略的結合應用，實現了兩車間分布式制造調度的綜合調度。主要結論如下：

(1)按可調度工序分批處理，再按工序設備分組和車間均衡處理，算法簡單，效果較好，且算法復雜度不超過二次多項式。

(2)按分組工序車間確定策略確定工序所在車間，減少了工序在兩車間的移動次數，縮短了產品加工時間。

本文為解決具有相同資源的兩車間分布式調度提供了解決方案，對研究多車間分布式綜合調度問題有一定的借鑒作用。

[1]黃啟春, 陳 奇, 俞瑞釗.一種面向作業的快速調度算法[J].軟件學報, 1999, 10(10): 1073-1077.

[2]Brucker P, Sotskov Y N, Werner F.Complexity of Shop-scheduling Problems with Fixed Number of Jobs: A Survey[J].Mathematical Methods of Operations Research,2007, 65(3): 461-481.

[3]張維存, 鄭丕諤, 吳曉丹.蟻群遺傳算法求解能力約束的柔性作業車間調度問題[J].計算機集成制造系統, 2007, 13(2):127-131, 156.

[4]羌 磊, 肖田元.應用擴展貝葉斯進化算法求解混流裝配調度問題[J].計算機集成制造系統, 2007, 13(2): 111-116.

[5]李 原, 張開富, 王 挺, 等.基于遺傳算法的飛機裝配序列規劃優化方法[J].計算機集成制造系統, 2006, 12(2): 30-33.

[6]謝志強.工件間有約束的復雜產品工序調度研究[D].哈爾濱:哈爾濱理工大學, 2009.

[7]謝志強, 辛 宇, 楊 靜.基于設備空閑事件驅動的綜合調度算法[J].機械工程學報, 2011, 47(11): 139-147.

[8]謝志強, 李志敏, 郝淑珍, 等.工序間存在零等待約束的復雜產品調度研究[J].自動化學報, 2009, 35(7): 983-989.

[9]Xie Zhiqiang, Hao Shuzhen, Ye Guangjie, et al.A New Algorithm for Complex Product Flexible Scheduling with Constraint Between Jobs[J].Computers & Industrial Engineering, 2009, 57(3): 766-772.

[10]Xie Zhiqiang, Ye Guangjie, Zhang Dali, et al.New Nonstandard Job Shop Scheduling Algorithm[J].Chinese Journal of Mechanical Engineering, 2008, 21(4): 97-100.

[11]謝志強, 王 悅, 楊 靜.存在批量為2的批處理設備的綜合調度算法[J].北京工業大學學報, 2011, 37(10): 1470- 1476, 1481.

[12]謝志強, 楊 靜, 楊 光, 等.可動態生成具有優先級工序集的動態Job-Shop調度算法[J].計算機學報, 2008, 31(3): 502-508.

[13]謝志強, 邵 俠, 楊 靜.存在設備無關延遲約束的綜合柔性調度算法[J].機械工程學報, 2011, 47(4): 177-185.

[14]熊禾根, 李建軍, 孔建益, 等.考慮工序相關性的動態Job Shop調度問題啟發式算法[J].機械工程學報, 2006, 42(8): 51-55.