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

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

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

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

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

1 問題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 編碼設(shè)計

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

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

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

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

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

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

2.3 遺傳算子

2.3.1 復(fù)制

2.3.2 交叉

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

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

(2)兩個父代交換彼此交叉點之間的子串。

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

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

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

2.3.3 變異

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

圖1 交叉算子Fig.1 Crossover operator

2.4 爬山操作

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

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

(1)對于記憶庫中的每個個體，隨機選擇個體上的兩個點，再將兩點之間的元素逆序插回到原來的位置中。

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

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

3 仿真實驗

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

3.1 仿真分析

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

表1 方法比較Tab.1 Method comparison

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

3.2 實例應(yīng)用

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

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

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

表3 實驗結(jié)果Tab.3 Experimental results

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

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

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

4 結(jié)論

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

【參 考 文 獻】

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

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

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

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

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

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

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

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

［9］玄光男，程潤偉．遺傳算法與工程優(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)化問題的研究［J］．中國管理科學(xué)，2002，10(5):51 －56．