基于約束模型的多目標柔性作業車間調度問題求解

羅 雄,錢 謙,伏云發,馮 勇

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

0 引言

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

(multi-objective flexible job-shop scheduling problem,MOFJSP)是FJSP 的子問題。 由于該問題更貼近實際的生產活動,對其進行研究可以更好地為企業經營者決策提供支持。 在實際生產活動中,MOFJSP 各個優化目標的相互沖突,導致MOFJSP 與單目標的FJSP、JSP 有著本質的區別,即一般情況下,多目標優化的最優解不是唯一的[1]。

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

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

1 問題描述及數學模型

1.1 柔性作業車間調度問題描述

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

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

表1 部分柔性作業車間調度問題實例Tab.1 Example of partially flexible job-shop scheduling problems

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

1.2 多目標柔性作業車間調度問題數學模型

在實際的生產活動中,優化問題一般都是多目標優化問題[8],如生產效率、生產成本和設備的利用率等。 這些都是企業普遍關心的問題。 因此,根據優化目標的不同,建立調度模型如下:

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

2 遺傳算法求解多目標柔性作業車間調度問題

2.1 編碼與解碼

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

圖1 一條染色體結構示意圖Fig.1 Schematic diagram of a chromosome structure

解碼時,工序編碼和機器編碼一一對應,只需要從左至右依次遍歷OS,根據表1 所示的時間表產生一個可行解,即一個合法的生產調度方案。

2.2 個體相似度

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

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

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

2.3 交叉操作

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

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

針對工序編碼OS 的交叉方式,本文使用IPOX[5]交叉方式。 ①在父代染色體P1中,產生2 個不大于染色體長度N的隨機點X1、X2。 如圖2 所示,產生隨機點基因位2 和基因位4。 ②在P2中搜索P1位于隨機點X1和X2之間的所有對應工序,用P2中對應工序的對應機器替換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]方式中,工序的隨機插入不但改變了同一工件的工序順序,同時也改變了工序所對應機器的編碼順序,導致第二層機器編碼MS 失效。針對上述缺陷,本文對該操作進行改進,使之不會產生非法解。 改進后的插入變異如圖3 所示。 針對機器編碼MS 的變異方式,本文使用常見的單點變異方式[5]。①在工序編碼OS 中,產生一個不大于染色體長度N的隨機點X1。 圖3 產生隨機點基因位4。 ②同時,往左、往右搜索,遇到相同工件,則停止。 如圖3 所示,隨機點X1為工件2,往左搜索至基因位2 為止,往右搜索至基因位5 為止。 則工序O22的可插入位置為S={基因位2,基因位3,基因位4,基因位5}。 ③產生一個在S內的隨機點X2,將隨機點X1的雙層編碼同時插入到隨機點X2。 如圖3 所示,隨機點X2為基因位2 位置。

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

3 試驗結果與分析

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

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

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

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

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

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

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

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

變異操作試驗結果如表3 所示。

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

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

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

3.2 多目標優化驗證

在實際生產環境中,工件的生產均基于車間生產管理人員的約束。 旺季生產需要較小的生產周期,將最大完工時間最小化作為主要優化目標,對碳排放量給定一個可供選擇的范圍,從而作為約束條件,進入約束條件組。 設定旺季生產中,碳排放量小于730,則有調度模型為:f1=Gmax=maxGi,i=1,2,…,n。

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

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

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

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

表4 可供選擇的調度方案Tab.4 Alternative scheduling programs p.u

4 結論

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