分布式3D 打印服務的實時多任務調度研究*

趙軍富 杜海淵 靳永勝 李建軍

（①內蒙古科技大學，內蒙古 包頭 014010；②內蒙古蒙牛乳業（集團）股份有限公司，內蒙古 呼和浩特 010000）

“工業4.0”由集中式控制向分散式增強型控制的基本模式轉變，建立了一個高度靈活的個性化和數字化的產品生產模式，實現大規模定制[1-4]個性化產品。當今，智能制造與IIoT 和云制造（CMFg）的結合，使3D 打印技術成為大規模定制和大規模生產的強大動力[5-7]，有效地縮短了設計與原型制造之間的時間[8-11]。3D 打印成為定制化大規模生產的最佳技術[12-14]，能以較少的材料和能源制造出常規制造技術無法實現的復雜形狀。

在IIoT 中，制造資源都被收集在一個虛擬的資源池中，為用戶提供在線按需使用的制造服務[15-17]。在符合時間、成本、服務質量（QoS）和服務可用性的情況下，在一段時間內分配和調度服務以執行一組任務的過程稱為多任務調度。本文研究IIoT 中多任務調度的方法，實現自主實時多任務調度來提高制造系統的性能[18-20]。

3D 打印、云制造和IIoT 技術的快速發展，使3D 打印能夠以相對低的成本制造定制產品，其應用范圍從研發領域的原型設計擴大到醫療、航空、汽車等領域的大規模定制生產[5-10]。Zhou L 等[21]在云制造中建立3D 打印服務模型，描述了服務需求者、服務提供者和云制造平臺之間的關系，給出了3D 打印服務匹配過程中的模型尺寸、打印精度、打印材料、成本、時間等屬性，對3D 打印服務調度（3DPSS）提出了一種基于優先級的改進遺傳算法。該改進遺傳算法與粒子群優化算法（PSO）和模式搜索算法相比，改變了任務調度的數量，縮短了平均任務交付時間。

Chen T 等[6]為3D 打印制造業設計了一個物聯網系統，該系統為實現工作量平衡使用分支限界法尋找最短交付路徑，以盡量減少訂單交付時間。

Luo X 等[22]提出了一個建模框架，解決網絡制造環境下有效管理3D 打印資源的匹配問題,研究了基于動態和靜態數據的3D 打印任務分配方法，在建模過程中采用二分圖匹配算法對靜態特性的各項參數指標進行了定量分析，同時對3D 打印機的動態特性，建立了通用的動態數據采集系統用于實時監測和協調3D 打印機，盡量縮短任務完成時間。

表1 為對現有關于分布式3D 打印服務調度文獻的歸納總結，但這些研究中忽略了幾個重要方面。首先，這些研究只關注靜態調度而完全忽略3D 打印服務調度中的實時性要求，與統一調度概念相違背。其次，大部分研究都針對數量有限的3D 打印服務進行調度，無法在高負荷的情況下平衡分布式3D 打印機之間的工作量，難以提高資源利用率。最后，這些研究選擇了基于群體的優化方法來調度3D 打印服務，如改進遺傳算法，采用這種優化算法可能導致提交的3D 打印任務響應時間相對延長，與實時性要求相矛盾。為此，本文研究了一個基于IIoT 定制的3D 打印任務的實時分配和調度架構，提出了實時分配算法和基于優先級的自適應實時多任務調度的算法（adaptive real-time multi-task priority-based scheduling，ARMPS），為定制的3D打印任務進行最佳分配和動態實時調度，實現負載平衡，提高能源效率和資源利用率，促進生態可持續發展。

表1 對現有分布式3D 打印服務調度文獻總結

1 3D 打印任務在IIoT 中實時分配與調度

1.1 分配與調度模型

圖1 所示為本文提出的基于IIoT 定制的3D 打印任務的實時分配和調度架構。3D 打印任務的需求者將3D 打印模型和3D 打印屬性提交給IIoT 平臺，3D 打印服務的每臺3D 打印機都有其特定的屬性，主要屬性包括打印材料、打印精度、噴嘴直徑、填充百分比、每克價格、模型體積、G 代碼的路徑長度、最后期限等。

圖1 3D 打印任務實時分配與調度框架

每個定制的3D 打印任務通過分配和調度模塊在3D 打印服務提供商數據庫中精確選擇最合適的3D 打印機，在滿足實時性和分布式3D 打印之間的工作負載平衡要求下，當需求者提交多個零部件需求時，必須指定這些零部件狀態為關聯或非關聯，關聯零部件即為同一組，將使用相同的3D 打印機，非關聯的可以使用不同的打印機。

1.2 任務分配與調度

為了實現能源優化，平衡3D 打印機之間的工作量，采用基于圖形著色的在線任務分配算法[23]，根據匹配屬性將提交的3D 打印任務與IIoT 平臺中最合適的3D 打印機相匹配。同時，提出一種基于優先級的自適應實時多任務調度算法，實時調度每一個3D 打印任務，滿足3D 打印任務的實時性以及動態性要求。

1.2.1 任務分配

在線圖著色算法是圖形的頂點按順序到達，每個新的頂點一旦到達都被分配一個不能改變的顏色。本文引入在線圖著色的任務分配算法，圖形中的每個頂點代表一個要執行的3D 打印任務，顏色代表3D 打印機，在線圖著色的定義與將3D 打印任務分配給3D 打印機的思路完全一致，每個頂點的著色類似于將一個3D 打印任務通過嚴格的屬性匹配方案分配給一個3D 打印機。匹配打印任務主要依據的打印屬性如下。

（1）打印材料（M）。假設每臺3D 打印機的打印材料不能改變，則 3D 打印任務所需的打印材料（M3DPT(x,y)）必須與3D 打印機的打印材料（MPZ）相同，即M3DPT(x,y)=MPZ。

（2）打印精度（AC）。打印精度（AC3DPT(x,y)）與打印每一層的厚度有關，對機械性能和打印品的表面光滑度有要求。3D 打印任務所需的打印精度應大于或等于3D 打印機的打印精度（ACPZ），即AC3DPT(x,y)≥ACPZ。

（3）噴嘴直徑（ND）。3D 打印機噴嘴的直徑（ND3DPT(x,y)）影響3D 打印部件的細節、強度和重量。打印3D 打印任務所需的噴嘴直徑應大于或等于3D 打印機的噴嘴直徑（NDPZ），即ND3DPT(x,y)≥NDPZ。

（4）填充百分比（INF）。填充百分比決定3D 打印部件的強度，3D 打印任務的指定填充率（INF3DPT(x,y)）應小于或等于3D 打印服務提供商在打印零件時調整的填充率（INFPZ），即INF3DPT(x,y)≤INFPZ。

（5）每克價格（PG）。成本以每克價格表示，3D 打印任務實際所需的每克價格（PG3DPT(x,y)）應大于或等于3D 打印服務提供商提供的每克價格（PGPZ），即PG3DPT(x,y)≥PGPZ。

（6）模型體積（Vol）。打印的3D 模型的最大體積（Vol3DPT(x,y)）必須小于3D 打印機允許的3D打印量（VolPZ），即Vol3DPT(x,y)＜VolPZ。

（7）G 代碼的路徑長度。在CAM 階段模型根據提交的層高被切開，然后轉化為G 代碼文件，G代碼的路徑長度將用于打印時間的計算。

（8）最后期限（DL）。需求者提交的最后期限（DL3DPT(x,y)）應小于等于服務提供者提供的交付時間，即

圖2 所示為任務分配流程。當同時收到多個3D 打印任務時，首先由在線圖著色算法根據用戶預定的3D 打印任務的類別或等級自動生成的優先級進行排列，對于具有相同優先級的多個3D 打印任務將依據其最后期限（DL3DP(x,y)）進行升序排列。然后對優先級高的3D 打印任務進行分配，每個打印機的工作時間總和大于或等于工作時間閾值，同時打印材料、打印精度、噴嘴直徑、填充百分比、每克價格、模型體積等打印屬性滿足條件時，計算所有3D 打印工作時間的總和，并與其工作時間最后期限（DL3DP(x,y)）進行比較，若，則離開打印列表，其狀態改為零，否則該打印機仍在列表中，其狀態保持不變。最后，就緒的3D 打印列表根據它們的能效功耗比（PPWPZ）降序排列，從而重新著色，更新3D 打印列表。

圖2 任務分配流程

1.2.2 任務調度

基于優先級的自適應實時多任務調度算法能夠保證每個3D 打印任務根據其提交的優先級進行及時調度，以便準確地滿足每個任務的最后期限。

（1）任務優先級。當請求者指定或選擇已提交3D 打印任務類別時，自動生成一個任務優先級。3D 打印任務的類別為[1,5]，其中1 代表最低的優先級，5 代表最高的優先級，每個類別都有一個預定的優先級，若是非關聯零部件，需求者為每個3D 打印任務單獨指定一個不同的類別；若是關聯的零部件，則為整個提交的3D 打印任務指定為同一個類別。式（1）給出了在打印機Z上執行的成功分配的3D 打印任務的隊列，相關的優先級向量（βP(Z)）顯示在式（2）中。

式（2）中，當具有相同優先級和相同到達時間的3D 打印任務分配和調度在同一個3D 打印機（即打印機Z）上執行時，這些3D 打印任務將根據它們的最后期限升序排列在打印機PZ中。

（2）到達時間（a3DPT）。根據到達率λ由式（3）可以依次產生不同3D 打印任務的到達時間。

式中：a3DPT是一個當前3D 打印任務的到達時間；a3DPT-1是其前一個3D 打印任務的到達時間；是一個高斯隨機數，其中λ是到達率，其平均值為，方差為 σ2。

如圖3 所示，在任務調度階段，首先確定優先次序，判斷同一時間（Ti）到達的3D 打印任務數是否大于等于2，若成立，則按優先級順序降序排列，對于相同優先權的3D 打印任務需要根據他們預設的最后期限升序排列。然后由多任務調度算法計算開始時間、執行時間、完成時間，將這些計算出的時間與接收該3D 打印任務的提交期限進行比較，來檢查這個3D 打印機是否滿足工作最后期限，是否有足夠的時間來執行這個3D 打印任務。如果這些時間限制中存在任何一個不匹配，那么子列表中的第二個3D 打印機就會進入調度階段，重復進行所有計算和比較，否則這個3D 打印機將當前3D 打印任務執行完畢，同時在隊列中的第二個3D打印任務進入分配和調度階段之前，可用的3D 打印的列表被更新。

圖3 確定ARMPS 算法優先次序

2 性能評價

使用Matlab2021 進行仿真模擬實驗，研究 3D打印數量、到達率等參數發生改變時對系統架構性能及分配和調度算法的影響，實現對系統的架構，以及 3D 打印任務的分配和調度算法的評估。

（1）3D 打印任務的數量（3DPTs）

在高負載情況下通過仿真模擬對架構的性能進行測試，3D 打印任務的數量從5 個任務增加到300 個任務。

（2）到達率（λ）

將3D 打印機的數量設定為50 臺，改變到達率λ的值，將λ=0.25 逐漸增加到λ=16。默認值為：ρ=0.9，α=0.4，λ=0.25。文中所有圖表都繪制了每個模擬實驗在5 次運行中獲得的平均數值。本研究中的性能指標包括成功率、平均響應率和系統獲得的總價值。

成功率：成功分配的3D 打印任務數量與所有提交的3DPT 的數量之比。

平均響應速度：3D 打印任務從到達時間到成功分配給3D 打印機的時長。

系統獲得的總價值：到截止時間成功分配的3D 打印任務的總價值與所有提交的3D 打印任務的總價值的比率。

此外，在仿真模擬中使用同一組數據集對本文提出的架構分別使用多任務調度算法與3D 打印服務調度的改進遺傳算法[21]、粒子群優化（PSO）、模式搜索（PS）等調度算法進行對比，驗證所提出的架構的穩健性。

2.1 3D 打印任務數量

如圖4 所示，隨著3D 打印任務數量從5 增加到300，響應速度逐漸增加，在300 個3D 打印任務高負荷的試驗中，每個任務的平均響應速度達到1.60 min。

圖4 3DPTs 的數量增加對平均響應速度的影響

圖5 所示為4 種不同的調度方法對每個3D 打印任務的平均響應速度的對比。將本文所提架構的參數ρ=0.9、α=0.4、λ=0.25 設置為默認值，3D 打印數量限制在最多80 個。由圖5 可知，本文所提架構采用多任務調度算法較其他三種調度方法平均響應速度明顯提高。

圖5 調度方法ARMPS、改進遺傳算法、粒子群優化、模式搜索對每個3D 打印任務的平均響應速度

如圖6 所示，在ρ=0.9、α=0.4、λ=0.25 為默認值時，3D 打印任務數量增加到100 時，成功率仍然是100%。當3D 打印任務數量接近200 個時，成功率略有下降，增加到300 個任務時成功率為97.6%。

圖6 改變3DPT 的數量對本架構的成功率影響

2.2 到達率

圖7 給出了當默認值ρ=0.9、α=0.4、λ=0.25 時，通過改變到達率和3D 打印任務數量對平均響應速度的影響。在300 個3D 打印任務數量試驗中，通過增加到達率可以提高每個3D 打印數量的平均響應速度，在λ=0.25 時平均響應速度是1.40 min，在λ=16 時平均響應速度達到1.65 min。

圖7 到達率和3D 打印數量對平均響應速度影響

從圖8 中可以看出增加到達率幾乎不影響成功率。結合圖4、圖6 至圖8 可以看出，當設置ρ=0.9、α=0.4 達到負載平衡。本文所提出的架構在高負載情況下，特別是3D 打印任務以極快的方式連續到達時，能夠明顯地應對高度動態的3D 打印任務的演變情況，這些結果證明了所提出架構的穩健性和可擴展性。

圖8 到達率和3D 打印數量對本框架的成功率影響

2.3 負載平衡

如圖9 所示，在300 個3D 打印任務的試驗中，默認值ρ=0.9、α=0.4、λ=0.25 時平均響應速度為1.65 min，而無負載平衡的情況下，同樣λ=0.25 平均響應速度為1.42 min，由此可見，應用負載平衡算法增加了平均響應速度。

圖9 應用負載平衡算法對平均響應速度的影響

應用負載平衡算法的主要目的是避免某些3D打印機負載不足和過載，確保3D 打印任務在3D打印機上均勻分布。由圖10 可見，設置默認值ρ=0.9、α=0.4、λ=0.25，應用工作負載平衡算法改善了3D 打印任務在可用3D 打印機上的分布，從而使停止狀態3D 打印機的數量比例大大降低。因此，本文所提的負載平衡算法能減少能源消耗并提高資源利用率。

圖10 應用負載平衡算法前后不工作的打印機數量之間對比

此外，本文架構中采用PPW 優先考慮最節能的可用3D 打印機，減少使用甚至關閉效率較低的3D 打印機，不僅可以促進節能，而且可以防止某些3D 打印機的過載或欠載，加強經濟和生態的可持續性。

2.4 魯棒性

將3D 打印機的數量設定為50 臺，ρ=0.9、α=0.4、λ=1 為默認值，改變3D 打印任務數量和到達率的值，3D 打印任務數量由10 逐漸增加到100，然后再劇增到500，如圖11 所示，當λ=1 和λ=30 時，打印任務數量為100 時，對應的平均響應速度分別是1.0 min 和1.15 min；打印任務數量為500時，對應平均響應速度是3.7 min 和3.9 min。由此可見，在打印機數量一定的情況下，3D 打印任務數量的從100 劇增到500，平均響應速度有所降低，λ的變化對平均響應速度影響不大。

圖11 3D 打印任務數量劇增平均響應速度變化情況

默認值ρ=0.9、α=0.4，當λ=30 時，打印任務數量為100 和500 時，對應的成功率分別為99.0%和95.2%，可見在3D 打印任務數量劇增成功率下降不大，如圖12 所示。在相同數量的3D 打印任務條件下，到達率的增加幾乎不影響成功率。

圖12 3D 打印任務數量劇增成功率變化情況

綜合圖11 和圖12，在3D 打印機數量不變和3D 打印任務的數量劇增的情況下，任務調度和分配的算法具有持續正確處理數據的能力，本框架具有穩健性，算法具有魯棒性。

2.5 獲得的系統總價值

圖13 顯示了所提出的架構使用EDF 調度算法與ARMPS 算法獲得的總價值比較。由圖13 可知，本文架構中ARMPS 算法獲得的總價值高于采用EDF 算法時獲得的總價值。EDF 算法是根據截止時間給3D 打印任務分配優先權，不考慮其重要性。而ARMPS 算法相反，它根據3D 打印任務的重要性分配優先權，根據3D 打印任務的重要性分配優先級的過程模擬了工業4.0 的真實場景。

圖13 EDF 算法與ARMPS 算法進行任務調度系統獲得的總值的對比

3 結語

本文提出了一個用于IIoT 中個性化3D 打印的實時綠色感知多任務調度架構，該架構由分配和調度兩個相互聯系的部分組成；提出了一種基于圖形著色的在線算法，以完全符合用戶自定義屬性的方式充分分配3D 打印任務。此外，還開發了一種基于優先級的自適應實時多任務調度算法來滿足3D打印任務的動態性和實時性要求，平衡了IIoT 中分布式3D 打印之間的工作負載，同時提高了資源利用率。在高負載環境中，通過性能評估測試證明所提出的架構是穩健的、可擴展的。