改進(jìn)遺傳算法求解作業(yè)車間提前/拖期調(diào)度問(wèn)題

葛安華，周晏明，李權(quán)章

(東北林業(yè)大學(xué)工程技術(shù)學(xué)院，哈爾濱 150040)

作業(yè)車間調(diào)度問(wèn)題，是一類滿足任務(wù)配置和順序約束要求的資源分配問(wèn)題，其目的是對(duì)作業(yè)進(jìn)行有效排序，是最難解決的組合優(yōu)化問(wèn)題之一［1］。在實(shí)際的制造企業(yè)加工車間中所面臨的問(wèn)題大多為作業(yè)車間調(diào)度，如車間生產(chǎn)自動(dòng)化水平相對(duì)較低，憑計(jì)劃員經(jīng)驗(yàn)調(diào)度，頻繁調(diào)整生產(chǎn)計(jì)劃，設(shè)備利用率不均衡，生產(chǎn)周期加長(zhǎng)以及人員與設(shè)備的浪費(fèi)［2］。對(duì)作業(yè)車間調(diào)度問(wèn)題的研究有助于提高生產(chǎn)車間自動(dòng)化水平，改善設(shè)備利用的均衡性，具有重要理論意義和工程價(jià)值。

隨著近年來(lái)智能優(yōu)化技術(shù)的發(fā)展，許多求解作業(yè)車間調(diào)度問(wèn)題的啟發(fā)式方法被提出，如禁忌搜索算法、模擬退火算法、遺傳算法等，國(guó)內(nèi)外的專家學(xué)者在相關(guān)方面也做了大量的研究工作［3－5］。文獻(xiàn)［3］研究了一種基于禁忌搜索技術(shù)解決作業(yè)車間調(diào)度最短完工時(shí)間的算法。禁忌搜索算法偏向于局部搜索，對(duì)初始解的依賴性較強(qiáng)，不好的初始解會(huì)造成計(jì)算時(shí)間過(guò)長(zhǎng)。文獻(xiàn) ［4］闡述了模擬退火算法在作業(yè)車間調(diào)度問(wèn)題上的應(yīng)用。雖然理論上模擬退火算法可以在足夠長(zhǎng)的時(shí)間后跳出局部最優(yōu)，但在實(shí)際應(yīng)用中往往會(huì)陷入到優(yōu)化效果與計(jì)算時(shí)間的矛盾中。遺傳算法，因其通用性強(qiáng)，全局搜索性能較好，在求解過(guò)程中可同時(shí)保留多個(gè)方案而得到廣泛的應(yīng)用。但因其固有特征，在求解作業(yè)車間調(diào)度問(wèn)題時(shí)仍具有局部尋優(yōu)能力差，搜索效率不高等現(xiàn)象。文獻(xiàn) ［5］通過(guò)改進(jìn)遺傳算法的編碼方式、交叉、變異策略等方法提高了算法求解總加工時(shí)間最短的作業(yè)調(diào)度問(wèn)題的能力。

在實(shí)際的車間調(diào)度問(wèn)題中，企業(yè)的生產(chǎn)調(diào)度多以產(chǎn)品的訂單交貨期為主要依據(jù)［6］，故本文將最小化產(chǎn)品的提前/拖期懲罰作為目標(biāo)函數(shù)，以提高遺傳算法在作業(yè)車間調(diào)度問(wèn)題中的求解質(zhì)量和收斂速度為目標(biāo)，提出一種帶有記憶功能的改進(jìn)遺傳算法，并利用爬山算法提高其局部搜索能力，通過(guò)與其他算法計(jì)算結(jié)果的對(duì)比分析驗(yàn)證其優(yōu)越性。

1 問(wèn)題描述

作業(yè)車間提前/拖期調(diào)度問(wèn)題可以描述為:

(1)在m臺(tái)機(jī)器上生產(chǎn)n個(gè)相互獨(dú)立的產(chǎn)品，產(chǎn)品集合表示為N={1，2，……，n}，機(jī)器集合表示為M={1，2，……，m}，每個(gè)產(chǎn)品需經(jīng)過(guò)若干道工序才能完成，且每道工序在特定的機(jī)器上加工;

(2)sijk和tijk分別表示第i個(gè)產(chǎn)品的第j道工序在機(jī)器k上的開(kāi)始加工時(shí)間和加工時(shí)數(shù)，產(chǎn)品i的最后一道工序的開(kāi)始加工時(shí)間和所需加工時(shí)數(shù)分別是siek和tiek，則產(chǎn)品i的完工時(shí)間ci=siek+tiek;

(3)產(chǎn)品i的交貨時(shí)間窗口為 ［ei，di］，產(chǎn)品i單位時(shí)間的提前懲罰為ωi，拖期懲罰為αi，若產(chǎn)品在時(shí)間窗口之內(nèi)完成生產(chǎn)，則不受懲罰，否則對(duì)產(chǎn)品i進(jìn)行懲罰;

目標(biāo)函數(shù)為最小化產(chǎn)品的總懲罰，表示為:

公式 (1)表示的是目標(biāo)函數(shù)，即最小化所有產(chǎn)品的提前/拖期懲罰。公式 (2)表示工藝約束條件決定的各產(chǎn)品的各道工序的先后加工順序以及各道工序在相應(yīng)機(jī)器上的加工順序。其中，若機(jī)器h先于機(jī)器k加工產(chǎn)品i，則aihk為1否則為0，若產(chǎn)品i先于工件j在機(jī)器k上加工，則bijk為1否則為0;sik和tik分別表示產(chǎn)品i在機(jī)器k上的開(kāi)始加工時(shí)間和加工時(shí)數(shù);G是一個(gè)足夠大的正數(shù)。

2 遺傳算法的設(shè)計(jì)

為提高遺傳算法的收斂速度，采用一種可以保留較高適應(yīng)度個(gè)體的記憶功能，并利用爬山算法對(duì)記憶種群進(jìn)行局部搜索，從而增強(qiáng)算法的局部搜索能力。改進(jìn)遺傳算法的具體步驟如下:

(1)設(shè)置種群尺寸為PS，記憶庫(kù)尺寸為MS。

(2)產(chǎn)生初始種群P(t)，從初始種群中選取MS個(gè)較優(yōu)個(gè)體保存在記憶庫(kù)M(t)中。

(3)分別以交叉概率Pc和變異概率Pm對(duì)個(gè)體進(jìn)行交叉和變異操作，將得到的子代個(gè)體保存到種群O(t)中。

(4)以記憶庫(kù)M(t)中的染色體為初始解，利用爬山算法進(jìn)行局部搜索，得到更新后的記憶庫(kù)M’(t)。

(5)評(píng)價(jià)種群P(t)，O(t)和M’(t)，從中選擇出種群P(t+1)。

(6)進(jìn)行記憶庫(kù)的第二次更新，從種群P(t+1)中選取其中較優(yōu)的MS個(gè)個(gè)體更新記憶庫(kù)。

(7)如果滿足終止條件 (達(dá)到最大迭代次數(shù)N)則結(jié)束計(jì)算，否則轉(zhuǎn)向 (3)。

2.1 編碼設(shè)計(jì)

遺傳算法在進(jìn)行編碼時(shí)，必須要考慮染色體的合法性、有效性、冗余性以及表征解空間的完全性［7］。編碼設(shè)計(jì)的優(yōu)劣對(duì)算法的各子階段都有重大影響。好的編碼設(shè)計(jì)可以保證在交叉、變異后依然保持染色體的有效性和完全性。目前已提出的編碼方法有，基于優(yōu)先規(guī)則的表達(dá)法、基于工序的表達(dá)法、基于優(yōu)先表的表達(dá)法、基于工件的表達(dá)法、基于工件對(duì)關(guān)系的表達(dá)法、基于機(jī)器的表達(dá)法等［8］。

將基于工序表達(dá)法與機(jī)器表達(dá)法的實(shí)數(shù)編碼方法相結(jié)合，形成一種新的雙染色體矩陣編碼方式。對(duì)于m臺(tái)機(jī)器生產(chǎn)n種產(chǎn)品的問(wèn)題，基于工序表達(dá)的實(shí)數(shù)編碼，染色體有n×m個(gè)基因，每個(gè)代表產(chǎn)品的十進(jìn)制數(shù)都在基因中重復(fù)出現(xiàn)m次，工序調(diào)度的順序由染色體基因的順序決定;同樣基于機(jī)器表達(dá)的實(shí)數(shù)編碼，其染色體也有n×m個(gè)基因，每個(gè)染色體基因分別表示相應(yīng)產(chǎn)品的各道加工工序所在的機(jī)器編號(hào)。

2.2 種群的初始化及適應(yīng)度函數(shù)的確定

依據(jù)上述編碼方式的種群初始化很簡(jiǎn)便，首先建立一個(gè)隨機(jī)分配個(gè)體基因的循環(huán)，生成個(gè)體的第一行基因，再利用產(chǎn)品的工序順序約束生成個(gè)體的第二行基因。如此重復(fù)進(jìn)行，直至達(dá)到設(shè)定的種群規(guī)模。

根據(jù)目標(biāo)函數(shù)定義的適應(yīng)度函數(shù)如下所示:

式中:F為適應(yīng)度函數(shù)，F(xiàn)取值越大，總懲罰越小，其對(duì)應(yīng)調(diào)度方案的適應(yīng)度越高。

2.3 遺傳算子

2.3.1 復(fù)制

2.3.2 交叉

考慮到基于雙染色體矩陣編碼交叉后子代的調(diào)度可行性，基于部分映射雜交 (PMX)和染色體分離的思想提出一種部分映射交叉重排算子［9－10］。這種交叉方法的具體過(guò)程如下:

(1)分別在兩個(gè)父代染色體上選擇兩個(gè)步數(shù)相同的交叉點(diǎn)。

(2)兩個(gè)父代交換彼此交叉點(diǎn)之間的子串。

(3)確定被交換的子串間基因的映射關(guān)系。

(4)消除掉染色體中多余的基因，以相應(yīng)的缺失基因補(bǔ)充。

(5)根據(jù)產(chǎn)品相應(yīng)工序所需加工機(jī)器的約束，重新排列染色體中的第二行基因。舉例說(shuō)明部分映射交叉重排算子，如圖1所示，A、B為兩個(gè)父代染色體，經(jīng)交叉后得到兩個(gè)子代個(gè)體A’、B’。

2.3.3 變異

為保證變異后的個(gè)體仍為可行解，基于前面交叉算子的設(shè)計(jì)思想，采用互反變異重排方法進(jìn)行個(gè)體的變異操作。首先在染色體上隨機(jī)選擇兩個(gè)位置，然后交換這兩處的基因，再根據(jù)產(chǎn)品各工序所需加工機(jī)器的約束重排第二行的染色體基因［11］。

圖1 交叉算子Fig.1 Crossover operator

2.4 爬山操作

爬山算法，又稱局部搜索算法，是一種基于鄰域搜索技術(shù)的、沿著可能改進(jìn)解的質(zhì)量的方向進(jìn)行單方向搜索 (爬山)的搜索方法，其局部搜索能力很強(qiáng)，是一種常用的尋找局部最優(yōu)解的方法［12］。它在解的空間內(nèi)，以當(dāng)前節(jié)點(diǎn)為中心和其鄰域的節(jié)點(diǎn)值相比較，若其鄰域節(jié)點(diǎn)更優(yōu)，則用其替換當(dāng)前節(jié)點(diǎn)繼續(xù)搜索;反之則返回當(dāng)前節(jié)點(diǎn)繼續(xù)搜索。如此循環(huán)直至到達(dá)終止條件。

為彌補(bǔ)傳統(tǒng)遺傳算法局部搜索能力較弱的不足，采用基因逆轉(zhuǎn)算子來(lái)實(shí)現(xiàn)爬山操作，更新種群記憶庫(kù)。具體步驟如下:

(1)對(duì)于記憶庫(kù)中的每個(gè)個(gè)體，隨機(jī)選擇個(gè)體上的兩個(gè)點(diǎn)，再將兩點(diǎn)之間的元素逆序插回到原來(lái)的位置中。

(2)判斷逆轉(zhuǎn)后的個(gè)體適應(yīng)值是否增加，若增加則以逆轉(zhuǎn)后的個(gè)體替換原個(gè)體，否則仍保留原個(gè)體。

(3)重復(fù) (1)、(2)的操作，直至達(dá)到設(shè)定的迭代次數(shù)為止。

3 仿真實(shí)驗(yàn)

本節(jié)的仿真實(shí)驗(yàn)在Genuine Intel(R)T2130 1.87GHz處理器，2.0GB RAM，MATLAB R2011a環(huán)境下進(jìn)行。

3.1 仿真分析

為驗(yàn)證文中改進(jìn)遺傳算法的優(yōu)越性，將本文算法與文獻(xiàn)［2］中的遺傳算法 (IGA)進(jìn)行比較。取種群規(guī)模100，記憶庫(kù)規(guī)模20，交叉概率0.5，變異概率0.05，在不同規(guī)模 (n×m)下進(jìn)行實(shí)驗(yàn)對(duì)比。實(shí)驗(yàn)中生產(chǎn)機(jī)器的集合，各工序所需加工時(shí)間隨機(jī)產(chǎn)生，且滿足平均分布。由于篇幅有限在此僅列出6組實(shí)驗(yàn)結(jié)果，見(jiàn)表1，每種規(guī)模仿真實(shí)驗(yàn)20次，其中最優(yōu)值為所有運(yùn)算結(jié)果中目標(biāo)函數(shù)最小的值，平均值為每次運(yùn)行所得最優(yōu)值的平均值。

表1 方法比較Tab.1 Method comparison

從表1中可以看出，本文算法所求得的最優(yōu)值和平均值均優(yōu)于IGA，而且隨著規(guī)模的不斷擴(kuò)大，效果更加明顯，體現(xiàn)了本文算法的優(yōu)越性。

3.2 實(shí)例應(yīng)用

以某加工制造企業(yè)為例，驗(yàn)證本文算法在實(shí)際應(yīng)用中的可行性和有效性，設(shè)提前懲罰為0.8，拖期懲罰設(shè)為1.4，產(chǎn)品各生產(chǎn)工序所需的加工時(shí)間、加工機(jī)器以及各產(chǎn)品的交貨時(shí)間窗口見(jiàn)表2。

表2 加工數(shù)據(jù)Tab.2 Machining data

設(shè)定遺傳算法的參數(shù)為:交叉概率Pc=0.4，變異概率Pm=0.02，種群尺寸PS=100，記憶庫(kù)尺寸MS=20，最大迭代次數(shù)N=100，爬山算法的最大迭代次數(shù)N’=5。分別采用不帶記憶功能的普通遺傳算法和文中的改進(jìn)算法，進(jìn)行20次仿真實(shí)驗(yàn)，兩種算法的實(shí)驗(yàn)結(jié)果見(jiàn)表3，圖2為兩種算法的收斂情況比較。

表3 實(shí)驗(yàn)結(jié)果Tab.3 Experimental results

圖2 兩種算法收斂情況Fig.2 Convergence situation of the two algorithms

從表3中可以看出，本文算法求解出了問(wèn)題的最優(yōu)解0，在20次仿真中搜索到最優(yōu)解的次數(shù)為18次，而且搜索到最優(yōu)值的平均迭代次數(shù)和平均計(jì)算時(shí)間都要優(yōu)于普通遺傳算法，說(shuō)明改進(jìn)遺傳算法的運(yùn)算性能穩(wěn)定，搜索能力強(qiáng)。通過(guò)圖2的比較則可以進(jìn)一步看出，在整個(gè)搜索過(guò)程中，本文算法的收斂速度較快，在41代左右達(dá)到全局最優(yōu)解0，而普通遺傳算法的收斂速度明顯較慢，且在43代左右以后逐步陷入局部最優(yōu)。綜上所述可知，無(wú)論是在求解質(zhì)量還是收斂速度上，文中的改進(jìn)遺傳算法都優(yōu)于不帶記憶功能的普通遺傳算法。

仿真結(jié)果表明，通過(guò)本文算法可以求解出懲罰值為0的最佳調(diào)度方案，即所有產(chǎn)品均可在交貨窗口內(nèi)按時(shí)完成生產(chǎn)。求解出的最優(yōu)個(gè)體如下:

4 結(jié)論

為求解作業(yè)車間提前/拖期調(diào)度問(wèn)題，文中提出一種基于雙染色體矩陣編碼的改進(jìn)遺傳算法，并利用記憶庫(kù)和爬山算法提升算法的尋優(yōu)能力和搜索速度。改進(jìn)遺傳算法的編碼簡(jiǎn)潔、直觀，收斂性能好，并能較好地解決相關(guān)的車間調(diào)度問(wèn)題，滿足大規(guī)模此類調(diào)度問(wèn)題的需要。下一步將繼續(xù)研究結(jié)合其他啟發(fā)式方法的改進(jìn)遺傳算法在多目標(biāo)作業(yè)車間調(diào)度問(wèn)題中的應(yīng)用，并進(jìn)一步提高算法的性能。

【參 考 文 獻(xiàn)】

［1］王萬(wàn)良，吳啟迪．生產(chǎn)調(diào)度智能算法及其應(yīng)用［M］．北京:科學(xué)出版社，2007．

［2］蘇 瑩，李 杰，陰慧輝，等．改進(jìn)遺傳算法求解作業(yè)車間調(diào)度問(wèn)題［J］．制造技術(shù)與機(jī)床，2010，10:104 －108．

［3］黃 志，黃文奇．一種基于禁忌搜索的作業(yè)車間調(diào)度算法［J］．計(jì)算機(jī)工程與應(yīng)用，2006，03:12 －14．

［4］趙良輝，鄧飛其．用于作業(yè)車間調(diào)度的模擬退火算法［J］．制造業(yè)自動(dòng)化，2006，28(3):10 －23．

［5］蘇 春，王大俠．基于改進(jìn)遺傳算法的偏柔性作業(yè)車間調(diào)度［J］．工業(yè)工程，2010，13(6):61 －65．

［6］陳 杰，張力菠．供應(yīng)鏈環(huán)境中交貨期問(wèn)題的研究［J］．中國(guó)制造業(yè)信息化，2005，34(4):105 －107．

［7］潘全科，朱劍英．多工藝路線的作業(yè)車間模糊調(diào)度優(yōu)化［J］．中國(guó)機(jī)械工程，2004，15(24):2199 －2202．

［8］呂文閣，劉志勇，成思源，等．基于競(jìng)選算法的生產(chǎn)調(diào)度問(wèn)題的研究［J］．機(jī)床與液壓，2009，37(10):33 －36．

［9］玄光男，程潤(rùn)偉．遺傳算法與工程優(yōu)化［M］．北京:清華大學(xué)出版社，2004．

［10］韓冰源，肖生苓．配送中心線路優(yōu)化方法的探討［J］．森林工程，2005，21(2):67 －68．

［11］郎茂祥．配送車輛優(yōu)化調(diào)度模型與算法［M］．北京:電子工業(yè)出版社，2009．

［12］郎茂祥，胡思繼．用混合遺傳算法求解物流配送優(yōu)化問(wèn)題的研究［J］．中國(guó)管理科學(xué)，2002，10(5):51 －56．