基于可持續性的云制造多任務調度

何 巍 賈國柱 孔繼利 宗恒山

1.北京航空航天大學經濟管理學院，北京，100191 2.北京郵電大學自動化學院，北京，100876 3.中國航天系統科學與工程研究院，北京，100048

0 引言

目前，全球制造業正經歷新一輪的轉型升級，現代企業的服務意識和環境意識逐步提高，制造業的服務化和可持續性引起了廣泛關注［1?3］。在制造業服務化方面，一種面向服務的網絡化制造新模式——云制造正在快速發展，用戶可以通過云制造平臺獲取按需使用的、安全可靠的、優質廉價的制造服務［2?3］；在制造業可持續性方面，綠色制造、可持續發展相繼被提出。在物聯網、云計算等新興技術的推動下，云制造快速發展作為一種先進的智能制造模式，在滿足客戶需求的同時，如何實現可持續發展成為一個越來越重要的問題。

影響制造系統可持續性的因素有很多，其中環境、經濟和社會因素是三大因素。在已有的可持續性相關研究中，既有學者單獨考慮其中某一種因素，也有學者將兩種因素組合起來考慮（如環境-經濟，環境-社會，經濟-社會）［1］。制造系統的可持續性可分為戰略、戰術和運作三個層面，其中戰略層面是目前學者們的關注重點，主要包括供應鏈設計、布局設計、清潔產品和生產方式設計、回收處理等內容［1?4］。然而，提升制造系統的可持續性必須考慮所有相關層面的問題，從而將戰略層的全局策略轉化為運作層的具體活動。在實際的生產過程中，在運作層中調度是影響生產效率、質量和成本的關鍵因素之一，不同的調度方案也會對資源消耗和排放產生不同影響。因此，在調度優化過程中考慮可持續性因素對從全局上提升可持續性起到了越來越重要的作用。

云制造環境下的調度問題可以分為單任務調度和多任務調度。其中，多任務調度指的是為了完成一系列制造任務，根據時間的推進來配置服務（或資源）的過程，與此同時考慮滿足時間、成本、服務質量和可用性等方面的約束。多任務調度是云制造系統的重要組成部分，對系統性能有著重要影響。目前，云制造環境下多任務調度問題引起了學者們廣泛關注。CHENG等［5］從云制造企業的角度研究了多任務虛擬資源整合與調度優化，他們把調度問題聚焦于在交貨期限的約束下，利用有限的資源盡可能獲得更高的利潤。LIU等［6］研究了云制造多任務服務組合問題，目的是最大限度地提高所有任務的總體QoS。趙金輝等［7］應用前景理論構建了一個考慮主體心理的云制造服務選擇雙層規劃模型，優化需求方對服務的心理滿意度。趙道致等［8］將主體的偏好序作為依據，基于前景理論設計了云制造資源供求雙方的穩定匹配機制。上述研究分別著眼于云制造任務調度過程中多任務協調問題、滿意度問題、能量消耗問題、資源利用率問題等［6，9?12］，但都沒有從完整的可持續性框架來研究如何調度云制造任務。

鑒于此，本文針對云制造多任務調度的實際，結合制造系統的可持續性框架，設計基于可持續性的云制造多任務調度模型，并改進遺傳算法對其進行求解。最后，通過實驗證明整個模型的可行性和有效性。

1 基于可持續性的云制造調度框架

基于可持續性的云制造多任務調度指的是為了完成一系列云制造任務，根據時間的推進來配置云服務（或資源）的過程，與此同時考慮滿足時間、成本服務質量等方面的約束，從而達到合理利用資源，提高環境、經濟和社會層面可持續性的目的。

假設云制造平臺上有M個注冊企業，表示為Ent(M)={E1,…,Ei,…,EM}，見圖1。每一個企業Ei(i=1,2,…,M)可以提供Li種不同類型的制造服務，并且用Si,l(l=1,2,…,Li)表示企業Ei的第l個服務。

圖1 云制造多任務調度示意圖Fig.1 Schematic diagram of CMfg multi-task scheduling

客戶將訂單發布到云制造服務平臺，平臺將這些訂單處理為不同的任務，這里考慮每一個訂單都被處理為一個云制造任務的情況。對于小型任務，平臺客戶與供應商之間能夠根據發布的信息自由選擇，而對于不能由一個供應商單獨完成的任務，就需要平臺方來統一調度。假設某一決策周期內（比如一天內）平臺上收到N個任務，用Task(N)={T1,…,Tj,…,TN}表示任務池。每個任務可能需要調用一種或者多種服務，將任務Tj分解為不同粒度的Kj子任務，STj,k（k=1,2,…，Kj）表示任務Tj的第k個子任務，每一個子任務需要一種不同類型的云制造服務。任務由一種特定的順序、并行、選擇和循環4種基本結構的組合而成。

一個任務被發布到云制造平臺以后，首先被分解為子任務，再為每一個子任務搜索可匹配的服務，見圖2。

圖2 云制造服務搜索與匹配示意圖Fig.2 Schematic diagram of CMfg service searching and matching

在云制造任務調度過程中，供應商根據工業產品的工作狀態和客戶的動態要求，承擔著相關的培訓、運行、維護、升級、回收再制造等相關服務，相比于客戶購買產品的方式，這將減少材料浪費和能源消耗?？蛻羲璧漠a品服務對維護產品功能和提供更好的解決方案非常重要。此外，與客戶的互動和他們在這個階段的反饋使云制造供應商能夠改善他們的產品和服務創新。另一方面，作為一種資源選擇或組合問題，資源服務調度對成功的產品服務交付是必不可少的。這些資源的異質性和動態性導致供應商產品服務配置的混亂和低效。此外，在資源方面，客戶對產品服務的要求更高，產品服務的數量和容量有限。在傳統的資源服務調度方法中，每個客戶的需求是由最優服務資源獨立滿足的。然而，在實際的服務運營中，在一個決策周期內多個客戶分別提出需求，產品服務的有限可用資源需要有效分配。此外，服務資源的調度結果應該基于客戶滿意度，并受產品服務成本和環境因素影響。因此，對于云制造平臺而言，如何分配和安排云制造運行階段的有限資源，必須從經濟、環境和社會可持續性的角度來確定，見圖3。

圖3 制造系統的可持續性框架Fig.3 Framework of sustainability in manufacturing system

2 基于可持續性的云制造調度模型

2.1 基本假設

（1）每一個任務需求都需要考慮可持續性；（2）從服務提供商的角度，任務需求之間相互獨立；

（3）每一個任務都需要分解為多個子任務，且每一個子任務都至少有一個可用的服務提供商；

（4）不同服務提供商完成同一個子任務需要的時間和成本不一樣；

（5）平臺上的供應商都是經過審核的，不會出現不端行為，即使有，也有相應的協議來彌補客戶的損失。

2.2 主要符號

2.3 目標函數

基于可持續性的云制造調度需要同時最大化客戶滿意度，最大化資源利用率，最小化資源服務成本，為了便于求解，本文在目標函數中采用不滿意度代替滿意度，用設備閑置率代替資源利用率，將目標函數統一為最小化問題。這三個目標分別體現了可持續性的不同層面，共同構成了云制造調度的可持續性目標函數。因此，調度模型的優化目標可以表示為

式中，z為綜合的可持續性；CSD為客戶的不滿意度；RUE表示資源閑置率；RSC為資源服務成本；ω1、ω2和 ω3為權重，滿足=1，ωj∈[0,1],?j。

2.3.1 客戶不滿意度

客戶不滿意度CSD源自于客戶需求和服務之間的匹配程度，反映了服務提供商與客戶之間的相互關系，對可持續性產生了人為影響。因此，CSD能夠看作為一種社會層面可持續性的非直接反應。通常，CSD包括服務質量和服務響應速度兩個方面。但是目前云制造還處于初級階段，沒有足夠的客戶評價數據來衡量服務質量的好壞，另一方面客戶對服務質量的滿意度更多是一種事后評價。因此，這里僅考慮服務響應速度對客戶滿意度的影響，忽略服務質量的影響只是影響CSD值的大小，并不會影響本文方法的可行性和有效性。CSD表達式為

式中，α、β、λ是參數。

云制造平臺在調度多個任務時，目標是保障所有的任務都盡可能在客戶期望的時間內完成。因此，當FTj≤ETj時，客戶對完成時間完全滿意，滿意度Stj=1；當 FTj＞ DLj時，任務Tj沒有在客戶給定的條件內完成，=0；當ETj≤ FTj≤ DLj時，根據式（2），同時考慮到結果的標準化，將客戶j對任務Tj完成時間的滿意度函數定義為=是客戶j對服務響應的心理參數，可以根據客戶的訂單問卷得到。因此，表示為

為了做對照實驗，構建完全基于客戶對時間和成本不滿意度的優化目標函數：

2.3.2 資源閑置率

最小化資源閑置率RUE意味著使用最少的資源獲得最大的效果，從而提升經濟層面的可持續性。需要說明的是，在任務不需要分解為子任務的情況下，為了讓客戶得到及時的服務，通常就需要讓資源處于等待狀態，這樣資源閑置率就不會太低，過低的資源閑置率會導致出現子任務需要花時間等待資源釋放的情況，從而降低客戶的滿意度。但是，這里我們考慮的是每一個任務都需要分解為多個子任務的情況，客戶對服務響應的要求是最終完成時間，而具體某一個子任務的等待時間并不會直接影響客戶的滿意度。相反，過高的資源閑置率會影響到云制造平臺經濟層面的可持續性。資源閑置率表達式為

2.3.3 資源服務成本

資源服務成本RSC是用實際服務成本TC的標準化處理來表示。TC由服務成本、物流成本和環境成本三個部分組成。在計算TC時，服務過程中的碳排放被考慮進去并轉換為環境成本。因此，RSC能夠綜合反映云制造調度過程中經濟和環境層面可持續性，表達式如下：

式中，TC、TCmin和TCmax分別為實際的服務成本、可選擇的最小服務成本和最大服務成本；SCj、LCj和ECj分別為任務Tj的服務成本、物流成本和環境成本；為決策變量；是任務成本和 b為決策變量，用于判斷任務Tj的兩個相鄰子任務分別被分配給哪兩個企業，然后根據前一個子任務STj,k的單位距離物流費用η和這兩個企業之間的距離di,i′計算物流成本；為服務l執行任務STj,k的環境成本。

2.4 約束條件

（1）時間約束。任務Tj的完成時間FTj由三部分組成：服務時間STj、物流時間LTj和等待時間WTj。startTj,k是子任務 STj,k的結束時間，end Tj,k是子任務STj,k的結束時間。

對于任意一個服務，后一個任務的開始時間大于前一個任務的結束時間，即滿足

在基于可持續性和基于滿意度的調度模型中都要求每一個任務完成時間小于客戶要求的最終期限：FTj＜ DLj。

（2）成本約束。在基于可持續性模型中，任務Tj的成本Cj包括服務成本、物流成本和環境成本，在基于滿意度的模型中，只考慮服務成本和物流成本，環境成本不作為優化目標。在基于滿意度的調度模型中每一個任務完成時間小于客戶要求的最終期限：FTj＜DLj。而在基于可持續性模型中，關注整體成本，不強調單個任務成本約束。

（3）任務約束。任務被分解后，云制造平臺為每一個子任務搜索和匹配服務，見圖2。每一個子任務只能分配給一個企業，且任務分配后，執行該任務不中斷直到任務完成。如果服務Si,l被選擇用于完成子任務STj,k，那么=1，否則=0。只允許匹配一個服務來執行子任務STj,k，對于任意給定的 j和k，都有

3 解決辦法

3.1 個體編碼

采用基于多層整數編碼的方式對染色體編碼。當待調度的任務總數為N，任務的子任務個數為j時，個體的長度為其中，染色體的前半部分表示所有任務在企業上的服務順序，后半部分表示任務每個子任務匹配的企業服務。如個體[1 2 3 42 4 3 1 2 2 1 3 1 3 3 2],該個體表達了4個子任務個數為2的任務在3個企業的服務順序。其中，前8位表示任務的調度順序，為任務1?2?3?4?2?4?3?1；9到16位表示服務企業，依次為2?2?1?3?1?3?3?2。

3.2 適應度值

染色體的適應度值為所有客戶總的不滿意度，適應度值計算公式為

式中，U為所有客戶對調度方案的總的可持續性。

3.3 選擇操作

選擇操作采用輪盤賭法選擇適應度較好的染色體，個體選擇概率為

式中，pi(i)為染色體i在每次選擇中被選中的概率。

3.4 交叉操作

交叉操作采用整數交叉法。步驟是首先從種群中隨機選取兩個染色體，并取出每個染色體的位，然后隨機選擇交叉位置進行交叉。交叉后某些任務的子任務多余或者缺失，因此，需要把多余的子任務調整為缺失的子任務，并調整對應的服務。交叉操作見圖4。

圖4 遺傳算法交換操作圖Fig.4 The crossover operation

3.5 變異操作

變異算子的步驟首先是從種群中隨機選取變異個體，然后隨機選擇變異位置1和2，最后把個體中這兩個子任務以及對應的服務序號交換。如果變異后的工序不符合要求，則進行調整。變異操作見圖5。

圖5 遺傳算法變異操作圖Fig.5 The mutation operation

基于多層編碼遺傳算法的云制造任務調度算法流程見圖6。

圖6 遺傳算法流程圖Fig.6 Flow chart of genetic algorithm

4 模擬實驗

為了驗證調度模型和遺傳算法的有效性，在MATLAB（R2016a）上設計了模擬實驗。實驗分為兩個部分，第一部分考慮的是本文提出的基于可持續性的調度模型（下文稱實驗一），第二部分將基于滿意度的調度模型作為對照（下文稱實驗二）。

本例中共有4家企業，5個任務，每家企業分別能夠提供3種類型的云制造服務，每個任務分別包含6個子任務，任務與服務的對應關系見表1。其中，企業 E2提供 S11、S12和 S133 種服務，任務T1的第一個子任務ST1,1可選的服務有S11和S31兩種。

表1 任務可選服務表Tab.1 List of available services for the tasks

在云制造環境下，任務中通常都包含了客戶的個性化需求，而每一個企業的能力和所提供的個性化服務特色也不會相同，因此同一個子任務采用不同的服務，其時間和成本也會不一樣，本例中任務成本和任務時間信息見表2和表3。這兩個表中的信息和表1是相互對應的，如任務T1的第5個子任務ST1,5在服務S23中成本和時間分別為673和26。

表2 任務成本信息Tab.2 Task cost information

表3 任務時間信息Tab.3 Task cost information

在基于可持續性的調度模型中，考慮了不同任務采用不同服務時，面臨著不一樣的環境成本，這個成本與任務成本雖然形式是一樣的，但其意義體現在對環境的重視，因此不能簡單地納入任務成本范圍內。在實驗一中，環境成本納入了可持續性優化目標，而在實驗二中，環境成本不計入客戶應該承擔的成本范圍。本例中具體的環境成本信息見表4。其中，任務T3的第3個子任務ST3,3在服務S42中的環境成本為23。

表4 環境成本信息Tab.4 Environmental cost information

企業之間的地理距離見表5。其中，企業2和企業5之間的距離為468.02。本例中假設所有服務之間都需要有物流過程，單位距離的物流費用為0.008，物流成本為0.005。

表5 企業間的地理距離Tab.5 Geographic distance between enterprises

在實驗一中，客戶對服務時間的不滿意度被認為是可持續性的一個方面，而服務成本則納入整體優化的范疇；在實驗二中，則以完全最優化客戶對時間和成本的不滿意度作為目標。本例中考慮的客戶與任務是一一對應的，即客戶3的任務稱為任務3，客戶的心理期望見表6。其中，客戶2的期望時間ET2為160，最終期限DL2為370，期望成本EC2為5 260，最高成本HC2為5 960，對時間的心理期望參數為2.9，對成本的心理期望參數為2.4，系統給定的重要程度μ2為0.27。

表6 客戶心理期望Tab.6 Customer psychological expectation

在兩組實驗中，遺傳算法的基本參數設置如下：種群數量為60，最大進化次數為50，交叉概率為0.8，變異概率為0.6。

首先在實驗一中，以優化可持續性為目標進行模擬實驗。我們將客戶對時間的不滿意度、資源服務閑置率和總成本的權重分別設為0.2、0.5和0.3。從圖7中可以看出種群的平均值和最優值都得到了有效的降低，最優解從最初的0.44降到了0.36，種群的平均值也從0.55降到了0.49。

圖7 基于可持續性目標的迭代過程（實驗一）Fig.7 Iterative process based on sustainability goals（experiment one）

在基于可持續性的調度模型中，同樣考慮了任務時間的客戶滿意度，并且將任務成本納入整體優化。因此，基于客戶滿意度的調度模型的最優解也隨著可持續性的優化過程而逐步變小，見圖8。但由于客戶滿意度不是實驗一的唯一優化目標，因此種群的平均適應度波動相對較大。

圖8 基于滿意度目標的迭代過程（實驗一）Fig.8 Iterative process based on satisfaction goals（experiment one）

實驗一得出的最優解的調度甘特見圖9和圖10。其中，圖9從企業的角度展示了調度過程，圖10則是從任務的角度展示了調度過程，調度任務之間的深色部分表示了物流過程。可以看出各任務依次進行，等待時間相對較少。

圖9 企業角度的調度甘特圖（實驗一）Fig.9 Gantt chart of enterprise perspective（experiment one）

圖10 任務角度的調度甘特圖（實驗一）Fig.10 Task scheduling Gantt chart（experiment one）

圖11 和圖12分別展示了對時間和成本的優化程度。總體來看，調度結果都盡可能滿足了客戶的期望，但優化目標強調整體的成本，因此在最優方案中出現了任務1的成本超過客戶設定范圍的情況。在實際中，實驗一對應的情況很可能是客戶先提出服務時間和成本，并交納了定金，因此即使在整體調度過程中，服務成本超過了客戶的預期，也很有必要完成任務，否則可能面臨更高的違約懲罰。

圖11 任務時間優化效果（實驗一）Fig.11 Optimization effect of task time（experiment one）

圖12 任務成本優化效果（實驗一）Fig.12 Optimization effect of task cost（experiment one）

在實驗一中，環境成本和資源閑置率都是優化目標的一部分，最優解的情況見圖13和圖14。

圖13 環境成本分布（實驗一）Fig.13 Environmental cost distribution（experiment one）

圖14 資源閑置率優化效果（實驗一）Fig.14 Optimization effect of resource idle rate（experiment one）

最后在實驗一中，以優化可持續性為目標，進行500次模擬，每一次都按照實驗二的參數求出客戶的不滿意度，其統計結果見圖15和圖16?？梢钥闯隹沙掷m性適應度分布在0.365的次數最多，而滿意度適應度分布在0.035的次數最多。

在實驗二中，以優化所有客戶總的滿意度為目標進行模擬實驗。遺傳算法的搜索過程見圖17。從圖中可以看出種群的平均值和最優值同樣得到了有效降低。相比于實驗一（圖8），種群平均值的變化更加穩定，且最優解效果更好。

圖15 可持續性適應度的統計結果（實驗一）Fig.15 Statistical results of sustainability fitness（experiment one）

圖16 滿意度適應度的統計結果（實驗一）Fig.16 Statistical results of satisfaction degree of fitness（experiment one）

圖17 基于滿意度目標的迭代過程（實驗二）Fig.17 Iterative process based on satisfaction goals（experiment two）

同樣，在優化客戶滿意度的過程中，可持續性指標也逐步變小，但達到最優解的速度更慢，同時種群平均值也波動較大，見圖18。

實驗二的調度甘特圖見圖19和圖20。其中，圖19從企業的角度展示了調度過程，圖20則是從任務的角度展示了調度過程，同樣用深色表示任務之間的調度過程。

圖18 基于可持續性目標的迭代過程圖（實驗二）Fig.18 Iterative process based on sustainability goals（experiment two）

圖19 企業角度的調度甘特圖（實驗二）Fig.19 Gantt chart of enterprise perspective（experiment two）

圖20 任務角度的調度甘特圖（實驗二）Fig.20 Task scheduling Gantt chart（experiment two）

圖21 和圖22分別展示了對時間和成本的優化程度，將優化的時間成本與客戶期望值與最大值作比較，總體來看，調度結果都很接近客戶的期望值。相比于實驗一，這里并沒有出現成本時間超過客戶設定界線的情況，因為那樣會導致目標函數的惡化。最優方案通過折中平衡各個客戶的利益，盡可能滿足每一個客戶。

實驗二中的環境成本和資源閑置率見圖23和圖24，與圖13和圖14相比較，可以發現在實驗一中，環境成本得到有效降低，而完全閑置的資源數量也只有1個，少于實驗二中的3個。

圖21 任務時間優化效果圖（實驗二）Fig.21 Optimization effect of task time（experiment two）

圖22 任務成本優化效果圖（實驗二）Fig.22 Optimization effect of task cost（experiment two）

圖23 環境成本分布圖（實驗二）Fig.23 Environmental cost distribution（experiment two）

圖24 資源閑置率優化效果圖（實驗二）Fig.24 Optimization effect of resource idle rate（experiment two）

最后在實驗二中，以優化總體不滿意度為目標，進行500次模擬，每一次都按照實驗一的參數求出可持續性，其統計結果見圖25和圖26。可以看出實驗二中客戶總體滿意度分布在0.03的最多，可持續性在0.39的最多，和實驗一相比較，實驗二在優化可持續性過程中客戶的滿意度沒有明顯降低，而可持續性則有所優化。

圖25 滿意度適應度的統計結果圖（實驗二）Fig.25 Statistical results of satisfaction degree of fitness（experiment two）

圖26 可持續性適應度的統計結果圖（實驗二）Fig.26 Statistical results of sustainability fitness（experiment two）

通過兩組實驗可以看出，在實驗一中以優化可持續性為目標，調度方案能夠在客戶滿意度、資源利用率和服務成本方面實現整體優化，雖然忽略了客戶對服務成本的要求，但對于平臺運營者來說這是合理的，一方面能夠按時完成任務，不會有違約金，另一方面平臺并沒有因為一個任務成本偏高而引起整體成本上升；在實驗二中，同時考慮客戶的時間和成本心理期望，將降低客戶總體不滿意度作為優化目標，調度結果符合每一個客戶的要求，并且非常接近客戶的期望目標，但是設備閑置率和環境成本相比于實驗一要高。隨著云制造的發展，不同的服務模式得到應用，經濟、社會和環境可持續性將會是不可忽略的因素，而基于可持續性的調度模型的優勢也會越來越明顯。

5 結論

對云制造平臺多任務調度流程和可持續性框架進行分析，構建了基于可持續性的云制造多任務調度模型。設計了改進的遺傳算法來有效解決調度模型的求解問題。通過兩組對比實驗，分析了可持續性因素對調度結果的影響。通過模擬實驗可知，在只考慮客戶滿意度的情況下，調度結果能夠實現每一個客戶期望的優化，但從整體的可持續發展來看，其設備閑置率和環境成本相對較高；而設計的基于可持續性的調度模型，能夠在不損失客戶滿意度的前提下，同時降低環境成本和設備閑置率，保障平臺整體的可持續運行。