基于改進(jìn)灰狼算法的印刷包裝車(chē)間動(dòng)態(tài)調(diào)度方法

彭來(lái)湖，萬(wàn)璐璐，李建強(qiáng)，袁嫣紅，王偉華

(1.浙江理工大學(xué)，浙江 杭州 310000；2.浙江理工大學(xué)龍港研究院，浙江 溫州 325000；3.浙江大學(xué)，浙江 杭州 310000)

1 引言(Introduction)

隨著我國(guó)經(jīng)濟(jì)的發(fā)展，印刷包裝行業(yè)的社會(huì)需求日益增加，其對(duì)包裝、印刷技術(shù)等方面的需求越來(lái)越大[1]。大部分印刷包裝企業(yè)主要以“按需生產(chǎn)，零剩余產(chǎn)品”為目標(biāo)制訂合理高效的生產(chǎn)計(jì)劃，從而提高生產(chǎn)效率和車(chē)間設(shè)備利用率。

近年來(lái)，研究車(chē)間動(dòng)態(tài)調(diào)度的文獻(xiàn)逐漸增多[2-4]。匡鵬等[5]提出了一種將動(dòng)態(tài)柔性作業(yè)車(chē)間調(diào)度問(wèn)題中動(dòng)態(tài)時(shí)間預(yù)測(cè)與遺傳模擬退火算法相結(jié)合的優(yōu)化調(diào)度方法。劉微等[6]針對(duì)動(dòng)態(tài)作業(yè)車(chē)間中的機(jī)器故障、取消訂單、增加訂單和加急訂單的動(dòng)態(tài)調(diào)度問(wèn)題，以最短加工時(shí)間為優(yōu)化目標(biāo)，提出了一種混合灰狼算法的動(dòng)態(tài)作業(yè)車(chē)間調(diào)度技術(shù)，但是未考慮機(jī)器負(fù)荷和機(jī)器總能耗情況。張祥等[7]提出了一種考慮最大完工時(shí)間、機(jī)器負(fù)荷和機(jī)器總能耗等性能指標(biāo)更加合理情況下的粒子群遺傳算法。

印刷包裝包括原材料供應(yīng)、切紙、設(shè)計(jì)、制版、印刷、燙金、蓋光、壓痕、裝訂、打包、托運(yùn)等多道工序分工協(xié)作，是典型的長(zhǎng)流程型生產(chǎn)工藝。在生產(chǎn)過(guò)程中存在設(shè)備故障、緊急插單、交貨期變更、物料短缺等不確定因素，目前針對(duì)印刷包裝車(chē)間動(dòng)態(tài)問(wèn)題進(jìn)行研究的文獻(xiàn)較少。

結(jié)合印刷包裝車(chē)間生產(chǎn)實(shí)際需求，綜合考慮機(jī)器故障和緊急訂單對(duì)正常生產(chǎn)的影響，本文設(shè)計(jì)了最大完工時(shí)間、機(jī)器負(fù)荷、機(jī)器總能耗為目標(biāo)函數(shù)的多目標(biāo)車(chē)間動(dòng)態(tài)調(diào)度優(yōu)化模型，并提出了一種改進(jìn)灰狼算法，以解決車(chē)間調(diào)度過(guò)程涉及大量人為主觀判斷而導(dǎo)致機(jī)器總能耗、訂單最大完工時(shí)間等無(wú)法保證的問(wèn)題。

2 問(wèn)題描述及建模(Problem description and modeling)

2.1 問(wèn)題描述

表1 參數(shù)含義表Tab.1 Parameter meaning table

(續(xù)表)

2.2 問(wèn)題建模

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

為應(yīng)對(duì)印刷包裝車(chē)間調(diào)度的需要，實(shí)現(xiàn)各個(gè)需求間的相互平衡，該印刷包裝車(chē)間調(diào)度模型設(shè)置了三個(gè)評(píng)價(jià)目標(biāo)。

(1)最大完工時(shí)間最小化。最大完工時(shí)間指訂單的最后一道工序完成時(shí)間，最大完工時(shí)間(f1)可以宏觀反映車(chē)間生產(chǎn)狀況和車(chē)間的生產(chǎn)效率，如公式(1)所示：

(2)機(jī)器負(fù)荷平衡。機(jī)器負(fù)荷與機(jī)器利用率成反比，若要提高機(jī)器的利用率，則需使機(jī)器的負(fù)荷盡量小且平衡，如公式(2)所示：

(3)機(jī)器總能耗低。合理的調(diào)度方案不僅要考慮最大完工時(shí)間，還要綜合考慮車(chē)間機(jī)器總能耗。在最大完工時(shí)間一樣的情況下，合理選擇機(jī)器，使機(jī)器總能耗最低，如公式(3)所示：

2.2.2 約束條件

印刷包裝車(chē)間調(diào)度問(wèn)題的約束條件如下。

(1)同一時(shí)刻、同一臺(tái)機(jī)器只能加工一個(gè)工件，同一時(shí)刻、同一工件只能在同一機(jī)器上加工。

(2)不同訂單的不同工序之間不存在順序約束，但同一訂單的不同工序存在順序約束，并且不同訂單的同一工序之間不存在優(yōu)先級(jí)約束。

(3)每臺(tái)機(jī)器和每個(gè)工件具有相同的優(yōu)先級(jí)，工件一旦開(kāi)始加工，除非機(jī)器發(fā)生故障，否則不能中斷加工過(guò)程。

(4)不同工序的準(zhǔn)備時(shí)間可忽略不計(jì)。

3 改進(jìn)灰狼算法設(shè)計(jì)(Design of improved Grey Wolf algorithm)

MIRJALILI等[8]提出了灰狼算法，它是由灰狼群體捕食機(jī)制演化而來(lái)的元啟發(fā)式算法。與其他智能算法相比，該算法設(shè)計(jì)簡(jiǎn)單，并且具有設(shè)置初始參數(shù)少、求解精度高等優(yōu)點(diǎn)，受到了學(xué)者的廣泛關(guān)注[9-11]，廣泛地應(yīng)用于車(chē)間調(diào)度等領(lǐng)域。與此同時(shí)，該算法存在種群多樣性差、后期收斂速度慢、易陷入局部最優(yōu)的缺點(diǎn)。因此，可以采用混合策略方法初始化、NSGAII方法更新決策層個(gè)體位置、局部搜索及精英反向?qū)W習(xí)策略的方法改進(jìn)灰狼算法，以提高算法的收斂性與分布性。

3.1 編碼與解碼機(jī)制

本文采用一種數(shù)字編碼的方法求解具有機(jī)器故障和緊急訂單的印刷包裝車(chē)間調(diào)度問(wèn)題。編碼包含兩個(gè)部分：機(jī)器選擇和工序排序。

(1)機(jī)器選擇：每個(gè)基因都用一個(gè)數(shù)字表示當(dāng)前的工序在可用機(jī)器中選擇的順序號(hào)，每個(gè)數(shù)字根據(jù)工序的加工順序依次排列(圖1)。

圖1 機(jī)器選擇編碼規(guī)則Fig.1 Coding rules of machine selection

(2)工序排序：每個(gè)基因由訂單編號(hào)編碼。訂單號(hào)出現(xiàn)的次數(shù)(工單J有n道工序)表示訂單與工序之間的連續(xù)處理順序，即從左到右編譯染色體，如J1表示訂單1，O11表示訂單1的第1 道工序(圖2)。

圖2 工序排序編碼規(guī)則Fig.2 Coding rules of process sequencing

依據(jù)機(jī)器選擇和工序排序的編碼機(jī)制轉(zhuǎn)換出工序的加工時(shí)間，通過(guò)每臺(tái)機(jī)器的生產(chǎn)狀況及對(duì)應(yīng)的加工時(shí)間計(jì)算出對(duì)應(yīng)機(jī)器負(fù)荷和最大完工時(shí)間。

3.2 混合策略的種群初始化

為了保證初始種群分布均勻且保存種群的多樣性，使用Logistic混沌與均勻分布相結(jié)合的混合策略對(duì)種群進(jìn)行初始化。Logistic序列具有全局遍歷性強(qiáng)的優(yōu)點(diǎn)，其方程如下：

其中，k為迭代的次數(shù)，ak是第k個(gè)混沌數(shù)。

針對(duì)機(jī)器選擇和工序排序進(jìn)行種群初始化。具體步驟如下。

(1)機(jī)器選擇：S為車(chē)間可用機(jī)器，統(tǒng)計(jì)每臺(tái)機(jī)器當(dāng)月工作時(shí)間，采用均勻分配原則，若某臺(tái)機(jī)器當(dāng)月工作時(shí)間超過(guò)平均工作時(shí)間，則優(yōu)先考慮使用其他機(jī)器，保證機(jī)器的負(fù)荷均衡。隨機(jī)生成一組數(shù)據(jù)M ij(Mij∈ [0,1])，根據(jù)Logistic方程得到具有混沌序列特性的Mij作為機(jī)器選擇的初始方案。

圖3 工序排序Fig.3 Process sequencing

3.3 策層個(gè)體位置更新機(jī)制

針對(duì)多目標(biāo)問(wèn)題，灰狼優(yōu)化算法由于多次迭代而難以判斷個(gè)體優(yōu)劣。為解決這一問(wèn)題，采用非支配排序遺傳算法(Non-dominated Sorted Genetic Algorithm-II，NSGAII)的非支配排序及擁擠度方法，將每個(gè)個(gè)體按照它們的支配與非支配關(guān)系進(jìn)行再分層，提出了擁擠度與擁擠度比較算子，按照擁擠度大小對(duì)種群進(jìn)行排序，并在快速排序后挑選出三組最優(yōu)解集分別為α狼、β狼、δ狼，重復(fù)上述，對(duì)種群進(jìn)行更新，從而確定新的三組最優(yōu)解集。

3.4 局部搜索

ω狼是等級(jí)最低的階層，需要依賴(lài)α狼、β狼、δ狼的信息進(jìn)行更新，多次運(yùn)行后會(huì)導(dǎo)致種群的多樣性下降，出現(xiàn)早熟收斂現(xiàn)象，因此在算法中融入局部搜索算法對(duì)決策層個(gè)體進(jìn)行擾動(dòng)，設(shè)計(jì)了以下兩種領(lǐng)域結(jié)構(gòu)。

(1)機(jī)器選擇：隨機(jī)選取一個(gè)訂單，其對(duì)應(yīng)每道工序可選擇的機(jī)器為多臺(tái)，任意選取一臺(tái)不同的機(jī)器代替原來(lái)的機(jī)器。

(2)工序排序：隨機(jī)選取兩個(gè)不同訂單的工序，將其位置互換。

3.5 精英反向?qū)W習(xí)策略

本文使用反向?qū)W習(xí)策略提高算法搜索性能和收斂速度。α狼、β狼和δ狼作為狼群中的精英群體，對(duì)其進(jìn)行反向求解，從中發(fā)現(xiàn)潛在的精英個(gè)體用于更新父代種群。某一解Di在某個(gè)n維空間內(nèi)，D'為反向解，數(shù)學(xué)模型如下：

其中，Di∈(ai,bi)，ai= min(Di)，bi= max(Di)，ai和bi為動(dòng)態(tài)邊界，反向?qū)W習(xí)策略解決了固定邊界難以保存搜索經(jīng)驗(yàn)的問(wèn)題，使精英反向解能夠在有限的空間中進(jìn)行搜索且不易陷于局部最優(yōu)。

3.6 算法流程

改進(jìn)灰狼算法(IGWO)算法求解流程如圖4所示。

圖4 算法流程圖Fig.4 Algorithm flow chart

步驟1：采用混合策略方法將種群初始化，設(shè)置當(dāng)前迭代次數(shù)k=0和最大迭代次數(shù)為kmax。

步驟2：尋找最優(yōu)解，采用NSGAII方法進(jìn)行非支配排序和擁擠度的計(jì)算，選取三個(gè)最優(yōu)解集分別為α狼、β狼、δ狼。

步驟3：對(duì)α狼、β狼、δ狼進(jìn)行局部搜索，根據(jù)適應(yīng)度值大小及狼群公式更新個(gè)體位置信息。

步驟4：采用精英反向?qū)W習(xí)策略，選取前N個(gè)最優(yōu)灰狼個(gè)體作為下一代種群。

步驟5：判斷是否滿(mǎn)足終止條件，若滿(mǎn)足，則輸出所有非支配解，若不滿(mǎn)足，則執(zhí)行步驟2。

4 實(shí)例驗(yàn)證與分析(Case verification and analysis)

4.1 案例背景

本文選擇某軟包制造企業(yè)的印刷包裝車(chē)間對(duì)IGWO進(jìn)行應(yīng)用驗(yàn)證。車(chē)間設(shè)備信息詳見(jiàn)表2，車(chē)間訂單信息詳見(jiàn)表3。

表2 車(chē)間設(shè)備信息(節(jié)選)Tab.2 Workshop equipment information (excerpt)

表3 車(chē)間訂單信息(節(jié)選)Tab.3 Workshop order information (excerpt)

4.2 案例驗(yàn)證

根據(jù)企業(yè)的實(shí)際需求，三個(gè)目標(biāo)函數(shù)所占權(quán)重比為最大完工時(shí)間f1＞機(jī)器負(fù)荷f2＞機(jī)器總能耗f3。本文采用AHP(層次分析法)確定最大完工時(shí)間、機(jī)器負(fù)荷、機(jī)器總能耗的權(quán)重為w= (0.563,0.297,0.14)T。初始種群規(guī)模為200，最大迭代次數(shù)取100。

4.2.1 初始調(diào)度方案

根據(jù)生產(chǎn)車(chē)間設(shè)備信息和訂單信息，基于改進(jìn)灰狼算法的動(dòng)態(tài)調(diào)度技術(shù)求解得到初始調(diào)度方案的甘特圖(圖5)。

圖5 初始調(diào)度方案甘特圖Fig.5 Gantt chart of initial scheduling scheme

4.2.2 機(jī)器故障下的調(diào)度方案

在10，000 s時(shí)，機(jī)器M5發(fā)生故障，維修時(shí)間為18，720 s。機(jī)器發(fā)生故障時(shí)，各訂單的加工狀態(tài)詳見(jiàn)表4。

表4 機(jī)器故障發(fā)生時(shí)的各訂單加工狀態(tài)Tab.4 Processing status of each order when machine failure occurs

采用兩種調(diào)度方案：(1)方案1為右移調(diào)度，在初始調(diào)度方案的基礎(chǔ)上，不改變其他工序的調(diào)度順序，將故障機(jī)器M8上等待加工的工序往右移18，720 s，如圖6(a)所示；(2)方案2為基于改進(jìn)灰狼算法的動(dòng)態(tài)調(diào)度技術(shù)求解得到動(dòng)態(tài)調(diào)度方案的甘特圖，如圖6(b)所示。

圖6 機(jī)器故障重調(diào)度方案Fig.6 Machine fault rescheduling scheme

對(duì)比兩種調(diào)度方案，方案2 的最大完工時(shí)間減少了2.74%，機(jī)器總能耗減少了3.42%，機(jī)器負(fù)荷減少了1.20%。方案1中的訂單工序不變，機(jī)器M5發(fā)生故障后與其相關(guān)聯(lián)的工序往后移，導(dǎo)致機(jī)器M6、M7、M8、M9、M10、M11、M12、M13的空閑等待時(shí)間和機(jī)器總能耗都增加。

4.2.3 緊急訂單下的調(diào)度方案

在初始調(diào)度方案執(zhí)行到80，000 s時(shí)，車(chē)間收到加工件數(shù)量為5，000 件的緊急訂單，需在3 天內(nèi)完成入庫(kù)，收到緊急訂單時(shí)各工件加工狀態(tài)詳見(jiàn)表5。

表5 收到緊急訂單時(shí)的各訂單加工狀態(tài)Tab.5 The processing status of each order when an urgent order is received

分別采用兩種調(diào)度方案：(1)方案1為不改變其他工序的調(diào)度順序，對(duì)空閑機(jī)器進(jìn)行工序分配，如圖7(a)所示；(2)方案2為基于改進(jìn)灰狼算法的動(dòng)態(tài)調(diào)度技術(shù)求解得到動(dòng)態(tài)調(diào)度方案的甘特圖，如圖7(b)所示。

圖7 緊急訂單重調(diào)度方案Fig.7 Emergency order rescheduling scheme

對(duì)比兩種調(diào)度方案，雖然最大完工時(shí)間相等，但方案2中緊急訂單的完工時(shí)間為19.1×104s，方案1中緊急訂單的完工時(shí)間為19.5×104s，方案2比方案1提前2.05%完成訂單。方案2的機(jī)器總能耗減少了3.04%，機(jī)器負(fù)荷減少了1.24%，原因是采用改進(jìn)的灰狼算法對(duì)車(chē)間未開(kāi)工的工序進(jìn)行重調(diào)度，選擇負(fù)荷和空載小的機(jī)器進(jìn)行加工，并且縮短了機(jī)器的空閑時(shí)間；方案1沒(méi)有考慮其他工序的影響，只是在初始調(diào)度的基礎(chǔ)上進(jìn)行調(diào)度。

4.3 與其他算法仿真對(duì)比

為了驗(yàn)證改進(jìn)灰狼算法的有效性，與NSGAII算法進(jìn)行比較，分別取機(jī)器數(shù)量為20、30、40 臺(tái)生成a、b、c三組訂單數(shù)量不同的案例，對(duì)每個(gè)案例獨(dú)立運(yùn)行20 次，并計(jì)算和統(tǒng)計(jì)相關(guān)評(píng)價(jià)指標(biāo)的最小值(min)、最大值(max)和平均值(avg)，測(cè)試算法性能的參數(shù)反世代距離(IIGD)、非支配解個(gè)數(shù)(NNDS)、非支配解比例(RNDS)，不同實(shí)例情況下，IGWO和NSGAII在IIGD、NNDS、RNDS三個(gè)方面的對(duì)比結(jié)果分別如表6、表7、表8所示。

表6 I IGD結(jié)果比較Tab.6 Comparison of I IGD results

表7 N NDS結(jié)果比較Tab.7 Comparison of N NDS results

表8 RN DS結(jié)果比較Tab.8 Comparison of R NDS results

(續(xù)表)

由表6可知，IGWO算法得到IIGD指標(biāo)的min、max和avg的平均值分別為0.02、0.27、0.13，遠(yuǎn)小于NSGAII算法得到的結(jié)果0.64、1.43、1.00。由此可得，IGWO算法的收斂性和分布性?xún)?yōu)于NSGAII算法。

由表7可知，IGWO算法得到NNDS指標(biāo)的min、max和avg的平均值分別為19.00、23.33、21.48，高于NSGAII算法得到的結(jié)果8.89、12.33、11.20，從上述實(shí)例結(jié)果可知，IGWO算法求得NNDS數(shù)量都多于NSGAII算法。

由表8可知，IGWO算法得到RNDS指標(biāo)的min、max和avg的平均值分別為1.00、1.00、1.00，優(yōu)于NSGAII算法得到的結(jié)果0.51、0.62、0.54。

最大完工時(shí)間、機(jī)器負(fù)荷、機(jī)器總能耗的權(quán)重為w= (0.563,0.297,0.14)T，得出三種調(diào)度事件中的最優(yōu)解(表9)，由表9可知，NSGAII在機(jī)器總能耗控制上具有優(yōu)勢(shì)，但考慮到IGWO能節(jié)省最大完工時(shí)間，因此仍具有較大優(yōu)勢(shì)。

表9 實(shí)驗(yàn)結(jié)果Tab.9 Experimental results

5 結(jié)論(Conclusion)

本文針對(duì)機(jī)器故障和緊急訂單兩種動(dòng)態(tài)事件對(duì)印刷包裝車(chē)間動(dòng)態(tài)調(diào)度產(chǎn)生干擾的問(wèn)題，建立了以最大完工時(shí)間、機(jī)器負(fù)荷和機(jī)器總能耗為目標(biāo)的印刷包裝車(chē)間動(dòng)態(tài)調(diào)度多目標(biāo)優(yōu)化模型，在此基礎(chǔ)上提出了解決該問(wèn)題的一種改進(jìn)灰狼算法。首先，采用Logistic混沌與均勻分布相結(jié)合的混合策略初始化種群，從而提高初始化種群的多樣性。為了確定最優(yōu)解集，利用非支配排序遺傳算法的非支配排序及擁擠度方法，按照擁擠度大小對(duì)種群進(jìn)行排序。為了避免算法出現(xiàn)早熟收斂現(xiàn)象，采用兩種鄰域結(jié)構(gòu)對(duì)獵物進(jìn)行鄰域搜索，并且利用精英反向?qū)W習(xí)策略?xún)?yōu)化算法搜索性能及收斂速度。其次，通過(guò)案例驗(yàn)證和對(duì)比不同方案，證明動(dòng)態(tài)事件發(fā)生時(shí)，所提方法能夠有效降低最大完工時(shí)間、機(jī)器負(fù)荷和機(jī)器總能耗。