基于改進啟發式

摘要：對于流水車間的調度問題，基于啟發式算法以及遺傳算法的特性，本文提出了一種啟發式-遺傳算法的混合智能優化算法。其主要思想是：通過構造流水車間的數學模型，采用palmer啟發式算法生成初始種群替代遺傳算法隨機生成的種群，然后使用兩點交叉的方式對新生成的染色體進行交叉操作，接下來對染色體進行的逆序變異，“復制、交叉、變異”后最終生成新的下一代染色體，通過保存其中性能較優的染色體，對較優個體繼續進行迭代操作。本文通過對比實驗結果，得出本文算法在一定條件下優于遺傳算法，對流水車間的最大完工時間有著優化效果。

關鍵詞：流水車間;遺傳算法;啟發式規則;車間調度;最小化最大完工時間

一、引言

流水車間（FSP）是經典的NP-hard調度問題，它是很多實際流水車間調度的簡化模型，廣泛用于機械設計制造及自動化、傳統紡織工藝與設備、半導體與晶體加工工業、冶金與化工、建筑學等領域。潘全科[1]在車間調度問題研究中提出了很多流水車間的車間調度模型，劉易林[2] 提出了根據兩個隨機工件的相對位置提高性能的啟發式算法。

流水車間（FSP）問題沿用了正常車間調度的排列編碼方法，再用各種規則解碼來獲得問題的可行解。目前，大多數的解碼方法采取先到先加工規則，以及優先空閑機器規則，以方便智能優化算法的操作，用各種規則解碼后，可以快速獲得問題的最優解，因此相關解碼方法被廣泛推廣。喬東平[3]在論文中介紹了蟻群算法在車間調度問題中的應用，解決車輛路徑問題以及在機器人路徑規劃中都有廣泛的應用。 邵晴[4]提出了一種基于粒子群算法的自適應結合算法，通過結合實際情況對粒子群算法進行改進，引入“閾值”“堆棧和指針”的概念，具體分析現實情況結合實際大幅提高粒子群算法在優化算法在工程應用中的能力。張森[5]在面對灰狼算法的全局和局部搜索問題時，設計了正交設計算子，提高了灰狼算法的全局搜索能力，并且在后期引入了差分變異概念，提高了算法后期的局部搜索能力。但其研究及應用仍處于起步階段，存在一定的不足之處。這為我們提供了很好的改進思路，對其他算法的改進提供了明確的方向。

模擬退火算法[6]提出了一種模擬算法退火回火的改進策略，通過實驗證明了收斂速度由于傳統模擬退火算法，相關研究文獻中設計的動力系統模型完全符合模擬退火算法的需求，與此同時模擬退火算法常常與群智能優化算法混合設計與應用，展現出很好的效果。本質上，流水車間最主要解決的問題就是時間，即盡可能讓完成調度的時間縮短，本文實驗的目標是：通過相關解碼方法和算法的迭代優化，實現調度目標為最小化流水車間的最大完工時間。由于單一的啟發式算法以及單一的智能優化算法都有各自的優缺點，對此我們結合兩種算法的優點，提出一種啟發式-遺傳算法的混合優化算法來解決單一算法性能不夠的問題。

綜上，本文主要目的是將流水車間轉換為數學模型，解決流水車間的最小化最大完工時間的問題。在實驗方法上，將啟發式算法和傳統算法的優缺點相結合，提出一種混合優化算法進行實驗設計，試圖通過對比實驗來驗證混合優化算法強于單一優化算法的相關結論。

二、問題描述及數學建模

流水車間[7]（FSP）流程描述為：有n個作業，按照不同的工序分別通過m臺機器，則n個作業m道工序，這些作業分別通過不同臺機器，并且整個加工過程全程不停，從第一個作業加工時間開始，到最后一個作業加工結束，并且第一臺機器開始運行，最后一臺機器停止運行，加工完作業。這時算完成一次完整的生產任務，我們本次實驗的目的是求得流水車間最大完工時間的最小值。在FSP問題中，有以下約束條件：1.所有工件在零時刻都可以被加工;2.一臺機器在某一時刻只能加工一個工件;3.一個工件在某一時刻只能被一臺機器加工;4.工件的某道工序在某臺設備一旦加工開始則無法中斷，直到該工序的加工完成;5.所有機器在零時刻均可被用。

為了可以快速完成生產加工任務是眾多企業的第一生產目標，優化目標的最大完工時間是我們的實驗任務。進行流水車間（FSP）的數學模型如下：

Min（max（C）） （1）

Xijk=1" i=1，2，…，n; j=1，2，… ，m， （2）

Cijklt;=bi（j+1）k" "i=1，2，…，n; j=1，2，…，m， （3）

Cijkgt;bijk" "i=1，2， … ，n; j=1，2，…，m， （4）

Cijk=pijk+bijk，" i=1，2，…，n; j=1，2，…，m， （5）

Xijk=0或1 （6）

其中，式（1）表示目標，即使得整個任務的最大完成時間最小;式（2）表示的是每個工件在一道工序上加工時只能被當前機器加工，其他機器不可使用;式（3）～式（5）是時間約束，式（3）表示上一道作業沒有完成之前，這個作業的下一個步驟不可以開始;式（4）表示當前加工工序未完成時，下一個本機器的加工工序不可比前一道工序先啟動;式（5）表示每個工件的完成時間等于前一工件的完成時間加上當前工件在當前機器上的加工時間;式（6）為變量的取值范圍。

使用以下的符號來定義整個流程中的約束：

n：加工工件的總數;

m：總的加工設備數;

i：作業編號，i=1，2，…，n;

j：工序編號，j=1，2，…，m;

mj：第j階段的加工設備總數;

k：每個階段的設備編號，k=1，2，…，mj;

xi，j，k：取值為1或0，為1時是i作業在j流程看上，為0時不在;

pi，j，k：第i個作業的第j道流程在k上的加工時間;

bi，j，k：第i個作業的第j道流程在k上的開始加工時間;

ci，j，k：第i個作業的第j道流程在k上的完成加工時間;

C：所有工件的完工時間。

三、Palmer-GA算法設計

本次實驗設計了Palmer-GA混合算法，該算法是采用palmer啟發式算法與遺傳算法的結合，提出的混合優化算法。通過結合palmer啟發式算法的優點，針對遺傳算法易早熟，易陷入局部最優的特點進行了改進操作。

Palmer-GA的基本步驟包括：初始化→工件對應機器的選擇→選擇操作→交叉操作→變異操作→判斷是否滿足輸出條件，滿足則終止，不滿足則轉回第二步操作（工件對應機器的選擇）。詳細實驗過程闡述如下：

（一）初始化

本文選用基于操作的編碼方法。比如，如果有8個待加工的工件的FSP車間，可以取P1=[5 8 6 7 3 4 1 2]作為一個染色體的基因串。染色體與工件和機器互相對應，染色體從頭到尾的位置代表著機器的順序，染色體內每個基因的值代表著工件的順序，這種方法構造的車間模擬比較相似，并且操作簡單。每次進行遺傳變異時，只需要變更染色體內部基因的值就可以達到我們想要改變工件在機器上的加工順序。我們通過Palmer啟發式算法的方法生成初始解，其操作步驟如下：

步驟1：先對每個工件計算參量 ;

步驟2：按照參量值遞減的順序對工件進行排列，生成一組新解;

步驟3：將啟發式算法產生的初始種群與隨機生成的初始種群混合，最終生成編碼的初始種群。

本次實驗，我們將這種策略進行進一步改進，使得算法可以產生更多的多樣性，還可以生成較優解。使用啟發式算法產生初始種群后再與隨機生成的初始種群混合，這種方法比傳統遺傳算法隨機生成種群的方法更科學，同時可以避免遺傳算法易陷入局部最優，很難得到最優解的情況。此外，我們通過這種策略方法，會比以前產生很多隨機解，有助于對該算法進行更好的理解和優化。在提高算法效率方面，本次實驗策略使得傳統問題有更好的方法去加以解決，既優化了操作，也減少了車間的完工時間，降低了車間的消耗以及不必要的浪費。

（二）工件對應機器的選擇

步驟1：開始時，所有機器初始時都為可用狀態，當一個工件在一臺機器上開始加工后，其他工件則不能在同一時間使用這臺機器上被加工，如果其他工件想要在這臺機器上加工，需要等待前一工件完成加工后，在該機器上進行加工，這時需要判斷當前工件的開工時間是否大于前一工件的完成時間;如果當前工件的開工時間大于前一工件的完成時間，這時，我們判定，該工件可以在該機器上被加工，否則，則不可以。

步驟2：選擇機器，優先選取完成時間最小的機器。

步驟3：判斷是否所有工件的所有工序都已經進行了機器的選擇。但所有工件的所有工序都進行了機器選擇時，結束循環，輸出調度方案;否則，返回步驟1。

（三）選擇算子

算法選用輪盤賭法進行染色體選擇。通過計算種群中染色體的適應度函數，每個個體被選中的概率與數值成反比，這是為了防止某些適應度較小的染色體串被直接忽略。

（四）交叉算子

本文采用線性次序交叉，首先隨機生成兩個可以交叉的點，再交換兩個交叉位置的內容，通過刪除父代中相同的基因后，最后從頭至尾，填入剩余基因。這樣完成一次線性次序交叉。

（五）變異算子

在算法中變異算子的目的是提高算法的局部搜索能力，使算法跳出局部最優，從而得到最優解。本文采用逆序變異的方法，這種方法能夠對原始的染色體干擾比較大，能夠很好地跳出局部最優，可以擴大可搜索的空間。首先隨機生成兩個將要進行變異的點，再對這兩個位置中所有的染色體串進行逆序處理，生成兩條新的染色體，其中變異概率根據具體情況來設置大小。變異操作會大大增加了種群的多樣性。例，當一串染色體串長度為9時，其染色體串的內容為 473578169，這樣一條染色體串，我們先隨機選擇兩個位置“2和7”，標記“2”和“7”這兩個位置的基因，同時逆序變異，這時染色體變為41875369，產生一條新染色體。

（六）合并種群

當整個流程運行時，每次循環會出現一個當代最優值，記錄最優解，并返回循環開頭，判斷循環條件，如果循環結束，則當前的最優解為本次算法運行的在最終解，此時輸出結果，結束循環。否則，繼續循環，當再出現當代最優值時，與之前的最優值進行比較，如果當代最優值比之前的最優值小，則替換之前的最優值。繼續循環，直到訓話結束。

四、仿真實驗

實驗環境：本文采用matlab軟件進行仿真模擬實驗，版本為2020b。采用對比實驗的方法，將本文提出算法與GA算法進行對比，兩種算法都采用相同的迭代次數200次，種群規模為80，交叉概率0.4，變異概率0.05，對Carlier提出的算例和C.R.Reeves提出的11個算例進行測試每個算例單獨運行40次。因為遺傳算法是隨機搜索算法，每次運行時得到的結果都有所不同，我們為了更準確地結果和更好的性能，我們設定判斷標準，設P為某一實驗算例在40次內求得的最優值，Q為某一實驗算例在40次循環的平均值，F為平均相對誤差值。F=（Q-P）/P×100。

從表1可以看出，本文算法比遺傳算法在car01， car02， car03， car06，rec11，rec15中對比平均誤差值要小，意味著本文算法比遺傳算法在一些算例中有提高。

五、結束語

在本文中，我們提出了P-GA算法改進遺傳算法去解決流水車間的調度問題。通過對比實驗，驗證了本文算法在一些算例中相比遺傳算法在調度問題的上性能有明顯的提高。通過本文的研究，我們發現啟發式結合智能優化算法比單一啟發式算法和單一智能優化算法求解能力都要優秀，使用混合智能優化算法來解決流水車間調度問題是未來算法發展的重要方向。

由于設計思路和實驗環境的局限性，本次實驗仍存在一些不足，需要啟發式算法與其他算法進行更多維度的混合優化，來進一步提高實驗效率和效果顯著性。

作者單位：李晨" "吉桐萱" " 大連交通大學軟件學院

參" 考" 文" 獻

[1]潘全科.車間調度問題研究[J].聊城大學學報（自然科學版），2004.03，17（1）：10.

[2]劉易麟. 流水車間調度問題的一種啟發式算法[J]. 信息工程期刊：中英文版， 2014， 4（6）：6.

[3]喬東平. 蟻群算法及其應用綜述[J].軟件導刊，2017，12.

[4]邵晴. 粒子群算法研究及其工程應用案例[D].長春：吉林大學，2017.

[5]張森 灰狼優化算法及其應用 [D].廣西民族大學，2017.

[6]李元香，項正龍，夏界寧.模擬退火算法的動力系統模型及收斂性分析[J].計算機學報，2018-11.

[7]熊學. 基于遺傳算法的排課問題研究[D].西南交通大學，2008.