面向云制造服務的制造資源多目標動態優化調度

邰麗君 胡如夫 趙 韓 陳曹維

1.寧波工程學院，寧波，315211 2.合肥工業大學，合肥，230009

0 引言

隨著工業化水平的提高和信息技術的高速發展，制造業正從靜態、組織內的供求關系向動態、跨組織方向發展。李伯虎等［1］依據網絡化制造技術的需求和發展趨勢，提出了云制造模式。云制造以云計算為基礎，融合了現有的信息化制造技術、物聯網技術、面向服務技術、智能科學技術，可隨時為用戶提供符合客戶需求、安全可靠的制造全生命周期服務。

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

本文根據云制造服務的特點，建立云制造環境下制造服務資源多目標動態調度模型，運用遺傳蟻群優化算法來解決制造服務資源多目標調度問題。

1 問題分析

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

2 多目標優化模型

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

2.1 目標函數

2.1.1 總制造服務時間

總制造服務時間為用戶從云平臺客戶端提交服務請求到獲得資源服務所花費的時間，主要包括制造時間和物流時間?？傊圃旆諘r間的目標函數為

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

當工件運輸到制造設備資源所需的時間超出閾值時，工件制造時間忽略不計。

2.1.2 制造服務能力

制造服務能力體現了制造服務提供企業完成制造任務的能力水平，包括工藝能力、故障率、廢品率、尺寸精度、協作能力、客戶信譽水平。根據平臺提供的制造能力評判標準，對企業制造服務能力的各個指標進行評價，并構建目標函數：

2.1.3 制造服務質量

制造服務質量體現了用戶對制造服務的滿意程度，其目標函數為

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

2.1.4 制造服務成本

制造服務成本除了資源設備、夾具、刀具等不同組合產生的生產成本外，還包括工件在不同制造資源之間運輸的物流成本，因此，制造服務成本的目標函數可以表示為

式中，cij為任務i的第j道工序的工件所需制造成本；c′ij為任務i的第j道工序的工件運輸到制造設備所需的運輸成本；δc1、δc2為權重系數。

2.2 約束條件

（1）制造服務任務交貨期約束。制造服務任務交貨期約束為每個制造服務任務的實際交貨期不能超過最遲交貨期，即

式中，Timax為制造服務任務i的允許最遲交貨時間。

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

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

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

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

（4）制造服務任務時序約束。制造服務任務時序約束為有時序約束關系的前一任務的結束時間不能超過下一任務的開始時間，即

式中，de，i為任務i的結束時間；db，i＋1為任務i＋1的開始時間。

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

式中，L′ij、δij分別為制造服務任務i的第j道工序的制造服務能力及其權重；L′i為制造服務任務i需要實現的制造能力。

（6）制造服務任務資源約束。制造服務任務資源約束為同一時間同一服務資源只能完成一個服務任務，即

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

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

2.3 基于Pareto最優集的多目標調度

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

這里根據制造資源調度的總制造服務時間、制造服務能力、制造服務質量和制造服務成本的目標函數組成最終的多目標優化目標函數F（X）＝（f1（X），f2（X），f3（X），f4（X））。

3 多目標優化動態調度算法

3.1 動態調度策略

云制造環境下，由于涉及的服務企業眾多、制造服務執行周期較長、制造現場復雜多變，因此在實際制造服務過程中勢必會產生大量的擾動事件。單純的靜態調度無法處理各種實時變化，無法實現自適應調度過程。本文提出動態調度技術，在發生擾動事件時能及時作出反應，通過調整調度方案來保證云制造生產任務按時完成。

3.1.1 調度生命周期的劃分

將整個生產調度過程按照整個制造生命周期T劃分為若干個時域周期，以滾動的時域周期優化取代一成不變的全局優化。在實際生產中，存在周期性調度和突發事件驅動的適時調度兩種情況。因此，設計了周期性調度和適時調度兩種調度模式。周期性調度模式按照劃分的時域周期，在每個周期內進行調度，適用于生產調度具有規律性的情況，使生產具有一定的穩定性，是實際生產中遇到最多的情況。適時調度模式是由故障、交貨期變化等突發事件驅動的調度模式，發生突發事件時可及時進行再調度，以適應變化了的環境。

生命周期T的劃分：

式中，g為時域周期數，g∈N。

在時域周期tk內，根據采樣情況，采用周期性調度模式，獲取該周期內的最優性能，若存在突發事件，則啟動適時調度模式，再實行一次調度，獲得新的調度結果；若沒有突發事件，繼續執行本周期內的調度結果。

3.1.2 事件影響關聯樹分析技術

對工序、設備、時間段等事件的調整必然會導致與該工序及設備相關聯工序的調整，因此需分析調整的關聯影響范圍。

根據工件調度工序間的先后時序關系，建立工件調度工序關聯樹。關聯樹的根節點（如Pi，j）為發生動態擾動的工序，一階子節點（如Pi，j＋1）為該工序的后驅工序，二階子節點（如Pi，j＋2）為后驅工序的下一個后驅工序。逐點建立后續的多階受影響節點，直至調度方案中不存在后續工序為止。關聯樹組織結構如圖1所示。

3.1.3 效能偏差比較

圖1 事件影響關聯樹組織結構

實際調度過程中存在大量的突發事件。對每一個突發事件都進行動態再調度，不但會造成調度方案的頻繁改動，而且會導致整個系統、人員的負擔大幅增加，反而降低生產效率。因此，本文提出一種效能偏差比較技術，對每一個擾動事件，先比較再調度過程與原調度方案的效能偏差值，若偏差值大于設定的指標閾值，則進行動態再調度；否則不啟動再調度過程，而是通過車間內部調整（如提高設備利用率、加班等方法）消除部分擾動事件，從而降低關聯調整的復雜度。

3.1.4 動態調度流程圖

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

3.2 遺傳－蟻群調度算法

3.2.1 算法描述

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

3.2.2 初始信息素濃度生成

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

圖2 動態調度流程圖

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

表1 染色體編碼

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

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

圖3 交叉示意圖

3.2.3 啟發式信息

啟發式信息與路徑長度無關。在云制造環境下，由于涉及的各個機器和工序處于不同的地點，這必然帶來額外的物流成本。所以在資源調度中，除了調度時間，成本也是重要的影響因素之一。因此本文將啟發式信息定義為

式中，Tij為任務執行時間；Cij為任務執行中產生的成本；α1、β1分別為Tij和Cij的權重系數。

3.2.4 狀態轉移規則

第K只螞蟻從節點i轉移到節點j的概率計算公式為

式中，α2、β2分別為信息素和啟發式信息的權重；ηij為節點i到j的啟發式信息；wi為第i個工序可選的資源節點的集合。

3.2.5 信息素更新規則

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

（2）交叉。首先引入交叉算子對路徑節點進行交叉操作，對任意路徑隨機產生2個交叉節點，交換2個節點的內容，產生新的路徑即新的調度方案。若新方案更優則替代原方案，否則不替換。

（3）變異。若某條路徑更優而信息素量不夠，則將原最優路徑上的信息素轉移到更優路徑上，對新路徑上的信息素進行變異操作，保留新的最優路徑，調整公式如下：

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

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

4 算法實現

算法實現步驟如下：

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

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

（3）將所有螞蟻置于出發點上，初始點位于當前解集中。

（4）按照狀態轉移規則（式（8））計算每一只螞蟻的概率選擇目標。

（5）按照式（1）計算每個調度路徑的目標函數最優值，若新路徑更優，按照式（2）變異信息素。

（6）對各路徑進行交叉操作，若產生更優解則替換新的交叉點信息，否則轉步驟（7）。

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

（8）如果迭代次數小于最大迭代次數，則轉步驟（2），否則輸出目前最優解。

5 實例應用

以汽車零部件云制造平臺中某汽車零部件企業為例驗證算法的有效性。該企業現有5個生產子任務需要制造服務，其相關信息見表2，在平臺中初步搜索到的與這些子任務對應的工序及制造資源集合見表3。

表2 云制造制造服務子任務信息

表3 候選制造資源在資源調度中的部分數據

根據本文提出的調度模型及算法，采用MATLAB編程進行運算，初始化參數如下：遺傳算法種群規模最大迭代次數為50，初始交叉概率Pc＝1，初始變異概率Pm＝0.05，螞蟻個數為20，最大迭代次數為50，α1＝1，β1＝7，ρ＝0.1。生產過程考慮以下擾動因素：資源M1在時刻60h發生故障，在時刻90h得到修復，采用本文提出多目標動態遺傳蟻群算法對子任務O3進行優化調度計算，得到靜態調度甘特圖和動態調度甘特圖（圖4、圖5）。

圖4 靜態調度甘特圖

由圖4、圖5可以看出，在不考慮機械故障擾動的情況下，靜態調度的加工周期為221h；在考慮動態擾動的情況下，加工周期為251h。而動態調度的加工周期為227h，可見動態調度在擾動出現時能大幅縮短加工周期。

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

圖5 動態調度甘特圖

表4 運算結果對比

圖6 目標函數變化曲線

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

6 結論

（1）針對云制造環境下制造資源調度的特點，綜合考慮影響制造資源調度的主要影響因素（最小化總制造服務時間、最優化制造服務能力、最優化制造服務質量、最小化制造服務成本），建立了一個制造服務多目標調度模型。

（2）根據云制造環境下極易發生突發擾動事件的特點，提出了一種動態調度技術。該技術將整個制造服務全生命周期中的調度分為周期性調度和適時調度兩種模式。當發生擾動時，首先根據擾動事件建立事件影響關聯樹，在此關聯樹的基礎上分析再調度的效能偏差，根據與閾值的比較結果決定下一步調度過程，通過調整調度方案，來保證云制造生產任務按時完成。

（3）提出了基于遺傳蟻群算法的制造資源調度算法。該算法利用遺傳算法的優勢對蟻群算法進行改進，彌補了蟻群算法存在的不足，使整個調度過程能快速地收斂于最優解。

（4）以某汽車零部件企業為例進行仿真實驗，仿真結果證明了該算法的有效性和可行性。

［1］李伯虎，張霖，王時龍，等.云制造——面向服務的網絡化制造新模式［J］.計算機集成制造系統，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］王正成，黃洋.面向服務鏈構建的云制造資源集成共享技術研究［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］陶飛，張霖，郭華，等.云制造特征及云服務組合關鍵問題研究［J］.計算機集成制造系統，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］程功勛，劉麗蘭，林智奇，等.面向用戶偏好的智能云服務平臺研究［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］尹超，黃必清，劉飛，等.中小企業云制造服務平臺共性關鍵技術體系［J］.計算機集成制造系統，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］張霖，羅永亮，陶飛，等.制造云構建關鍵技術研究［J］.計 算 機 集 成 制 造 系 統，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］賀東京，宋曉，王琪，等.基于云服務的復雜產品協同設計方法［J］.計算機集成制造系統，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］尹勝，尹超，劉飛，等.云制造環境下外協加工資源集成服務模式及語義描述［J］.計算機集成制造系統，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］.上海交通大學學報（自然科學版），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.