基于改進粒子群算法的多機器多任務3D打印智能調度方法

周明霞，張夢娜，李宇，吳 川，張 瀟

(徐州醫科大學 醫學信息與工程學院，江蘇 徐州 221000)

0 引言

3D打印，也稱為增材制造(AM, additive manufacturing)，根據材料類型與凝聚方式，目前3D打印機主要分為光固化式、光融化式以及熱熔化式。與傳統的減法制造不同[1]，該技術通過將材料融化經噴頭一層一層“打印”目標物品，因此使得3D打印具有應用范圍廣，能滿足個性化多樣化要求的優點[2]。同時隨著制造技術的不斷發展與精度提升，3D打印已進入零件生產等領域[3]，受到了越來越多用戶的密切關注。

隨著3D打印技術的快速發展，批量3D打印成本高的問題凸顯，在一定程度上限制了3D打印技術的應用與發展，因此在工廠生產過程中，提高3D打印機的利用效率，降低3D打印成本，合理安排任務調度方案尤為重要。3D打印調度問題是指在面對多機器多任務的實地工廠生產時，根據目標物品的要求，合理有效地將生產部件任務分配給3D打印機以最終完成客戶的要求。在此過程中，工廠需平衡生產部件的成本要求、材料要求、時間要求，部件之間的關系，考慮3D打印機的工作臺大小等多方面約束因素[4]，因此面向多機器多任務的3D打印調度問題是一個復雜多變、難以求解的問題。

基于上述問題，為推進3D打印的廣泛應用，需將批量打印成本作為重要考慮因素。3D打印技術操作所需時間主要包括人工操作時間(放置物品所需材料、開機輸入模型、清理臺面)、機器預熱時間(達到設定的溫度)、打印目標成品時間等[5]。其中，打印機預熱時間占據較長的空白時間段，浪費許多人工成本與耗能，因此在考慮調度問題時，根據3D打印機一層一層累積的特點，任務調度時可以將多個部件任務分配在同一臺打印機上，以此減少多個機器開機預熱時間，提高打印機的利用效率，減少損耗成本。但由于機器工作臺面積和最大高度的限制，一些部件無法分配給一些機器，因此難以確定如何分配零件放在合適的機器上生產，即調度問題。

目前，3D打印批量調度成本最優化的研究較少，同時階段安排打印批次容易陷入局部最優的困境。粒子群算法是一種傳統的群體智能優化算法，通過模擬鳥類覓食，將鳥類聚集看做一個粒子群，在不淘汰任何一個個體的情況下，根據群體中個體之間的協作與信息共享最終找到覓食的最優解。由于其思想簡單，模擬效果好，粒子群算法被廣泛應用于非線性、非凸性或組合優化問題[6]。因此提出一種基于改進粒子群算法的成本最優化模型以求解面向多機器多任務的3D打印調度問題。

以下章節劃分：第1章首先介紹國內外研究現狀，總結了目前對于面向多機器多任務的3D打印調度問題研究較少，成本最優又在實際生產中扮演重要角色，因此研究該問題十分必要。在第2章闡述研究的多機器多任務的3D打印調度問題，并在第3章給出數學模型。考慮實際生產場景，分析打印工場，結合生產流程，建立單位體積成本模型，在第4章中闡述如何具體應用改進粒子群算法尋找單位體積平均成本最優化，解決面向多機器多任務的3D打印調度問題。第5章中，基于具體的一個實驗算例，給出基于改進粒子群算法的3D打印智能調度方法的實驗結果與分析。最后在第6章中進行總結。

1 國內外研究現狀

智能制造一詞，20世紀末最早起源于美國，自此世界多國投入智能制造的研究[7]。3D打印是智能制造領域的重要部分，它是以計算機三維設計模型為直接驅動，目前我國3D打印處于快速發展階段[8]。

為提高3D打印機利用效率，降低生產成本，推動3D打印技術的進一步應用，以成本最優化為目的，研究面向多機器多任務的3D打印調度問題十分必要。針對3D打印調度成本最優化的研究較少，目前有一些用于批處理過程的生產調度技術，如L.Rickenbacher等人提出了一個針對SLM過程的通用成本模型，對每個過程進行詳細的建模與分析，包括預處理和后處理過程[9]；文獻[10]通過研究真實的供應鏈場景設置模型，為分布式備件生產奠定了基礎。但面對復雜場景，需要新的生產計劃模型促進優化。

同時，對成本模型內部具體架構研究較少，階段安排打印批次容易陷入局部最優問題。L.Rickenbacher等人提出的成本模型未應用解決實際生產問題，但發現同時構建多個部件，將大大減少任務完成時間，從而使得成本降低[11]。Uzsoy等人提出了面向工件尺寸不同的單機調度問題，同一批次的工件加工時間取決于該批次中加工時間最長的工件[12]，同時同一批次的工件需滿足機器的容量限制。食品加工、半導體芯片老化測試等符合該問題的特征[13]。

多機器多任務的3D打印調度是一個難以解決的問題，如何將部件更高效合適的分配進入機器與批次是難以確定的，特別當一個新的部件加入批次時，部件的成本與加工時間都將發生變化，由此結合實際生產問題，在批量3D打印調度中，成本不易控制，難以確定哪個零件在哪個機器上生產。因此，研究多機器多任務的3D打印調度問題并提出一易實施高效率的方法是十分必要的。

2 多機器多任務的3D打印調度問題闡述

常用的FDM(fused deposition modeling)類型的3D打印機一般具有噴頭、熱床、絲桿、步進電機和控制板等部件[14]。噴頭一般是由步進電機、加熱器、噴嘴和風扇組成。加熱噴嘴后，將耗材通過噴嘴擠出在熱床上。打印機的噴頭與熱床固定在絲桿上，通過轉動絲桿調節噴頭移動。而金屬3D打印機中核心部分即為單螺桿擠出裝置，主要由螺桿、料筒、噴嘴、螺桿驅動裝置、支承裝置等幾大部分組成[15]，是熔融原料制備裝置、堆積快速成形的前提保證。

金屬3D打印的原理是先通過計算機輔助設計(CAD)或計算機動畫建模軟件建模為一組3D數據，將數據與原料輸入3D打印機，機器便會逐層分切，金屬耗材為固態材料，在高功率光束照射下，固態材料燒結或熔解，冷卻后成型，通過層層燒結、熔煉和焊接制成金屬物品。

在3D打印調度問題中，假設有需要加工的P個部件，工廠中有M臺機器，每個部件、機器有預定義的相關參數信息。同時，根據部件的需求，這些部件包含附加信息，如截止日期、材料需求等。在分配收到訂單時，遵循以下原則：1)部件不可再分割，每個部件作為一個獨立的整體被明確的分配到一個機器上；2)所有的部件都需要進入調度序列最終打印完成；3)被分配到機器上的部件的底面積不得超過機器的工作臺面積，高度不得超過機器的高度；4)一個機器可以同時處理多個部件。

在討論成本問題時，每臺機器設置指定的打印速度和層厚，設置固定的工作臺底面積及支持的最大高度，同時在人工操作階段、清理階段，設置固定的人工成本與時間成本。當一個工廠收到訂單時，需要根據訂單需求將部件重新組合分配至合適不同的機器上完成，同時使訂單成本最小。在此過程中，研究需要解決以下幾個關鍵問題：1)所有部件都分配給合適的機器；2)在合適的機器上確定所有部件的加工順序；3)目標是使得加工成本盡可能小。

面向多機器多任務的3D打印調度問題，在滿足約束的情況下，可將部件放入同一個作業中同時被一個機器加工，以提高3D打印機的利用效率。在理想狀態下，M個機器加工P個部件所需的總成本與時間成正相關。由于3D打印技術是層層累積的，在機器同時處理多個部件組成的一個作業時，完成時間取決于作業中高度最大的部件打印完成時間。即：

hj=max{hp},p∈Pmj

(1)

其中:Pmj表示分配在機器m上的作業j中的部件集。

在調度過程中，所有部件在高度和底面積的限制下，隨機分配給合適的機器，經過組合優化調度，最終使得成本最優化并完成所有部件的打印，由此確定的調度序列即為問題的最優解。

3 單位體積平均成本最優化模型

為了方便表述搭建的研究多機器多任務的3D打印調度問題模型，表1給出構建解決問題的數學模型所用的符號及其定義。

表1 符號及其定義

每個部件包含部件高度h、體積v以及底面積s共3個參數信息，機器包含支持的最大高度H、工作臺面積S兩個約束參數，為保證部件打印完整與準確，在調度過程中，需滿足以下約束：

1)當一個作業的任意一個部件分配給一個機器時，該作業必須全部分配在該機器上；

2)部件的高度需小于該機器支持的最大高度，否則該部件不可在不符合條件的機器上打印；

max{hp·Xjp·Ymj}≤H

(2)

3)同一作業中打印的部件的底面積之和需小于該機器工作臺的面積，否則不可調度安排在該機器上。

(3)

4)每個部件之間相互獨立，每臺機器之間相互獨立，任何一臺機器的工作情況不影響其他機器。

5)不考慮故障等不確定因素。

在這一模型中，機器相關系統參數已知。每個部件需且僅需打印一次，對機器加工多少部件沒有要求。

P個部件在M個機器上的總成本計算公式為：

MTC×Tah×hj+Tn×Cp+W

(4)

其中:hj=max{hp},p∈Pmj，Pmj表示分配在機器m上的作業j中的部件集。

該成本計算方式主要包括4個部分:1)由總體積所需確定的原材料融化的成本；2)由完成時間確定的分層打印成本，由于3D打印技術是層層累積的，在機器同時處理多個部件時，即一個作業時，完成時間取決于高度最大的部件打印完成時間；3)人工成本，建立新作業機器開機、預熱以及清理機器的時間統稱為機器設置時間，此過程需要人工操作；4)機器工作期間的損耗成本[16]。

為研究面向多機器多任務的3D打印調度問題，在合理調度完成部件的打印任務基礎上，提出構建單位體積平均成本最小化的函數如下：

(5)

綜上，面向多機器多任務的3D打印調度問題，構建考慮上述單位體積平均成本的模型，模型建立如下：

(6)

4 基于改進粒子群算法的問題求解

4.1 粒子群算法

粒子群優化算法(particle swarm optimization)是一種群體智能優化算法，1995年由Eberhart博士和Kennedy博士提出，通過模擬鳥類覓食行為，每只鳥都作為一個獨立覓食的個體，通過傳遞信息，讓其他的鳥知道自己的位置與食物情況，以此判斷自己所找到的食物是不是最優的，這樣利用群體中個體的信息共享與協作找到全局最優[17]。

粒子群算法思想容易簡單且只需調整少量參數便可實現，目前已廣泛應用于優化問題[18]。粒子群算法通過一群無質量的獨立粒子來代表鳥類，每個粒子僅有位置矢量與速度矢量兩個參數，以表示粒子所處的位置以及運動的速度、方向[19]。在智能優化過程中，每個粒子單獨尋找最優解，并記錄下來，根據適應度即目標函數值的不斷更新，經過粒子群之間的位置信息以及目標函數值的共享，記錄當前個體的最優值Pbest及全局最優值Gbest。經過算法的不斷迭代，粒子群們向最優位置移動，最終得出全局最優解與位置。

面向多機器多任務的3D打印調度問題，嘗試在編碼方式及更新策略上進行針對性改進。首先采用了十進制順序二維編碼方式表示問題的解，并在更新策略上應用線性遞減權值的動態ω來調整全局與局部的搜索能力。

4.2 編碼與解碼方案

面向多機器多任務的3D打印調度問題比較復雜，在編碼過程中不僅需要考慮部件的組合調度，還需要為一個作業中的所有部件選擇一個合適的加工機器，因此僅僅采用一維的部件編碼是不可取得。因此，采用十進制順序二維編碼方式表示問題的解。第一部分為基于機器的編碼，用于確定每個部件的加工機器選擇，第二部分為基于部件的順序編碼，用來確定部件的加工組合順序。通過該二維編碼方式，可以得到問題的一個可行解。

假設一工廠接到10個部件的訂單，編號為1,2,3,…，10，可調用的加工3D打印機3臺，編號為1,2,3，則其中的一個可行解表示如下：

部件編號 1 2 3 4 5 6 7 8 9 10

機器向量 1 3 2 1 1 3 2 1 3 2

順序向量 1 1 1 2 3 2 1 2 1 2

部件編號對應的機器向量值，表示對應的加工機器編號，如部件1,4,5,8在機器1上加工；部件編號對應的順序向量值，表示部件組成的一個作業在對應機器上的組合加工順序，如機器1加工的4個部件加工順序為[p1]、[p4,p8]、[p5]，部件4與8作為一個作業放入機器1加工，機器1需加工4個部件組成的3個作業。

則上述粒子解碼后，得到3個機器加工10個部件的一個解，在機器M1上完成部件P1的單獨加工、部件P4、P8的組合加工及部件P5的單獨加工的3個作業，在機器M2上完成部件P3、P7的組合加工與部件P10的獨立加工的2個作業，在機器M3上完成部件P2、P9的組合加工與部件P6的單獨加工的2個作業。

機器1 [p1]、[p4,p8]、[p5]

機器2 [p3,p7]、[p10]

機器3 [p2,p9]、[p6]

4.3 種群初始化

一般來說，隨著迭代次數的增加，算法的搜索時間增加，但搜索的結果可能會更好，因此對于粒子群算法，選擇合適的迭代次數與種群數十分重要。一般地，種群數取20～50，具體取值根據研究問題的復雜程度而定。針對多機器多任務的3D打印調度問題，因其較為復雜，故設置種群數PN為50，迭代次數IN為300。

粒子的初始位置均勻的分布在整個搜索空間，初始化過程中，將粒子群初始化為一群可表示問題解的隨機粒子，每個粒子包含機器向量與順序向量二維實數，向量值的取值空間為[1,m]，m為機器總數；初始速度可設置為0或一個隨機值；將對應的初始適應度函數即單位體積成本值作為個體最優解。

在初始設置速度時，設置為0時，粒子與搜索空間是靜態的，當速度非0時，考慮到當粒子速度較大時，粒子移動較快，容易錯過最優解，從而增加迭代次數，提高了算法復雜性，較小時，開發能力強，但容易陷入局部最優，收斂緩慢，算法效率不高[20]。因此為合理尋求算法搜索能力與收斂速度的平衡，設置了粒子的最大速度，通常設定為粒子的范圍寬度，且保持變量變化的范圍為10%～20%。

4.4 更新策略

在初始化為一群隨機粒子(隨機解)后，這些粒子通過不斷的分享個體與群體之間的位置與最優值，迭代后更新位置與目標函數值，最終得到最優解。在算法的每一次迭代中，記錄下當前個體的最優值Pbest以及全局最優解Gbest，之后更新自己的速度與位置。

種群的多樣性即各粒子個體上的差異決定了算法的全局探索能力，因此在更新個體粒子向最優解學習移動時，如何保持粒子間的差異性十分重要。在粒子群算法搜索的前期，往往希望能快速的搜索更多的領域并確定全局最優的大致范圍，而在搜索后期，往往希望快速準確找到局部的最優解，完成收斂，因此在整個算法迭代過程中，搜索要求與希望不是一成不變的[21]。

個體粒子在向最優解靠攏時，一定程度上對自身軌跡進行調整，開展對未知領域的探索，此探索能力為全局探索能力。而在原始軌跡上進行進一步探索的便稱為局部探索能力。為有效防止陷入局部最優，采用線性遞減權值的動態ω來調整全局與局部的搜索能力。ω又稱為慣性因子，取值為非負。當ω取值較大時，全局搜索能力較強，而局部搜索能力較弱；當ω取值較小時，全局搜索能力較弱，而局部搜索能力較強。一般在實際應用中ω取值由大變小，先全局最優搜索至大致范圍，在局部搜索最優值，提高效率與準確率。

慣性因子ω更新公式如下：

ωt=(ωini-ωend)(Gk-g)/Gk+ωend

(7)

其中：Gk為最大迭代次數，ωini為初始慣性權值，ωend為迭代至最大次數時的慣性權值，一般取ωini=0.9，ωend=0.4，從而有利于算法后期的收斂。

速度更新公式如下：

vi+1=ω×vi+c1×rand()×(Pbestt-xi)+

c2×rand()×(Gbesti-xi)

(8)

其中：vi+1為粒子的速度，rand()代表介于(0，1)的隨機值，c1、c2為學習因子，通常c1=c2=2，xi為粒子的當前位置。

PSO算法沒有像遺傳算法的交叉變異操作，而僅僅根據自己的經驗更新搜索，追隨最優的粒子。式(8)包含3個部分之和，第一部分表示上次速度矢量的影響，第二部分稱為自身認知項，表示基于個體經驗粒子向自身最優解移動的矢量，第三部分稱為群體認知項，表示基于個體與群體的經驗粒子向全局最優解移動的矢量。

位置更新公式如下：

xi+1=xi+vi+1

(9)

種群在迭代過程中，根據式(8)、(9)更新速度與位置矢量，但由于本問題中部件與機器都是整數，更新后的新粒子不一定代表有效解。因此對更新后的位置矢量進行四舍五入和邊界限制處理調整，使之成為有效解。

基于前文建立的面向多機器多任務的3D打印調度問題的數學模型，算法中的適應度函數為單位體積平均成本函數。在迭代過程中，不斷比較適應度，并將更小的單位體積成本值更新為全局最優值。

4.5 收斂依據

優化收斂停止準則一般有兩種，一是設置最大迭代次數，二是達到可接受的滿意適應度值，設置上一次最優化適應度值與更新后的最優化適應度值之間的差值小于某個值停止迭代，即達到收斂要求[22]。本研究設置收斂判據為迭代次數是否到達到300次，達到收斂判據后，便退出循環，輸出結果。

4.6 算法流程

面向多機器多任務的3D打印調度問題，基于改進的粒子群算法，將目標函數設置為單位體積平均成本，考慮機器工作臺底面積與支持的最大高度及其他約束，通過不斷迭代優化最終得到單位體積成本最優值及最優調度方案。

算法的流程如圖1所示。

圖1 改進粒子群算法流程圖

算法的詳細步驟如下：

步驟1：依據調度原則，在考慮約束的情況下，初始化粒子群及參數設置，包括粒子數PN，迭代次數IN，學習因子c1、c2，慣性權重ω，最大粒子速度等；

步驟2：根據參數設置初始化粒子位置矢量與速度矢量，根據式(6)所建立的模型，計算適應度單位體積成本值，初始化個體最優值Pbest和全局最優值Gbest；

步驟3：利用式(8)、式(9)更新粒子的速度矢量與位置矢量；

步驟4：對更新后的粒子進行編碼解碼，更新適應度單位體積成本值，更新種群；

步驟5：與之前存儲的單位體積成本比較，更新個體最優值Pbest和全局最優值Gbest，將更優的目標函數值更新，同步更新對應的粒子解集；

步驟6：判斷是否滿足收斂判據，若迭代次數滿足設定的迭代值，則停止迭代，否則轉到步驟3繼續執行；

步驟7：循環結束，輸出最終的目標函數值與粒子解集，得到結果。

5 實驗結果與分析

選區激光熔化金屬3D打印步驟如下：1)設計模型；2)將模型轉化為打印機能識別的Gcode代碼；3)將代碼輸入打印機開始打印；4)鋪粉器將金屬粉末鋪至打印工作臺；5)激光器將金屬粉末融化后完成一層的打印；6)每完成一層的打印，打印平臺會便下降一層的高度，直至打印完成。3D打印實例如圖2所示。

圖2 批次調度實例

5.1 實驗算例

面向多機器多任務的3D打印調度問題，實驗任務設置為在2個不同的機器完成6個不同的部件打印任務，使得生產成本最優，其中要求部件P4不可在機器M2上加工。

實驗數據中部件與機器的相關數據來自 Exeter’s ORE-Repository數據集，該數據集可供永久訪問。此外，根據實際生產應用情況，增加機器單位體積損耗參數。需加工部件相關參數如表2所示，機器相關參數如表3所示。

表2 部件參數信息

表3 機器參數信息

經過分析，部件P2的高度大于機器M1的支持最大高度，部件P3的高度大于機器M1的支持最大高度，底面積大于M1的工作臺面積，部件P4明確要求在機器M2上完成，因此在調度過程中，基于約束條件，部件P2、P3不可分配給機器M1，部件P5在調度過程中不可分配給機器M2。

實驗仿真環境為Windows 10操作系統，采用python3.8實現算法的編程。在該算例中，總的部件數P為6，機器數M為2。基于改進粒子群算法，在python3.8環境下運行，將算例中的數據代入進行了30次獨立的運行搜索，經過多次迭代最終得到了最優方案及最優單位體積平均成本。

具體參數設置如下：粒子群種群數PN為50，迭代次數IN為300，學習因子c1=2、c2=2，慣性權重ωini=0.9，ωend=0.4。

初始化過程中，求得各部件在各機器上的單位體積平均成本如表4所示，由于不滿足約束條件，部件P2、P3不可分配給機器M1，部件P4在調度過程中不可分配給機器M2，相應位置的目標值為空。則其中的一個可行解為：

機器M1 [P1]、[P4]、[P5]、[P6]

機器M2 [P2]、[P3]

該調度方案表示各部分單獨在機器上打印，取單位體積平均成本低的作為加工機器。由此計算出總單位體積平均成本為4.632 5 GBP/cm3，即適應度初始值為4.632 5 GBP/cm3。

表4 各單位體積平均成本

5.2 實驗結果

經過粒子群算法300次迭代，不斷更新個體最優值與全局最優值，式(8)、式(9)更新粒子的速度矢量與位置矢量，最終最優方案結果如表5所示。

表5 最優調度方案

即調度方案為：

機器M1 [p1]、[p4,p5]

機器M2 [p2,p3,p6]

在機器M1上完成部件P1的單獨加工與部件P4、P5的組合加工的2個作業，在機器M2上完成部件P2、P3、P6的組合加工1個作業，其對應的單位體積平均成本為4.531 2 GBP/cm3。

最佳調度方案與一部分其他調度方案對比的單位體積平均成本減少量如表6所示。

表6 最優調度方案與其他方案對比

在30次計算中，有22次達到最優，證明了方法的可靠性。面向多機器多任務的3D打印調度問題，采用上述最優調度方案進行部件與機器的調度，最終比單獨打印加工的單位體積平均成本(初始值)4.632 5 GBP/cm3降低了0.101 3GBP/cm3，較其他調度方案均降低了單位體積平均成本，因此認為提出的基于改進粒子群算法的面向多機器多任務的3D打印智能調度方法是有效且實用的，較好地降低了生產成本，提高3D打印機的利用效率。

6 結束語

針對批量3D打印成本高，多機器多任務的3D打印批次調度復雜的問題，建立以最小單位體積平均成本為目標的優化模型，并提出一種基于改進粒子群算法的智能調度方法求解該模型。實驗結果表明該模型方法能有效解決面向多機器多任務的3D打印調度問題，合理的調度序列有效地降低了完成訂單的總成本，有利于提高工廠的打印效率，以更低的成本為客戶提供服務，有利于3D打印技術的推廣。隨著3D打印技術的不斷發展，未來的3D打印調度問題將越來越復雜，在成本最優化問題上的研究也將更加深入。未來將在此基礎上結合實際工廠完成訂單情況，更加

深入的分析，以解決更復雜的問題。同時深入研究面向多機器多任務的3D打印調度問題，與其他智能優化算法進行對比，進一步分析算法能力，提高算法搜索能力。