打印參數(shù)可變模式下3D打印批調(diào)度問(wèn)題研究

王 彬 唐 昊 戴 飛 譚 琦

(1.合肥工業(yè)大學(xué)電氣與自動(dòng)化工程學(xué)院,安徽合肥 230009;2.工業(yè)自動(dòng)化安徽省工程技術(shù)研究中心,安徽合肥 230009)

1 引言

3D打印技術(shù)被稱為“具有工業(yè)革命意義的制造技術(shù)”,是制造領(lǐng)域中一項(xiàng)正在飛速發(fā)展的新興制造技術(shù).采用3D打印技術(shù)進(jìn)行生產(chǎn)的主要流程是:應(yīng)用3D模型設(shè)計(jì)軟件設(shè)計(jì)出打印件的立體模型,然后通過(guò)3D打印設(shè)備,用液化、粉末化、絲化的打印材料逐層堆積“打印”出打印件[1].隨著網(wǎng)絡(luò)技術(shù)與先進(jìn)制造技術(shù)結(jié)合得越來(lái)越緊密,一種通過(guò)物聯(lián)網(wǎng)將3D打印設(shè)備接入制造網(wǎng)絡(luò),接收客戶設(shè)計(jì)的3D打印件模型進(jìn)行打印的網(wǎng)絡(luò)化制造系統(tǒng)被提出[2],并在實(shí)際生產(chǎn)中開(kāi)始廣泛應(yīng)用.但現(xiàn)階段3D打印產(chǎn)業(yè)處于發(fā)展階段,設(shè)備資源比較短缺,因此,針對(duì)這種打印任務(wù)隨機(jī)的3D打印服務(wù)系統(tǒng),如何提高系統(tǒng)的處理率是急需解決的問(wèn)題.

針對(duì)該問(wèn)題,已有學(xué)者為了減少設(shè)備預(yù)熱時(shí)間、工作臺(tái)調(diào)整時(shí)間和打印完成后設(shè)備冷卻時(shí)間[3],研究了3D打印批次規(guī)劃問(wèn)題[4].該問(wèn)題可歸類為工件尺寸不同的單機(jī)批調(diào)度問(wèn)題,對(duì)該問(wèn)題的相關(guān)研究成果較多.例如,Ikura等人首先提出單機(jī)單工件簇的批處理優(yōu)化控制問(wèn)題[5].Lee等進(jìn)一步研究了多工件簇的單機(jī)批處理優(yōu)化問(wèn)題[6],且已有學(xué)者提出采用微粒群算法和改進(jìn)蟻群算法可對(duì)問(wèn)題進(jìn)行求解[7–8].同時(shí)根據(jù)各批次加工時(shí)間與批中工件的關(guān)系,該類批調(diào)度問(wèn)題可分為3類,第1類假定各批次加工時(shí)間與批中工件無(wú)關(guān)[9];第2類假定各批次加工時(shí)間取決于批中最大工件[10];第3類則假定各批次的加工時(shí)間為批中工件的加工時(shí)間之和[11].由于3D打印過(guò)程中掃描填充時(shí)間與所選批中打印件的總體積成正比,而層間調(diào)整所需時(shí)間取決于批中最高打印件的高度,因此本文研究的問(wèn)題屬于第2類和第3類的結(jié)合.由于打印任務(wù)隨機(jī)到達(dá),因此本文研究的問(wèn)題也屬于在線批調(diào)度優(yōu)化問(wèn)題[12–14].

上述研究主要是對(duì)任務(wù)進(jìn)行調(diào)度以提高系統(tǒng)的處理率.除了對(duì)任務(wù)進(jìn)行調(diào)度外,還可通過(guò)改變服務(wù)率提高系統(tǒng)性能.例如在單站點(diǎn)傳送帶給料生產(chǎn)加工站(conveyor-serviced production station,CSPS)系統(tǒng)的優(yōu)化控制問(wèn)題中,將服務(wù)率作為系統(tǒng)的一個(gè)控制變量,求解系統(tǒng)的最優(yōu)控制策略[15].有學(xué)者進(jìn)一步研究了顧客需求隨機(jī)到達(dá)和服務(wù)率可動(dòng)態(tài)實(shí)時(shí)變化的情況,將系統(tǒng)的最優(yōu)控制問(wèn)題建成半馬爾科夫決策過(guò)程(semi-Markov decision process,SMDP)模型,采用策略迭代算法和Q學(xué)習(xí)算法求解了系統(tǒng)的最優(yōu)控制策略,提高了系統(tǒng)的生產(chǎn)率[16].通過(guò)以上研究可知,通過(guò)動(dòng)態(tài)設(shè)定打印參數(shù),調(diào)整打印速度,以提高系統(tǒng)的處理率[14].

因此,本文研究在打印任務(wù)隨機(jī)到達(dá)情況下,如何根據(jù)任務(wù)到達(dá)情況動(dòng)態(tài)選擇任務(wù)組合以及設(shè)置打印參數(shù),以提高系統(tǒng)的處理率.由于對(duì)打印速度影響最大的是切片參數(shù)層高[17–18],因此本文選擇打印參數(shù)層高作為控制變量.雖然層高設(shè)置的得越大,打印速度越快,但打印出的產(chǎn)品質(zhì)量會(huì)降低[19],如何減少打印質(zhì)量損失,也是本文需要考慮的問(wèn)題.本文根據(jù)系統(tǒng)工作模式和決策過(guò)程的特點(diǎn),以各個(gè)任務(wù)隊(duì)列長(zhǎng)度作為系統(tǒng)聯(lián)合狀態(tài),以任務(wù)組合以及打印參數(shù)層高作為系統(tǒng)的聯(lián)合控制變量,以提高生產(chǎn)率、減少打印質(zhì)量損失、節(jié)約電能為綜合目標(biāo),將該問(wèn)題描述為SMDP模型,采用策略迭代及Q學(xué)習(xí)算法對(duì)系統(tǒng)的最優(yōu)策略進(jìn)行求解.

2 系統(tǒng)組成及決策過(guò)程

如圖1所示,本文研究的對(duì)象是一種3D打印服務(wù)系統(tǒng),主要由存儲(chǔ)打印任務(wù)的任務(wù)隊(duì)列以及單臺(tái)3D打印設(shè)備組成.打印任務(wù)由不同種類的3D打印件模型組成,各類打印任務(wù)按照獨(dú)立的泊松過(guò)程隨機(jī)到達(dá),并自動(dòng)存儲(chǔ)在相應(yīng)的任務(wù)隊(duì)列中,任務(wù)隊(duì)列容量有限.3D 打印設(shè)備以工作臺(tái)作為其打印區(qū)間.系統(tǒng)運(yùn)行時(shí),根據(jù)任務(wù)隊(duì)列中的任務(wù)數(shù)量,選擇進(jìn)行打印的任務(wù)組合,并設(shè)置打印參數(shù)層高,然后對(duì)所選任務(wù)組合進(jìn)行切片處理,再由3D打印設(shè)備逐層累積打印,直至打印完成.因此,系統(tǒng)需要根據(jù)任務(wù)隊(duì)列中的任務(wù)數(shù)量對(duì)進(jìn)行打印的任務(wù)組合和打印參數(shù)層高進(jìn)行決策,在此定義系統(tǒng)的決策時(shí)刻為打印完成時(shí)刻或打印任務(wù)到達(dá)時(shí)刻,其典型決策過(guò)程如下:在決策時(shí)刻,系統(tǒng)根據(jù)當(dāng)前任務(wù)隊(duì)列中的任務(wù)數(shù)量,選擇由各類打印任務(wù)組成的任務(wù)組合并設(shè)置打印參數(shù)層高.若所選組合不包含打印任務(wù),則不進(jìn)行打印操作,等待下一任務(wù)到達(dá),以進(jìn)行下次任務(wù)組合選擇.當(dāng)有任務(wù)到達(dá)時(shí),系統(tǒng)進(jìn)入下一決策時(shí)刻;若所選組合包含打印任務(wù),則從各個(gè)任務(wù)隊(duì)列中選取相應(yīng)個(gè)數(shù)的任務(wù),按照所選打印參數(shù)層高進(jìn)行打印,打印過(guò)程結(jié)束時(shí),系統(tǒng)進(jìn)入下一決策時(shí)刻.本文主要研究如何根據(jù)任務(wù)到達(dá)情況動(dòng)態(tài)選擇任務(wù)組合和層高,以提高系統(tǒng)和系統(tǒng)的生產(chǎn)性能.

圖1 系統(tǒng)的示意圖Fig.1 Physical model of the system

本文的研究主要基于以下假設(shè):

1) 打印任務(wù)服從不同參數(shù)的泊松過(guò)程隨機(jī)到達(dá)并且相互獨(dú)立,打印件所需的打印材料相同;

2) 忽略打印過(guò)程中的熱量散失,噴頭在預(yù)熱和打印時(shí)加熱功率相同且恒定;

3) 忽略在打印同一層時(shí)噴頭的空行時(shí)間;

4) 噴絲截面為矩形,且忽略由于切片誤差產(chǎn)生的打印材料消耗以及打印時(shí)間消耗;

5) 工作臺(tái)每次調(diào)整的時(shí)間相同.

為了方便地進(jìn)行數(shù)學(xué)描述以及進(jìn)行數(shù)學(xué)建模,本文定義了系統(tǒng)的參數(shù)和變量,如表1所示.本文研究的系統(tǒng)由M種打印任務(wù)、M個(gè)任務(wù)隊(duì)列以及一臺(tái)單噴頭的3D打印設(shè)備組成.這M種打印任務(wù)分別代表M種待打印的3D打印件模型,并按照獨(dú)立的泊松分布隨機(jī)到達(dá),記第m種打印任務(wù)的到達(dá)率為λm,這M種打印任務(wù)分別存儲(chǔ)在M個(gè)任務(wù)隊(duì)列中,第m個(gè)任務(wù)隊(duì)列用于存儲(chǔ)第m種打印任務(wù),其隊(duì)列容量為Cm.3D打印件模型的種類根據(jù)底面尺寸om、體積qm和高度hm來(lái)區(qū)分.本文將3D打印件模型的水平投影輪廓最小包絡(luò)矩形作為底面尺寸,記第m種3D打印件模型的底面尺寸為omnm,Length×nm,Width,記其水平投影輪廓最小包絡(luò)矩形的長(zhǎng)和寬分別為nm,Length和nm,Width.一般3D打印設(shè)備的工作臺(tái)為矩形區(qū)域,本文將3D打印設(shè)備的工作臺(tái)作為打印設(shè)備的打印區(qū)域,定義NLength和NWidth為工作臺(tái)的長(zhǎng)和寬.本文以任務(wù)m的隊(duì)列長(zhǎng)度cm作為任務(wù)隊(duì)列的狀態(tài),其狀態(tài)空間為

表1 符號(hào)變量表Table 1 Variable table

現(xiàn)以M個(gè)任務(wù)隊(duì)列的狀態(tài)作為系統(tǒng)的聯(lián)合狀態(tài),記為Sn(c1,···,cm,···,cM),其狀態(tài)空間為

定義在系統(tǒng)狀態(tài)S下采取的行動(dòng)為vS(JS,hS),其中JS為選擇的任務(wù)組合,

jm表示所選任務(wù)組合中第m種打印任務(wù)的個(gè)數(shù),所選任務(wù)組合中各類打印任務(wù)的數(shù)量不超過(guò)隊(duì)列長(zhǎng)度,即jm≤cm≤Cm.hS為設(shè)置的打印參數(shù)層高,其取值范圍為Hmin≤hS≤Hmax.DJS為系統(tǒng)在狀態(tài)S下的可選打印件組合的集合.由于多打印任務(wù)同時(shí)打印時(shí)需要將打印任務(wù)布排到工作臺(tái)上,在已知工作臺(tái)尺寸以及打印件水平投影的最小包絡(luò)矩形條件下,該問(wèn)題屬于矩形件排樣問(wèn)題.在指定空間布排矩形的方法有多種,可根據(jù)問(wèn)題的不同采用不同的方法.對(duì)于復(fù)雜的排樣問(wèn)題可采用多啟發(fā)式算法、粒子群算法等算法[20],對(duì)于簡(jiǎn)單的排樣問(wèn)題可采用Bottom–Left規(guī)則[21].因此本文根據(jù)具體排樣問(wèn)題選擇合適的算法求解得到系統(tǒng)在狀態(tài)S下的可選任務(wù)組合的集合定義系統(tǒng)平穩(wěn)策略為

優(yōu)化目標(biāo)是找到一個(gè)最優(yōu)策略使3D打印服務(wù)系統(tǒng)在長(zhǎng)時(shí)間運(yùn)行情況下代價(jià)最小.

系統(tǒng)狀態(tài)S隨時(shí)間隨機(jī)跳變,記t時(shí)刻的狀態(tài)為St,第n次決策時(shí)刻記為T(mén)n,在決策時(shí)刻Tn時(shí)系統(tǒng)狀態(tài)為簡(jiǎn)記為Sn.在決策時(shí)刻Tn,系統(tǒng)所選任務(wù)組合和層高設(shè)置作為決策行動(dòng).若0,則不進(jìn)行打印操作,等待下一任務(wù)到達(dá),記決策過(guò)程中等待下一任務(wù)到達(dá)的時(shí)間為?n,?n服從指數(shù)分布.當(dāng)有任務(wù)到達(dá)時(shí),系統(tǒng)進(jìn)入下一決策時(shí)刻,記為T(mén)n+1,滿足Tn+1Tn+?n,若到達(dá)的是第m類打印任務(wù),則系統(tǒng)轉(zhuǎn)移到下一狀態(tài)Sn+1(c1,···,···,cM),其中min{cm+1,Cm};若0,則執(zhí)行打印操作,記打印過(guò)程所需的時(shí)間為確定.在打印過(guò)程中,將第m種打印任務(wù)到達(dá)的個(gè)數(shù)記為bm,則系統(tǒng)轉(zhuǎn)移到下一狀態(tài)

3 系統(tǒng)的半馬爾科夫決策過(guò)程模型及優(yōu)化算法

3.1 系統(tǒng)的半馬爾科夫決策過(guò)程模型

由系統(tǒng)決策過(guò)程可知,系統(tǒng)狀態(tài)跳變只與當(dāng)前狀態(tài)有關(guān),與歷史狀態(tài)無(wú)關(guān),因此在一次樣本軌道仿真決策過(guò)程中產(chǎn)生的狀態(tài)序列{S1,S2,···,Sn,···}是一個(gè)嵌入式馬爾科夫鏈.此外由于系統(tǒng)打印過(guò)程所需時(shí)間為確定值,不服從指數(shù)分布,因此系統(tǒng)決策過(guò)程是連續(xù)時(shí)間半馬爾科夫過(guò)程[22].除狀態(tài)空間和行動(dòng)集外,系統(tǒng)的SMDP模型還包括逗留時(shí)間分布矩陣Fv(t)、狀態(tài)轉(zhuǎn)移矩陣Pv以及性能函數(shù)矩陣Rv,下面將分別進(jìn)行分析.

3.1.1 系統(tǒng)逗留時(shí)間分布矩陣

首先,定義在策略v下系統(tǒng)逗留時(shí)間分布矩陣為

在決策時(shí)刻Tn,系統(tǒng)在狀態(tài)Sn下選擇行動(dòng)若則進(jìn)行等待操作,等待下一任務(wù)到達(dá),決策周期為等待下一任務(wù)到達(dá)的等待時(shí)間?ntwait,系統(tǒng)轉(zhuǎn)移到下一狀態(tài)Sn+1,此時(shí)狀態(tài)逗留時(shí)間分布如下:

λ為M種任務(wù)到達(dá)率之和.

圖2 打印操作時(shí)間軸Fig.2 Timeline of printing operation

接下來(lái)文中給出預(yù)熱時(shí)間theat、掃描填充時(shí)間tprint冷卻時(shí)間tcool和打印過(guò)程所需時(shí)間τ的具體計(jì)算過(guò)程.

3D打印機(jī)在打印前需要對(duì)工作臺(tái)以及噴頭等部件進(jìn)行加熱,已有技術(shù)實(shí)現(xiàn)噴頭在較短的時(shí)間內(nèi)加熱到設(shè)置溫度,且基本實(shí)現(xiàn)無(wú)超調(diào)[23],因此本文認(rèn)為預(yù)熱時(shí)間theat為固定值.

由于打印時(shí)噴頭需要對(duì)每層截面掃描填充,掃描填充完一層后,工作臺(tái)需要向下調(diào)整,然后對(duì)下一層進(jìn)行掃描填充,因此掃描打印時(shí)間tprint由噴頭掃描填充時(shí)間tscan與工作臺(tái)調(diào)整時(shí)間組成,噴頭掃描填充時(shí)間tscan與打印件的體積成正比,工作臺(tái)調(diào)整時(shí)間取決于工作臺(tái)的移動(dòng)次數(shù).多打印件打印時(shí)噴頭掃描填充時(shí)間tscan等于各打印件的掃描填充時(shí)間之和,工作臺(tái)調(diào)整時(shí)間取決于最高打印件的高度.噴頭掃描填充時(shí)間tscan在忽略切片產(chǎn)生的填充體積誤差時(shí),可根據(jù)掃描路徑寬度d、參數(shù)層高、噴頭的掃描速度ascan以及打印件的總體積求出,計(jì)算式如下:

其中:Q[q1··· qm ··· qM]為M種打印件的體積向量.

記所選打印件組合中最高打印件的高度為hmax,hmaxmax{hm|jm0且jm ∈JSn},則掃描打印時(shí)間tprint(vSn)計(jì)算公式如下:

上式中「·」為向上取整函數(shù).

3D打印機(jī)完成逐層掃描填充后,需要等待機(jī)器冷卻后將打印件取出,記這段時(shí)間為冷卻時(shí)間tcool,本文采用固定值.

綜上可知,在決策時(shí)刻Tn,系統(tǒng)在狀態(tài)Sn下選擇的行動(dòng)若則進(jìn)行打印操作,系統(tǒng)轉(zhuǎn)移到下一狀態(tài).在此過(guò)程中系統(tǒng)狀態(tài)逗留時(shí)間分布為

3.1.2 狀態(tài)轉(zhuǎn)移矩陣

定義在策略v下系統(tǒng)的嵌入鏈轉(zhuǎn)移矩陣為Pv其中表示在狀態(tài)Sn采取行動(dòng),轉(zhuǎn)移到下一狀態(tài)Sn+1的概率.執(zhí)行打印操作時(shí),在t時(shí)間內(nèi),任務(wù)隊(duì)列m由狀態(tài)cm轉(zhuǎn)移到的概率為

當(dāng)執(zhí)行等待操作時(shí),到達(dá)的為第m種任務(wù)的概率為,系統(tǒng)下一狀態(tài)為

若cmCm,則Sn+1Sn,當(dāng)存在任務(wù)隊(duì)列為滿時(shí),系統(tǒng)轉(zhuǎn)移到相同狀態(tài)的概率為

其中:λfull為狀態(tài)Sn中所有為滿隊(duì)列對(duì)應(yīng)任務(wù)的到達(dá)率之和,Bfull為狀態(tài)Sn中所有為滿隊(duì)列對(duì)應(yīng)的任務(wù)種類的集合.

3.1.3 性能函數(shù)矩陣

本文通過(guò)SMDP模型描述3D打印批調(diào)度問(wèn)題,其優(yōu)化目標(biāo)是找到一個(gè)最優(yōu)策略使系統(tǒng)在無(wú)窮時(shí)段下的單位時(shí)間代價(jià)最小.

首先,由于系統(tǒng)采取不同行動(dòng)時(shí)會(huì)產(chǎn)生不同代價(jià),因此定義R(Sn,vSn,Sn+1)為系統(tǒng)在決策時(shí)刻Tn采取行動(dòng)vSn并轉(zhuǎn)移到下一決策時(shí)刻Tn+1過(guò)程中的單位時(shí)間期望代價(jià)函數(shù),則性能函數(shù)矩陣為

系統(tǒng)的優(yōu)化目標(biāo)函數(shù)為[22]

系統(tǒng)在執(zhí)行打印操作或等待操作會(huì)產(chǎn)生多類代價(jià),例如任務(wù)隊(duì)列中打印任務(wù)的等待代價(jià),打印材料損耗代價(jià),電能損耗代價(jià)等,下面將具體分析R(Sn,vSn,Sn+1)的計(jì)算.

首先,打印任務(wù)在任務(wù)隊(duì)列等待時(shí)需要占用一定的存儲(chǔ)空間,同時(shí)任務(wù)等待時(shí)間會(huì)影響任務(wù)的交貨時(shí)間,因此定義第m種任務(wù)等待時(shí)單位時(shí)間等待代價(jià)為k1,m.

其次,3D打印過(guò)程需消耗電能,因此定義電能單價(jià)為k2.打印設(shè)備在打印過(guò)程中能量損耗主要用于噴頭加熱用于融化打印材料,則在忽略熱量散失及其他加熱裝置的條件下,噴頭的加熱功率g近似等于單位時(shí)間融化材料所需的熱能,與參數(shù)層高h(yuǎn)成正比.在參數(shù)層高為h時(shí),單位時(shí)間打印材料擠出量為dhascanρ,其中d為掃描路徑寬度,ascan為噴頭的掃描速度,ρ為打印材料的密度.則打印材料由環(huán)境溫度θenvir加熱到打印材料的融化溫度θmelt所需的熱量為dhascanρδ×(θmelt?θenvir),δ為打印材料的比熱容,則選擇行動(dòng)時(shí),打印設(shè)備的加熱功率為

另外,打印過(guò)程中需要消耗打印材料,因此定義材料單價(jià)為k3.進(jìn)行打印行動(dòng)時(shí),所需的打印材料與選擇打印的打印件組合的總體積成正比,則選擇打印的打印件組合時(shí)消耗的打印材料質(zhì)量計(jì)算式如下:

此外,系統(tǒng)打印完產(chǎn)品會(huì)獲得報(bào)酬,由于層高參數(shù)h影響產(chǎn)品質(zhì)量,因此本文根據(jù)產(chǎn)品質(zhì)量決定產(chǎn)品的打印報(bào)酬,根據(jù)文獻(xiàn)[19]的研究結(jié)果可知,打印產(chǎn)品的磨損強(qiáng)度與層高參數(shù)h函數(shù)關(guān)系近似擬合為

式中:ξ2,ξ1,ξ0為各項(xiàng)系數(shù),在此定義打印報(bào)酬由固定報(bào)酬以及浮動(dòng)報(bào)酬這兩部分組成,其中浮動(dòng)報(bào)酬與打印質(zhì)量成正比,定義打印第m類任務(wù)的報(bào)酬rm與層高參數(shù)關(guān)系為

其中:?m為打印第m類任務(wù)的獎(jiǎng)勵(lì)報(bào)酬系數(shù),?m,fix為打印第m類任務(wù)獲得的固定報(bào)酬.則采取行動(dòng)獲得的報(bào)酬為

因此,系統(tǒng)執(zhí)行打印操作時(shí),單位時(shí)間期望代價(jià)為

其中φ1(Sn,Sn+1)為電能代價(jià)在整個(gè)時(shí)間段上的折扣,計(jì)算式為

φ3(Sn,,Sn+1)為打印立即報(bào)酬在整個(gè)時(shí)間段上的折扣,計(jì)算如下:

與打印操作不同,執(zhí)行等待操作時(shí)只存在等待代價(jià),此時(shí)系統(tǒng)單位時(shí)間期望代價(jià)為

3.2 優(yōu)化算法

本文的優(yōu)化目標(biāo)就是找到一個(gè)最優(yōu)策略v?,使系統(tǒng)在折扣均準(zhǔn)則或平均準(zhǔn)則下的無(wú)窮時(shí)段的單位時(shí)間代價(jià)最小.在此本文給出策略迭代和Q學(xué)習(xí)這兩種算法求解系統(tǒng)最優(yōu)策略.

盡管策略迭代算法可以求出系統(tǒng)最優(yōu)解,但是需要求解系統(tǒng)矩陣,并進(jìn)行矩陣求逆,當(dāng)系統(tǒng)參數(shù)例如到達(dá)率未知,或狀態(tài)龐大造成維數(shù)災(zāi)使矩陣運(yùn)算計(jì)算困難時(shí),最優(yōu)制策略無(wú)法求解或求解十分困難.因此,可用Q學(xué)習(xí)算法進(jìn)行求解.

Q學(xué)習(xí)算法的主要步驟分為如下幾個(gè)過(guò)程:首先采用矩形排樣方法得到打印件組合行動(dòng)集DJ,然后將層高h(yuǎn)取值范圍用一個(gè)很小的常數(shù)Δh離散化,得到一個(gè)離散的緊致行動(dòng)集Dh,通過(guò)組合得到系統(tǒng)行動(dòng)集.在每次決策過(guò)程中,通過(guò)觀測(cè)得到一個(gè)樣本數(shù)據(jù),ωn為第n個(gè)決策時(shí)刻與第n+1個(gè)決策時(shí)刻的時(shí)間間隔,則平均準(zhǔn)則和折扣準(zhǔn)則下統(tǒng)一差分計(jì)算式為

其中:Qα(·,·)是在折扣因子α下的狀態(tài)–行動(dòng)對(duì)的值,R′(Sn,Sn+1)表示在第n個(gè)決策時(shí)刻系統(tǒng)在狀態(tài)Sn下,采取行動(dòng)轉(zhuǎn)移到狀態(tài)Sn+1過(guò)程中產(chǎn)生的累計(jì)折扣代價(jià).具體代價(jià)計(jì)算如下:當(dāng)進(jìn)行等待操作時(shí)

當(dāng)進(jìn)行打印操作時(shí)

此外,ηn是平均代價(jià)的當(dāng)前估計(jì)值,可根據(jù)樣本軌道直接計(jì)算.則Qα(·,·)更新式如下:

其中γ(Sn,vSn)為學(xué)習(xí)步長(zhǎng).本文介紹的Q學(xué)習(xí)算法具體步驟已在文獻(xiàn)[26]中經(jīng)進(jìn)行了詳細(xì)介紹,在此不再詳述.

4 仿真結(jié)果

本文根據(jù)實(shí)驗(yàn)室中的3D打印設(shè)備的參數(shù)對(duì)系統(tǒng)的物理參數(shù)進(jìn)行設(shè)置,具體參數(shù)設(shè)置如表2所示.同時(shí)設(shè)置了仿真參數(shù)如表3所示.根據(jù)仿真實(shí)驗(yàn)給出的3D打印機(jī)和打印件的尺寸可知,本文給出的排樣問(wèn)題屬于簡(jiǎn)單排樣問(wèn)題,因此本文選擇Bottom–Left規(guī)則對(duì)打印任務(wù)進(jìn)行布排[4],按照此規(guī)則求解系統(tǒng)可行打印件組合集合為

表2 物理參數(shù)表Table 2 Physical parameters

表3 仿真參數(shù)表Table 3 Simulation parameters

仿真實(shí)驗(yàn)首先介紹了策略迭代算法和Q學(xué)習(xí)算法在折扣和平均準(zhǔn)則下的優(yōu)化過(guò)程,圖3為在平均和折扣準(zhǔn)則下采用策略迭代算法和Q學(xué)習(xí)算法的系統(tǒng)優(yōu)化的優(yōu)化曲線,此時(shí)折扣因子α0.01.由圖3可知,平均和折扣準(zhǔn)則下采用策略迭代算法對(duì)系統(tǒng)進(jìn)行優(yōu)化,在第2步或第3步就已經(jīng)收斂,得到系統(tǒng)的最優(yōu)策略.在平均準(zhǔn)則下采用Q學(xué)習(xí)算法的優(yōu)化曲線,每學(xué)3000步評(píng)估一次,由圖可知曲線在第100次評(píng)估時(shí)算法基本穩(wěn)定.與策略迭代算法相比,Q學(xué)習(xí)算法的收斂步數(shù)更大.

通過(guò)圖3可以看出折扣準(zhǔn)則下的優(yōu)化曲線是相互分離的,在不同狀態(tài)下系統(tǒng)的代價(jià)不同.這里定義3個(gè)特殊狀態(tài).狀態(tài)1:任務(wù)隊(duì)列全為空.狀態(tài)14:隊(duì)列1長(zhǎng)度為0,隊(duì)列2長(zhǎng)度為2,隊(duì)列3長(zhǎng)度為3.狀態(tài)60:任務(wù)隊(duì)列全為滿.在狀態(tài)1任務(wù)隊(duì)列全為空時(shí),由于沒(méi)有進(jìn)行打印,因此沒(méi)有打印報(bào)酬,所以代價(jià)曲線在最上方.在狀態(tài)14時(shí)隊(duì)列1長(zhǎng)度為0,隊(duì)列2長(zhǎng)度為2,隊(duì)列3長(zhǎng)度為3,此時(shí)可以組合成兩個(gè)最優(yōu)的打印件組合進(jìn)行打印,因此獲得較高的打印報(bào)酬.在狀態(tài)60時(shí),任務(wù)隊(duì)列全為滿,此時(shí)等待代價(jià)變大,同時(shí)由于系統(tǒng)對(duì)任務(wù)1的處理效率不高,所以代價(jià)曲線在狀態(tài)14的代價(jià)曲線的上方.由策略迭代求解的最優(yōu)策略可知,在狀態(tài)14時(shí),系統(tǒng)選擇的打印件組合J(0,2,0),參數(shù)層高h(yuǎn)0.1739,在狀態(tài)60時(shí),系統(tǒng)選擇的打印件組合J(0,2,0),層高參數(shù)h0.2415,這表明當(dāng)任務(wù)隊(duì)列為滿時(shí),系統(tǒng)選擇最優(yōu)的打印件組合進(jìn)行打印,層高參數(shù)設(shè)置較大,與實(shí)際情況相符合.

圖3 平均和折扣準(zhǔn)則下兩種算法的優(yōu)化曲線Fig.3 Optimization curves of two algorithms under average and discount criteria

為了進(jìn)一步分析兩種算法的特點(diǎn),仿真實(shí)驗(yàn)給出了兩種算法的運(yùn)行時(shí)間以及優(yōu)化后系統(tǒng)的平均代價(jià)、打印任務(wù)的處理率和產(chǎn)品的平均質(zhì)量,其中策略迭代算法的結(jié)果為3996 s,?2.485,0.977,0.0328,而Q學(xué)習(xí)算法的運(yùn)行時(shí)間以及優(yōu)化后系統(tǒng)的平均代價(jià)、打印任務(wù)的處理率和平均質(zhì)量分別為1222 s,?2.448,0.972,0.0327.同時(shí)為了對(duì)Q學(xué)習(xí)算法的結(jié)果進(jìn)行方差分析,在實(shí)驗(yàn)中對(duì)Q 學(xué)習(xí)算法進(jìn)行5次獨(dú)立試驗(yàn)取均值并統(tǒng)計(jì)各項(xiàng)數(shù)據(jù)的標(biāo)準(zhǔn)差,對(duì)應(yīng)每項(xiàng)的標(biāo)準(zhǔn)差分別為32 s,0.003,0.0019,0.000103,分析各項(xiàng)標(biāo)準(zhǔn)差可知Q學(xué)習(xí)算法比較穩(wěn)定.本文還對(duì)兩種算法的復(fù)雜度進(jìn)行了對(duì)比分析,首先比較空間復(fù)雜度,根據(jù)實(shí)驗(yàn)部分設(shè)置的系統(tǒng)參數(shù)求得系統(tǒng)狀態(tài)數(shù)為3×4×560,策略迭代算法需要存儲(chǔ)逗留時(shí)間分布矩陣、狀態(tài)轉(zhuǎn)移矩陣以及性能函數(shù)矩陣,由于這3個(gè)矩陣維度和系統(tǒng)狀態(tài)數(shù)相同,且都是方陣,所需存儲(chǔ)空間為3×60×6010800.而Q學(xué)習(xí)需要存儲(chǔ)每個(gè)狀態(tài)–行動(dòng)對(duì)的值,所需存儲(chǔ)空間為

兩種存儲(chǔ)空間相同.在迭代步數(shù)方面,策略迭代算法在第3步就已經(jīng)收斂,而Q學(xué)習(xí)算法在第100次評(píng)估時(shí)算法基本穩(wěn)定.在運(yùn)行時(shí)間方面,策略迭代算法運(yùn)行時(shí)間為3996 s,然而Q學(xué)習(xí)算法運(yùn)行時(shí)間為1222 s.通過(guò)上述結(jié)果可知,雖然策略迭代算法收斂速度較快,但運(yùn)行時(shí)間更長(zhǎng),這是由于策略迭代算法需要進(jìn)行矩陣求逆運(yùn)算,所以算法運(yùn)行時(shí)間長(zhǎng).Q學(xué)習(xí)算法運(yùn)行速度快,當(dāng)模型參數(shù)未知時(shí),可采用Q學(xué)習(xí)算法進(jìn)行求解.本文接下來(lái)對(duì)3D打印服務(wù)系統(tǒng)的性能分析,將依據(jù)策略迭代算法的求解結(jié)果.

本文研究的系統(tǒng)作為一種排隊(duì)服務(wù)系統(tǒng),通過(guò)設(shè)置合理的任務(wù)隊(duì)列容量,可以提高系統(tǒng)性能.為了探究任務(wù)隊(duì)列容量與系統(tǒng)性能之間的關(guān)系,本次實(shí)驗(yàn)同時(shí)比較了3個(gè)隊(duì)列的容量變化對(duì)系統(tǒng)性能的影響,在此次實(shí)驗(yàn)中假設(shè)λ10.2,λ20.3,λ30.5,實(shí)驗(yàn)結(jié)果如圖4所示.根據(jù)實(shí)驗(yàn)結(jié)果可知,任務(wù)隊(duì)列1容量增大時(shí),系統(tǒng)代價(jià)會(huì)有所上升,任務(wù)隊(duì)列1容量增大到2以后,系統(tǒng)代價(jià)也有所上升,隨著任務(wù)隊(duì)列2和任務(wù)隊(duì)列3的容量分別增大到2和3時(shí),系統(tǒng)的平均代價(jià)逐漸收斂,這是由于兩個(gè)第2種打印件和三個(gè)第3種打印件分別組成兩種等高且完全占滿工作臺(tái)的打印件組合.處理這種能夠占滿工作臺(tái)且等高的打印件組合,可以節(jié)省打印所花時(shí)間,提高系統(tǒng)的處理率.

圖4 不同隊(duì)列容量下的平均代價(jià)Fig.4 Average cost under different queue capacities

本文同時(shí)研究了隊(duì)列容量變化對(duì)不同打印任務(wù)的處理率影響,如表4所示.由表4可知當(dāng)某一種打印任務(wù)的任務(wù)隊(duì)列容量增大時(shí),對(duì)應(yīng)種類打印任務(wù)的處理率有較大幅度的提高,當(dāng)隊(duì)列容量增大到一定值后打印任務(wù)的處理率基本不變.隨著某一任務(wù)隊(duì)列容量的增大,其他種類打印任務(wù)的處理率會(huì)小幅度下降,這是由于該種隊(duì)列容量增大時(shí),其接收對(duì)應(yīng)種類任務(wù)的容量越大,當(dāng)其處理速度不及打印任務(wù)到達(dá)速度時(shí),任務(wù)產(chǎn)生堆積.同時(shí)由于任務(wù)等待代價(jià)隨著隊(duì)列長(zhǎng)度增加而增加,因此會(huì)優(yōu)先處理隊(duì)列長(zhǎng)度長(zhǎng)的任務(wù),其他打印任務(wù)的處理率會(huì)有所降低.

表4 不同隊(duì)列容量下系統(tǒng)處理率Table 4 System processing rate under different queue capacities

上面仿真實(shí)驗(yàn)研究了在任務(wù)到達(dá)率固定時(shí)隊(duì)列容量對(duì)系統(tǒng)性能的影響,但是在實(shí)際系統(tǒng)中,任務(wù)到達(dá)率是變化的,因此本次仿真實(shí)驗(yàn)探究了任務(wù)到達(dá)率與系統(tǒng)性能之間的關(guān)系.圖5為不同到達(dá)率下系統(tǒng)的平均報(bào)酬,在本次仿真實(shí)驗(yàn)中的隊(duì)列容量設(shè)置為C12,C23,C34.由圖可知隨著任務(wù)到達(dá)率的增加,系統(tǒng)的平均報(bào)酬增大,這是由于在系統(tǒng)打印能力之內(nèi),到達(dá)率越大,系統(tǒng)單位時(shí)間打印的打印件越多,獲得的報(bào)酬越大.

圖5 不同到達(dá)率下的平均報(bào)酬Fig.5 Average reward under different arrival rates

本次仿真實(shí)驗(yàn)還研究了在不同任務(wù)到達(dá)率下按照先到先服務(wù)(first-come-first-served,FCFS)規(guī)則、打印參數(shù)固定模式和打印參數(shù)可變模式這3種模式下系統(tǒng)的處理率和產(chǎn)品平均質(zhì)量,如表5所示.隨著任務(wù)到達(dá)率增大,系統(tǒng)的處理率和產(chǎn)品質(zhì)量隨之降低.但與FCFS規(guī)則和參數(shù)固定模式下系統(tǒng)性能相比,參數(shù)可變模式下系統(tǒng)的處理率下降比較緩慢.這是由于任務(wù)到達(dá)率較小時(shí),參數(shù)可變模式下系統(tǒng)為了獲得較高的打印報(bào)酬,將打印參數(shù)層高設(shè)置得較小,提高了產(chǎn)品質(zhì)量.隨著打印任務(wù)到達(dá)率增大,任務(wù)隊(duì)列中會(huì)堆積較多的打印任務(wù),參數(shù)可變模式下的系統(tǒng)為了提高處理速度,將打印參數(shù)層高設(shè)置得較大,加快了打印任務(wù)的處理速度,因此能夠及時(shí)處理到達(dá)的打印任務(wù),打印任務(wù)的流失率小.通過(guò)比較可知,在任務(wù)到達(dá)率為[0.2 0.3 0.1]時(shí),3種情況下系統(tǒng)的處理率十分接近,都在99%左右,但在參數(shù)可變模式下系統(tǒng)的產(chǎn)品的平均質(zhì)量與在其他兩種模式下系統(tǒng)產(chǎn)品質(zhì)量相比提高了4.3%.在任務(wù)到達(dá)率為[0.5 0.3 0.5]時(shí),參數(shù)可變模式下系統(tǒng)處理率比FCFS規(guī)則下系統(tǒng)的處理率高出6.6%.根據(jù)仿真實(shí)驗(yàn)結(jié)果可知,參數(shù)可變模式下系統(tǒng)對(duì)任務(wù)到達(dá)率變化的適應(yīng)性更強(qiáng),當(dāng)?shù)竭_(dá)率較小或較大時(shí),通過(guò)動(dòng)態(tài)設(shè)置打印參數(shù)調(diào)整打印任務(wù)處理速度,提高系統(tǒng)的處理率.

表5 不同到達(dá)率下系統(tǒng)處理率和產(chǎn)品平均質(zhì)量Table 5 System processing rate and average product quality under different arrival rates

5 總結(jié)

本文研究了在打印任務(wù)隨機(jī)到達(dá)情況下,如何根據(jù)任務(wù)到達(dá)情況動(dòng)態(tài)選擇任務(wù)組合和層高的問(wèn)題,并將優(yōu)化問(wèn)題描述為SMDP模型,采用策略迭代算法和Q學(xué)習(xí)算法這兩種優(yōu)化算法求解了系統(tǒng)的最優(yōu)調(diào)度策略.仿真實(shí)驗(yàn)結(jié)果表明所求調(diào)度策略可以提高系統(tǒng)的處理率.本文目前只考慮了簡(jiǎn)單的排布問(wèn)題以及單3D打印設(shè)備,如何將復(fù)雜排樣問(wèn)題納入到整個(gè)優(yōu)化問(wèn)題中,以及如何對(duì)多臺(tái)3D打印設(shè)備進(jìn)行資源優(yōu)化,是未來(lái)值得研究的問(wèn)題.