一種啟發式算法和改進遺傳混合算法在流水車間重調度中的應用

王 森, 熊福力,李 志

(西安建筑科技大學 信息與控制工程學院,西安 710055)

0 引言

流水車間重調度問題是以流水車間調度問題(flow shop scheduling problem,FSP)為基礎模型的一種動態調度問題，多年來，研究者們大多關注以最大完工時間為優化目標，較少關注工件交貨期對流水車間調度問題的影響。在考慮交貨期時，一般認為交貨期是一個固定的值，而不是一個模糊變量。遺傳算法作為一種群體智能算法，具有全局搜索的特點，是求解流水車間調度問題常用的一種算法。然而，傳統遺傳算法存在收斂速度慢、穩定性差等缺點[1]。

在實際生產過程中，干擾事件的突然到來往往導致原調度不在可行，繼而重新生成新調度方案，即為重調度。重調度即在盡量小損耗原調度性能水平的同時追求調度穩定性的優越， 如何既經濟又髙效地實施干擾，重調度一直以來備受國內外調度學者與實踐者的關注。常見的生產干擾事件有機器突然故障、一批新工件到達、工件返工、訂單撤銷、交貨期提前、誤操作等等[2]。

Chan和Hu[3]介紹了一種基于人工智能的制造業流水調度方法，并通過對預制生產特點的分析，建立了預制生產流水車間排序模型。Benjaoran[4]等人研究了模具數量對預制生產車間進度的影響，提出了定制預制生產車間進度模型。Ko和Wang[5]通過包括緩沖區大小的限制，即臨時存儲位置的大小，改進了人工智能調度的可行性，在機器之間，將待完工的部分完工預制件(以下簡稱在制品)存儲到優化模型中，并開發出相應的調度系統。Yang[6]等人提出了多條預制生產線的流水車間調度模型，以促進多條預制生產線的優化調度。動態調度出現較早，Jackson對靜態調度和動態調度做了區分。Yang[7]提出了流水車間預制生產多條生產線優化重調度模型。

本文針對傳統遺傳算法的不足之處對其作了相應的改進，在選擇階段引入了精英保留策略來確保算法的收斂性，在進行重調度時引入啟發式算法；最后通過實驗分析了該算法的優點，描述了流水車間重調度模型，并且通過實驗分析了啟發式算法和改進遺傳混合算法求解流水車間重調度問題。

1 重調度的數學模型

FSP一般描述如下：有m臺機器和n個作業；每個作業由m個操作組成，每個操作需要不同的機器。必須在所有機器上以相同的順序處理n個作業[8]。其目的是找出作業順序，使最大流動時間最小化，這在技術上被稱為生產計劃的最大完成時間。兩個重要的約束為：① 一臺機器上不能同時加工多個工件，且一個工件不能同時在多臺機器上加工[9]；② 同一機器上工件的加工次序不限制，每個工件的加工路線亦無限制。預制構件都要經過6個生產步驟，即6道工序，它們分別為成型(M1)、放置鋼筋和埋件(M2)、澆注(M3)、養護(M4)、脫模(M5)和精加工(M6)。其中，養護是一個并行過程，可以同時處理多個作業。除養護外，其余步驟是串行過程。澆筑，養護不可中斷，其余步驟可中斷；

1)優化目標

合同懲罰和存儲成本是優化目標中，將隨著工件數量線性增加。即優化目標表示為：

minfcs=αi*Max[0,duedate(i)-C(Ji,M6)]+

βi*Max[0,C(Ji,M6)-duedate(i)]

(1)

其中：fcs代表合同懲罰和存儲成本；

Ji是按順序i生產的工件號，Mk是處理第k步的機器的序號;

C(Ji,Mk)是預制件Ji在機器Mk上的離開時間;

αi,βk為早期懲罰與延期懲罰的懲罰系數;

duedate(i)是預制件Ji的交貨期。

2)優化約束

(1)機器生產率約束

在調度過程中，不僅要考慮正常生產對機器生產率的約束，還要考慮生產緊急情況對機器生產率的制約。約束取決于生產條件變化的原因。式(2)和式(3)表示生產率的約束；

S(JiMk)≥

(2)

C(Ji,Mk)≥S(Ji,Mk)+Pi,k

(3)

其中：C(Ji,Mk),S(Ji,Mk),Pi,k是預制件Ji在機器Mk上的離開時間、進入時間、處理時間。

(2)八小時工作制的約束

式(4)表示澆注工序每天八小時的工作；式(5)表示養護工序每天八小時的工作；式(6)表示其他工序每天八小時的工作。

C(Ji,M3)≥

(4)

C(Ji,M4)≥

(5)

C(Ji,Mk)≥

(6)

其中：HW，HN,HE是每天允許工作時間、非工作時間和加班時間。T是在不考慮8小時工作制的情況下計算C(Ji,Mk)得到的。D=(T/24)是從生產開始到C(Ji,Mk)的總天數，D取整。

當有緊急加工工件時，對其進行重調度處理，對緊急工件的處理方式本文的做法為：給予緊急加工工件更高的加工權重，使其先加工；在重調度過程中盡可能早地完工緊急加工工件；而對于重調度的開始時間的設置，假設原調度的開始時間從零開始，在急件到達時刻RT>0，而工件交付日期不變，故而重調度的開始時間Txtart即為RT時刻當前工件的6個工序的離開時間：

Txtart=C(JRT,Mk)

(7)

其中：JRT取整數；

重調度策略的步驟如下所示：

①在已排好的調度計劃基礎上，有緊急訂單到來；

②假設有多個緊急訂單，確定影響訂單優先級的各個因素，將所有訂單按優先級進行排序；

③根據緊急訂單策略，將緊急訂單依次插入到待加工工序，找到庫存成本與延期交貨的懲罰之和最小的位置；

④找到所有緊急訂單的插單位置，得出最小懲罰，插單結束。

2 啟發式算法和改進遺傳混合算法

2.1 改進遺傳算法

遺傳算法是一種模擬達爾文生物進化論的模型，是通過模擬自然進化來尋找最優解的一種群體優化算法。改進遺傳算法在傳統遺傳算法的基礎上，加入精英保留策略以及動態變異率，最后經過調參，找出結果最優的遺傳算法各個參數，從而使得改進遺傳算法結果更優。

2.1.1 編碼

本文采用工件號編碼來表示個體(染色體)，一組編碼代表一種加工方案，如對于6個工件中的工序 [4 1 3 2 6 5]，其中數字的順序代表工件在各個機器上的順序，數字代表著相應的工件號，如數字“4”表示在機器上第一個加工工件為工件4，數字“1”表示機器上第二個加工工件為工件1，以此類推，數字“5”表示在機器上第六個加工工件為工件5。所有工件在機器上的加工順序相同，且每臺機器在同一時刻只能加工一個工件。

2.1.2 初始種群的產生

在本文中，初始種群是隨機產生的。使用MATLAB軟件中的隨機排序函數“randperm”對染色體進行隨機編碼，給定種群大小，通過多次調用該函數得到所需大小的初始種群。

2.1.3 計算個體適應度值

以目標函數的倒數作為個體的適應度值，并采用精英保留策略[10]使最優個體存活下來。

2.1.4 選擇

本文采用合同懲罰和存儲成本最小的指標來對調度個體的適應度值進行評價，即個體適應度值大的為優良個體。在計算完每個調度個體的適應度值后，采用精英保留策略進行個體選擇。

2.1.5 交叉

本文采用部分映射交叉(Partial-Mapped Crossover，PMX)進行交叉，首先，隨機選擇一對染色體(父代)中多個基因的起始和終止位置(在同一位置選擇兩條染色體)；然后，交換兩組基因的位置；最后，進行重復檢測，并建立基于兩組交換基因的映射關系，如圖1所示，以1-6-3這一映射關系為例，可以看到第二步結果中Child1存在兩個重復基因1，則將基因1先變為基因6，在變為基因3，Child2存在兩個重復基因3，與Child1基因轉變順序相反，這時將其通過映射關系將Child1中的重復基因1轉變為基因6，將Child2中的重復基因3轉變成基因6，可以看到第三步Mid1存在兩個重復基因6，Mid2也存在兩個重復基因6，再通過映射關系將Mid1中的重復基因6轉變為基因3，Mid2中的重復基因轉變為基因1。以此類推至沒有重復基因為止，即圖2中第四步Final1和Final2所示。最后所有重復的基因都會經過映射轉變為另一個基因，保證形成的新子代基因無重復基因。

2.1.6 變異

交叉操作后形成的新個體具有一定的基因突變概率。與選擇操作一樣，這種操作是基于概率的，這就變成了變異概率pm。一般來說，變異概率設置得很小，一般pm≤0.05。

對交叉后代集中每個后代的每一位，產生一個隨機數rand∈[0,1]，若rang

改進遺傳算法的流程圖如圖2所示。

2.2 啟發式算法和改進遺傳混合算法

對于啟發式算法，本文選取NEH快速啟發式算法，該算法為快速求解生產調度問題的算法。由于遺傳算法具有可擴展性，容易與其他算法結合的優點。因此當干擾事件到來時，采用啟發式算法與改進遺傳混合算法，改進遺傳算法得出的最優結果作為初始解傳入快速啟發式算法中，作為快速啟發式算法的初始解，將緊急加工工件依次插入到每個位置上，得到不同位置的解，找出最小懲罰的調度工序的位置，可以快速解決干擾事件帶來的影響，而且兩種算法的優點都體現出來，不僅運行時間短，而且得到合適解與對應的調度工序。

2.3 啟發式算法和改進遺傳混合算法流程

1)利用MATLAB軟件中的隨機排序函數“randperm”產生染色體的初始種群，每個染色體代表一個生產安排；

2)生成與染色體相對應的條件最優調度；

3)基于優化目標對它們進行評估并確定是否終止；

4)如果要繼續，則基于前一個染色體，通過變異和交叉并返回到第二個步驟來生成新的染色體群；否則，結束計算并輸出由步驟3選擇的最優調度。

當迭代次數達到調度器給定的極限時，優化終止，得到最合適的調度工序。

5)先提取出調度工序，在上述步驟完成后，當有緊急加工工件即在RT時刻有新工件到來，將RT時刻之后的未加工工件的工序提取；

6)保持原有調度工序，將緊急工件依次插入所有位置，每次找出最優解的位置，逐次進行到最后一個緊急加工工件，最終得出最優調度。

3 實驗結果及分析

程序運行平臺是Windows10操作系統中的MATLAB軟件，經過調參可得各種參數如下：種群規模大小取為NIND=50,迭代次數取為MAXGEN=200,改進遺傳算法采用部分映射交叉方法進行交叉操作，采用換位法進行變異操作，交叉率和變異率分別取作：Pc=0.85，Pm=0.02。以下面5種規模來驗證改進遺傳混合算法的性能。本仿真實驗包含10*6、20*6、30*6、50*6、70*6五種問題規模，每個規模在相同條件下運行30次。通過模擬緊急加工工件干擾下的重調度情景，統計了合同違約金與倉儲成本(Earliness/Tardiness，E/T)的實施方案，在相同運行時間下與不同運行時間下的不同方案，在不同大小規模下的方案。

表1為部分結果，由表1可得，10*6，20*6，30*6，50*6，70*6的最優解分別為1 263.9，2 024.8，1 909.5，9 369.1，22 462，緊急訂單規模分別取4*6，10*6，14*6，20*6，30*6。結果分析為在小規模如10*6與20*6規模情況下，蟻群算法結果較好，在30*6，50*6，70*6的其他大規模情況下，改進遺傳算法結果較好，但所需時間遠遠大于提出的改進遺傳混合算法的時間，以70*6為例，蟻群算法與改進遺傳算法單次運行耗時50 s左右，而啟發式算法和改進遺傳混合算法單次運行耗時15 s左右，時間差距比較大，因此，對3種算法在相同運行時間下進行比較。

表1 不同運行時間下合同違約金與倉儲成本E/T的比較

運行結果如表2所示，10*6，20*6，30*6，50*6，70*6的最優解分別為1 363.9，4 155.6，3 875，17 122，28 644，結果分析為在相同運行時間下，在10*6與20*6規模情況下，蟻群算法結果較好，對于30*6，50*6，70*6等其余規模情況下，啟發式算法和改進遺傳混合算法結果最優。故而，在同運行時間下對于大規模情況來說，本文提出的啟發式算法和改進遺傳混合算法結果最優。

表2 同運行時間下合同違約金與倉儲成本E/T的比較

4 結束語

本文以合同違約金與倉儲成本最小化為優化目標的流水車間重調度問題。采用精英保留策略以及動態變異概率對遺傳算法進行了相應的改進。使算法具有較強的尋優能力。同時，考慮到隨著個體數目變大遺傳算法運行時間過長的缺陷，以及遺傳算法容易與其他算法結合的優點，提出了啟發式算法與改進遺傳算法的混合算法，算法包含了兩種算法的優點，在前期具有較強的尋優能力，隨著個體數目變大運行時間也不會變慢。