一種面向定點(diǎn)輸出的分布式制造調(diào)度算法?

張祥甫

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

1 引言

目前，隨著全球一體化的發(fā)展以及區(qū)域經(jīng)濟(jì)格局的形成，一件產(chǎn)品的生產(chǎn)已不再由傳統(tǒng)的局部設(shè)備生產(chǎn)，而是許多分布式生產(chǎn)單元進(jìn)行協(xié)同制造。其中以局部區(qū)域加工能力為主傳的傳統(tǒng)制造業(yè)模式，已逐步被以物流運(yùn)輸為中心的分布式制造所代替。從而導(dǎo)致了現(xiàn)代化的制造業(yè)向分布式產(chǎn)業(yè)轉(zhuǎn)型。因此，需要好的調(diào)度算法對(duì)分布式設(shè)備進(jìn)行協(xié)調(diào)，從而對(duì)產(chǎn)品的生產(chǎn)進(jìn)行全局優(yōu)化。由于傳統(tǒng)的車(chē)間調(diào)度問(wèn)題僅將調(diào)度算法局限在一個(gè)相對(duì)較小的車(chē)間內(nèi)，其較少地考慮了產(chǎn)品的運(yùn)輸及分布協(xié)同問(wèn)題。因此，近十年來(lái)，學(xué)者們開(kāi)始對(duì)分布式制造進(jìn)行調(diào)度優(yōu)化研究。

然而，分布式調(diào)度過(guò)程中的另一項(xiàng)關(guān)鍵因素在于對(duì)輸出點(diǎn)的選擇，即任務(wù)在何處加工完畢。分布式產(chǎn)品的最終完成位置是分布式調(diào)度需要考慮的現(xiàn)實(shí)問(wèn)題，其具有較強(qiáng)的實(shí)際意義。例如，在分布調(diào)度中以特定的位置作為出口點(diǎn)，分布式生產(chǎn)的過(guò)程即圍繞著出口點(diǎn)進(jìn)行任務(wù)分配。對(duì)此，需要在調(diào)度優(yōu)化過(guò)程中考慮加工設(shè)備與出口點(diǎn)的距離，以及加工任務(wù)的結(jié)構(gòu)特點(diǎn)與分布式設(shè)備選擇的關(guān)聯(lián)。對(duì)此，本文所研究的內(nèi)容在于，在分布式調(diào)度過(guò)程中指定輸出設(shè)備，即固定輸出設(shè)備約束，并分別根據(jù)設(shè)備網(wǎng)絡(luò)的物理距離分布與任務(wù)結(jié)構(gòu)分析，建立任務(wù)調(diào)度的優(yōu)化方案。對(duì)此本文提出了RSM 算法，該方法不僅可以解決，分布設(shè)備的定點(diǎn)輸出約束，還建立了任務(wù)結(jié)構(gòu)度量及設(shè)備分布狀態(tài)度量，從而為工序與設(shè)備的分配提供量化指標(biāo)的同時(shí)，綜合表達(dá)了任務(wù)與設(shè)備分配的合理性。

2 相關(guān)工作

生產(chǎn)調(diào)度問(wèn)題是實(shí)際工業(yè)生產(chǎn)中的一個(gè)重要問(wèn)題，早在七十多年前就已受到學(xué)者們的廣泛關(guān)注和研究。根據(jù)建模，該問(wèn)題可以表述為滿(mǎn)足一系列連續(xù)約束和離散約束條件下的目標(biāo)優(yōu)化問(wèn)題［1］。目前，即使是較小規(guī)模的生產(chǎn)調(diào)度問(wèn)題，也很難得到最優(yōu)解隨著市場(chǎng)需求的變化和生產(chǎn)設(shè)備的改進(jìn)，同一種類(lèi)型的設(shè)備可以實(shí)現(xiàn)多種類(lèi)型工序的加工，這使得工序不再與設(shè)備綁定，而是可以在某個(gè)設(shè)備集合中選擇設(shè)備進(jìn)行加工。為了滿(mǎn)足這種調(diào)度要求，Bruker 等進(jìn)一步提出了柔性作業(yè)調(diào)度（Flexible Job Shop Scheduling Problem，F(xiàn)JSP）［2］。作為傳統(tǒng)生產(chǎn)調(diào)度問(wèn)題的一種擴(kuò)展，柔性作業(yè)調(diào)度也是NP 困難。為了得到這兩類(lèi)問(wèn)題的最優(yōu)解和近似最優(yōu)解，研究者們提出了大量的啟發(fā)式算法，其中最著名的算法是由Watson等提出的禁忌搜索算法［3］，近年來(lái)人們?cè)诖嘶A(chǔ)上提出了一系列的改進(jìn)算法［4～6］。此外，研究者們還將遺傳算法［7～8］，蟻群算法［9］，粒子群算法［10］，Petri網(wǎng)模型［11］等算法成功應(yīng)用到生產(chǎn)調(diào)度問(wèn)題和柔性作為調(diào)度問(wèn)題求解中。

近年來(lái)，學(xué)者們對(duì)多目標(biāo)FJSP 進(jìn)行了大量的研究。文獻(xiàn)［12］以最大完工成時(shí)間（Makespan）、加工成本和提前拖期懲罰值為優(yōu)化目標(biāo)，建立了相應(yīng)的優(yōu)化模型，針對(duì)該問(wèn)題，提出了一種多目標(biāo)粒子群算法，最后以實(shí)例對(duì)所建模型及算法進(jìn)行了驗(yàn)證；文獻(xiàn)［13］以Makespan、機(jī)器總負(fù)載及機(jī)器最大負(fù)載為目標(biāo)，提出了一種基于Pareto 優(yōu)化的離散自由搜索算法，并通過(guò)兩個(gè)實(shí)例驗(yàn)證了算法的有效性；文獻(xiàn)［14］以Makespan 及設(shè)備最大負(fù)載為目標(biāo)，將生產(chǎn)能力約束考慮到約束條件，對(duì)問(wèn)題進(jìn)行建模，提出了一種改進(jìn)的遺傳算法，最后以標(biāo)準(zhǔn)算例對(duì)模型及算法進(jìn)行了驗(yàn)證；文獻(xiàn)［15］以Makespan、設(shè)備總負(fù)載和設(shè)備最大負(fù)載為目標(biāo)，提出了一種基于粒子群算法和局部搜索算法的混合智能算法，并以實(shí)例對(duì)該算法進(jìn)行了驗(yàn)證；文獻(xiàn)［16］以Makespan、設(shè)備總負(fù)載和設(shè)備最大負(fù)載為目標(biāo)，通過(guò)對(duì)各優(yōu)化目標(biāo)賦予相應(yīng)的權(quán)重，將多個(gè)優(yōu)化目標(biāo)合并成單一優(yōu)化目標(biāo)，從而實(shí)現(xiàn)調(diào)度優(yōu)化。

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

本文不同與以上算法，本文的創(chuàng)新之處在于利用了分布式設(shè)備的運(yùn)輸特性，在考慮設(shè)備柔性加工能力的同時(shí)，考慮設(shè)備的運(yùn)輸關(guān)系。對(duì)此，本文不僅需要考慮任務(wù)的結(jié)構(gòu)特性以及設(shè)備的加工能力，還需要考慮設(shè)備間的運(yùn)輸關(guān)系，此外，對(duì)于指定出口節(jié)點(diǎn)問(wèn)題，還需要考慮終止加工的設(shè)備的約束。因此，本文所研究問(wèn)題的復(fù)雜性相對(duì)于傳統(tǒng)算法較高，且具有較好的實(shí)用性。對(duì)此本文提出了RSM算法，其貢獻(xiàn)為：分別建立了任務(wù)結(jié)構(gòu)度量及設(shè)備分布狀態(tài)度量，其中任務(wù)結(jié)構(gòu)度量反映了后續(xù)工序?qū)溥x工序的影響，設(shè)備分布狀態(tài)度量反映了設(shè)備在設(shè)備網(wǎng)絡(luò)中的局部影響力。從而為工序與設(shè)備的分配提供量化指標(biāo)的同時(shí)，綜合表達(dá)了任務(wù)與設(shè)備分配的合理性。

3 數(shù)學(xué)描述說(shuō)明

分布式系統(tǒng)任務(wù)以分片的形式進(jìn)行調(diào)度且各工序之間滿(mǎn)足以下約束，即DAG約束：

1）分布式任務(wù)具有唯一的終止工序（DAG 出口節(jié)點(diǎn)）；

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

3）某一工序僅在滿(mǎn)足其要求的設(shè)備中執(zhí)行，且可滿(mǎn)足同一工序要求的設(shè)備不唯一，工序在各設(shè)備中的執(zhí)行時(shí)間已知；

4）任一設(shè)備在同一時(shí)刻只能執(zhí)行一個(gè)工序；

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

6）每一工序必須在其緊前工序均執(zhí)行完畢，并收集到所有前序工序運(yùn)輸來(lái)的原料時(shí)才可開(kāi)始執(zhí)行；

7）設(shè)備呈離散分布狀態(tài)，設(shè)備間的運(yùn)輸時(shí)間受設(shè)備通路狀態(tài)影響；

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

DAG調(diào)度模型的符號(hào)描述如下：

1）V=｛v1，v2，……｝表示任務(wù)的工序集合，其中|V|為工序的個(gè)數(shù)；

2）M=｛m1，m2，……｝表示設(shè)備的集合，其中|M|表示分布式環(huán)境中設(shè)備的個(gè)數(shù)；

3）U 表示運(yùn)輸時(shí)間矩陣，ui，j表示設(shè)備mi到設(shè)備mj的運(yùn)輸時(shí)間，若設(shè)備mi到設(shè)備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加工完畢且收集到所有前序工序運(yùn)輸來(lái)的原料時(shí)才可開(kāi)始執(zhí)行；

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

6）加工矩陣A 表示，Ai，j表示任務(wù)vi在設(shè)備mj上加工所需要的時(shí)間，Ai表示工序v 在所有設(shè)備上的加工時(shí)間構(gòu)成的向量。

圖1為某一任務(wù)的DAG結(jié)構(gòu)，其中節(jié)點(diǎn)表示工序，節(jié)點(diǎn)v8為終止工序，有向邊表示工序的有序關(guān)系。表1 為工序在各設(shè)備中的執(zhí)行時(shí)間，列舉了各工序在8 個(gè)設(shè)備m1-8上的執(zhí)行時(shí)間。表2 為設(shè)備間運(yùn)輸時(shí)間矩陣U。圖2 為各設(shè)備m1-8的分布狀態(tài)，其權(quán)值代表相鄰設(shè)備的運(yùn)輸時(shí)間，m7為終止設(shè)備。

表1 圖1中工序在各設(shè)備上的執(zhí)行時(shí)間

表2 設(shè)備間運(yùn)輸時(shí)間矩陣U

圖1 任務(wù)結(jié)構(gòu)模型

圖2 設(shè)備分布狀態(tài)

定點(diǎn)輸出的調(diào)度優(yōu)化算法的目標(biāo)是，最小化加工時(shí)間。為實(shí)現(xiàn)這一目標(biāo)，需要建立合理的任務(wù)分配策略，對(duì)此，本文提出了定點(diǎn)輸出調(diào)度算法。

4 逆向分配調(diào)度算法

4.1 逆向分配適應(yīng)策略

分布式制造調(diào)度問(wèn)題是一類(lèi)NP 問(wèn)題，在有限時(shí)間內(nèi)沒(méi)有最優(yōu)的分配方案。對(duì)此，本文所設(shè)計(jì)的逆向分配適應(yīng)策略。其調(diào)度原則即在進(jìn)行設(shè)備分配時(shí)，以任務(wù)的后續(xù)設(shè)備占用狀態(tài)及設(shè)備分布狀態(tài)作為指導(dǎo)。其調(diào)度過(guò)程如下：

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

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

3）計(jì)算各備選工序v 與其備選設(shè)備m 的優(yōu)先度Ov，m，對(duì)于優(yōu)先度Ov，m最小的一對(duì)v 與m，將工序v分配到設(shè)備m上加工。Ov，m的表達(dá)式如下：

其中pi為工序v 基于任務(wù)結(jié)構(gòu)的加工時(shí)間權(quán)重向量，qj為設(shè)備mj基于設(shè)備分布狀態(tài)的加工時(shí)間權(quán)重，Oi，j為特定v，m 的優(yōu)先度。其中pi表達(dá)了工序的前續(xù)工序的加工時(shí)間向量。qj是設(shè)備的分布狀態(tài)的權(quán)重，表達(dá)了設(shè)備運(yùn)輸環(huán)境中對(duì)任務(wù)后續(xù)調(diào)度的貢獻(xiàn)度，q 越大其環(huán)境貢獻(xiàn)度越高。因此，式（1）中，Oi，j越小表示將工序vi分配到設(shè)備mj的合理性越強(qiáng)。

4）重復(fù)上述過(guò)程，直到所有的工序分配完畢。上述過(guò)程的重點(diǎn)在于p與q模型的建立，對(duì)此，本文在后繼部分分別對(duì)p模型與q模型的構(gòu)建過(guò)程進(jìn)行了描述。

4.2 任務(wù)結(jié)構(gòu)度量

任務(wù)結(jié)構(gòu)度量的目標(biāo)是根據(jù)工序在任務(wù)中的分布狀態(tài)及設(shè)備依賴(lài)度，對(duì)后續(xù)調(diào)度過(guò)程中各工序?qū)υO(shè)備的依賴(lài)度進(jìn)行估計(jì)。若工序vj是工序vi的前續(xù)工序，按逆向分配適應(yīng)策略，vj的設(shè)備分配需要等待vi分配設(shè)備結(jié)束。因此，若vj與vi的距離越遠(yuǎn)，則vj的設(shè)備依賴(lài)性對(duì)vi設(shè)備分配決策的影響越小。對(duì)此，本文設(shè)計(jì)了如下的任務(wù)結(jié)構(gòu)度量，以度量工序vi及其后續(xù)調(diào)度過(guò)程的設(shè)備依賴(lài)度。

其中foreword（vi）表示工序vi的前續(xù)工序集合，dis（vi，vj）表示工序vi與工序vi在任務(wù)結(jié)構(gòu)圖中的最小距離，α為控制參數(shù)，Aj表示加工矩陣A 的第j 行，即工序vj在各設(shè)備上加工所需要的時(shí)間。例如當(dāng)v8分配到m7設(shè)備時(shí)，工序v6和v7變?yōu)榭烧{(diào)度工序。對(duì)于工序v6，其前續(xù)工序?yàn)関2，v4，v1，v3其與v6的距離分別為1，1，2，2。因此，在v6進(jìn)行調(diào)度決策時(shí)，需要考慮v6，v2，v4，v1，v3的設(shè)備依賴(lài)性，根據(jù)式（2），當(dāng)時(shí)，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］。此時(shí)對(duì)于工序v7，根據(jù)式（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 設(shè)備分布狀態(tài)度量

設(shè)備分布狀態(tài)度量是根據(jù)局部區(qū)域內(nèi)設(shè)備對(duì)各工序的加工時(shí)間及各設(shè)備間的運(yùn)輸時(shí)間，建立以特定設(shè)備為中心的局部區(qū)域加工能力度量。對(duì)于圖2 當(dāng)v8分配到m7設(shè)備后，工序v6和v7變?yōu)榭烧{(diào)度工序，此時(shí)v6與v7可選擇的設(shè)備為m6，m3，m7，其中m3的相鄰設(shè)備為｛m1，m5，m6，m7｝，m6的相鄰設(shè)備為｛m3，m4，m7｝，m7的相鄰設(shè)備為｛m3，m6｝，m3較于m6和m7具有較好的運(yùn)輸環(huán)境，可為后續(xù)任務(wù)提供更為豐富的設(shè)備選擇方案，從而減小設(shè)備的競(jìng)爭(zhēng)。對(duì)此本文利用數(shù)據(jù)場(chǎng)模型設(shè)計(jì)了如下的設(shè)備分布狀態(tài)度量，該模型可度量設(shè)備局部區(qū)域運(yùn)輸環(huán)境中對(duì)任務(wù)的后續(xù)適應(yīng)度，即為設(shè)備的權(quán)重。

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

5 實(shí)驗(yàn)分析

5.1 實(shí)驗(yàn)環(huán)境介紹

為驗(yàn)證CESM 算法的有效性，本文實(shí)驗(yàn)部分利用Workflow Generator 生成實(shí)驗(yàn)數(shù)據(jù)，以模擬分布式系統(tǒng)的DAG 任務(wù)結(jié)構(gòu)。硬件：intel i3 處理器，4G內(nèi)存。在對(duì)比算法方面，本文將調(diào)度問(wèn)題中的HEFT［22］，CEFT［23］，DCP［24］算法作為對(duì)比算法。由于各個(gè)算法沒(méi)有考慮定點(diǎn)輸出的問(wèn)題，因此，需要對(duì)以下算法進(jìn)行定點(diǎn)輸出改進(jìn)：

由于缺少對(duì)定點(diǎn)輸出調(diào)度問(wèn)題的調(diào)度算法

1）HEFT算法，改進(jìn)方法利用HEFT的rank進(jìn)行逆向調(diào)度，即從終止節(jié)點(diǎn)向開(kāi)始節(jié)點(diǎn)方向進(jìn)行調(diào)度。在rank計(jì)算過(guò)程中，以相鄰設(shè)備的運(yùn)輸時(shí)間均值作為運(yùn)輸作為輸入，以rank作為工序選擇的優(yōu)先性；

2）CEFT 算法，改進(jìn)方法從終止節(jié)點(diǎn)開(kāi)始逆向計(jì)算關(guān)鍵路徑長(zhǎng)度，并以該關(guān)鍵路徑長(zhǎng)度對(duì)任務(wù)結(jié)果進(jìn)行逆向拆分；

3）DCP 算法，以工序的最晚開(kāi)始時(shí)間，最早結(jié)束時(shí)間和作為工序選擇設(shè)備的優(yōu)先性，并從任務(wù)的終止工序開(kāi)始，進(jìn)行逆向調(diào)度。

5.2 調(diào)度總時(shí)間分析

本實(shí)驗(yàn)將數(shù)據(jù)分為Set1，Set2，Set3，Set4 共4個(gè)數(shù)據(jù)集，每個(gè)數(shù)據(jù)集包含100 個(gè)‘任務(wù)-設(shè)備對(duì)’。各數(shù)據(jù)集的生成參數(shù)如表3所示。

表3 任務(wù)-設(shè)備的生成參數(shù)表

表4 6種設(shè)備集

由于‘各任務(wù)-設(shè)備對(duì)’的總時(shí)間差異較大，因此，本文將4個(gè)利用如下的score模型對(duì)各算法的總時(shí)間進(jìn)行歸一化度量：

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

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

5.3 設(shè)備依賴(lài)性分析

設(shè)備依賴(lài)性是算法對(duì)不同設(shè)備的選擇傾向。為分析各算法的設(shè)備依賴(lài)性，本實(shí)驗(yàn)利用設(shè)備占用率作為度量方法，其中占用率（occupancy rate）的表達(dá)式如下：

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

圖4 各算法的設(shè)備占用率

5.4 設(shè)備均衡性分析

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

圖5 500個(gè)任務(wù)在6個(gè)設(shè)備集中執(zhí)行時(shí)間散點(diǎn)圖

6 結(jié)語(yǔ)

本文利用分布式制造系統(tǒng)中設(shè)備的分布狀態(tài)及運(yùn)輸關(guān)系，針對(duì)任務(wù)的定點(diǎn)輸出問(wèn)題，設(shè)計(jì)了一種逆向分配調(diào)度算法RSM。該算法創(chuàng)新思想在于：根據(jù)任務(wù)結(jié)構(gòu)及設(shè)備網(wǎng)絡(luò)的分布狀態(tài)，分別建立了任務(wù)結(jié)構(gòu)度量p 及設(shè)備分布狀態(tài)度量q，其中任務(wù)結(jié)構(gòu)度量反映了后續(xù)工序?qū)溥x工序的影響，設(shè)備分布狀態(tài)度量q 反映了設(shè)備在設(shè)備網(wǎng)絡(luò)中的局部影響力。所建立備選工序與備選設(shè)備的量化度量，可以為任務(wù)調(diào)度提供依據(jù)，簡(jiǎn)化了調(diào)度過(guò)程，并考慮了任務(wù)與設(shè)備結(jié)構(gòu)兩方面優(yōu)化。

本文利用了實(shí)驗(yàn)驗(yàn)證的方式分析了算法的參數(shù)取值，其論證過(guò)程及原理說(shuō)明可作為調(diào)度算法的一般性論證方法。通過(guò)實(shí)驗(yàn)分析驗(yàn)證了本文算法相對(duì)于其他面向運(yùn)算代價(jià)優(yōu)化的調(diào)度算法（如HEFT，CEFT，DCP 算）具有更高的有效性。本文分別從調(diào)度總時(shí)間分析、設(shè)備依賴(lài)性分析、設(shè)備集分析三個(gè)方面展開(kāi)實(shí)驗(yàn)，驗(yàn)證了本文RSM 算法的有效性。在實(shí)驗(yàn)過(guò)程中，由于RSM 從總體出發(fā)考慮了任務(wù)與設(shè)備結(jié)構(gòu)兩方面優(yōu)化，使得RSM 在處理定點(diǎn)輸出任務(wù)調(diào)度問(wèn)題時(shí)的表現(xiàn)突出。

RSM的缺點(diǎn)在于，其調(diào)度過(guò)程依賴(lài)于量化的任務(wù)結(jié)構(gòu)度量p 及設(shè)備分布狀態(tài)度量q，因此，其調(diào)度結(jié)果依賴(lài)于p 與q 的參數(shù)取值，然而對(duì)于不同的數(shù)據(jù)無(wú)法精確確定有效的參數(shù)取值，因此，本文的后續(xù)工作是對(duì)模型參數(shù)的取值研究。此外，RSM本質(zhì)上屬于模糊調(diào)度，因此，RSM 具有模糊調(diào)度的一般缺點(diǎn)，即在任務(wù)的工序數(shù)量較大時(shí)RSM 的優(yōu)勢(shì)較明顯，而工序數(shù)量較少時(shí)，RSM的性能波動(dòng)較大。