考慮零件構(gòu)建方向的增材制造單機(jī)調(diào)度研究

黃 彬，肖彥楷

(福州大學(xué)機(jī)械工程及自動(dòng)化學(xué)院，福建 福州 350108)

增材制造(additive manufacturing，AM)技術(shù)是通過(guò)逐層添加材料的方式制造實(shí)體零件的技術(shù)[1]。作為一種不需要傳統(tǒng)的刀具、夾具、模具以及多道加工工序的新興智能制造技術(shù)，增材制造對(duì)解決復(fù)雜結(jié)構(gòu)物體的加工難題、縮短新產(chǎn)品的研發(fā)周期具有極大的幫助。以往增材制造的研究主要集中于材料、設(shè)備、工藝及精度等方面，近年來(lái)，對(duì)增材制造生產(chǎn)調(diào)度的研究引起了國(guó)內(nèi)外學(xué)者的重視。

在增材制造技術(shù)中，選擇性激光熔融(selective laser melting，SLM)工藝因?yàn)槠渚邆渲圃炜芍苯邮褂媒饘倭悴考哪芰?，是目前發(fā)展最快、應(yīng)用前景最好的技術(shù)之一。面向SLM工藝的生產(chǎn)調(diào)度研究中，Li等[2]建立了以最小化平均成本為目標(biāo)的調(diào)度模型；Chergui等[3]建立了以最小化拖期時(shí)間為目標(biāo)的增材制造調(diào)度模型；Kucukkoc等[4]以最小化最大完工時(shí)間為目標(biāo)，研究了面向SLM工藝的調(diào)度問(wèn)題；Fera等[5]建立了以最小化生產(chǎn)成本以及提前期/拖期為目標(biāo)的單機(jī)調(diào)度模型。

上述研究考慮了零件體積、機(jī)器容積、交貨期等因素，且假設(shè)零件只有單一的構(gòu)建(打印)方向。文獻(xiàn)[6]表明，零件在滿足工藝以及客戶需求時(shí)，通常有多種構(gòu)建方向可供選擇，而不同構(gòu)建方向的組合對(duì)零件加工時(shí)間會(huì)有很大的影響，因此有必要研究考慮零件構(gòu)建方向的增材制造調(diào)度問(wèn)題。本文在綜合考慮零件構(gòu)建方向、交貨期的前提下，研究面向SLM工藝的AM機(jī)器的單機(jī)調(diào)度問(wèn)題，提出了以最小化零件單位體積生產(chǎn)成本為優(yōu)化目標(biāo)的數(shù)學(xué)模型，并設(shè)計(jì)了一種改進(jìn)分布估計(jì)算法對(duì)模型進(jìn)行求解。

1 問(wèn)題描述及調(diào)度模型

1.1 問(wèn)題描述

與傳統(tǒng)機(jī)器加工不同，來(lái)自于不同訂單，不同形狀、尺寸和交貨期的零件可同時(shí)在一臺(tái)AM機(jī)器上加工。本文將同時(shí)在同一AM機(jī)器上的零件加工定義為一個(gè)作業(yè)，作業(yè)的完工時(shí)間取決于作業(yè)內(nèi)最后一個(gè)零件的完工時(shí)間。在滿足一定條件的情況下(足夠的有效生產(chǎn)面積，交貨期等)，一個(gè)作業(yè)可能包含多個(gè)不同的零件，一般每個(gè)零件至少有一個(gè)備選構(gòu)建方向。由于不同的零件構(gòu)建方向?qū)?dǎo)致零件加工時(shí)的最大高度不同和在AM機(jī)器上的投影面積不同，進(jìn)而影響到作業(yè)內(nèi)零件的數(shù)目，導(dǎo)致加工時(shí)間和成本不同，因此零件分配前要明確零件的備選構(gòu)建方向。當(dāng)采用不同的零件分配方案時(shí)，作業(yè)的數(shù)目有可能改變。

增材制造作業(yè)總成本由零件的最大高度和總體積決定，因此不同零件組合成的作業(yè)的生產(chǎn)成本不同，且相同零件組合成的作業(yè)在不同的構(gòu)建方向下的生產(chǎn)成本也不相同。一個(gè)作業(yè)內(nèi)安排的零件越多，必然導(dǎo)致作業(yè)的加工時(shí)間越長(zhǎng)，但可以減少總作業(yè)數(shù)目以減少機(jī)器準(zhǔn)備時(shí)間(布置作業(yè)以及清理時(shí)間)，并且多個(gè)零件還可以均分零件分層時(shí)間(分層時(shí)間由作業(yè)內(nèi)零件最大高度決定)所導(dǎo)致的成本；而作業(yè)內(nèi)零件較少時(shí)，零件可以選取高度較低、投影面積較大的構(gòu)建方向以降低成本，但這勢(shì)必增加多個(gè)作業(yè)帶來(lái)的機(jī)器準(zhǔn)備時(shí)間以及額外的零件分層時(shí)間，降低機(jī)器利用率。因此增材制造的單機(jī)調(diào)度要求在一定的優(yōu)化目標(biāo)下，將所有訂單中的零件拆分到幾個(gè)作業(yè)并依照一定的加工順序分配到一臺(tái)AM機(jī)器中，從而找到一種可行的調(diào)度方案。

1.2 調(diào)度模型

1.2.1模型假設(shè)

面向SLM工藝的增材制造單機(jī)調(diào)度問(wèn)題，做以下假設(shè)：1)加工過(guò)程中只考慮一種制造材料；2)作業(yè)的零件之間不會(huì)相互接觸，且不考慮零件之間的嵌套問(wèn)題(嵌套指在一定條件下，小零件可放在大零件的孔隙中或斜面下)；3)為了保證零件質(zhì)量，零件在加工平臺(tái)上僅放置一層；4)所有零件的備選構(gòu)建方向均能滿足質(zhì)量要求，并且都可放置于AM機(jī)器的生產(chǎn)區(qū)域內(nèi)；5)生產(chǎn)過(guò)程中，機(jī)器具有固定的加工速度、層厚度參數(shù)及單位人工成本、作業(yè)生產(chǎn)準(zhǔn)備時(shí)間。

1.2.2數(shù)學(xué)模型

定義以下變量符號(hào)：Ii為第i個(gè)零件(i=1,…,m)；Jj為第j個(gè)作業(yè)(j=1,…,n)；Kik為第i個(gè)零件的第k個(gè)備選構(gòu)建方向(k=1,…,M)；hik為第i個(gè)零件在第k個(gè)備選構(gòu)建方向的高度；aik為第i個(gè)零件在第k個(gè)備選構(gòu)建方向在生產(chǎn)區(qū)域的投影面積(包含了一定的裕度，以避免零件接觸)；Vi為第i個(gè)零件的體積；A為機(jī)器的生產(chǎn)區(qū)域面積；ts為機(jī)器的準(zhǔn)備時(shí)間；th為單位高度的分層時(shí)間；tV為單位體積材料的加工時(shí)間；Ct為單位時(shí)間機(jī)器的運(yùn)行成本；CH為單位時(shí)間的人工成本；Dj為第j個(gè)作業(yè)的交貨期，等于作業(yè)內(nèi)所有零件交貨期的最小值；hmax(j)為第j個(gè)作業(yè)內(nèi)零件的最大高度；C為所有作業(yè)零件的單位體積生產(chǎn)成本；xij為反映零件i是否放入作業(yè)j的二進(jìn)制決策變量，yik為反映零件i是否選擇備選機(jī)構(gòu)建方向k的二進(jìn)制決策變量；zj為反映作業(yè)j是否被安排生產(chǎn)的二進(jìn)制決策變量。

由上可得，作業(yè)j零件的生產(chǎn)成本Cj為：

Cj=(tg(j)+tp(j))Ct+(ts+tg(j)+tp(j))CH

(1)

(2)

tp(j)=thhmax(j)

(3)

式中：tg(j)為作業(yè)j生產(chǎn)時(shí)加工材料的時(shí)間(激光頭的運(yùn)動(dòng)時(shí)間)；tp(j)為作業(yè)j生產(chǎn)時(shí)的分層時(shí)間。

作業(yè)j的完工時(shí)間tj為：

tj=tj-1+tp(j)+tg(j)+ts,t0=0

(4)

以最小化所有作業(yè)零件的單位體積生產(chǎn)成本為優(yōu)化目標(biāo)的增材制造單機(jī)調(diào)度問(wèn)題可以描述為如下模型：

(5)

(6)

(7)

(8)

zj-zj+1≥0

(9)

(10)

tj-Dj≤0

(11)

式(5)為最小化所有作業(yè)零件單位體積生產(chǎn)成本的目標(biāo)函數(shù)；式(6)表示一個(gè)零件最多只能安排在一個(gè)作業(yè)中；式(7)表示每個(gè)零件生產(chǎn)時(shí)只能選擇一個(gè)備選構(gòu)建方向；式(8)表示每個(gè)作業(yè)只能生產(chǎn)一次，不能重復(fù)生產(chǎn)，且所有作業(yè)都需要完成；式(9)表示作業(yè)按照先后順序加工；式(10)表示每個(gè)作業(yè)內(nèi)零件的總投影面積要小于機(jī)器總生產(chǎn)面積；式(11)保證作業(yè)的交貨期。

2 模型求解的改進(jìn)分布估計(jì)算法

2.1 分布估計(jì)算法(EDA)

分布估計(jì)算法(estimation of distribution algorithm，EDA)是一種基于統(tǒng)計(jì)學(xué)原理的隨機(jī)群體優(yōu)化算法[7]，該算法具有較強(qiáng)的全局收斂能力和較快的收斂速度。以二進(jìn)制編碼問(wèn)題為例，算法中解空間分布的概率模型可以使用一個(gè)概率向量ρ(g)表示：

ρ(g)=[ρ1(g),ρ2(g),…,ρn(g)]T

(12)

式中：ρi(g)為在第g次迭代中個(gè)體的第i個(gè)基因位置上取值為1的概率。在本文模型中，基因位置i代表采用某個(gè)構(gòu)建方向的零件i。

(13)

式中：α為學(xué)習(xí)速率，α∈(0,1)。

2.2 改進(jìn)的分布估計(jì)算法(IEDA)

2.2.1編碼方式

算法中作業(yè)所包含的零件組合以及其對(duì)應(yīng)的構(gòu)建方向都采用自然數(shù)編碼方式，即Jj=[I1,I2,…,Ii]，Kj=[K1k,K2k,…,Kik]，1≤i≤m，1≤k≤M。Jj表示作業(yè)j內(nèi)所包含的零件組合，Kj表示作業(yè)j內(nèi)各零件構(gòu)建方向的組合。

一個(gè)生產(chǎn)流程通常包括多個(gè)作業(yè)，稱為作業(yè)組，可表示為J=[J1J2…Jj]T。

由于一個(gè)作業(yè)能容納多少零件是由零件所占的生產(chǎn)面積決定的，因此每個(gè)作業(yè)的零件數(shù)不一定相同。每個(gè)作業(yè)內(nèi)的零件具有固定的構(gòu)建方向，作業(yè)組的構(gòu)建方向矩陣可表示為K=[K1K2…Kj]T。

2.2.2概率模型及其更新

概率模型及其更新機(jī)制是設(shè)計(jì)分布估計(jì)算法的關(guān)鍵。本文采用m×M的ρ(g)作為概率模型，表征各零件選取各備選構(gòu)建方向的概率，如式(14)所示：

(14)

式中：ρik(g)為第g次迭代中零件i選擇第k個(gè)備選構(gòu)建方向的概率，矩陣每行的元素之和為1。顯然本文中ρ(g)所產(chǎn)生的每個(gè)個(gè)體都有m個(gè)隨機(jī)采用構(gòu)建方向k(1≤k≤M)的零件。

為保證算法初始階段對(duì)解空間的均勻采樣，初始概率分布取均勻分布，同時(shí)在每次迭代中選取適應(yīng)度值最優(yōu)的前10%個(gè)體作為更新概率模型的依據(jù)，使用Heb規(guī)則更新概率矩陣，如式(15)所示：

(15)

2.2.3適應(yīng)度函數(shù)

本文構(gòu)造的適應(yīng)度函數(shù)Fitness如下：

Fitness=C+F(x)

(16)

式中：C為目標(biāo)函數(shù)；F(x)為懲罰函數(shù)。當(dāng)作業(yè)滿足式(6)～(11)的所有約束時(shí)，F(xiàn)(x)等于0；否則，F(xiàn)(x)為足夠大的正值。

2.2.4鄰域搜索策略

由于EDA局部搜索能力較差，因此本文引入一種鄰域搜索機(jī)制設(shè)計(jì)一種IEDA來(lái)求解上述調(diào)度問(wèn)題。在已知零件作業(yè)分組的情況下，對(duì)原精英種群內(nèi)每個(gè)作業(yè)內(nèi)零件的構(gòu)建方向進(jìn)行搜索，降低作業(yè)內(nèi)零件的最大高度，可以較好地彌補(bǔ)EDA算法的不足，提高收斂效率。具體流程如下：

1)判斷作業(yè)j中最高的零件，記為Imax。如果Imax當(dāng)前的構(gòu)建方向是其所有備選構(gòu)建方向中高度最小的構(gòu)建方向，則轉(zhuǎn)至步驟5)；如果Imax存在其他高度更小且投影面積位于作業(yè)剩余生產(chǎn)區(qū)域面積內(nèi)的備選構(gòu)建方向可供選擇時(shí)，則進(jìn)行步驟2)；如果Imax由于作業(yè)剩余生產(chǎn)區(qū)域面積不足而無(wú)法選擇其他高度更小的備選構(gòu)建方向時(shí)，轉(zhuǎn)至步驟3)。

2)選取Imax可供選擇的備選構(gòu)建方向中高度最小的構(gòu)建方向，返回步驟1)。

3)判斷除Imax外的其他零件是否存在投影面積比其當(dāng)前構(gòu)建方向的投影面積小且高度不高于Imax的備選構(gòu)建方向，如果存在則進(jìn)行步驟4)；如果不存在轉(zhuǎn)至步驟5)。

4)隨機(jī)選取步驟3)中可選零件中的一個(gè)零件，改變其構(gòu)建方向，選取一個(gè)投影面積小于它當(dāng)前投影面積且高度不高于Imax高度的備選構(gòu)建方向。返回步驟1)。

5)如果j達(dá)到最大值，轉(zhuǎn)至步驟6)；否則j←j+1，轉(zhuǎn)至步驟1)。

6)根據(jù)式(16)計(jì)算并對(duì)比經(jīng)過(guò)局部搜索后的各作業(yè)組的適應(yīng)度值，用適應(yīng)度值最優(yōu)的作業(yè)組取代精英種群中的原作業(yè)組。

2.3 算法流程

1)生成初始種群和概率模型，令迭代代數(shù)iter=1，根據(jù)式(16)計(jì)算各作業(yè)組的適應(yīng)度值；

2)選擇適應(yīng)度值最優(yōu)的前10%的個(gè)體作為精英群體；

3)對(duì)精英群體進(jìn)行鄰域搜索；

4)根據(jù)式(15)更新概率模型(式(14))；

5)根據(jù)概率模型對(duì)精英種群采樣生成新種群；

6)如果iter已經(jīng)達(dá)到最大值，轉(zhuǎn)至步驟7)；否則令iter←iter+1，轉(zhuǎn)至步驟2)；

7)輸出最優(yōu)解。

3 算例

某企業(yè)需用一臺(tái)AM機(jī)器加工一批零件，每個(gè)零件的體積、交貨期、備選構(gòu)建方向及相應(yīng)的投影面積及最大高度見表1，AM機(jī)器參數(shù)見表2。

表1 零件的尺寸及其交貨期

續(xù)表

表2 AM機(jī)器的參數(shù)

在同一臺(tái)式機(jī)上，分別運(yùn)行EDA和IEDA算法各300次求解本文調(diào)度問(wèn)題，算法的最大迭代代數(shù)為50，種群大小為50。兩者的優(yōu)化結(jié)果對(duì)比見表3，由表3可以看出，IEDA的收斂穩(wěn)定性比EDA更好，收斂率更高。求得的最優(yōu)作業(yè)分配為[1,2,3,0;4,5,6,7;8,9,10,0]，相對(duì)應(yīng)的構(gòu)建方向?yàn)閇3,3,1,0;4,1,3,2;4,3,3,0]。即1,2,3為第一個(gè)作業(yè)，4,5,6,7為第二個(gè)作業(yè)，8,9,10為第三個(gè)作業(yè)；零件1選擇其編號(hào)3的構(gòu)建方向，零件2選擇其編號(hào)3的構(gòu)建方向……零件10選擇其編號(hào)為3的構(gòu)建方向。本調(diào)度方案的每立方厘米材料的加工成本為21.374 3元，各作業(yè)的完成時(shí)間分別為77.674 4 h、108.211 0 h和44.379 1 h。

表3 EDA與IEDA優(yōu)化結(jié)果對(duì)比

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

本文面向選擇性激光熔融工藝，建立了以最小化所有零件單位體積生產(chǎn)成本為優(yōu)化目標(biāo)的單機(jī)調(diào)度模型，以解決考慮零件構(gòu)建方向的增材制造生產(chǎn)調(diào)度問(wèn)題，并引入鄰域搜索策略對(duì)標(biāo)準(zhǔn)分布估計(jì)算法進(jìn)行改進(jìn)，設(shè)計(jì)了一種改進(jìn)分布估計(jì)算法求解本文的調(diào)度問(wèn)題。算例分析表明該方法可行、有效，為增材制造生產(chǎn)調(diào)度的研究提供了一種新的方法和途徑。