基于改進(jìn)粒子群算法的多機(jī)器多任務(wù)3D打印智能調(diào)度方法

周明霞，張夢(mèng)娜，李宇，吳 川，張 瀟

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

0 引言

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

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

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

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

以下章節(jié)劃分：第1章首先介紹國(guó)內(nèi)外研究現(xiàn)狀，總結(jié)了目前對(duì)于面向多機(jī)器多任務(wù)的3D打印調(diào)度問題研究較少，成本最優(yōu)又在實(shí)際生產(chǎn)中扮演重要角色，因此研究該問題十分必要。在第2章闡述研究的多機(jī)器多任務(wù)的3D打印調(diào)度問題，并在第3章給出數(shù)學(xué)模型?？紤]實(shí)際生產(chǎn)場(chǎng)景，分析打印工場(chǎng)，結(jié)合生產(chǎn)流程，建立單位體積成本模型，在第4章中闡述如何具體應(yīng)用改進(jìn)粒子群算法尋找單位體積平均成本最優(yōu)化，解決面向多機(jī)器多任務(wù)的3D打印調(diào)度問題。第5章中，基于具體的一個(gè)實(shí)驗(yàn)算例，給出基于改進(jìn)粒子群算法的3D打印智能調(diào)度方法的實(shí)驗(yàn)結(jié)果與分析。最后在第6章中進(jìn)行總結(jié)。

1 國(guó)內(nèi)外研究現(xiàn)狀

智能制造一詞，20世紀(jì)末最早起源于美國(guó)，自此世界多國(guó)投入智能制造的研究[7]。3D打印是智能制造領(lǐng)域的重要部分，它是以計(jì)算機(jī)三維設(shè)計(jì)模型為直接驅(qū)動(dòng)，目前我國(guó)3D打印處于快速發(fā)展階段[8]。

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

同時(shí)，對(duì)成本模型內(nèi)部具體架構(gòu)研究較少，階段安排打印批次容易陷入局部最優(yōu)問題。L.Rickenbacher等人提出的成本模型未應(yīng)用解決實(shí)際生產(chǎn)問題，但發(fā)現(xiàn)同時(shí)構(gòu)建多個(gè)部件，將大大減少任務(wù)完成時(shí)間，從而使得成本降低[11]。Uzsoy等人提出了面向工件尺寸不同的單機(jī)調(diào)度問題，同一批次的工件加工時(shí)間取決于該批次中加工時(shí)間最長(zhǎng)的工件[12]，同時(shí)同一批次的工件需滿足機(jī)器的容量限制。食品加工、半導(dǎo)體芯片老化測(cè)試等符合該問題的特征[13]。

多機(jī)器多任務(wù)的3D打印調(diào)度是一個(gè)難以解決的問題，如何將部件更高效合適的分配進(jìn)入機(jī)器與批次是難以確定的，特別當(dāng)一個(gè)新的部件加入批次時(shí)，部件的成本與加工時(shí)間都將發(fā)生變化，由此結(jié)合實(shí)際生產(chǎn)問題，在批量3D打印調(diào)度中，成本不易控制，難以確定哪個(gè)零件在哪個(gè)機(jī)器上生產(chǎn)。因此，研究多機(jī)器多任務(wù)的3D打印調(diào)度問題并提出一易實(shí)施高效率的方法是十分必要的。

2 多機(jī)器多任務(wù)的3D打印調(diào)度問題闡述

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

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

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

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

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

hj=max{hp},p∈Pmj

(1)

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

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

3 單位體積平均成本最優(yōu)化模型

為了方便表述搭建的研究多機(jī)器多任務(wù)的3D打印調(diào)度問題模型，表1給出構(gòu)建解決問題的數(shù)學(xué)模型所用的符號(hào)及其定義。

表1 符號(hào)及其定義

每個(gè)部件包含部件高度h、體積v以及底面積s共3個(gè)參數(shù)信息，機(jī)器包含支持的最大高度H、工作臺(tái)面積S兩個(gè)約束參數(shù)，為保證部件打印完整與準(zhǔn)確，在調(diào)度過程中，需滿足以下約束：

1)當(dāng)一個(gè)作業(yè)的任意一個(gè)部件分配給一個(gè)機(jī)器時(shí)，該作業(yè)必須全部分配在該機(jī)器上；

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

max{hp·Xjp·Ymj}≤H

(2)

3)同一作業(yè)中打印的部件的底面積之和需小于該機(jī)器工作臺(tái)的面積，否則不可調(diào)度安排在該機(jī)器上。

(3)

4)每個(gè)部件之間相互獨(dú)立，每臺(tái)機(jī)器之間相互獨(dú)立，任何一臺(tái)機(jī)器的工作情況不影響其他機(jī)器。

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

在這一模型中，機(jī)器相關(guān)系統(tǒng)參數(shù)已知。每個(gè)部件需且僅需打印一次，對(duì)機(jī)器加工多少部件沒有要求。

P個(gè)部件在M個(gè)機(jī)器上的總成本計(jì)算公式為：

MTC×Tah×hj+Tn×Cp+W

(4)

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

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

為研究面向多機(jī)器多任務(wù)的3D打印調(diào)度問題，在合理調(diào)度完成部件的打印任務(wù)基礎(chǔ)上，提出構(gòu)建單位體積平均成本最小化的函數(shù)如下：

(5)

綜上，面向多機(jī)器多任務(wù)的3D打印調(diào)度問題，構(gòu)建考慮上述單位體積平均成本的模型，模型建立如下：

(6)

4 基于改進(jìn)粒子群算法的問題求解

4.1 粒子群算法

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

粒子群算法思想容易簡(jiǎn)單且只需調(diào)整少量參數(shù)便可實(shí)現(xiàn)，目前已廣泛應(yīng)用于優(yōu)化問題[18]。粒子群算法通過一群無質(zhì)量的獨(dú)立粒子來代表鳥類，每個(gè)粒子僅有位置矢量與速度矢量?jī)蓚€(gè)參數(shù)，以表示粒子所處的位置以及運(yùn)動(dòng)的速度、方向[19]。在智能優(yōu)化過程中，每個(gè)粒子單獨(dú)尋找最優(yōu)解，并記錄下來，根據(jù)適應(yīng)度即目標(biāo)函數(shù)值的不斷更新，經(jīng)過粒子群之間的位置信息以及目標(biāo)函數(shù)值的共享，記錄當(dāng)前個(gè)體的最優(yōu)值Pbest及全局最優(yōu)值Gbest。經(jīng)過算法的不斷迭代，粒子群們向最優(yōu)位置移動(dòng)，最終得出全局最優(yōu)解與位置。

面向多機(jī)器多任務(wù)的3D打印調(diào)度問題，嘗試在編碼方式及更新策略上進(jìn)行針對(duì)性改進(jìn)。首先采用了十進(jìn)制順序二維編碼方式表示問題的解，并在更新策略上應(yīng)用線性遞減權(quán)值的動(dòng)態(tài)ω來調(diào)整全局與局部的搜索能力。

4.2 編碼與解碼方案

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

假設(shè)一工廠接到10個(gè)部件的訂單，編號(hào)為1,2,3,…，10，可調(diào)用的加工3D打印機(jī)3臺(tái)，編號(hào)為1,2,3，則其中的一個(gè)可行解表示如下：

部件編號(hào) 1 2 3 4 5 6 7 8 9 10

機(jī)器向量 1 3 2 1 1 3 2 1 3 2

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

部件編號(hào)對(duì)應(yīng)的機(jī)器向量值，表示對(duì)應(yīng)的加工機(jī)器編號(hào)，如部件1,4,5,8在機(jī)器1上加工；部件編號(hào)對(duì)應(yīng)的順序向量值，表示部件組成的一個(gè)作業(yè)在對(duì)應(yīng)機(jī)器上的組合加工順序，如機(jī)器1加工的4個(gè)部件加工順序?yàn)閇p1]、[p4,p8]、[p5]，部件4與8作為一個(gè)作業(yè)放入機(jī)器1加工，機(jī)器1需加工4個(gè)部件組成的3個(gè)作業(yè)。

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

機(jī)器1 [p1]、[p4,p8]、[p5]

機(jī)器2 [p3,p7]、[p10]

機(jī)器3 [p2,p9]、[p6]

4.3 種群初始化

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

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

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

4.4 更新策略

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

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

個(gè)體粒子在向最優(yōu)解靠攏時(shí)，一定程度上對(duì)自身軌跡進(jìn)行調(diào)整，開展對(duì)未知領(lǐng)域的探索，此探索能力為全局探索能力。而在原始軌跡上進(jìn)行進(jìn)一步探索的便稱為局部探索能力。為有效防止陷入局部最優(yōu)，采用線性遞減權(quán)值的動(dòng)態(tài)ω來調(diào)整全局與局部的搜索能力。ω又稱為慣性因子，取值為非負(fù)。當(dāng)ω取值較大時(shí)，全局搜索能力較強(qiáng)，而局部搜索能力較弱；當(dāng)ω取值較小時(shí)，全局搜索能力較弱，而局部搜索能力較強(qiáng)。一般在實(shí)際應(yīng)用中ω取值由大變小，先全局最優(yōu)搜索至大致范圍，在局部搜索最優(yōu)值，提高效率與準(zhǔn)確率。

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

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

(7)

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

速度更新公式如下：

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

c2×rand()×(Gbesti-xi)

(8)

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

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

位置更新公式如下：

xi+1=xi+vi+1

(9)

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

基于前文建立的面向多機(jī)器多任務(wù)的3D打印調(diào)度問題的數(shù)學(xué)模型，算法中的適應(yīng)度函數(shù)為單位體積平均成本函數(shù)。在迭代過程中，不斷比較適應(yīng)度，并將更小的單位體積成本值更新為全局最優(yōu)值。

4.5 收斂依據(jù)

優(yōu)化收斂停止準(zhǔn)則一般有兩種，一是設(shè)置最大迭代次數(shù)，二是達(dá)到可接受的滿意適應(yīng)度值，設(shè)置上一次最優(yōu)化適應(yīng)度值與更新后的最優(yōu)化適應(yīng)度值之間的差值小于某個(gè)值停止迭代，即達(dá)到收斂要求[22]。本研究設(shè)置收斂判據(jù)為迭代次數(shù)是否到達(dá)到300次，達(dá)到收斂判據(jù)后，便退出循環(huán)，輸出結(jié)果。

4.6 算法流程

面向多機(jī)器多任務(wù)的3D打印調(diào)度問題，基于改進(jìn)的粒子群算法，將目標(biāo)函數(shù)設(shè)置為單位體積平均成本，考慮機(jī)器工作臺(tái)底面積與支持的最大高度及其他約束，通過不斷迭代優(yōu)化最終得到單位體積成本最優(yōu)值及最優(yōu)調(diào)度方案。

算法的流程如圖1所示。

圖1 改進(jìn)粒子群算法流程圖

算法的詳細(xì)步驟如下：

步驟1：依據(jù)調(diào)度原則，在考慮約束的情況下，初始化粒子群及參數(shù)設(shè)置，包括粒子數(shù)PN，迭代次數(shù)IN，學(xué)習(xí)因子c1、c2，慣性權(quán)重ω，最大粒子速度等；

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

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

步驟4：對(duì)更新后的粒子進(jìn)行編碼解碼，更新適應(yīng)度單位體積成本值，更新種群；

步驟5：與之前存儲(chǔ)的單位體積成本比較，更新個(gè)體最優(yōu)值Pbest和全局最優(yōu)值Gbest，將更優(yōu)的目標(biāo)函數(shù)值更新，同步更新對(duì)應(yīng)的粒子解集；

步驟6：判斷是否滿足收斂判據(jù)，若迭代次數(shù)滿足設(shè)定的迭代值，則停止迭代，否則轉(zhuǎn)到步驟3繼續(xù)執(zhí)行；

步驟7：循環(huán)結(jié)束，輸出最終的目標(biāo)函數(shù)值與粒子解集，得到結(jié)果。

5 實(shí)驗(yàn)結(jié)果與分析

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

圖2 批次調(diào)度實(shí)例

5.1 實(shí)驗(yàn)算例

面向多機(jī)器多任務(wù)的3D打印調(diào)度問題，實(shí)驗(yàn)任務(wù)設(shè)置為在2個(gè)不同的機(jī)器完成6個(gè)不同的部件打印任務(wù)，使得生產(chǎn)成本最優(yōu)，其中要求部件P4不可在機(jī)器M2上加工。

實(shí)驗(yàn)數(shù)據(jù)中部件與機(jī)器的相關(guān)數(shù)據(jù)來自 Exeter’s ORE-Repository數(shù)據(jù)集，該數(shù)據(jù)集可供永久訪問。此外，根據(jù)實(shí)際生產(chǎn)應(yīng)用情況，增加機(jī)器單位體積損耗參數(shù)。需加工部件相關(guān)參數(shù)如表2所示，機(jī)器相關(guān)參數(shù)如表3所示。

表2 部件參數(shù)信息

表3 機(jī)器參數(shù)信息

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

實(shí)驗(yàn)仿真環(huán)境為Windows 10操作系統(tǒng)，采用python3.8實(shí)現(xiàn)算法的編程。在該算例中，總的部件數(shù)P為6，機(jī)器數(shù)M為2?；诟倪M(jìn)粒子群算法，在python3.8環(huán)境下運(yùn)行，將算例中的數(shù)據(jù)代入進(jìn)行了30次獨(dú)立的運(yùn)行搜索，經(jīng)過多次迭代最終得到了最優(yōu)方案及最優(yōu)單位體積平均成本。

具體參數(shù)設(shè)置如下：粒子群種群數(shù)PN為50，迭代次數(shù)IN為300，學(xué)習(xí)因子c1=2、c2=2，慣性權(quán)重ωini=0.9，ωend=0.4。

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

機(jī)器M1 [P1]、[P4]、[P5]、[P6]

機(jī)器M2 [P2]、[P3]

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

表4 各單位體積平均成本

5.2 實(shí)驗(yàn)結(jié)果

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

表5 最優(yōu)調(diào)度方案

即調(diào)度方案為：

機(jī)器M1 [p1]、[p4,p5]

機(jī)器M2 [p2,p3,p6]

在機(jī)器M1上完成部件P1的單獨(dú)加工與部件P4、P5的組合加工的2個(gè)作業(yè)，在機(jī)器M2上完成部件P2、P3、P6的組合加工1個(gè)作業(yè)，其對(duì)應(yīng)的單位體積平均成本為4.531 2 GBP/cm3。

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

表6 最優(yōu)調(diào)度方案與其他方案對(duì)比

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

6 結(jié)束語(yǔ)

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

深入的分析，以解決更復(fù)雜的問題。同時(shí)深入研究面向多機(jī)器多任務(wù)的3D打印調(diào)度問題，與其他智能優(yōu)化算法進(jìn)行對(duì)比，進(jìn)一步分析算法能力，提高算法搜索能力。