劉雪紅，張 濤，彭 兆，王 磊

(武漢理工大學(xué) 1.機(jī)電工程學(xué)院；2.湖北省數(shù)字制造重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430070)

當(dāng)前我國醫(yī)療水平不斷提高，醫(yī)療器械制造技術(shù)高速發(fā)展，醫(yī)療器械產(chǎn)品的生產(chǎn)面臨如下現(xiàn)狀：1) 客戶對高精度醫(yī)療器械產(chǎn)品的個(gè)性化需求越來越高，醫(yī)療器械產(chǎn)品的生產(chǎn)模式由面向產(chǎn)品轉(zhuǎn)變?yōu)槊嫦蚩蛻艉陀唵?，催生了高精度醫(yī)療器械產(chǎn)品多品種小批量的生產(chǎn)模式；2) 由于當(dāng)前環(huán)境問題日益突出，政府和社會大眾的環(huán)保意識越來越強(qiáng)烈，因此企業(yè)在生產(chǎn)過程中，不僅要考慮產(chǎn)品質(zhì)量、生產(chǎn)成本和準(zhǔn)時(shí)交貨率，還要考慮產(chǎn)品的社會和環(huán)境效益。為了適應(yīng)社會和市場發(fā)展需求，醫(yī)療器械制造企業(yè)需要建立高準(zhǔn)時(shí)交貨率和低能耗的生產(chǎn)調(diào)度與控制體系。

在高精度醫(yī)療器械產(chǎn)品的車間生產(chǎn)過程中，滅菌工藝是成品出廠前的最后一道工藝，但其加工時(shí)間較長，導(dǎo)致在制品庫存積壓、產(chǎn)品訂單頻繁拖期的問題較為突出。此外，加工過程能耗較高，對企業(yè)的生產(chǎn)效益造成極大的影響。因此，滅菌工藝是影響產(chǎn)品生產(chǎn)進(jìn)度和企業(yè)生產(chǎn)效益的瓶頸環(huán)節(jié)[1]。制定合理的生產(chǎn)和調(diào)度計(jì)劃，提高滅菌車間的生產(chǎn)運(yùn)作效率是醫(yī)療器械企業(yè)亟待解決的核心問題。

為滿足滅菌工藝的要求，滅菌車間采用組批加工方式，對其調(diào)度屬于平行機(jī)批調(diào)度(parallel machine batch scheduling，PMBS)問題。PMBS問題在制造業(yè)中是一類常見的批調(diào)度問題，在應(yīng)用方面具有很強(qiáng)的實(shí)用背景，如模具熱處理、機(jī)械加工、港口貨運(yùn)調(diào)度等領(lǐng)域[2]。近年來，PMBS問題的研究取得了很大的進(jìn)展[3-13]。針對平行機(jī)批調(diào)度問題，目前大多研究集中在以最大完工時(shí)間為目標(biāo)的調(diào)度研究，部分文獻(xiàn)同時(shí)考慮了能耗指標(biāo)和不相同平行機(jī)的約束，如加工速度或容量等。但是在醫(yī)療器械企業(yè)滅菌實(shí)際工藝生產(chǎn)過程中，到達(dá)時(shí)間和尺寸不同的工件在不同容量、不同加工速度的平行機(jī)上的批調(diào)度問題更為常見，而這一研究國內(nèi)并無報(bào)道。

因此，本文基于醫(yī)療器械企業(yè)的實(shí)際生產(chǎn)需求，研究面向企業(yè)滅菌工藝生產(chǎn)過程的不同容量的平行機(jī)批調(diào)度問題(different capacity parallel machine batch scheduling，DCPMBS)，建立以總延遲時(shí)長、總加工能耗和機(jī)器的平均裝載率為優(yōu)化目標(biāo)，兼顧考慮企業(yè)生產(chǎn)效益和社會環(huán)境效益的混合整數(shù)規(guī)劃調(diào)度模型。并綜合應(yīng)用INSGA-III算法、EDT+MLC(earliest delivery time and machine loading capacity，交貨時(shí)間越緊優(yōu)先和裝載容量與機(jī)器容量成比例)啟發(fā)式規(guī)則和改善非支配解質(zhì)量的局部搜索策略進(jìn)行模型求解。

1 問題描述與建模

1.1 問題描述

在醫(yī)療器械制造的滅菌工藝生產(chǎn)過程中，產(chǎn)品在生產(chǎn)車間完成組裝包裝流程后，必須經(jīng)過滅菌工藝處理達(dá)到質(zhì)量標(biāo)準(zhǔn)。如圖1所示，企業(yè)資源計(jì)劃(enterprise resource planning，ERP)系統(tǒng)接收客戶訂單，經(jīng)ERP系統(tǒng)處理后下發(fā)給制造執(zhí)行系統(tǒng)(manufacturing execution system，MES)，MES根據(jù)訂單的需求時(shí)間和數(shù)量，結(jié)合實(shí)時(shí)已到達(dá)的任務(wù)和未來一段時(shí)間內(nèi)預(yù)測的將要到達(dá)的任務(wù)，考慮滅菌車間的加工能力，對訂單進(jìn)行組批，然后分配到相應(yīng)的滅菌柜中加工，同時(shí)制定相應(yīng)的生產(chǎn)計(jì)劃給生產(chǎn)車間，滅菌完成后放入倉庫等待發(fā)貨。

圖 1 滅菌工藝加工過程示意圖Figure 1 Schematic diagram of sterilization process

1.2 問題模型

為研究DCPMBS問題，本文作如下假設(shè)。

1) 由于滅菌工藝是最后一道工序，系統(tǒng)能基本預(yù)測未來一定時(shí)間段內(nèi)將會到達(dá)的任務(wù)、任務(wù)到達(dá)的時(shí)間、批量大小和交貨時(shí)間，且任務(wù)不能進(jìn)行拆分；

2) 單個(gè)任務(wù)批量均小于任意批處理機(jī)容量；

3) 滅菌車間包含一個(gè)無容量限制的緩存區(qū)，當(dāng)對任務(wù)分配滅菌批后，一旦開始滅菌，不允許中斷。

模型涉及的參數(shù)及其描述如表1所示。

表 1 模型參數(shù)符號及說明Table 1 Model parameter symbols and descriptions

本文以最小化總延遲時(shí)長、最小化總能耗、最大化滅菌柜平均裝載率為目標(biāo)函數(shù)，使用Graham[14]的三參數(shù)表示法，將DCPMBS問題表示為為此，構(gòu)建多目標(biāo)混合整數(shù)規(guī)劃模型如下。

目標(biāo)函數(shù)為

其中，約束(5)表示每個(gè)滅菌批都會且只能被分配到一個(gè)滅菌柜；約束(6)表示每個(gè)任務(wù)都會被分到一個(gè)滅菌批，每個(gè)滅菌批都會被分配到一個(gè)滅菌柜；約束(7)表示任一滅菌批k的批量大小等于該批中所有任務(wù)批量大小之和，且不超過所在滅菌柜Mi的容量Ci；約束(8)表示滅菌批的滅菌時(shí)長為其所在滅菌柜的滅菌時(shí)長；約束(9)表示滅菌批k的到達(dá)時(shí)間Tkr為滅菌批內(nèi)最遲到達(dá)任務(wù)的到達(dá)時(shí)間；約束(10)表示滅菌批k的開始滅菌時(shí)間為到達(dá)時(shí)間Tkr與該滅菌柜內(nèi)上一滅菌批完工時(shí)間的最大值；約束(11)表示任務(wù)j的拖期時(shí)長為0與完工時(shí)間減交貨時(shí)間的最大值。

2 算法設(shè)計(jì)

Uzsoy[15]已經(jīng)證實(shí)了以最小化制造跨度為目標(biāo)，工件尺寸不同的單機(jī)批調(diào)度問題為NP-hard問題。而本文研究的DCPMBS問題是在單機(jī)批調(diào)度問題的基礎(chǔ)上演化來的更為復(fù)雜的NP-hard問題，難以在多項(xiàng)式時(shí)間內(nèi)找到最優(yōu)的調(diào)度方案。考慮到本文所研究的是一個(gè)多目標(biāo)優(yōu)化模型，因此利用多目標(biāo)遺傳算法“基于參考點(diǎn)的非支配排序多目標(biāo)優(yōu)化算法(NSGA-III)”求解。NSGA-III是由Deb等[16]于2014年提出的一種基于參考點(diǎn)的非支配排序多目標(biāo)優(yōu)化算法，Jain等[17]、陳立鵬[18]和袁源[19]對該算法進(jìn)行了擴(kuò)展和應(yīng)用。NSGA-III采用基于參考點(diǎn)的方法對個(gè)體進(jìn)行選擇，很好地解決了在面對3個(gè)及以上目標(biāo)的多目標(biāo)優(yōu)化問題時(shí)，算法的收斂性和多樣性不好的問題。因其具有較快的收斂速度以及良好的Pareto解集分布性，在生產(chǎn)調(diào)度領(lǐng)域得到廣泛的關(guān)注與應(yīng)用[20]。根據(jù)所研究的多目標(biāo)優(yōu)化問題的特性，本文提出一種改進(jìn)的NSGA-III(INSGA-III)算法用于求解DCPMBS。該算法制定了新的初始種群生成規(guī)則，選擇、交叉和變異策略，并加入一種局部搜索策略來提高算法的求解質(zhì)量。

2.1 INSGA-III算法

求解DCPMBS問題的INSGA-III算法流程如圖2所示。

圖 2 INSGA-III算法流程圖Figure 2 INSGA - III algorithm flow chart

2.2 編碼與解碼

編碼規(guī)則采用基于滅菌柜的實(shí)數(shù)編碼方式，以確定每個(gè)任務(wù)的加工滅菌柜。染色體長度為n，表示n個(gè)待滅菌的任務(wù)，每個(gè)位置代表相應(yīng)的任務(wù)批次；以長度為m的數(shù)組表示m個(gè)滅菌柜，在基因串對應(yīng)的位置賦予滅菌柜的值，表示該任務(wù)被分配到對應(yīng)的滅菌柜上滅菌。

解碼規(guī)則對于分配在同一臺滅菌柜Mi上的任務(wù)，按順序排列，依次將任務(wù)取出，直到滿足滅菌批量小于滅菌柜容量且使滅菌批量最大化時(shí)，組成一批進(jìn)行滅菌，余下的任務(wù)再進(jìn)行組批。同理，其他滅菌柜上的任務(wù)也按此規(guī)則組批。圖3所示為一個(gè)由3臺滅菌柜、10個(gè)任務(wù)組成的編碼和解碼方式示 例。任 務(wù)N1、N2、N6、N10被 分 配 給 滅 菌 柜M1，N3、N5、N9被分配給滅菌柜M2，N4、N7、N8被分配給滅菌柜M3。然后逐一對分配給各自滅菌柜的任務(wù)，按照任務(wù)的排列順序，根據(jù)滅菌柜容量進(jìn)行組批，形成各自的滅菌批加工。

圖 3 編碼解碼方式示例Figure 3 Example of encoding and decoding

2.3 初始種群的生成

為了生成高質(zhì)量的初始種群，參考Pinedo等[21]提出的最長加工時(shí)間(largest processing time，LPT)規(guī)則，結(jié)合本文所提出的多目標(biāo)優(yōu)化中的交貨延遲時(shí)長與滅菌柜的裝載率，根據(jù)啟發(fā)式規(guī)則EDT+MLC產(chǎn)生初始個(gè)體。

啟發(fā)式規(guī)則步驟如下。

步驟1全部任務(wù)按照交貨時(shí)間非降序排列，若交貨時(shí)間相同，則按任務(wù)到達(dá)時(shí)間非降序排列，得到排序后的任務(wù)集合N。

步驟2全部滅菌柜按空閑時(shí)間順序按非降序排列，若空閑時(shí)間相同則按照滅菌時(shí)長非降序排列，得到排序后的滅菌柜集合M。

步驟3選擇任務(wù)序列中未被分配的第1個(gè)任務(wù)N1，生成1個(gè)[1,n]之間的隨機(jī)數(shù)i，表示任務(wù)N1在滅菌柜Mi上滅菌。

步驟5重復(fù)執(zhí)行步驟4，直到所有任務(wù)被分配完成，得到1個(gè)個(gè)體。

步驟6重復(fù)執(zhí)行步驟1～5，生成初始種群。

2.4 選擇策略

傳統(tǒng)的NSGA-III采用典型的二元錦標(biāo)賽選擇機(jī)制。該機(jī)制有助于種群進(jìn)行全局尋優(yōu)。但隨著種群的進(jìn)化，種群的基因趨于相似，單純使用錦標(biāo)賽選擇機(jī)制，會使種群產(chǎn)生大量相同個(gè)體，種群容易陷入局部最優(yōu)，并且不利于種群的多樣性增加。因此，本文采用基于精英保留策略的二元錦標(biāo)賽選擇機(jī)制。

步驟1首先將種群中位于第1層級的個(gè)體復(fù)制到子代中(精英保留策略)，使得優(yōu)秀的基因可以直接保留到下一代。

研發(fā)基于BIM技術(shù)的設(shè)計(jì)軟件主要目的是實(shí)現(xiàn)PKPM系列不同設(shè)計(jì)軟件間數(shù)據(jù)共享、系統(tǒng)集成，綠色建筑設(shè)計(jì)以綠色建筑評價(jià)標(biāo)準(zhǔn)指標(biāo)為依據(jù)，所以軟件集成的數(shù)據(jù)核心是以綠色建筑評價(jià)標(biāo)準(zhǔn)為基準(zhǔn)，達(dá)到軟件之間數(shù)據(jù)共享的目的，從而提高建筑信息的復(fù)用率，保證數(shù)據(jù)的一致性，達(dá)到提高生產(chǎn)效率的目的。

步驟2將剩下的種群個(gè)體進(jìn)行二元錦標(biāo)賽選擇，首先隨機(jī)選擇2個(gè)個(gè)體i和j。選擇過程如下。

若Ranki＞Rankj，則選擇個(gè)體j進(jìn)入下一代；

若Ranki=Rankj，且NPi＜NPj，則 選 擇 個(gè) 體i進(jìn)入下一代；

若Ranki=Rankj，且NPi=NPj，則隨機(jī)選擇一個(gè)個(gè)體進(jìn)入下一代。

其中，Ranki表示個(gè)體i所在非支配層級數(shù)。NPi表示個(gè)體i關(guān)聯(lián)的參考點(diǎn)Pi所對應(yīng)的關(guān)聯(lián)到的個(gè)體數(shù)量。

步驟3判斷選擇的個(gè)體是否達(dá)到初始種群數(shù)量PopSize，若否，繼續(xù)執(zhí)行步驟2；否則，選擇過程結(jié)束，輸出下一代中的個(gè)體參加交叉變異。

2.5 交叉和變異策略

交叉策略采用部分映射交叉策略(partial-mapped crossover，PMX)。對種群中的2個(gè)個(gè)體i和j，首先產(chǎn)生2個(gè)交叉點(diǎn)，然后確定具體的基因交叉位置，規(guī)則如下。

步驟1首先生成2個(gè)隨機(jī)數(shù)ri∈(0,1)、rj∈(0,1)，根據(jù)ri、rj產(chǎn)生的交叉點(diǎn)。按cpi=ceil(rin)確定交叉位置cpi、cpj，其中n為任務(wù)數(shù)量。

變異策略采用多點(diǎn)位隨機(jī)變異策略，增加種群中基因的多樣性，將不同滅菌柜中的任務(wù)進(jìn)行交換，步驟如下。

步驟1對種群中參與變異的個(gè)體，首先隨機(jī)產(chǎn)生變異任務(wù)的數(shù)量r∈[1,n]，然后根據(jù)變異任務(wù)數(shù)量，產(chǎn)生r個(gè)隨機(jī)數(shù)ir∈(0,1)，確定具體的變異位置。

步驟2對于需要變異的任務(wù)進(jìn)行滅菌柜的替換，使之變異為另一個(gè)滅菌柜編號，進(jìn)而產(chǎn)生一個(gè)新的個(gè)體。假設(shè)產(chǎn)生的隨機(jī)數(shù)r=3，i1=2，i2=5，i3=7，變異操作流程如圖5所示。

圖 4 交叉策略示意圖Figure 4 Crossover strategy diagram

圖 5 變異策略示意圖Figure 5 Mutation strategy diagram

2.6 局部搜索策略

為了提高算法的求解效果，獲得更好的Pareto解集，本文在算法中加入一種局部搜索策略，在種群進(jìn)行交叉變異之后，將執(zhí)行局部搜索，局部搜索策略步驟如下。

步驟1對產(chǎn)生的子代以比例γ隨機(jī)選取進(jìn)行局部搜索的個(gè)體，并分別選取個(gè)體中對各適應(yīng)度值影響最大的的任務(wù)批。

步驟2將所選任務(wù)批中的滅菌柜編號，依次設(shè)定為除當(dāng)前滅菌柜編號之外的其他所有滅菌柜編號，以n個(gè)適應(yīng)度值和m個(gè)滅菌柜為例，則會生成至多mn-1個(gè)局部可行解。

步驟3計(jì)算適應(yīng)度值，對其進(jìn)行非支配排序，以提高非支配解的分布性。

以2個(gè)適應(yīng)度值、2個(gè)滅菌柜為例，其局部搜索過程如圖6所示。

3 仿真實(shí)驗(yàn)

3.1 參數(shù)設(shè)置

對不同規(guī)模(加工任務(wù)數(shù)量不同)的實(shí)例分別進(jìn)行仿真實(shí)驗(yàn)。采用某醫(yī)療器械企業(yè)滅菌生產(chǎn)過程中的數(shù)據(jù)，根據(jù)企業(yè)一定周期內(nèi)銷售訂單的規(guī)模，確定不同規(guī)模任務(wù)數(shù)量n分別為60、120和180；生產(chǎn)過程中，滅菌柜數(shù)量為4臺，其參數(shù)信息如表2所示。以規(guī)模為60的任務(wù)批量為例，其任務(wù)批量信息如表3所示。為了更好地檢驗(yàn)所提INSGA-III算法在求解DCPMBS問題上的有效性，將分別以NSGAIII和企業(yè)實(shí)際生產(chǎn)過程中所產(chǎn)生的目標(biāo)值(actual production，AP)作為比較對象，將實(shí)驗(yàn)所得非支配解集作為該算法的求解結(jié)果，通過比較所獲解集相應(yīng)目標(biāo)值的平均值作為算法評估的依據(jù)。算例中，最大迭代次數(shù)MaxIt = 100，初始種群數(shù)目PopSize=200。本實(shí)驗(yàn)在Matlab 2019a上實(shí)現(xiàn)。

圖 6 局部搜索過程示意圖Figure 6 Local search process diagram

表 2 滅菌柜參數(shù)信息Table 2 Parameter information of sterilization cabinet

表 3 規(guī)模為60的任務(wù)批量信息Table 3 Task batch information of size 60

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

當(dāng)任務(wù)規(guī)模n分別為60、120和180時(shí)，INSGAIII算法與傳統(tǒng)NSGA-III算法求解得到的Pareto解集以及實(shí)際生產(chǎn)(AP)所求得的各目標(biāo)值在三維坐標(biāo)系中位置，如圖7～9所示。在不同規(guī)模實(shí)例下獲得的非支配解實(shí)驗(yàn)結(jié)果對比如表4～5所示，表中各目標(biāo)值為10次運(yùn)行結(jié)果的平均值。

圖 7 Pareto解集圖(n = 60)Figure 7 Pareto chart (n = 60)

圖 8 Pareto解集(n=120)Figure 8 Pareto chart (n=120)

圖 9 Pareto解集(n=180)Figure 9 Pareto chart (n=180)

由圖7～9和表4～5可以看出，INSGA-III算法相較傳統(tǒng)的NSGA-III算法和AP調(diào)度方式有明顯的優(yōu)勢。INSGA-III算法在各目標(biāo)值上都有明顯的優(yōu)化結(jié)果(表5)。當(dāng)n=60時(shí)，相較傳統(tǒng)的NSGA-III算法，INSGA-III算法在總延遲時(shí)長方面，降低12.08 d，降低比例為33.53%；在總能耗方面，降低5.02×105kw·h，降低比例為33.94%；在裝載率方面，提高6.29%，提高比例為7.89%。相較實(shí)際生產(chǎn)(AP)，INSGA-III算法在總延遲時(shí)長方面，降低17.41 d，降低比例為42.09%；在總能耗方面，降低7.99×105kw· h，降低比例為44.99%；在裝載率方面，提高10.65%，提高比例為14.13%。因此，綜合考慮不同規(guī)模任務(wù)，從滅菌工藝的3個(gè)優(yōu)化目標(biāo)來看，INSGA-III算法具有較好的效果。

表 4 調(diào)度結(jié)果比較Table 4 Comparison of scheduling results

表 5 INSGA-III算法相較其他調(diào)度方式優(yōu)化結(jié)果Table 5 INSGA-III algorithm optimizes the quantity and percentage compared with other scheduling methods

4 結(jié)論

本文主要針對醫(yī)療器械企業(yè)滅菌工藝生產(chǎn)過程的調(diào)度問題，提出面向滅菌工藝的不同容量平行機(jī)批調(diào)度問題的多目標(biāo)優(yōu)化調(diào)度模型。針對求解目標(biāo)設(shè)計(jì)一種啟發(fā)式規(guī)則生成初始種群，并設(shè)計(jì)一種改進(jìn)NSGA-III算法求解該問題。通過算例仿真表明，改進(jìn)算法在求解該問題上具有良好的性能，可為企業(yè)實(shí)際生產(chǎn)調(diào)度提供指導(dǎo)。但仍存在一些問題，之后的研究中可以考慮任務(wù)存在不相容，加工機(jī)器存在時(shí)間限制等約束，以便更好地與企業(yè)實(shí)際相結(jié)合。