基于約束模型的多目標(biāo)柔性作業(yè)車間調(diào)度問題求解

羅 雄,錢 謙,伏云發(fā),馮 勇

(1.昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院,云南 昆明 650500;2.昆明理工大學(xué)云南省計(jì)算機(jī)技術(shù)應(yīng)用重點(diǎn)實(shí)驗(yàn)室,云南 昆明 650500)

0 引言

柔性作業(yè)車間調(diào)度問題( flexible job-shop scheduling problem,FJSP)是作業(yè)車間調(diào)度問題(jobshop scheduling problem,JSP)的擴(kuò)展,是計(jì)算復(fù)雜度更高的NP 難問題。 多目標(biāo)柔性作業(yè)車間調(diào)度問題

(multi-objective flexible job-shop scheduling problem,MOFJSP)是FJSP 的子問題。 由于該問題更貼近實(shí)際的生產(chǎn)活動(dòng),對(duì)其進(jìn)行研究可以更好地為企業(yè)經(jīng)營者決策提供支持。 在實(shí)際生產(chǎn)活動(dòng)中,MOFJSP 各個(gè)優(yōu)化目標(biāo)的相互沖突,導(dǎo)致MOFJSP 與單目標(biāo)的FJSP、JSP 有著本質(zhì)的區(qū)別,即一般情況下,多目標(biāo)優(yōu)化的最優(yōu)解不是唯一的[1]。

在現(xiàn)階段使用遺傳算法求解MOFJSP 的研究中,朱偉[2]基于基礎(chǔ)模型,考慮了工件移動(dòng)時(shí)間的約束,建立了包括最小化最大完工時(shí)間、最小化總加工成本在內(nèi)的多目標(biāo)組合優(yōu)化模型,并改進(jìn)遺傳算法中的變異算子自適應(yīng)變異規(guī)則,求解MOFJSP。 王雷[3]等建立以完工時(shí)間、機(jī)器能耗和工人操作機(jī)器的舒適度為優(yōu)化目標(biāo)的優(yōu)化模型,并使用改進(jìn)的遺傳算法進(jìn)行求解。Fattahi[4]考慮了機(jī)器與工件的動(dòng)態(tài)插入調(diào)度,建立了多目標(biāo)優(yōu)化的動(dòng)態(tài)調(diào)度模型,并使用遺傳算法進(jìn)行求解。 張國輝[5]等構(gòu)建了低碳多目標(biāo)調(diào)度模型,使用改進(jìn)的遺傳算法對(duì)有低碳需求的車間進(jìn)行求解。 以上研究均使用加權(quán)求和法將多個(gè)優(yōu)化目標(biāo)進(jìn)行加權(quán)求和,從而轉(zhuǎn)化為單目標(biāo)進(jìn)行求解。 雖然該方法易操作、易實(shí)現(xiàn),但每次只能獲得一個(gè)解,且權(quán)重設(shè)置的不同會(huì)導(dǎo)致輸出結(jié)果的嚴(yán)重差異。 因此,如何保證產(chǎn)生多個(gè)調(diào)度方案供選以及盡可能地靠近最優(yōu)解,是使用遺傳算法求解MOFJSP 所需解決的問題之一。 極大極小法[6]是求解多目標(biāo)優(yōu)化的方法之一,被廣泛運(yùn)用于機(jī)械設(shè)計(jì)[7]中。 其主要思想是:若優(yōu)化問題的某一目標(biāo)可以給出一個(gè)可供選擇的范圍,則該目標(biāo)就可以作為約束條件,從而被排除出目標(biāo)組,進(jìn)入約束組。 因此,該方法也被稱為約束模型方法。 與加權(quán)求和法相比,該方法更為簡單,并且能夠在無需人為設(shè)置權(quán)重的情況下,產(chǎn)生多個(gè)調(diào)度方案供選。

本文基于極大極小法,對(duì)調(diào)度模型的優(yōu)化目標(biāo)作約束化處理,并以改進(jìn)的遺傳算法求解MOFJSP。 具體操作如下:使用余弦相似度計(jì)算個(gè)體間的相似程度,避免算法在運(yùn)算過程中丟失種群的多樣性從而陷入局部最優(yōu);改進(jìn)基于機(jī)器編碼的交叉操作及基于工序編碼的變異操作,避免算法在運(yùn)算過程中產(chǎn)生非法解,從而對(duì)上述兩種算子作有效性驗(yàn)證;最后,建立以最小化最大完工時(shí)間和最小化碳排放量為優(yōu)化目標(biāo)的多目標(biāo)調(diào)度模型,以改進(jìn)后的遺傳算法對(duì)MOFJSP 的實(shí)例進(jìn)行仿真運(yùn)算,驗(yàn)證算法的性能及方法的可行性。

1 問題描述及數(shù)學(xué)模型

1.1 柔性作業(yè)車間調(diào)度問題描述

柔性作業(yè)車間調(diào)度問題通常分為完全柔性作業(yè)車間調(diào)度問題(T-FJSP)和部分柔性作業(yè)車間調(diào)度問題(P-FJSP)。 由于P-FJSP 更貼近實(shí)際的生產(chǎn)活動(dòng),其研究較多,一般描述如下:對(duì)于給定的一個(gè)待加工工件集合與機(jī)器集合,每個(gè)工件包含多道工序,且有特定的加工順序;允許工序在任意臺(tái)可用機(jī)器上進(jìn)行加工,且加工時(shí)間確定;若不單獨(dú)指明柔性,一般默認(rèn)為具有機(jī)器柔性的作業(yè)車間調(diào)度問題。 部分柔性作業(yè)車間調(diào)度問題實(shí)例如表1 所示。

表1 中,N 表示該機(jī)器無法對(duì)當(dāng)前工序進(jìn)行加工。如O23表示第2 個(gè)工件J2的第3 道工序,可選機(jī)器集為{M1,M2,M3,M4}。M5為不可選機(jī)器,無法對(duì)O23工序進(jìn)行加工。 如果選擇第1 臺(tái)機(jī)器,則O23工序使用第1 臺(tái)機(jī)器進(jìn)行加工的時(shí)間長度為1。

表1 部分柔性作業(yè)車間調(diào)度問題實(shí)例Tab.1 Example of partially flexible job-shop scheduling problems

其約束條件如下。 ①令J={Ji},1Tijk。⑤工序Oij在機(jī)器Mk上的加工時(shí)間不能為負(fù):Tijk>0。⑥每道工序Oij在機(jī)器Mk上的加工時(shí)間已經(jīng)包含加工準(zhǔn)備時(shí)間Sijk?{t|tijk

1.2 多目標(biāo)柔性作業(yè)車間調(diào)度問題數(shù)學(xué)模型

在實(shí)際的生產(chǎn)活動(dòng)中,優(yōu)化問題一般都是多目標(biāo)優(yōu)化問題[8],如生產(chǎn)效率、生產(chǎn)成本和設(shè)備的利用率等。 這些都是企業(yè)普遍關(guān)心的問題。 因此,根據(jù)優(yōu)化目標(biāo)的不同,建立調(diào)度模型如下:

式中:f1為基于最大完工時(shí)間的指標(biāo),表示生產(chǎn)效率的高低;Gi為完成第i個(gè)工件所用時(shí)間;n為工件總數(shù);f2與f3為基于設(shè)備負(fù)荷的指標(biāo),表示設(shè)備利用率;Tijk為工件i的第j道工序在機(jī)器Mk上的加工時(shí)間;ni為其工序總數(shù);f4與f5為基于拖期的指標(biāo),表示交貨性能的強(qiáng)弱;Ei為工件i的交貨期時(shí)間di與工件i的完工時(shí)間Gj的非負(fù)差值,Ei=max(di-Gi,0),即工件i的提前完工時(shí)間;ΔTi為工件i的完工時(shí)間Gi與工件i的交貨期時(shí)間di的非負(fù)差值;Ti=max(Gi-di,0),即工件i的拖期時(shí)間;f6為基于節(jié)能減排類的指標(biāo),表示生產(chǎn)成本或碳排放量等成本類指標(biāo);ei為單位時(shí)間內(nèi)的碳排放量或生產(chǎn)成本。

2 遺傳算法求解多目標(biāo)柔性作業(yè)車間調(diào)度問題

2.1 編碼與解碼

本文采用雙層編碼方式對(duì)染色體進(jìn)行編碼:每條染色體由工序編碼OS 和機(jī)器編碼MS 組成。 其中:工序編碼OS 為隨機(jī)編碼,即隨機(jī)產(chǎn)生工序序列;MS 按照已產(chǎn)生的工序順序OS,依次從可選機(jī)器集中隨機(jī)選擇可用機(jī)器作為MS 的編碼。 根據(jù)表1 所描述的FJSP,隨機(jī)產(chǎn)生的一條染色體結(jié)構(gòu)如圖1 所示。

圖1 一條染色體結(jié)構(gòu)示意圖Fig.1 Schematic diagram of a chromosome structure

解碼時(shí),工序編碼和機(jī)器編碼一一對(duì)應(yīng),只需要從左至右依次遍歷OS,根據(jù)表1 所示的時(shí)間表產(chǎn)生一個(gè)可行解,即一個(gè)合法的生產(chǎn)調(diào)度方案。

2.2 個(gè)體相似度

個(gè)體的相似度用于衡量個(gè)體之間的相似程度,一般通過計(jì)算個(gè)體在特征空間中的距離獲得。 在使用遺傳算法的個(gè)體相似度計(jì)算中,一般將每條染色體作為一個(gè)特征向量,使用海明距離[9]計(jì)算個(gè)體等位基因的相同基因個(gè)數(shù),從而得到兩條染色體之間的相似度。但該方法針對(duì)一些與問題密切相關(guān)的編碼方式時(shí)并不適用[9]。 例如,該方法并不適用或很難適用于MOFJSP。 因此,本文引入余弦相似度[10]對(duì)個(gè)體進(jìn)行相似度區(qū)分。 由上述編碼方式,可將每條染色體作為一個(gè)多維向量,通過計(jì)算每一對(duì)個(gè)體的夾角余弦值得到個(gè)體相似度后,再確定其是否進(jìn)行交叉操作或進(jìn)行變異操作。 其公式如下:

式中:xi、yi為即將交叉的2 個(gè)個(gè)體;cosθ的取值范圍為[0,1]。

由式(1)可知,余弦值越大,夾角越小,說明2 個(gè)個(gè)體間的相似度越高。

2.3 交叉操作

使用遺傳算法求解MOFJSP 的交叉操作分為兩部分。 第一部分為基于工序編碼OS 的交叉操作。第二部分為基于機(jī)器編碼MS 的交叉操作。 在常用基于機(jī)器編碼MS 的互換交叉方式[11]中,機(jī)器編碼的隨機(jī)互換易導(dǎo)致工序所對(duì)應(yīng)的機(jī)器編碼MS 失效。針對(duì)上述缺陷,本文對(duì)該方式進(jìn)行改進(jìn),使之不會(huì)產(chǎn)生非法解。 改進(jìn)后的互換交叉如圖2 所示。

圖2 改進(jìn)后的互換交叉示意圖Fig.2 Schematic diagram of improved crossover

針對(duì)工序編碼OS 的交叉方式,本文使用IPOX[5]交叉方式。 ①在父代染色體P1中,產(chǎn)生2 個(gè)不大于染色體長度N的隨機(jī)點(diǎn)X1、X2。 如圖2 所示,產(chǎn)生隨機(jī)點(diǎn)基因位2 和基因位4。 ②在P2中搜索P1位于隨機(jī)點(diǎn)X1和X2之間的所有對(duì)應(yīng)工序,用P2中對(duì)應(yīng)工序的對(duì)應(yīng)機(jī)器替換P1位于隨機(jī)點(diǎn)X1和X2之間的機(jī)器。 如圖2 所示,在P2中搜索工序O21、O12和O22,將P2中的機(jī)器編碼3、2、4 替換P1中的機(jī)器編碼1、5、5。 保持父代P1和P2的順序,從而得到兩個(gè)交叉后的子代C1和C2。

2.4 變異操作

使用遺傳算法求解MOFJSP 的變異操作也分為兩部分。 第一部分為基于工序編碼OS 的變異操作。 第二部分為基于機(jī)器編碼MS 的變異操作。 基于工序編碼OS 的常用插入變異[3]方式中,工序的隨機(jī)插入不但改變了同一工件的工序順序,同時(shí)也改變了工序所對(duì)應(yīng)機(jī)器的編碼順序,導(dǎo)致第二層機(jī)器編碼MS 失效。針對(duì)上述缺陷,本文對(duì)該操作進(jìn)行改進(jìn),使之不會(huì)產(chǎn)生非法解。 改進(jìn)后的插入變異如圖3 所示。 針對(duì)機(jī)器編碼MS 的變異方式,本文使用常見的單點(diǎn)變異方式[5]。①在工序編碼OS 中,產(chǎn)生一個(gè)不大于染色體長度N的隨機(jī)點(diǎn)X1。 圖3 產(chǎn)生隨機(jī)點(diǎn)基因位4。 ②同時(shí),往左、往右搜索,遇到相同工件,則停止。 如圖3 所示,隨機(jī)點(diǎn)X1為工件2,往左搜索至基因位2 為止,往右搜索至基因位5 為止。 則工序O22的可插入位置為S={基因位2,基因位3,基因位4,基因位5}。 ③產(chǎn)生一個(gè)在S內(nèi)的隨機(jī)點(diǎn)X2,將隨機(jī)點(diǎn)X1的雙層編碼同時(shí)插入到隨機(jī)點(diǎn)X2。 如圖3 所示,隨機(jī)點(diǎn)X2為基因位2 位置。

圖3 改進(jìn)后的插入變異示意圖Fig.3 Schematic diagram of improved insertion mutation

3 試驗(yàn)結(jié)果與分析

3.1 交叉及變異算子有效性驗(yàn)證

為了驗(yàn)證改進(jìn)后的基于機(jī)器編碼的互換交叉方式及基于工序編碼的插入變異方式的有效性,現(xiàn)對(duì)上述交叉方式及變異方式計(jì)算交叉優(yōu)秀解[12]和變異優(yōu)秀解。 為了使結(jié)果盡量客觀有效,設(shè)交叉概率Pc和變異概率Pm均為1,以Brandimarte[13]設(shè)計(jì)的MK01 為測(cè)試數(shù)據(jù),以Visual Studio 2017 為仿真平臺(tái)進(jìn)行算子的有效性驗(yàn)證。

交叉優(yōu)秀解指的是父代個(gè)體進(jìn)行交叉之后,生成的子代個(gè)體的適應(yīng)度值優(yōu)于父代個(gè)體適應(yīng)度值的數(shù)量比例。 交叉后,若交叉優(yōu)秀解個(gè)數(shù)較多,說明交叉方式較優(yōu);若交叉優(yōu)秀解個(gè)數(shù)較少,則交叉方式較差。 根據(jù)MK01 的數(shù)據(jù),隨機(jī)生成兩條適應(yīng)度值較高的染色體,以保證算法在尋找交叉優(yōu)秀解的過程中有較高的上、下限。 隨機(jī)生成的2 條染色體如圖4 所示。

圖4 隨機(jī)生成的2 條染色體Fig.4 Two chromosomes out of random

圖4 中,P1染色體適應(yīng)度值為114,P2染色體適應(yīng)度值為94。 現(xiàn)將P1和P2這2 條父代染色體使用改進(jìn)前、后的互換交叉方式[12]分別進(jìn)行10 000 次不相關(guān)對(duì)比交叉操作。 交叉操作試驗(yàn)結(jié)果如表2 所示。

表2 交叉操作試驗(yàn)結(jié)果Tab.2 Experimental results of crossover

由表2 可知,改進(jìn)后的互換交叉方式的最大適應(yīng)度值為122,最小適應(yīng)度值為74,平均適應(yīng)度值為101.923,方差為75.433 9。 改進(jìn)后的互換交叉方式在平均適應(yīng)度上僅比常用的互換交叉方式高1.727。 但改進(jìn)后的互換交叉方式產(chǎn)生的子代個(gè)體總體方差較小,低于常用互換交叉方式7.842 3。 因此,改進(jìn)后的互換交叉方式與常用的互換交叉方式相比,具有較高的穩(wěn)定性。 改進(jìn)后的互換交叉方式產(chǎn)生的子代交叉優(yōu)秀解個(gè)數(shù)為7 043 個(gè),而常用的互換交叉方式產(chǎn)生的子代交叉優(yōu)秀解個(gè)數(shù)為6 520,因此,改進(jìn)后的互換交叉方式與常用的互換交叉方式相比,在尋找交叉優(yōu)秀解上具有一定優(yōu)勢(shì)。 同時(shí),由于常用的互換交叉方式打亂了工件的工序順序,且交叉時(shí)未綁定工序編碼,導(dǎo)致交叉后的機(jī)器編碼幾乎全部失效,需要多次對(duì)交叉后的染色體基因位進(jìn)行修復(fù)。 因此,非法基因位個(gè)數(shù)較多,為108 962 個(gè),平均修復(fù)非法基因位所需時(shí)間為0.000 216 1。 當(dāng)數(shù)據(jù)規(guī)模較大或迭代次數(shù)較多時(shí),基因位修復(fù)時(shí)間較長。

驗(yàn)證基于工序的變異方式,首先根據(jù)MK01 的數(shù)據(jù),隨機(jī)生成一條染色體,如圖4 中的P1染色體。 現(xiàn)將P1染色體使用改進(jìn)后的插入變異方式與常用的插入變異方式、常用的互換變異方式進(jìn)行10 000 次不相關(guān)對(duì)比變異操作。

變異操作試驗(yàn)結(jié)果如表3 所示。

表3 變異操作試驗(yàn)結(jié)果Tab.3 Experimental results of mutation

由表3 可知,改進(jìn)后的插入變異方式的最大適應(yīng)度值為126,最小適應(yīng)度值為73,平均適應(yīng)度值為113.083,方差為22.303 2。 改進(jìn)后的插入變異方式與其余2 種變異方式相比,平均適應(yīng)度有所降低,且在總體方差上,改進(jìn)后的插入變異方式為22.303 2,遠(yuǎn)遠(yuǎn)低于其余2 種變異方式。 因此,改進(jìn)后的插入變異方式與其余2 種變異方式相比,具有較高的穩(wěn)定性。 改進(jìn)后的插入變異方式產(chǎn)生的子代變異優(yōu)秀解個(gè)數(shù)為8 272 個(gè),改進(jìn)前的插入變異方式與它在此性能上類似,優(yōu)秀解個(gè)數(shù)為8 531 個(gè),但互換變異方式的子代變異優(yōu)秀解個(gè)數(shù)為7 844。 因此,插入變異方式與互換變異方式相比,在尋找變異優(yōu)秀解上具有一定優(yōu)勢(shì)。 同時(shí),由于以上2 種已有變異方式均打亂了工件的工序順序,且變異時(shí)未綁定工序編碼,導(dǎo)致變異后的機(jī)器編碼幾乎全部失效。 因此,非法基因位個(gè)數(shù)較多,需要多次對(duì)變異后的染色體基因位進(jìn)行修復(fù),從而增加了算法的運(yùn)算時(shí)間。

由有效性驗(yàn)證可知,改進(jìn)后的交叉及變異方式杜絕了算法在運(yùn)行過程中的非法解,節(jié)省了算法的運(yùn)行時(shí)間。

3.2 多目標(biāo)優(yōu)化驗(yàn)證

在實(shí)際生產(chǎn)環(huán)境中,工件的生產(chǎn)均基于車間生產(chǎn)管理人員的約束。 旺季生產(chǎn)需要較小的生產(chǎn)周期,將最大完工時(shí)間最小化作為主要優(yōu)化目標(biāo),對(duì)碳排放量給定一個(gè)可供選擇的范圍,從而作為約束條件,進(jìn)入約束條件組。 設(shè)定旺季生產(chǎn)中,碳排放量小于730,則有調(diào)度模型為:f1=Gmax=maxGi,i=1,2,…,n。

其約束條件為:ti(j+1)k-tijg>Tijk;Tijk>0;Sijk?{t|tijk

淡季生產(chǎn)與旺季生產(chǎn)類似,設(shè)定完工時(shí)間小于67,現(xiàn)采用上述改進(jìn)遺傳算法對(duì)此多目標(biāo)優(yōu)化問題進(jìn)行求解,并使用文獻(xiàn)[5]中的實(shí)例數(shù)據(jù)與方法進(jìn)行對(duì)比。 相關(guān)參數(shù)設(shè)置如下:種群規(guī)模P=100;最大迭代次數(shù)t=300,閾值S=0.8。 為了檢測(cè)調(diào)度方案的優(yōu)劣,已知該文獻(xiàn)所用數(shù)據(jù)的最小完工時(shí)間為64。

由于該算法一次運(yùn)行可得到較多調(diào)度方案,現(xiàn)運(yùn)行5 次,從中挑選出表現(xiàn)較佳的10 個(gè)調(diào)度方案供決策者進(jìn)行決策。 可供選擇的調(diào)度方案如表4 所示。

由表4 可知,旺季生產(chǎn)只考慮生產(chǎn)周期時(shí),整體生產(chǎn)周期均較短,10 個(gè)最優(yōu)調(diào)度方案中有9 個(gè)達(dá)到64,但整體碳排放量相對(duì)較高。 淡季生產(chǎn)只考慮碳排放量時(shí),整體碳排放量較低,最小值為660.3,低于文獻(xiàn)[5]中的677.4,但生產(chǎn)周期相對(duì)較長。 文獻(xiàn)[5]使用的加權(quán)求和法的每次計(jì)算均需按經(jīng)驗(yàn)設(shè)定權(quán)重。 該方法易影響子代個(gè)體基因的繼承。 當(dāng)完工時(shí)間權(quán)重較高時(shí),調(diào)度方案的碳排放量較高,有關(guān)碳排放量的優(yōu)秀基因易丟失;當(dāng)碳排放量權(quán)重較高時(shí),調(diào)度方案的完工時(shí)間較長,有關(guān)完工時(shí)間的優(yōu)秀基因易丟失。 且該方法在每次計(jì)算后僅能得到一個(gè)調(diào)度結(jié)果,不利于企業(yè)經(jīng)營者進(jìn)行決策。 文中使用極大極小法,對(duì)基礎(chǔ)模型進(jìn)行約束。 該模型無需設(shè)定權(quán)重,使得算法在運(yùn)行過程中,能夠較好地繼承優(yōu)秀基因,從而較快地得到滿意的調(diào)度方案,且產(chǎn)生多個(gè)調(diào)度方案供企業(yè)經(jīng)營者進(jìn)行決策。雖然未同時(shí)兼顧多個(gè)目標(biāo),但是在優(yōu)先考慮主要目標(biāo)的基礎(chǔ)上,將剩余優(yōu)化目標(biāo)作為約束條件,在一定程度上達(dá)到了多目標(biāo)優(yōu)化的目的,為企業(yè)的調(diào)度決策提供了一定的理論依據(jù)。

表4 可供選擇的調(diào)度方案Tab.4 Alternative scheduling programs p.u

4 結(jié)論

本文針對(duì)柔性作業(yè)車間調(diào)度問題,將易產(chǎn)生非法解的互換交叉算子及插入變異算子進(jìn)行改進(jìn),并驗(yàn)證了上述算子的性能。 同時(shí),使用余弦相似度對(duì)個(gè)體進(jìn)行相似度計(jì)算,避免在運(yùn)算過程中丟失種群的多樣性。最后,使用極大極小法對(duì)多目標(biāo)調(diào)度模型進(jìn)行約束,并對(duì)多目標(biāo)柔性作業(yè)車間調(diào)度問題的實(shí)例進(jìn)行仿真運(yùn)算。 該研究為解決多目標(biāo)柔性作業(yè)車間調(diào)度問題提供了新的思路。