邰麗君 胡如夫 趙 韓 陳曹維

1.寧波工程學(xué)院，寧波，315211 2.合肥工業(yè)大學(xué)，合肥，230009

0 引言

隨著工業(yè)化水平的提高和信息技術(shù)的高速發(fā)展，制造業(yè)正從靜態(tài)、組織內(nèi)的供求關(guān)系向動(dòng)態(tài)、跨組織方向發(fā)展。李伯虎等［1］依據(jù)網(wǎng)絡(luò)化制造技術(shù)的需求和發(fā)展趨勢(shì)，提出了云制造模式。云制造以云計(jì)算為基礎(chǔ)，融合了現(xiàn)有的信息化制造技術(shù)、物聯(lián)網(wǎng)技術(shù)、面向服務(wù)技術(shù)、智能科學(xué)技術(shù)，可隨時(shí)為用戶提供符合客戶需求、安全可靠的制造全生命周期服務(wù)。

國內(nèi)外學(xué)者對(duì)云制造進(jìn)行了大量的研究［2－9］，但是這些研究只是局限在概念、模型、平臺(tái)框架結(jié)構(gòu)及相關(guān)關(guān)鍵技術(shù)，對(duì)云制造服務(wù)的具體實(shí)現(xiàn)過程卻鮮有研究。云制造服務(wù)過程中，如何通過動(dòng)態(tài)調(diào)度對(duì)已虛擬化的制造資源和制造能力進(jìn)行統(tǒng)一的智能化經(jīng)營和管理，是云制造服務(wù)能否實(shí)現(xiàn)的關(guān)鍵。目前，對(duì)資源調(diào)度的研究大量集中于車間內(nèi)部的生產(chǎn)調(diào)度和制造系統(tǒng)服務(wù)組合優(yōu)化，而這些研究方法無法應(yīng)用于云制造的特殊環(huán)境。云制造環(huán)境下，由于制造服務(wù)周期長(zhǎng)、涉及的加工企業(yè)眾多，因此在執(zhí)行過程中極易受到負(fù)載、故障、環(huán)境變化等不確定因素的干擾，這就要求資源調(diào)度過程適應(yīng)動(dòng)態(tài)的制造環(huán)境，具有動(dòng)態(tài)再調(diào)度功能。同時(shí)由于各個(gè)制造服務(wù)來源于不同的企業(yè)，勢(shì)必產(chǎn)生相應(yīng)的運(yùn)輸成本。因此，云制造資源調(diào)度是一個(gè)綜合考慮時(shí)間、成本、質(zhì)量和能力的動(dòng)態(tài)多目標(biāo)調(diào)度過程。

本文根據(jù)云制造服務(wù)的特點(diǎn)，建立云制造環(huán)境下制造服務(wù)資源多目標(biāo)動(dòng)態(tài)調(diào)度模型，運(yùn)用遺傳蟻群優(yōu)化算法來解決制造服務(wù)資源多目標(biāo)調(diào)度問題。

1 問題分析

假定一個(gè)云制造服務(wù)平臺(tái)上有多個(gè)制造服務(wù)申請(qǐng)，每個(gè)制造服務(wù)申請(qǐng)經(jīng)過任務(wù)分解后，分為若干個(gè)制造服務(wù)子任務(wù)。每個(gè)制造服務(wù)子任務(wù)包含一道或多道工序（這些工序是預(yù)先確定的）。每道工序有多個(gè)候選制造資源，可隨機(jī)在這些候選制造資源上進(jìn)行制造服務(wù)。工序的完成時(shí)間是隨著制造資源的性能不同而變化的。由于制造資源可能會(huì)處于不同的企業(yè)，因此不同工序節(jié)點(diǎn)處會(huì)產(chǎn)生一定的物流成本。制造任務(wù)在執(zhí)行過程中常存在機(jī)器故障、交貨期提前或延后等突發(fā)擾動(dòng)問題。調(diào)度的目標(biāo)是為每道工序選擇最合適的制造資源，確定制造任務(wù)中每個(gè)制造資源上的最佳加工順序及加工時(shí)間，使制造服務(wù)的服務(wù)周期和各項(xiàng)性能指標(biāo)達(dá)到最優(yōu)。為使研究更具可操作性，本文設(shè)定以下假設(shè)條件：①主要研究云制造企業(yè)間的協(xié)作調(diào)度，不考慮企業(yè)內(nèi)部的調(diào)度流程；②同一個(gè)制造服務(wù)任務(wù)只能通過一個(gè)制造服務(wù)資源完成；③一個(gè)制造服務(wù)資源至少能完成一個(gè)制造服務(wù)任務(wù)；④不同制造資源之間的運(yùn)輸成本和運(yùn)輸時(shí)間、距離成正比，不考慮運(yùn)輸物料材料問題；⑤每個(gè)子任務(wù)的執(zhí)行時(shí)間根據(jù)任務(wù)間的關(guān)系和執(zhí)行順序進(jìn)行。

2 多目標(biāo)優(yōu)化模型

設(shè)云制造服務(wù)平臺(tái)有多個(gè)制造服務(wù)任務(wù)，每個(gè)服務(wù)任務(wù)可分為N個(gè)子任務(wù)，子任務(wù)F I有M I個(gè)制造服務(wù)資源可以完成，I＝1，2，…，N。FIj為子任務(wù)F I的第j道工序。T為任務(wù)交貨時(shí)間，L為制造服務(wù)能力，Q為制造服務(wù)質(zhì)量，C為制造服務(wù)成本。

2.1 目標(biāo)函數(shù)

2.1.1 總制造服務(wù)時(shí)間

總制造服務(wù)時(shí)間為用戶從云平臺(tái)客戶端提交服務(wù)請(qǐng)求到獲得資源服務(wù)所花費(fèi)的時(shí)間，主要包括制造時(shí)間和物流時(shí)間?？傊圃旆?wù)時(shí)間的目標(biāo)函數(shù)為

式中，x ij為決策變量；tij為制造任務(wù)i的第j道工序所需制造時(shí)間；t′ij為制造任務(wù)i的第j道工序的物流時(shí)間；αi為制造任務(wù)i的工件數(shù)量；δT1、δT2為權(quán)重系數(shù)；H i為任務(wù)i的工序總量；n為制造任務(wù)數(shù)量；W為閾值。

當(dāng)工件運(yùn)輸?shù)街圃煸O(shè)備資源所需的時(shí)間超出閾值時(shí)，工件制造時(shí)間忽略不計(jì)。

2.1.2 制造服務(wù)能力

制造服務(wù)能力體現(xiàn)了制造服務(wù)提供企業(yè)完成制造任務(wù)的能力水平，包括工藝能力、故障率、廢品率、尺寸精度、協(xié)作能力、客戶信譽(yù)水平。根據(jù)平臺(tái)提供的制造能力評(píng)判標(biāo)準(zhǔn)，對(duì)企業(yè)制造服務(wù)能力的各個(gè)指標(biāo)進(jìn)行評(píng)價(jià)，并構(gòu)建目標(biāo)函數(shù)：

2.1.3 制造服務(wù)質(zhì)量

制造服務(wù)質(zhì)量體現(xiàn)了用戶對(duì)制造服務(wù)的滿意程度，其目標(biāo)函數(shù)為

式中，sij為用戶對(duì)任務(wù)i的第j道工序加工的滿意程度；μi為滿意程度修正系數(shù)。

2.1.4 制造服務(wù)成本

制造服務(wù)成本除了資源設(shè)備、夾具、刀具等不同組合產(chǎn)生的生產(chǎn)成本外，還包括工件在不同制造資源之間運(yùn)輸?shù)奈锪鞒杀荆虼?，制造服?wù)成本的目標(biāo)函數(shù)可以表示為

式中，cij為任務(wù)i的第j道工序的工件所需制造成本；c′ij為任務(wù)i的第j道工序的工件運(yùn)輸?shù)街圃煸O(shè)備所需的運(yùn)輸成本；δc1、δc2為權(quán)重系數(shù)。

2.2 約束條件

（1）制造服務(wù)任務(wù)交貨期約束。制造服務(wù)任務(wù)交貨期約束為每個(gè)制造服務(wù)任務(wù)的實(shí)際交貨期不能超過最遲交貨期，即

式中，Timax為制造服務(wù)任務(wù)i的允許最遲交貨時(shí)間。

（2）制造服務(wù)任務(wù)成本約束。制造服務(wù)任務(wù)成本約束為每個(gè)制造服務(wù)任務(wù)的總服務(wù)成本不能超過最高服務(wù)成本，即

式中，Cimax為制造服務(wù)任務(wù)i所能支付的最高服務(wù)成本。

（3）制造服務(wù)任務(wù)區(qū)域約束。制造服務(wù)任務(wù)區(qū)域約束為每個(gè)制造服務(wù)資源的區(qū)域距離不能超過所要求的最大距離，即

式中，Yi為制造服務(wù)任務(wù)i的服務(wù)資源的區(qū)域距離；Yimax為制造服務(wù)任務(wù)i所要求的服務(wù)資源區(qū)域的最大距離。

（4）制造服務(wù)任務(wù)時(shí)序約束。制造服務(wù)任務(wù)時(shí)序約束為有時(shí)序約束關(guān)系的前一任務(wù)的結(jié)束時(shí)間不能超過下一任務(wù)的開始時(shí)間，即

式中，de，i為任務(wù)i的結(jié)束時(shí)間；db，i＋1為任務(wù)i＋1的開始時(shí)間。

（5）制造服務(wù)任務(wù)服務(wù)能力約束。制造服務(wù)任務(wù)服務(wù)能力約束為制造資源的服務(wù)能力水平必須滿足制造任務(wù)的能力需求，即

式中，L′ij、δij分別為制造服務(wù)任務(wù)i的第j道工序的制造服務(wù)能力及其權(quán)重；L′i為制造服務(wù)任務(wù)i需要實(shí)現(xiàn)的制造能力。

（6）制造服務(wù)任務(wù)資源約束。制造服務(wù)任務(wù)資源約束為同一時(shí)間同一服務(wù)資源只能完成一個(gè)服務(wù)任務(wù)，即

（7）制造服務(wù)任務(wù)可信任性約束。制造服務(wù)任務(wù)可信任性約束為每個(gè)制造服務(wù)資源的信譽(yù)度不能小于所要求的最小信譽(yù)度，即

式中，U i為制造服務(wù)任務(wù)i服務(wù)資源的信譽(yù)度；U imin為制造服務(wù)任務(wù)i所要求的服務(wù)資源最小信譽(yù)度。

2.3 基于Pareto最優(yōu)集的多目標(biāo)調(diào)度

對(duì)于多目標(biāo)問題，最優(yōu)解不是一個(gè)確定的解而是一個(gè)最優(yōu)解的集合，稱這種解為Pareto最優(yōu)解，該解的集合通常被稱為 Pareto最優(yōu)集［10－11］。Pareto有效解的定義如下［10］：如果對(duì)一個(gè)可行解向量x＝ （x1，x2，…，x v）∈S（S為可行解空間，v為解向量的維數(shù)），當(dāng)且僅當(dāng)不存在x∈S，使得目標(biāo)函數(shù)F（X）＝ （f1（X），f2（X），…，f v（X））優(yōu)于F（x）＝ （f1（x），f2（x），…，f v（x）），那么稱x為多目標(biāo)問題的Pareto非劣解，稱集合P＊＝｛x｜x∈S｝為多目標(biāo)問題的Pareto最優(yōu)解集。

這里根據(jù)制造資源調(diào)度的總制造服務(wù)時(shí)間、制造服務(wù)能力、制造服務(wù)質(zhì)量和制造服務(wù)成本的目標(biāo)函數(shù)組成最終的多目標(biāo)優(yōu)化目標(biāo)函數(shù)F（X）＝（f1（X），f2（X），f3（X），f4（X））。

3 多目標(biāo)優(yōu)化動(dòng)態(tài)調(diào)度算法

3.1 動(dòng)態(tài)調(diào)度策略

云制造環(huán)境下，由于涉及的服務(wù)企業(yè)眾多、制造服務(wù)執(zhí)行周期較長(zhǎng)、制造現(xiàn)場(chǎng)復(fù)雜多變，因此在實(shí)際制造服務(wù)過程中勢(shì)必會(huì)產(chǎn)生大量的擾動(dòng)事件。單純的靜態(tài)調(diào)度無法處理各種實(shí)時(shí)變化，無法實(shí)現(xiàn)自適應(yīng)調(diào)度過程。本文提出動(dòng)態(tài)調(diào)度技術(shù)，在發(fā)生擾動(dòng)事件時(shí)能及時(shí)作出反應(yīng)，通過調(diào)整調(diào)度方案來保證云制造生產(chǎn)任務(wù)按時(shí)完成。

3.1.1 調(diào)度生命周期的劃分

將整個(gè)生產(chǎn)調(diào)度過程按照整個(gè)制造生命周期T劃分為若干個(gè)時(shí)域周期，以滾動(dòng)的時(shí)域周期優(yōu)化取代一成不變的全局優(yōu)化。在實(shí)際生產(chǎn)中，存在周期性調(diào)度和突發(fā)事件驅(qū)動(dòng)的適時(shí)調(diào)度兩種情況。因此，設(shè)計(jì)了周期性調(diào)度和適時(shí)調(diào)度兩種調(diào)度模式。周期性調(diào)度模式按照劃分的時(shí)域周期，在每個(gè)周期內(nèi)進(jìn)行調(diào)度，適用于生產(chǎn)調(diào)度具有規(guī)律性的情況，使生產(chǎn)具有一定的穩(wěn)定性，是實(shí)際生產(chǎn)中遇到最多的情況。適時(shí)調(diào)度模式是由故障、交貨期變化等突發(fā)事件驅(qū)動(dòng)的調(diào)度模式，發(fā)生突發(fā)事件時(shí)可及時(shí)進(jìn)行再調(diào)度，以適應(yīng)變化了的環(huán)境。

生命周期T的劃分：

式中，g為時(shí)域周期數(shù)，g∈N。

在時(shí)域周期tk內(nèi)，根據(jù)采樣情況，采用周期性調(diào)度模式，獲取該周期內(nèi)的最優(yōu)性能，若存在突發(fā)事件，則啟動(dòng)適時(shí)調(diào)度模式，再實(shí)行一次調(diào)度，獲得新的調(diào)度結(jié)果；若沒有突發(fā)事件，繼續(xù)執(zhí)行本周期內(nèi)的調(diào)度結(jié)果。

3.1.2 事件影響關(guān)聯(lián)樹分析技術(shù)

對(duì)工序、設(shè)備、時(shí)間段等事件的調(diào)整必然會(huì)導(dǎo)致與該工序及設(shè)備相關(guān)聯(lián)工序的調(diào)整，因此需分析調(diào)整的關(guān)聯(lián)影響范圍。

根據(jù)工件調(diào)度工序間的先后時(shí)序關(guān)系，建立工件調(diào)度工序關(guān)聯(lián)樹。關(guān)聯(lián)樹的根節(jié)點(diǎn)（如Pi，j）為發(fā)生動(dòng)態(tài)擾動(dòng)的工序，一階子節(jié)點(diǎn)（如Pi，j＋1）為該工序的后驅(qū)工序，二階子節(jié)點(diǎn)（如Pi，j＋2）為后驅(qū)工序的下一個(gè)后驅(qū)工序。逐點(diǎn)建立后續(xù)的多階受影響節(jié)點(diǎn)，直至調(diào)度方案中不存在后續(xù)工序?yàn)橹?。關(guān)聯(lián)樹組織結(jié)構(gòu)如圖1所示。

3.1.3 效能偏差比較

圖1 事件影響關(guān)聯(lián)樹組織結(jié)構(gòu)

實(shí)際調(diào)度過程中存在大量的突發(fā)事件。對(duì)每一個(gè)突發(fā)事件都進(jìn)行動(dòng)態(tài)再調(diào)度，不但會(huì)造成調(diào)度方案的頻繁改動(dòng)，而且會(huì)導(dǎo)致整個(gè)系統(tǒng)、人員的負(fù)擔(dān)大幅增加，反而降低生產(chǎn)效率。因此，本文提出一種效能偏差比較技術(shù)，對(duì)每一個(gè)擾動(dòng)事件，先比較再調(diào)度過程與原調(diào)度方案的效能偏差值，若偏差值大于設(shè)定的指標(biāo)閾值，則進(jìn)行動(dòng)態(tài)再調(diào)度；否則不啟動(dòng)再調(diào)度過程，而是通過車間內(nèi)部調(diào)整（如提高設(shè)備利用率、加班等方法）消除部分?jǐn)_動(dòng)事件，從而降低關(guān)聯(lián)調(diào)整的復(fù)雜度。

3.1.4 動(dòng)態(tài)調(diào)度流程圖

設(shè)計(jì)動(dòng)態(tài)調(diào)度流程如下：首先初始化工件、工藝、設(shè)備等信息，然后根據(jù)制造服務(wù)任務(wù)劃分制造過程的生命周期和時(shí)域周期。當(dāng)時(shí)域周期到來時(shí)執(zhí)行周期性調(diào)度。在執(zhí)行周期性調(diào)度過程中若發(fā)生突發(fā)擾動(dòng)事件，則進(jìn)入適時(shí)調(diào)度模式，根據(jù)獲得的突發(fā)事件的工序節(jié)點(diǎn)建立工序影響關(guān)聯(lián)樹。若關(guān)聯(lián)樹存在子節(jié)點(diǎn)，則根據(jù)關(guān)聯(lián)影響程度判斷是否需要調(diào)整零件工序，若需要調(diào)整，則根據(jù)需求調(diào)整生成新的調(diào)度方案，并將其與原調(diào)度方案進(jìn)行效能偏差的比較。若偏差值小于閾值，則放棄新的調(diào)度方案，繼續(xù)執(zhí)行周期性調(diào)度；反之，則執(zhí)行新的再調(diào)度過程。在執(zhí)行周期性調(diào)度過程中若沒有發(fā)生突發(fā)擾動(dòng)事件，則繼續(xù)執(zhí)行原調(diào)度方案，在再調(diào)度周期來臨時(shí)進(jìn)行周期性再調(diào)度，如圖2所示。

3.2 遺傳－蟻群調(diào)度算法

3.2.1 算法描述

將制造資源調(diào)度方案轉(zhuǎn)化為類似旅行商問題（travelling salesman problem，TSP）中的一條路徑，螞蟻可任意選擇節(jié)點(diǎn)，所選的節(jié)點(diǎn)路徑即為調(diào)度方案。螞蟻選擇路徑后，信息素留在節(jié)點(diǎn)上，而不是路上。

3.2.2 初始信息素濃度生成

在螞蟻的路徑節(jié)點(diǎn)集合中，節(jié)點(diǎn)i和j間的信息素濃度可表示為τij。初始信息素濃度τij（0）由遺傳算法求得，方法如下：

圖2 動(dòng)態(tài)調(diào)度流程圖

（1）編碼。本文設(shè)計(jì)了一種3層矩陣編碼方法，第1層編碼表示工件，第2層編碼表示工序，第3層編碼表示設(shè)備制造資源。如表1所示，第1個(gè)染色體表示工件3的第1道工序由設(shè)備制造資源4加工。依次類推，任意基因串的排列與調(diào)度方案一一對(duì)應(yīng)。

表1 染色體編碼

（2）交叉變異。交叉、變異操作是遺傳算法中增加種群多樣性、防止算法早熟和停滯的操作。本文針對(duì)的多目標(biāo)優(yōu)化問題需既考慮種群的多樣性又考慮其收斂性，因此采用全交叉方式，交叉概率為1。由于本文采用了3層編碼，所以需要對(duì)3部分分別進(jìn)行交叉操作，包括工件交叉、工序交叉和設(shè)備交叉，如圖3所示。

（3）求解步驟。① 初始化參數(shù)，子群個(gè)數(shù)為A，每個(gè)子群產(chǎn)生p個(gè)個(gè)體，最大進(jìn)化代數(shù)為O；②產(chǎn)生交叉概率Pc、變異概率Pm；③將目標(biāo)函數(shù)作為適應(yīng)度函數(shù)f（x），計(jì)算子群每個(gè)個(gè)體的適應(yīng)度函數(shù)值f（x ij）（i＝1，2，…，n；j＝1，2，…，H i）；④采用輪盤賭選擇法進(jìn)行選擇操作；⑤進(jìn)行交叉變異操作，按照交叉概率Pc從第i個(gè)子群中隨機(jī)對(duì)個(gè)體進(jìn)行交叉操作，按照變異概率Pm選擇個(gè)體進(jìn)行變異操作；⑥根據(jù)適應(yīng)度值排序選擇最優(yōu)染色體，若滿足收斂條件，結(jié)束返回最優(yōu)解，否則退回步驟④；⑦對(duì)選出的染色體解碼，轉(zhuǎn)化為初始信息化濃度。

圖3 交叉示意圖

3.2.3 啟發(fā)式信息

啟發(fā)式信息與路徑長(zhǎng)度無關(guān)。在云制造環(huán)境下，由于涉及的各個(gè)機(jī)器和工序處于不同的地點(diǎn)，這必然帶來額外的物流成本。所以在資源調(diào)度中，除了調(diào)度時(shí)間，成本也是重要的影響因素之一。因此本文將啟發(fā)式信息定義為

式中，Tij為任務(wù)執(zhí)行時(shí)間；Cij為任務(wù)執(zhí)行中產(chǎn)生的成本；α1、β1分別為Tij和Cij的權(quán)重系數(shù)。

3.2.4 狀態(tài)轉(zhuǎn)移規(guī)則

第K只螞蟻從節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的概率計(jì)算公式為

式中，α2、β2分別為信息素和啟發(fā)式信息的權(quán)重；ηij為節(jié)點(diǎn)i到j(luò)的啟發(fā)式信息；wi為第i個(gè)工序可選的資源節(jié)點(diǎn)的集合。

3.2.5 信息素更新規(guī)則

（1）更新策略。信息素是螞蟻進(jìn)行路徑選擇的唯一因素，隨著信息素的累積，螞蟻很容易傾向于信息素量大的節(jié)點(diǎn)，忽略實(shí)際路徑更優(yōu)、信息素量不大的節(jié)點(diǎn)，而陷入局部最優(yōu)。遺傳算法的交叉算子和變異算子可以產(chǎn)生多樣性的子代，從而擴(kuò)大解的搜索空間，因此將其引入蟻群算法的信息素更新策略中，以避免解陷入局部最優(yōu)。

（2）交叉。首先引入交叉算子對(duì)路徑節(jié)點(diǎn)進(jìn)行交叉操作，對(duì)任意路徑隨機(jī)產(chǎn)生2個(gè)交叉節(jié)點(diǎn)，交換2個(gè)節(jié)點(diǎn)的內(nèi)容，產(chǎn)生新的路徑即新的調(diào)度方案。若新方案更優(yōu)則替代原方案，否則不替換。

（3）變異。若某條路徑更優(yōu)而信息素量不夠，則將原最優(yōu)路徑上的信息素轉(zhuǎn)移到更優(yōu)路徑上，對(duì)新路徑上的信息素進(jìn)行變異操作，保留新的最優(yōu)路徑，調(diào)整公式如下：

式中，τi，j為原最優(yōu)路徑 上 的 信 息 素；τ′i，j為 交叉 后 更 優(yōu) 路徑上的信息素；τ′i，j＋1為變異后的新最優(yōu)路徑的信息素。

螞蟻完成一次循環(huán)后，信息素更新公式如下：

4 算法實(shí)現(xiàn)

算法實(shí)現(xiàn)步驟如下：

（1）初始化α1、β1、ρ、Pc、Pm等參數(shù)，置初始迭代次數(shù)為0。

（2）由遺傳算法產(chǎn)生初始信息素濃度τij（0）。

（3）將所有螞蟻置于出發(fā)點(diǎn)上，初始點(diǎn)位于當(dāng)前解集中。

（4）按照狀態(tài)轉(zhuǎn)移規(guī)則（式（8））計(jì)算每一只螞蟻的概率選擇目標(biāo)。

（5）按照式（1）計(jì)算每個(gè)調(diào)度路徑的目標(biāo)函數(shù)最優(yōu)值，若新路徑更優(yōu)，按照式（2）變異信息素。

（6）對(duì)各路徑進(jìn)行交叉操作，若產(chǎn)生更優(yōu)解則替換新的交叉點(diǎn)信息，否則轉(zhuǎn)步驟（7）。

（7）按照式（3）更新信息素。

（8）如果迭代次數(shù)小于最大迭代次數(shù)，則轉(zhuǎn)步驟（2），否則輸出目前最優(yōu)解。

5 實(shí)例應(yīng)用

以汽車零部件云制造平臺(tái)中某汽車零部件企業(yè)為例驗(yàn)證算法的有效性。該企業(yè)現(xiàn)有5個(gè)生產(chǎn)子任務(wù)需要制造服務(wù)，其相關(guān)信息見表2，在平臺(tái)中初步搜索到的與這些子任務(wù)對(duì)應(yīng)的工序及制造資源集合見表3。

表2 云制造制造服務(wù)子任務(wù)信息

表3 候選制造資源在資源調(diào)度中的部分?jǐn)?shù)據(jù)

根據(jù)本文提出的調(diào)度模型及算法，采用MATLAB編程進(jìn)行運(yùn)算，初始化參數(shù)如下：遺傳算法種群規(guī)模最大迭代次數(shù)為50，初始交叉概率Pc＝1，初始變異概率Pm＝0.05，螞蟻個(gè)數(shù)為20，最大迭代次數(shù)為50，α1＝1，β1＝7，ρ＝0.1。生產(chǎn)過程考慮以下擾動(dòng)因素：資源M1在時(shí)刻60h發(fā)生故障，在時(shí)刻90h得到修復(fù)，采用本文提出多目標(biāo)動(dòng)態(tài)遺傳蟻群算法對(duì)子任務(wù)O3進(jìn)行優(yōu)化調(diào)度計(jì)算，得到靜態(tài)調(diào)度甘特圖和動(dòng)態(tài)調(diào)度甘特圖（圖4、圖5）。

圖4 靜態(tài)調(diào)度甘特圖

由圖4、圖5可以看出，在不考慮機(jī)械故障擾動(dòng)的情況下，靜態(tài)調(diào)度的加工周期為221h；在考慮動(dòng)態(tài)擾動(dòng)的情況下，加工周期為251h。而動(dòng)態(tài)調(diào)度的加工周期為227h，可見動(dòng)態(tài)調(diào)度在擾動(dòng)出現(xiàn)時(shí)能大幅縮短加工周期。

為驗(yàn)證算法的性能，將本文所提出的算法（遺傳蟻群算法）與改進(jìn)蟻群算法［12］進(jìn)行對(duì)比分析，結(jié)果如表4及圖6所示。比較得出，遺傳蟻群算法由于充分利用了遺傳算法在全局搜索、快速收斂等方面的優(yōu)勢(shì)，因此在全局搜索能力及收斂速度上均比改進(jìn)蟻群算法有明顯的提高。

圖5 動(dòng)態(tài)調(diào)度甘特圖

表4 運(yùn)算結(jié)果對(duì)比

圖6 目標(biāo)函數(shù)變化曲線

從圖6可以看出，隨著迭代次數(shù)的增加，算法趨于穩(wěn)定，由于基本蟻群算法在進(jìn)化過程的最優(yōu)解可能會(huì)丟失、造成局部收斂，所以出現(xiàn)最優(yōu)解跳躍及收斂速度慢的情況；而改進(jìn)的遺傳蟻群算法由于采用了交叉和變異的方法，既繼承了最優(yōu)解，又增大了搜索空間避免進(jìn)入局部最優(yōu)，加快了收斂速度。

6 結(jié)論

（1）針對(duì)云制造環(huán)境下制造資源調(diào)度的特點(diǎn)，綜合考慮影響制造資源調(diào)度的主要影響因素（最小化總制造服務(wù)時(shí)間、最優(yōu)化制造服務(wù)能力、最優(yōu)化制造服務(wù)質(zhì)量、最小化制造服務(wù)成本），建立了一個(gè)制造服務(wù)多目標(biāo)調(diào)度模型。

（2）根據(jù)云制造環(huán)境下極易發(fā)生突發(fā)擾動(dòng)事件的特點(diǎn)，提出了一種動(dòng)態(tài)調(diào)度技術(shù)。該技術(shù)將整個(gè)制造服務(wù)全生命周期中的調(diào)度分為周期性調(diào)度和適時(shí)調(diào)度兩種模式。當(dāng)發(fā)生擾動(dòng)時(shí)，首先根據(jù)擾動(dòng)事件建立事件影響關(guān)聯(lián)樹，在此關(guān)聯(lián)樹的基礎(chǔ)上分析再調(diào)度的效能偏差，根據(jù)與閾值的比較結(jié)果決定下一步調(diào)度過程，通過調(diào)整調(diào)度方案，來保證云制造生產(chǎn)任務(wù)按時(shí)完成。

（3）提出了基于遺傳蟻群算法的制造資源調(diào)度算法。該算法利用遺傳算法的優(yōu)勢(shì)對(duì)蟻群算法進(jìn)行改進(jìn)，彌補(bǔ)了蟻群算法存在的不足，使整個(gè)調(diào)度過程能快速地收斂于最優(yōu)解。

（4）以某汽車零部件企業(yè)為例進(jìn)行仿真實(shí)驗(yàn)，仿真結(jié)果證明了該算法的有效性和可行性。

［1］李伯虎，張霖，王時(shí)龍，等.云制造——面向服務(wù)的網(wǎng)絡(luò)化制造新模式［J］.計(jì)算機(jī)集成制造系統(tǒng)，2010，16（1）：1－7.

Li Bohu，Zhang Lin，Wang Shilong，et al.Cloud Manufacturing：a New Service－oriented Manufacturing Model［J］.Computer Integrated Manufacturing Systems，2010，16（1）：1－7.

［2］王正成，黃洋.面向服務(wù)鏈構(gòu)建的云制造資源集成共享技術(shù)研究［J］.中國機(jī)械工程，2012，23（11）：1323－1331.

Wang Zhengcheng，Huang Yang.Research on Integration Sharing Technology of Cloud Manufacturing Resource Oriented to Service Chain Construction［J］.China Mechanical Engineering，2012，23（11）：1323－1331.

［3］陶飛，張霖，郭華，等.云制造特征及云服務(wù)組合關(guān)鍵問題研究［J］.計(jì)算機(jī)集成制造系統(tǒng)，2011，17（3）：477－486.

Tao Fei，Zhang Lin，Guo Hua，et al.Typical Characteristics of Cloud Manufacturing and Several Key Issues of Cloud Service Composition［J］.Computer Integrated Manufacturing Systems，2011，17（3）：477－486.

［4］程功勛，劉麗蘭，林智奇，等.面向用戶偏好的智能云服務(wù)平臺(tái)研究［J］.中國機(jī)械工程，2012，23（11）：1315－1322.

Cheng Gongxun，Liu Lilan，Lin Zhiqi，et al.Intelligent Cloud Service Platform for Customer Preference［J］.China Mechanical Engineering，2012，23（11）：1315－1322.

［5］Zhang Qian，Qi Deyu.Service－oriented Collaborative Design Platform for Cloud Manufacturing［J］.Journal of South China University of Technology：Natural Science，2011，39（12）：75－81.

［6］尹超，黃必清，劉飛，等.中小企業(yè)云制造服務(wù)平臺(tái)共性關(guān)鍵技術(shù)體系［J］.計(jì)算機(jī)集成制造系統(tǒng)，2011，17（3）：495－503.

Yin Chao，Huang Biqing，Liu Fei，et al.Common Key Technology System of Cloud Manufacturing Service Platform for Small and Medium Enterprises［J］.Computer Integrated Manufacturing Systems，2011，17（3）：495－503.

［7］張霖，羅永亮，陶飛，等.制造云構(gòu)建關(guān)鍵技術(shù)研究［J］.計(jì) 算 機(jī) 集 成 制 造 系 統(tǒng)，2010，16（11）：2510－2520.

Zhang Lin，Luo Yongliang，Tao Fei，et al.Study on the Key Technologies for Construction of Manufacturing Cloud［J］.Computer Integrated Manufacturing Systems，2010，16（11）：2510－2520.

［8］賀東京，宋曉，王琪，等.基于云服務(wù)的復(fù)雜產(chǎn)品協(xié)同設(shè)計(jì)方法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2011，17（3）：533－539.

He Dongjing，Song Xiao，Wang Qi，et al.Method for Complex Product Collaborative Design Based on Cloud Service［J］.Computer Integrated Manufacturing Systems，2011，17（3）：533－539.

［9］尹勝，尹超，劉飛，等.云制造環(huán)境下外協(xié)加工資源集成服務(wù)模式及語義描述［J］.計(jì)算機(jī)集成制造系統(tǒng)，2011，17（3）：525－532.

Yin Sheng，Yin Chao，Liu Fei，et al.Outsourcing Resources Integration Service Mode and Semantic Description in Cloud Manufacturing Environment［J］.Computer Integrated Manufacturing Systems，2011，17（3）：525－532.

［10］Khalid K，Henri P，Nasser M.Using Multi－agent Architecture in FMS for Dynamic Scheduling［J］.Journal of Intelligent Manufacturing，1997，8（1）：41－47.

［11］Zitzler E.Evolution Algorithms for Multi－objective Optimization［D］.Zurich：Swiss Federal Institute of Technology，1999.

［12］胡凱林，李平.基于改進(jìn)蟻群算法的煉鐵原料混勻過程調(diào)度優(yōu)化［J］.上海交通大學(xué)學(xué)報(bào)（自然科學(xué)版），2011，45（8）：1105－1112.

Hu Kailin，Li Ping.The Optimized Scheduling for Iron－making Bulk Ore Blending Process Based on Improved Ant Colony Optimization［J］.Journal of Shanghai Jiao Tong University（Science），2011，45（8）：1105－1112.