基于最小機器數(shù)的柔性作業(yè)車間調(diào)度研究

李中勝，楊玉中

河南理工大學(xué) 能源科學(xué)與工程學(xué)院，河南 焦作 454003

柔性作業(yè)車間調(diào)度問題（flexible job-shop scheduling problem，F(xiàn)JSP）是對傳統(tǒng)作業(yè)車間調(diào)度的擴展，F(xiàn)JSP的柔性表現(xiàn)在加工某道工序的機器有多種選擇，而且機器性能的不同可能導(dǎo)致工序的加工時間存在差異[1]。在對FJSP模型研究的過程中，往往需要對機器故障[2-5]、準(zhǔn)備時間[6]、最大延遲[7]、緩沖區(qū)間[8]、工件移動[9]等這些問題進行約束，以貼合實際生產(chǎn)。在對機器故障的研究上，朱傳軍等人[10]在研究含有機器故障的FJSP模型中，為保證調(diào)度的穩(wěn)定性和魯棒性，對故障機器上的未加工工件進行重調(diào)度，以減少故障對優(yōu)化指標(biāo)的影響，而Iwona等人[5]對機器故障問題提出一種先驗規(guī)則、優(yōu)先級規(guī)則的預(yù)測調(diào)度方法，并允許人員計劃性、預(yù)防性的維護，這種方法降低了由機器故障引起意外中斷的頻率。在對機器準(zhǔn)備時間和延遲時間的研究上，李明等人[6]采用新型帝國競爭算法對關(guān)鍵目標(biāo)的最大完工時間和總延遲時間進行持續(xù)優(yōu)化，同時兼顧非關(guān)鍵目標(biāo)的總耗能，以此來改善作業(yè)車間調(diào)度的結(jié)果。在對緩沖區(qū)間設(shè)置的研究上，曾程寬等人[8]在緩沖區(qū)間有限的條件下，提出以最小化最大完工時間為目標(biāo)的非線性混合整數(shù)規(guī)劃模型，來分析緩沖區(qū)間的大小對車間調(diào)度產(chǎn)生的影響。在對夾具資源有限和工件移動的研究上，吳秀麗等人[11]針對夾具資源有限的情況，提出一種考慮裝卸的FJSP雙資源調(diào)度模型來解決此問題。以上文獻，為貼合實際生產(chǎn)，考慮了FJSP的眾多因素，但都是在指定機器數(shù)量的基礎(chǔ)上進行生產(chǎn)調(diào)度優(yōu)化，并未在生產(chǎn)調(diào)度之前測算調(diào)度的最小、最優(yōu)機器數(shù)，也沒有在最小機器數(shù)的條件下研究機器利用率等其他指標(biāo)的變化趨勢，導(dǎo)致其在優(yōu)化提升方面具有一定的限制性和盲目性，需要相關(guān)研究來補充此內(nèi)容。因此提出一種在滿足最小化最大完工時間和交貨期的條件下，求解最小機器數(shù)（minimum number of machines，MNM）的雙層優(yōu)化模型。模型的外層目標(biāo)為最小機器數(shù)，主要作用是提供機器數(shù)量不同的機器組合，然后以內(nèi)層目標(biāo)、交貨期等約束來選擇符合條件的機器組合，并在此基礎(chǔ)上，對比機器組合中的機器數(shù)，最后求得眾多機器組合中最小的機器數(shù)。模型的內(nèi)層目標(biāo)為最小化最大完工時間，用于求解在某一機器組合下的最小化最大完工時間，供外層目標(biāo)使用。通過實例驗證分析，該模型可行、有效，能夠在實際應(yīng)用中減少機器數(shù)，縮減加工成本和人力，節(jié)約能耗。

在研究FJSP問題中，很多學(xué)者提出或引入多種智能算法，來優(yōu)化生產(chǎn)調(diào)度。常用的算法有粒子群算法[12-14]、蟻群算法[15-16]、免疫算法[17-18]、遺傳算法[7，19-24]和其他融合算法[18，21-22]。因遺傳算法具有良好的魯棒性和可擴展性[1]，所以在FJSP中應(yīng)用較多。如李尚函等人[20]用一種超啟發(fā)式遺傳算法求解模糊柔性作業(yè)車間調(diào)度。石小秋等人[21]提出一種自適應(yīng)變級遺傳雜草融合算法來求解FJSP。在眾多相應(yīng)的研究文獻中，遺傳算法表現(xiàn)出“早熟”的缺點[1，7，20]，容易陷入局部最優(yōu)，無法取得全局最優(yōu)解。理論上，遺傳算法中的變異操作能夠防止算法“早熟”，但是為了保證算法的穩(wěn)定性，變異率通常設(shè)定很小，導(dǎo)致其無法突破“早熟”。因此采用大變異遺傳算法（great mutation genetic algorithm，GMGA）來減少陷入局部最優(yōu)解的可能，GMGA在迭代過程中[23]，當(dāng)所有的個體集中在一起時，進行一次遠大于設(shè)定變異率的變異操作，使其產(chǎn)生更多的新個體，“打散”收斂，從而使整個種群脫離“早熟”。GMGA既保證了遺傳算法的穩(wěn)定性，又大大提高了其突破“早熟”的能力。通過對最小機器數(shù)優(yōu)化模型的實例驗證分析，證明了算法的有效性。

1 最小機器數(shù)優(yōu)化模型

1.1 問題描述

求解最小機器數(shù)時，首先要對數(shù)據(jù)中指定的機器數(shù)（工序所利用到的全部機器）進行調(diào)度，初始化參數(shù)，然后對加工時間矩陣，采用遍歷法的方式，減少機器序列，如調(diào)度共有5個機器，首先減少一個機器數(shù)，然后分別遍歷刪除第一個機器、第二個機器、……、第五個機器，并刪除對應(yīng)機器的加工時間序列，其次記錄產(chǎn)生的五種機器組合和組合對應(yīng)的加工時間矩陣，如果減少一個機器數(shù)的調(diào)度，仍然滿足約束，再次減少一個機器數(shù)，即減少2個機器數(shù)，按照上述方法再次遍歷刪除機器，直至調(diào)度不滿足約束，即求得最小機器數(shù)。其具體約束如下：

（1）所有的機器在t=0時刻都是可以使用的；

（2）每一個工件都可以在t=0時刻開始加工；

（3）在相同的時刻，每臺機器只能加工一道工序；

（4）在相同的時刻，每個工件只能在一臺機器上加工；

（5）工件加工順序不能更改，即待加工工件，只能在緊前工序加工完成后，才能進行下一道工序；

（6）機器在加工工件時不能中斷；

（7）每道工序在可選擇機器上的加工時間是確定的；

（8）總工件完工時間小于交貨期；

（9）在機器數(shù)相同、最小化最大完工時間相同的情況下，保留機器總負(fù)載較小的機器組合。

1.2 符號定義

MNM優(yōu)化模型所涉及到的符號及定義如表1所示。

表1 符號及其定義Table 1 Symbols and their definitions

1.3 模型構(gòu)建

通過機器總數(shù)減去刪除的機器數(shù)獲得最小機器數(shù)，即優(yōu)化模型目標(biāo)。目標(biāo)函數(shù)表達式，見式（1）：

約束條件的具體表達式為：

式（2）表示每個工件的工序，必須按照工藝順序進行加工；式（3）和式（4）表示一個工序只能在所選機器空閑且前道工序加工完成后才能加工；式（5）表示每個工序只能從候選機器集合中選擇一臺機器；式（6）表示最大完工時間；式（7）表示機器k的上加工工序總時間小于等于機器負(fù)載；式（8）表示在最小機器數(shù)的情況下，總工件的加工時間小于等于交貨期內(nèi)的有效時間；式（9）表示工序的開始時間和加工時間；式（10）表示決策變量的取值范圍；式（11）為最小化最大完工時間。

1.4 模型求解步驟

PC代表某一種機器組合的最小化最大完工時間F；FG代表在G機器數(shù)量下，所有機器組合中最小的F，G為常數(shù)；MC為常數(shù)，用于記錄在減少同樣數(shù)量機器的情況下，每次刪除的機器序號；儲備集用于儲存每次調(diào)度的FG和其對應(yīng)刪除的機器序號、機器數(shù)量SC。圖1為求解步驟圖，模型的具體步驟如下：

圖1 求解模型步驟圖Fig.1 Solving model steps diagram

（1）在不刪減機器的情況下，對機器運用GMGA進行求解F，并把機器總數(shù)賦予G。

（2）初始化參數(shù)MC=0,G,FG=F。

（3）首先刪除G數(shù)量下第一個機器(MC=1)和其對應(yīng)的加工時間序列，生成新的加工時間矩陣。

（4）導(dǎo)入新的加工時間矩陣，用GMGA進行求解，并記錄當(dāng)前機器組合下的最小化最大完工時間，即PC，同時記錄刪除的機器數(shù)量SC。

（5）判斷k是否小于G，如果MCG，轉(zhuǎn)（10）。

（6）比較當(dāng)前機器組合下的PC與減少同樣機器數(shù)量下的FG的大小，如果PC≤FG，進行（7）操作。如果PC>FG，直接轉(zhuǎn)（9）操作。

（7）判斷PC是否等于FG，如果相等，比較FG和PC對應(yīng)調(diào)度方案下的機器負(fù)載，PC負(fù)載小轉(zhuǎn)（8），PC負(fù)載大轉(zhuǎn)（9）。如果PC≠FG，轉(zhuǎn)（8）。

（8）把PC得到的最小化最大完工時間F賦值給FG，始終保證FG為同樣機器數(shù)量下最小的F，記錄PC對應(yīng)的機器號，并放在同樣機器數(shù)量下的儲備集中。

（9）重新恢復(fù)G數(shù)量下的加工時間矩陣，進行MC=MC+1操作，刪除下一個機器號和其對應(yīng)的加工時間序列，生成新的加工時間矩陣，轉(zhuǎn)（4）。

（10）判斷在此機器數(shù)下的生產(chǎn)總時間是否大于交貨期，如果大于交貨期，輸出上一代的G、FG、SC，結(jié)束求解，如果小于交貨期，轉(zhuǎn)（11）。注：假設(shè)減少一個機器數(shù)時，發(fā)現(xiàn)其不符合交貨期，則輸出上代未減少機器數(shù)時的G、FG、SC，參數(shù)儲存在儲備集中。

（11）剔除在G數(shù)量下，與FG對應(yīng)的機器號，刪除機器號對應(yīng)的加工時間序列，并賦值G=G-1，生成新的加工時間矩陣，覆蓋上一代G數(shù)量下的加工時間矩陣，轉(zhuǎn)（3）。

2 基于MNM優(yōu)化模型的大變異遺傳算法

2.1 編碼方案

編碼就是把解的參數(shù)形式與基因串的表達形式對應(yīng)起來。針對FJSP問題，通常采用基于工序編碼和基于機器編碼相結(jié)合的二維染色體編碼方式，即雙層實值編碼。高變異率下實值編碼優(yōu)于二進制編碼，實值編碼可以提高搜索能力，且不會損害收斂特征[25]。其運用兩個L維的數(shù)據(jù)串，來描述每道工序在選定機器上的加工順序，L代表總工序數(shù)，見式（12）：

OS（operation sequencing）數(shù)據(jù)串用來確定工序Oij的加工位置，MA（machine assignment）數(shù)據(jù)串用來確定每道工序Oij的加工機器Mk。如表2，OS行中2工件的第一次出現(xiàn)，表示2工件的第一道工序，2工件的第二次出現(xiàn)，表示2工件的第二道工序，由此對應(yīng)的MA位置，代表工序在此機器上加工。如表2中工序的加工順 序是(O21→O41→O31→O11→O42→O22→O32→O12→O23→O43→O33→O13→O14→O24→O44→O34),OS工序?qū)?yīng)的MA加工機器為(M1,M3,M6,M3,M7,M4,M2,M4,M5,M2,M6,M7,M5,M8,M2,M3)，數(shù)據(jù)引用文獻[26]。

表2 編碼表達式實例Table 2 Examples of coding expressions

2.2 解碼方案

對FJSP的染色體進行解碼，就是確定加工工序在對應(yīng)加工機器上的起止時間。本文采用半主動調(diào)度的解碼方式[27-28]：在滿足工序約束的情況下，從左至右遍歷OS、MA，即依次根據(jù)工序染色體OS上的加工順序，染色體MA上對應(yīng)的機器順序，并對照各工序的加工時間，累計計算到最后一道工序的結(jié)束時間，即得到完工時間。對表2數(shù)據(jù)進行解碼，其結(jié)果見圖2車間調(diào)度甘特圖。

圖2 機器分配甘特圖Fig.2 Gantt chart of machine allocation

2.3 選擇操作

選擇操作的作用就是優(yōu)勝劣汰，在父代種群中選出優(yōu)良個體，給予優(yōu)良個體更大的生存概率，實現(xiàn)復(fù)制、交叉重組等操作。選擇操作采用順序選擇策略[28-29]來設(shè)置固定化的概率，具體的操作步驟為：根據(jù)個體適應(yīng)度值的大小進行排序，其次為最優(yōu)的個體設(shè)定選擇概率q，則排序后的第n個個體的選擇概率見公式（13），其優(yōu)點是能最大限制地保留最優(yōu)個體。NP表示種群總數(shù)，選擇概率為0.9，個體適應(yīng)度值為最小化最大完工時間。

2.4 交叉操作

交叉操作采用Shi在1997年提出的優(yōu)先操作交叉算子（priority operation crossover，POX），基于雙層編碼的POX具體操作過程為[28]：首先將工件集I隨機分為2個互補子集I1和I2,I1、I2非空，在屬于I1的父代P1中選擇出集合I1里面的工件，復(fù)制到子代offspring中，同時在屬于I2的父代P2中選擇出集合I2里面的工件，復(fù)制到子代offspring中，復(fù)制過程中集合I1、I2的工序順序，依照其在父代P1、P2的位置順序進行排列組合，同時復(fù)制工件對應(yīng)的機器號，POX交叉過程中保留了父代部分工件的位置，而且子代保留了父代在每臺機器上加工工序的順序，具有很好的保優(yōu)作用。POX交叉的具體過程見圖3，圖3應(yīng)產(chǎn)生兩個子代，但由于圖線交叉，不易理解，所以另一個子代并未在圖中顯示。

圖3 POX交叉過程Fig.3 POX crossover process

2.5 變異操作

基于遺傳算法“早熟”的特點，采用大變異策略來彌補這種缺陷。GMGA中大變異的操作步驟為[23-24]：首先設(shè)置合適的變異率進行搜索，同時記錄迭代過程中的最大適應(yīng)度值，一旦迭代的過程中，出現(xiàn)種群個體比較集中的現(xiàn)象，即平均適應(yīng)度值滿足δ×Fmax

在大變異策略下的變異操作，采用互換變異的方式，具體步驟為[1，25]：首先按照事先設(shè)置的變異概率，判斷個體是否進行變異，然后對確定變異的個體，隨機選擇兩個變異位置，并交換這兩個變異位置上的OS、MA基因，見圖4。

圖4 互換變異操作Fig.4 Swap mutation operation

大變異遺傳算法整體流程圖見圖5。

圖5 算法流程圖Fig.5 Algorithm flowchart

3 實例分析與結(jié)果

3.1 變異率敏感性分析

在進行實例分析時，首先要對GMGA的參數(shù)進行設(shè)置。經(jīng)過大量算例驗證[20-21，26，30-32]，GMGA在交叉率0.8、變異率0.08效果最優(yōu)。對變異率進行敏感性分析，采用文獻[26]的數(shù)據(jù)做驗證說明。圖6表示在變異率為0.1、0.08、0.03的情況下，種群均值和迭代速度的變化趨勢。從圖6中可以看到在變異率為0.08時，收斂速度下降最快，種群均值最小，并能得到最優(yōu)解。在變異率0.1和0.03情況下，其最優(yōu)解、收斂速度、適應(yīng)度平均值（即圖6中種群均值的變化）稍遜于變異率為0.08情況下的運算結(jié)果，所以在求解模型時采用0.08的變異率。

圖6 不同變異率下的仿真效果Fig.6 Simulation effect under different mutation rates

3.2 模型、算法對比分析

測試環(huán)境是在Window10操作系統(tǒng)、處理器Intel?CoreTMi5-4200M CPU@2.50 GHz、運行內(nèi)存8 GB的個人PC電腦上進行測試。運用GMGA對文獻[30]、[31]、[32]中的三組實例數(shù)據(jù)進行求解驗證、對比分析。其求解思路是在最小化最大完工時間的基礎(chǔ)上考慮最小機器數(shù)，依據(jù)最小化最大完工時間與交貨期的比較結(jié)果，來判定是否進一步減少機器數(shù)或終止運算。

圖7采用文獻[30]的數(shù)據(jù)（10工件、8機器、35工序），其主要運用改進型的蝙蝠算法（bat algorithm，BA）和非支配排序遺傳算法（non-dominated sorting genetic algorithm II，NSGA-II）進行對比分析。由于文獻未給交貨期，所以采用文獻中的最優(yōu)解作為交貨期，以下兩組數(shù)據(jù)的處理也采用此方法。獨立運行20次，其結(jié)果見表3。GMGA達到最優(yōu)解的概率為0.45，NSGA-II達到最優(yōu)解的概率為0.15，說明GMGA具有較強的穩(wěn)定性。其次機器數(shù)減少1臺，最優(yōu)解從85、79提升到76，機器利用率分別提升了22.39%、12.76%。從以上四個方面來看，GMGA在機器數(shù)、最優(yōu)解、機器利用率、算法穩(wěn)定性上均優(yōu)于其他兩種算法（下文表中“—”表示文獻未給出相關(guān)數(shù)據(jù)或者此項無數(shù)據(jù)）。

圖7 基于GMGA的調(diào)度結(jié)果（采用文獻[30]的數(shù)據(jù)）Fig.7 Scheduling results based on GMGA（using Ref.[30]data）

表3 算法對比結(jié)果（采用文獻[30]的數(shù)據(jù)）Table 3 Algorithm comparison results（using Ref.[30]data）

圖8采用文獻[31]的數(shù)據(jù)（5工件、11機器、26工序），其主要運用基于直覺模糊集相似度值的遺傳算法（genetic algorithm based on intuitionistic fuzzy set similarity，IFS_GA）和NSGA-II進行對比分析。獨立運行20次，其結(jié)果如表4。GMGA達到最優(yōu)解的概率為0.8，說明GMGA具有很強的尋優(yōu)能力和穩(wěn)定性。其次機器數(shù)減少3臺，最優(yōu)解從913、793提升到781，機器利用率分別提升了12.09%、6.56%。從以上三個方面來看，GMGA在機器數(shù)、最優(yōu)解、機器利用率上均優(yōu)于其他兩種算法。

圖8 基于GMGA的調(diào)度結(jié)果（采用文獻[31]的數(shù)據(jù)）Fig.8 Scheduling results based on GMGA（using Ref.[31]data）

表4 算法對比結(jié)果（采用文獻[31]的數(shù)據(jù)）Table 4 Algorithm comparison results（using Ref.[31]data）

圖9采用文獻[32]的數(shù)據(jù)（6工件、10機器、36工序），其主要運用基本遺傳算法和多種群遺傳算法進行對比分析。獨立運行20次，結(jié)果如表5。GMGA達到最優(yōu)解的概率為0.45，說明GMGA具有較強的穩(wěn)定性。其次機器數(shù)減少3臺，最優(yōu)解從55、50提升到49，機器利用率分別提升了20.3%、16.1%。從以上三個方面來看，GMGA在機器數(shù)、最優(yōu)解、機器利用率上均優(yōu)于其他兩種算法。

表5 算法對比結(jié)果（采用文獻[32]的數(shù)據(jù)）Table 5 Algorithm comparison results（using Ref.[32]data）

圖9 基于GMGA的調(diào)度結(jié)果（采用文獻[32]的數(shù)據(jù)）Fig.9 Scheduling results based on GMGA（using Ref.[32]data）

綜上所述，模型在減少機器的情況下，還能滿足交貨期等其他約束，說明模型假設(shè)成立，有效且可行。從最優(yōu)解和穩(wěn)定性兩方面來看，算法有效、可行。結(jié)合文獻[30-32]可以看出，在最小機器數(shù)的模型中，機器柔性越大，機器利用率就越高。在柔性較大的情況下，機器數(shù)比工件數(shù)越大，其減少機器數(shù)的可能性就越大，減少的機器數(shù)也就越多。

4 結(jié)語

通過對MNM優(yōu)化模型和GMGA的研究，并結(jié)合實例驗證分析，結(jié)果表明在可接受的交貨期內(nèi)，所構(gòu)建的MNM優(yōu)化模型有效，可使車間調(diào)度性能明顯提升，能為企業(yè)生產(chǎn)管理提供相應(yīng)的指導(dǎo)，是一種實現(xiàn)高效率、低成本的有效調(diào)度方法，進一步豐富了車間調(diào)度的研究內(nèi)容。本文提出的問題，在資源限制上僅研究了機器數(shù)量和加工時間，為了進一步貼合實際生產(chǎn)，應(yīng)系統(tǒng)全面考慮機器效能、機器耗能、機器固定成本等因素，進行全資源優(yōu)化，以此來完善模型，這也是下一步研究的方向。