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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 編碼與解碼

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

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

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

2.2 個體相似度

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

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

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

2.3 交叉操作

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

圖2 改進后的互換交叉示意圖Fig.2 Schematic diagram of improved crossover

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

2.4 變異操作

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

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

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

3.1 交叉及變異算子有效性驗證

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

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

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

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

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

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

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

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

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

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

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

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

在實際生產(chǎn)環(huán)境中,工件的生產(chǎn)均基于車間生產(chǎn)管理人員的約束。 旺季生產(chǎn)需要較小的生產(chǎn)周期,將最大完工時間最小化作為主要優(yōu)化目標(biāo),對碳排放量給定一個可供選擇的范圍,從而作為約束條件,進入約束條件組。 設(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è)定完工時間小于67,現(xiàn)采用上述改進遺傳算法對此多目標(biāo)優(yōu)化問題進行求解,并使用文獻[5]中的實例數(shù)據(jù)與方法進行對比。 相關(guān)參數(shù)設(shè)置如下:種群規(guī)模P=100;最大迭代次數(shù)t=300,閾值S=0.8。 為了檢測調(diào)度方案的優(yōu)劣,已知該文獻所用數(shù)據(jù)的最小完工時間為64。

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

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

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

4 結(jié)論

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