基于混合遺傳算法的訂單生產調度在機車車輛行業中的應用

李永妮，曹 瑞，韓彩夏

（南車青島四方機車車輛股份有限公司 信息技術部，山東 青島 266111）

機車車輛企業是典型的訂單式生產企業，面對全球經濟一體化，客戶需求個性化以及產品交貨高速化的經濟時代，機車車輛行業面臨著快速響應客戶需求、縮短產品交貨期、提高產品質量和改進產品服務的壓力。為了在激烈的市場競爭中求得生存和發展，企業需要從生產調度環節進行優化。生產調度是制造系統的一個研究熱點，調度的任務是根據生產目標和約束，為每一個對象確定具體的加工路徑、時間、機器和操作等，優良的調度策略對于縮短產品的生產時間，降低成本有著極大的作用。

訂單生產調度問題屬于一類NP-hard組合問題，因此尋找具有多項式復雜性的最優算法幾乎是不可能的。傳統的啟發式算法、智能模擬退火算法、禁忌算法、神經網絡法等算法其共性是對生產線優化問題尋求滿足實際需要的近似解或滿意解，但都是局部尋優的方法。而各種基于統計優化的方法諸如模擬退火法、遺傳算法等，提供了一種解決調度優化問題的新途徑，但也存在著一定程度的枚舉，一般來說收斂到最優解較慢，并且對于判斷解的最優性也很困難。將遺傳算法與優化算法結合起來對解決訂單生產調度問題具有較高的性能。

1 混合遺傳算法

1.1 遺傳算法

遺傳算法由于其運算的簡易性和解決問題的高效性而被廣泛應用于眾多的領域。理論上已經證明，遺傳算法能從概率的意義上以隨機的方式尋求到問題的最優解。但是另一方面，應用實踐表明，在遺傳算法的應用過程中也會出現一些不盡如人意的問題，這些問題主要表現為：容易產生早熟現象、局部尋優能力較差等。并且一般來說，對很多問題，基本遺傳算法的求解效果往往不是解決這個問題的最有效的方法，它比起專門針對該問題的知識型啟發算法的求解效率要差，雖然這種知識型啟發算法并保證不了一定能夠找到問題的全局最優解。另外，遺傳算法也無法避免多次搜索同一個可行解的情況，這也是影響遺傳算法運行效率的一個重要因素。

1.2 混合遺傳算法

梯度法、爬山法、模擬退火算法、列表尋優法等一些優化算法卻具有很強的局部搜索能力，而遺傳算法由于其運算的簡易性以及另一些含有問題與相關知識的啟發式算法的運行效率也比較高。因此可以預計，在遺傳算法的搜索過程中融合這些優化方法的思想，構成一種混合遺傳算法是提高遺傳算法運行效率和求解質量的一個有效手段。

混合遺傳算法是在標準遺傳算法中融合了局部搜索算法的思想，其特點主要體現在以下兩個方面：

（1）引入了局部搜索過程。基于群體中各個個體所對應的表現型，進行局部搜索，從而找出各個個體在目前的環境下所對應的局部最優解，以便達到改善群體總體性能的目的。

（2）增加了編碼變換操作過程。對局部搜索過程所得到的局部最優解，再通過編碼過程將它們變化為新的個體，以便能夠以一個性能較優的新群體為基礎來進行下一代的遺傳進化操作。

2 機車車輛業面向訂單生產調度模型

訂單生產調度問題中存在著多種優化目標或者綜合優化目標，調度問題的優化目標通常從生產的成本和生產的時間兩個方面來考慮。從生產成本方面來考慮，其優化目標有：制品最少、庫存最少、設備利用率最高等；從生產時間方面來考慮，其優化目標有：最小完成時間、最大程度滿足交貨期、最小流動時間和最小等待時間等。這兩個方向的優化目標之間彼此不是相互孤立的，其中的許多具體目標之間聯系非常密切，有的相互促進，有的相互沖突，也有的毫無聯系。本算法采用以總加工時間最小為目標，具體表示為：

其中：Rk表示需要在設備k上加工的總工序數；Aijk表示第i個工件的第j道工序在設備k上完成加工所需要的時間。這個時間包括開始加工此道工序之前的等待時間Wijk和從開始加工到完成此道工序的所需時間Nijk；Cj表示訂單 j的生產時間是訂單 j中包括的所有部件全部完成的時間總和；Cmax為所有訂單在并行生產的情況下，最大完工時間，即各個訂單完成時間最晚的訂單的完成時間；目標函數 F（x）的目的是使得最長需要時間盡可能地短。這樣，經過算法的多次迭代后就可以生成調度的近似最優解，得到滿意的調度結果。

3 混合遺傳算法的生產調度設計

根據上述思想，設計的混合遺傳算法的基本步驟如下：

（1）輸入數據，并初始化種群。

（2）計算種群的適配值的樣本方差FSD。

（3）判斷遺傳算法的停止準則是否滿足要求。如果滿足停止算法，輸出結果，否則繼續以下步驟。

（4）基于當前種群進行選擇交叉操作。

（5）計算種群的樣本方差 fsd，判斷fsd是否小于FSD/n，若小于則進行第（6）步，如果大于則進行變異操作。

（6）初始化禁忌搜索算法，當前染色體即為初始解。

（7）判斷禁忌搜索算法迭代準則是否滿足要求，如果滿足結束禁忌搜索，進行第（2）步；否則繼續以下操作。

（8）產生候選解集。

（9）根據設定的渴望水平和禁忌表情況，選擇一個解，并更新禁忌表。

（10）轉到步驟（7）。

（11）轉到步驟（2）。

4 仿真實驗

本文的仿真試驗中，以某機車車輛行業的10個零件、10臺機器的調度問題為例。下面給出加工時間陣、機器順序陣以及GATS算法計算10次所得的最優工件排序陣及其對應的最優加工Gantt圖，如圖1所示，最優解為87個單位時間。同時，該調度問題的Gantt圖也明顯地反映了此問題的求解復雜性。通過Gantt圖可以清晰地了解到在每臺機器上加工的工件及其各工序加工的起始時間和終止時間。如果調度的最佳解不是唯一的，則該調度算法同樣也可以將它們全部搜索到，該算例的最佳調度結果就也不是唯一的，圖1只是其中的一個最佳調度的Gantt圖。

以下是其各個矩陣的表示方法，其中機器順序陣為Jm；加工時間陣為 T；工件排列陣為 MJ。

（1）機器順序陣 Jm，Jm（i，j）表示加工 i工件的第 j個操作的機器號。

（2）加工時間陣 T，T（i，j）為 j工件在機器上的加工時間。

（3）工件排列陣 MJ，MJ（i，j）為 i機器上第 j次加工的工件號。

實驗在仿真環境下分別使用GATS和GA計算了10次，并且記錄了每次得到目標函數的最小值，如表1所示。由表1的結果表明，禁忌搜索算法在10次運算中有2次達到最小值，而且最差的值與最優值之間的偏差也只有3，結果波動不大。

表1 仿真試驗10次運行結果次數

為了驗證算法的有效性，在交叉算法和變異算法以及一些參數設置相同的情況下，采用傳統的遺傳算法重復運算10次得到的最優解為95，與最差值之間的偏差為8。同時可以比較出，禁忌搜索混合遺傳算法比傳統的遺傳算法有較好的穩定性。

在充分分析機車車輛行業生產調度特點的基礎上，提出的遺傳算法和禁忌搜素算法混合的混合遺傳算法應用在生產調度中。實驗數據表明，改進的混合遺傳算法既保存了遺傳算法和禁忌搜索算法的各自優點，又針對各自的不足做了改進，使得混合遺傳算法既克服了禁忌搜索算法對初始解的依賴性，又克服了遺傳算法爬山能力差、易于早熟的缺點。實驗證明，本文提出的混合遺傳算法可以改善原有算法，是可行的。

[1]梁旭，黃明.禁忌-并行遺傳算法在在作業車間調度中的應用 [J].計算機集成制造系統 CIMS，2005，11（5）：678-681.

[2]方劍，席裕庚.FMS中的工件調度[J].高科技通訊，1997（7）：53-58.

[3]曹承煌，李人厚，樊健.車間調度算法研究和開發[J].控制理論與應用，2000，17（1）：31-35.

[4]BAKER K R.Introduction to sequencing and scheduling[M].Wiley，New York.1974.

[5]BALES E，VAZAEOPOULOS A.Guidedloeal search wiht shitfingbottleneckofr job-shop scheduling[J].Management Science， 1998，44（2）：262-275.

[6]BLAZEWICZ J， DOMSHCKE W， PESEHE.The job-shop scheduling Problem： Conventional and new solution techniques[J].Europe JournalofOperationalResearch，1996：93（1）：1-33.