一種面向定點輸出的分布式制造調度算法?

張祥甫

（海軍裝備部駐連云港地區軍代室 連云港 222061）

1 引言

目前，隨著全球一體化的發展以及區域經濟格局的形成，一件產品的生產已不再由傳統的局部設備生產，而是許多分布式生產單元進行協同制造。其中以局部區域加工能力為主傳的傳統制造業模式，已逐步被以物流運輸為中心的分布式制造所代替。從而導致了現代化的制造業向分布式產業轉型。因此，需要好的調度算法對分布式設備進行協調，從而對產品的生產進行全局優化。由于傳統的車間調度問題僅將調度算法局限在一個相對較小的車間內，其較少地考慮了產品的運輸及分布協同問題。因此，近十年來，學者們開始對分布式制造進行調度優化研究。

然而，分布式調度過程中的另一項關鍵因素在于對輸出點的選擇，即任務在何處加工完畢。分布式產品的最終完成位置是分布式調度需要考慮的現實問題，其具有較強的實際意義。例如，在分布調度中以特定的位置作為出口點，分布式生產的過程即圍繞著出口點進行任務分配。對此，需要在調度優化過程中考慮加工設備與出口點的距離，以及加工任務的結構特點與分布式設備選擇的關聯。對此，本文所研究的內容在于，在分布式調度過程中指定輸出設備，即固定輸出設備約束，并分別根據設備網絡的物理距離分布與任務結構分析，建立任務調度的優化方案。對此本文提出了RSM 算法，該方法不僅可以解決，分布設備的定點輸出約束，還建立了任務結構度量及設備分布狀態度量，從而為工序與設備的分配提供量化指標的同時，綜合表達了任務與設備分配的合理性。

2 相關工作

生產調度問題是實際工業生產中的一個重要問題，早在七十多年前就已受到學者們的廣泛關注和研究。根據建模，該問題可以表述為滿足一系列連續約束和離散約束條件下的目標優化問題［1］。目前，即使是較小規模的生產調度問題，也很難得到最優解隨著市場需求的變化和生產設備的改進，同一種類型的設備可以實現多種類型工序的加工，這使得工序不再與設備綁定，而是可以在某個設備集合中選擇設備進行加工。為了滿足這種調度要求，Bruker 等進一步提出了柔性作業調度（Flexible Job Shop Scheduling Problem，FJSP）［2］。作為傳統生產調度問題的一種擴展，柔性作業調度也是NP 困難。為了得到這兩類問題的最優解和近似最優解，研究者們提出了大量的啟發式算法，其中最著名的算法是由Watson等提出的禁忌搜索算法［3］，近年來人們在此基礎上提出了一系列的改進算法［4～6］。此外，研究者們還將遺傳算法［7～8］，蟻群算法［9］，粒子群算法［10］，Petri網模型［11］等算法成功應用到生產調度問題和柔性作為調度問題求解中。

近年來，學者們對多目標FJSP 進行了大量的研究。文獻［12］以最大完工成時間（Makespan）、加工成本和提前拖期懲罰值為優化目標，建立了相應的優化模型，針對該問題，提出了一種多目標粒子群算法，最后以實例對所建模型及算法進行了驗證；文獻［13］以Makespan、機器總負載及機器最大負載為目標，提出了一種基于Pareto 優化的離散自由搜索算法，并通過兩個實例驗證了算法的有效性；文獻［14］以Makespan 及設備最大負載為目標，將生產能力約束考慮到約束條件，對問題進行建模，提出了一種改進的遺傳算法，最后以標準算例對模型及算法進行了驗證；文獻［15］以Makespan、設備總負載和設備最大負載為目標，提出了一種基于粒子群算法和局部搜索算法的混合智能算法，并以實例對該算法進行了驗證；文獻［16］以Makespan、設備總負載和設備最大負載為目標，通過對各優化目標賦予相應的權重，將多個優化目標合并成單一優化目標，從而實現調度優化。

車間調度問題一直是制造領域中的一個研究熱點和難點，是實現生產運作與管理的核心，在很大程度上影響著企業的生存和發展。作業車間調度問題（Job Shop Scheduling Problem，JSP）是一種典型的車間調度問題，絕大多數JSP問題均具有NP難特性。元啟發式算法為JSP 問題的求解提供了一種有效可行的方案，這些算法雖無法保證達到全局最優解，但通常能在可行的時間內得到問題的近似解，其中包括模擬退火算法、遺傳算法、免疫算法以及粒子群算法等等。文獻［17］將一種并行模擬退火算法應用于求解JSP 問題，給出了有效的鄰域搜索規則。文獻［18］提出了一種基于遺傳算法和模擬退火算法的混合算法求解以最小化最大完工時間為目標的JSP 問題。文獻［19］針對零等待時間的作業車間調度問題，設計了一種混合型遺傳算法。文獻［8］將局部搜索算法和遺傳算法相結合用于求解機器調整時間與工序順序相關的作業車間調度問題。文獻［20］針對以總權重拖期時間為目標的作業車間調度問題，設計了一種免疫退火算法。文獻［21］研究了具備路徑柔性特征的作業車間調度問題，提出了一種混合型算法求解JSP 問題，利用基于人工免疫算法進行求解。

本文不同與以上算法，本文的創新之處在于利用了分布式設備的運輸特性，在考慮設備柔性加工能力的同時，考慮設備的運輸關系。對此，本文不僅需要考慮任務的結構特性以及設備的加工能力，還需要考慮設備間的運輸關系，此外，對于指定出口節點問題，還需要考慮終止加工的設備的約束。因此，本文所研究問題的復雜性相對于傳統算法較高，且具有較好的實用性。對此本文提出了RSM算法，其貢獻為：分別建立了任務結構度量及設備分布狀態度量，其中任務結構度量反映了后續工序對備選工序的影響，設備分布狀態度量反映了設備在設備網絡中的局部影響力。從而為工序與設備的分配提供量化指標的同時，綜合表達了任務與設備分配的合理性。

3 數學描述說明

分布式系統任務以分片的形式進行調度且各工序之間滿足以下約束，即DAG約束：

1）分布式任務具有唯一的終止工序（DAG 出口節點）；

2）分布式設備具有唯一的終止設備，即終止工序需要在終止設備表上完成加工；

3）某一工序僅在滿足其要求的設備中執行，且可滿足同一工序要求的設備不唯一，工序在各設備中的執行時間已知；

4）任一設備在同一時刻只能執行一個工序；

5）若vj為vi的緊后工序，則vj需要在vi執行完畢后等待vi向vj運輸。若vi與vj在同一設備中執行則運輸時間為0；

6）每一工序必須在其緊前工序均執行完畢，并收集到所有前序工序運輸來的原料時才可開始執行；

7）設備呈離散分布狀態，設備間的運輸時間受設備通路狀態影響；

8）任務具有指定的終止設備，即終止工序必須在終止設備上完成加工。

DAG調度模型的符號描述如下：

1）V=｛v1，v2，……｝表示任務的工序集合，其中|V|為工序的個數；

2）M=｛m1，m2，……｝表示設備的集合，其中|M|表示分布式環境中設備的個數；

3）U 表示運輸時間矩陣，ui，j表示設備mi到設備mj的運輸時間，若設備mi到設備mj間存在一條最短路｛mi，mi'，mi''，…，mj'，mj｝，則ui，j=ui，i'+ui'，i''+…+uj'，j；

4）r（v）表示v 緊前工序，若vi，vj為vk的緊前工序，即r（vk）=｛vi，vj｝，則vk必須在vi，vj加工完畢且收集到所有前序工序運輸來的原料時才可開始執行；

5）e（v）表示分配給工序v的設備；

6）加工矩陣A 表示，Ai，j表示任務vi在設備mj上加工所需要的時間，Ai表示工序v 在所有設備上的加工時間構成的向量。

圖1為某一任務的DAG結構，其中節點表示工序，節點v8為終止工序，有向邊表示工序的有序關系。表1 為工序在各設備中的執行時間，列舉了各工序在8 個設備m1-8上的執行時間。表2 為設備間運輸時間矩陣U。圖2 為各設備m1-8的分布狀態，其權值代表相鄰設備的運輸時間，m7為終止設備。

表1 圖1中工序在各設備上的執行時間

表2 設備間運輸時間矩陣U

圖1 任務結構模型

圖2 設備分布狀態

定點輸出的調度優化算法的目標是，最小化加工時間。為實現這一目標，需要建立合理的任務分配策略，對此，本文提出了定點輸出調度算法。

4 逆向分配調度算法

4.1 逆向分配適應策略

分布式制造調度問題是一類NP 問題，在有限時間內沒有最優的分配方案。對此，本文所設計的逆向分配適應策略。其調度原則即在進行設備分配時，以任務的后續設備占用狀態及設備分布狀態作為指導。其調度過程如下：

1）將終止工序分配到終止設備上，并將止工序的緊前工序作為備選工序，并由備選工序構成的集合即為備選工序集合。例如v8是終止工序，m7為終止設備，則v8需要在m7上加工，則任務v6和v7即為v8分配后的備選工序集B，即B=｛v6，v7｝；

2）若某一任務v 已分配至設備m，即e（v）=m，則v的緊前工序r（v）需要以e（v）與e（v）直接相鄰的設備作為備選設備。例如v8是終止工序，m7為終止設 備，即e（v8）=m7，則r（v8）=｛v6，v7｝。此 時，｛m7，m6，m3｝即為工序v6和v7的備選設備集E，即E（v6）=E（v7）=｛m7，m6，m3｝；

3）計算各備選工序v 與其備選設備m 的優先度Ov，m，對于優先度Ov，m最小的一對v 與m，將工序v分配到設備m上加工。Ov，m的表達式如下：

其中pi為工序v 基于任務結構的加工時間權重向量，qj為設備mj基于設備分布狀態的加工時間權重，Oi，j為特定v，m 的優先度。其中pi表達了工序的前續工序的加工時間向量。qj是設備的分布狀態的權重，表達了設備運輸環境中對任務后續調度的貢獻度，q 越大其環境貢獻度越高。因此，式（1）中，Oi，j越小表示將工序vi分配到設備mj的合理性越強。

4）重復上述過程，直到所有的工序分配完畢。上述過程的重點在于p與q模型的建立，對此，本文在后繼部分分別對p模型與q模型的構建過程進行了描述。

4.2 任務結構度量

任務結構度量的目標是根據工序在任務中的分布狀態及設備依賴度，對后續調度過程中各工序對設備的依賴度進行估計。若工序vj是工序vi的前續工序，按逆向分配適應策略，vj的設備分配需要等待vi分配設備結束。因此，若vj與vi的距離越遠，則vj的設備依賴性對vi設備分配決策的影響越小。對此，本文設計了如下的任務結構度量，以度量工序vi及其后續調度過程的設備依賴度。

其中foreword（vi）表示工序vi的前續工序集合，dis（vi，vj）表示工序vi與工序vi在任務結構圖中的最小距離，α為控制參數，Aj表示加工矩陣A 的第j 行，即工序vj在各設備上加工所需要的時間。例如當v8分配到m7設備時，工序v6和v7變為可調度工序。對于工序v6，其前續工序為v2，v4，v1，v3其與v6的距離分別為1，1，2，2。因此，在v6進行調度決策時，需要考慮v6，v2，v4，v1，v3的設備依賴性，根據式（2），當時，p6=1×A6+0.5×A2+0.5×A4+0.33×A1+0.33×A3=［17.8，20.6，16.9，19.3，20.1，21.9，20.6］。此時對于工序v7，根據式（2），p7=1×A7+0.5×A5+0.33×A3=［19.3，11.2，7.5，15.6，10.3，19.6，12.1］。

4.3 設備分布狀態度量

設備分布狀態度量是根據局部區域內設備對各工序的加工時間及各設備間的運輸時間，建立以特定設備為中心的局部區域加工能力度量。對于圖2 當v8分配到m7設備后，工序v6和v7變為可調度工序，此時v6與v7可選擇的設備為m6，m3，m7，其中m3的相鄰設備為｛m1，m5，m6，m7｝，m6的相鄰設備為｛m3，m4，m7｝，m7的相鄰設備為｛m3，m6｝，m3較于m6和m7具有較好的運輸環境，可為后續任務提供更為豐富的設備選擇方案，從而減小設備的競爭。對此本文利用數據場模型設計了如下的設備分布狀態度量，該模型可度量設備局部區域運輸環境中對任務的后續適應度，即為設備的權重。

其中uk，i為設備mk與mi之間的運輸時間，σ為距離控制參數，Rk和Ri分別為B 中工序在設備mk與設備mi上加工的等待時間。該模型表達了設備mi所處位置相對于工序加工的重要程度，式（3）中若mi與其他設備的運輸時間越短且與mi鄰近的設備越多時，qi的取值越大即設備的權重越高。

5 實驗分析

5.1 實驗環境介紹

為驗證CESM 算法的有效性，本文實驗部分利用Workflow Generator 生成實驗數據，以模擬分布式系統的DAG 任務結構。硬件：intel i3 處理器，4G內存。在對比算法方面，本文將調度問題中的HEFT［22］，CEFT［23］，DCP［24］算法作為對比算法。由于各個算法沒有考慮定點輸出的問題，因此，需要對以下算法進行定點輸出改進：

由于缺少對定點輸出調度問題的調度算法

1）HEFT算法，改進方法利用HEFT的rank進行逆向調度，即從終止節點向開始節點方向進行調度。在rank計算過程中，以相鄰設備的運輸時間均值作為運輸作為輸入，以rank作為工序選擇的優先性；

2）CEFT 算法，改進方法從終止節點開始逆向計算關鍵路徑長度，并以該關鍵路徑長度對任務結果進行逆向拆分；

3）DCP 算法，以工序的最晚開始時間，最早結束時間和作為工序選擇設備的優先性，并從任務的終止工序開始，進行逆向調度。

5.2 調度總時間分析

本實驗將數據分為Set1，Set2，Set3，Set4 共4個數據集，每個數據集包含100 個‘任務-設備對’。各數據集的生成參數如表3所示。

表3 任務-設備的生成參數表

表4 6種設備集

由于‘各任務-設備對’的總時間差異較大，因此，本文將4個利用如下的score模型對各算法的總時間進行歸一化度量：

其中timei（n）表示，算法i 在第n 個‘任務-設備對’上的加工時間，max｛time（n）｝表示各算法對第n 個‘任務-設備對’上加工時間的最大值，scorei表示算法i在100個‘任務-設備對’上的累計得分，若score越低說明算法的加工時間相對越小。例如利用RSM，HEFT，CEFT，DCP對于‘任務-設備對’的調度總時間分別為：20，25，15，10，則各算法對該‘任務-設備對’的得分分別為20/25，25/25，15/25，10/25，即0.8，1，0.6，0.2。圖3 為算法在Set1～5 上的scores 分布，其中RSM 的score 取值相對于其他3 個算法最低，說明RSM的總體調度時間最低。

圖3 各算法在Set1～5上的scores分布

5.3 設備依賴性分析

設備依賴性是算法對不同設備的選擇傾向。為分析各算法的設備依賴性，本實驗利用設備占用率作為度量方法，其中占用率（occupancy rate）的表達式如下：

其中o（mj）表示設備mj被占用的時間，|M|為設備總數。若某算法在某一類設備上的占用率越高，說明該算法對該設備依賴性越強。若算法的均衡負載性能越好，則設備的占用率相對越均勻。本次實驗設計了5 種設備Machine1～5，每種設備6 個共30 個設備，各設備加工工序的平均時間分別為5，10，15，20，25。以相鄰設備的平均運輸時間為10 設備網絡密度為0.25，隨機生成100個含有該30設備的網絡。以任務鏈接密度為0.3，工序個數為100 為參數，隨機生成100 個任務。利用RSM，HEFT，CEFT，DCP分別將100個任務在100個設備網絡上進行調度，并計算5 種設備的平均占用率。圖4 為4 種算法運行結果的設備占用率直方圖。從圖10的對比可知，HEFT，CEFT，DCP 算法在Machine1～3的占用率明顯高于其他設備，且從Machine1 到Machine5 的占用率呈下降趨勢，說明HEFT，PCH，HHDS算法均依賴于高效設備。RSM算法在5個設備上的利用率相對均勻，說明RSM 算法具有更好的設備均衡負載的性能，能充分利用低效設備，從而降低了總執行時間。

圖4 各算法的設備占用率

5.4 設備均衡性分析

本實驗是針對不同的設備集分析RSM 算法的執行效率。實驗過程為：1）生成數據D500：500 個任務，每個任務包含的工序數為150，工序的平均加工時間為10，任務鏈接密度為0.2；2）設備集中的設備分為3 種類型（高效型設備平均加工時間為10，一般型設備平均加工時間為20，低效型設備平均加工時間為30），設備網絡的密度為0.25，相鄰設備的平均運輸時間為10。本實驗所設計的6 個設備集如表7 所示，其中每個設備集包含9 個設備。例如設備集Set1 中包含：2 個高效設備，4 個一般設備和3 個低效設備；3）利用4 種算法對每組任務進行調度，并記錄每組數據中D500 的500 個任務在6個設備集中的執行時間分布。圖4 為4 種算法在6個設備集中的500 個任務執行時間分布散點圖，其中從MSet1到MSet6設備集的工作效率逐漸降低，4種算法的任務執行時間分布隨之逐漸變高。圖5中RSM 在MSet1 和MSet2 設備集中的表現明顯優于其他3 種算法，而RSM 在MSet5 和MSet6 中的表現與其他3 種算法接近，其原因在于：在MSet1 和MSet2 中3 種設備的分布較平均，此時考慮均衡負載的RSM 算法優勢明顯，而在MSet5和Set6中設備類型趨于一致，此時RSM 算法與其他3種算法的表現接近。

圖5 500個任務在6個設備集中執行時間散點圖

6 結語

本文利用分布式制造系統中設備的分布狀態及運輸關系，針對任務的定點輸出問題，設計了一種逆向分配調度算法RSM。該算法創新思想在于：根據任務結構及設備網絡的分布狀態，分別建立了任務結構度量p 及設備分布狀態度量q，其中任務結構度量反映了后續工序對備選工序的影響，設備分布狀態度量q 反映了設備在設備網絡中的局部影響力。所建立備選工序與備選設備的量化度量，可以為任務調度提供依據，簡化了調度過程，并考慮了任務與設備結構兩方面優化。

本文利用了實驗驗證的方式分析了算法的參數取值，其論證過程及原理說明可作為調度算法的一般性論證方法。通過實驗分析驗證了本文算法相對于其他面向運算代價優化的調度算法（如HEFT，CEFT，DCP 算）具有更高的有效性。本文分別從調度總時間分析、設備依賴性分析、設備集分析三個方面展開實驗，驗證了本文RSM 算法的有效性。在實驗過程中，由于RSM 從總體出發考慮了任務與設備結構兩方面優化，使得RSM 在處理定點輸出任務調度問題時的表現突出。

RSM的缺點在于，其調度過程依賴于量化的任務結構度量p 及設備分布狀態度量q，因此，其調度結果依賴于p 與q 的參數取值，然而對于不同的數據無法精確確定有效的參數取值，因此，本文的后續工作是對模型參數的取值研究。此外，RSM本質上屬于模糊調度，因此，RSM 具有模糊調度的一般缺點，即在任務的工序數量較大時RSM 的優勢較明顯，而工序數量較少時，RSM的性能波動較大。