方　霞，曹　潔

（湖南文理學(xué)院，計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖南，常德　415000）

基于遺傳算法的多目標(biāo)生產(chǎn)車間調(diào)度研究

方霞，曹潔

（湖南文理學(xué)院，計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖南，常德415000）

針對(duì)生產(chǎn)調(diào)度多目標(biāo)動(dòng)態(tài)復(fù)雜性，提出了一種基于AOE圖尋找關(guān)鍵路徑的改進(jìn)遺傳算法。采用基于工件和機(jī)器相結(jié)合的編碼方法，根據(jù)多目標(biāo)要求，設(shè)計(jì)了相應(yīng)的交叉遺傳算子。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的遺傳算法符合車間實(shí)際應(yīng)用情況，對(duì)解決多目標(biāo)動(dòng)態(tài)車間調(diào)度問題有實(shí)際的應(yīng)用意義。

遺傳算法；多目標(biāo)；車間調(diào)度；關(guān)鍵路徑

1　概述

調(diào)度功能是車間管理的核心功能之一，它直接關(guān)系著車間能否在指定的時(shí)間段內(nèi)合理利用有限的制造資源完成相應(yīng)的加工任務(wù)。調(diào)度問題不但沖突多、求解過程相當(dāng)復(fù)雜，而且在不同制造環(huán)境下所考慮的約束、達(dá)到的目的等均不相同，使得調(diào)度問題之間的差別很大［1］，特別是對(duì)于多目標(biāo)問題，求解尤其困難。

組合優(yōu)化問題通常具有大量的局部極值點(diǎn)，往往是不可微的、不連續(xù)的、多維的、有約束條件的、高度非線性的NP完全問題，因此，精確求解組合優(yōu)化問題往往是不可能的。生產(chǎn)調(diào)度（JSP）問題是一類典型NP完全問題，隨著問題規(guī)模的擴(kuò)大，會(huì)發(fā)生組合爆炸，算法復(fù)雜性呈指數(shù)增長［2-3］。各類混合遺傳算法是解決實(shí)際調(diào)度問題最有效的途徑和最有前途的調(diào)度方法［4］。在充分進(jìn)行調(diào)查研究和比較各類優(yōu)化搜索方法［5-9］的基礎(chǔ)上，提出一種混合遺傳算法來有效解決生產(chǎn)調(diào)度中的多目標(biāo)問題。

2　JSP問題描述

JSP（Job-Shop）問題研究n個(gè)工件在m臺(tái)機(jī)器上的加工，已知各操作的加工時(shí)間和各工件在各機(jī)器上的加工次序約束，要求確定與工藝約束條件相容的各機(jī)器上所有工件的加工時(shí)間或完成時(shí)間或加工次序［10］。

使加工性能指標(biāo)達(dá)到最優(yōu)，具體滿足如下條件：

1）同一時(shí)刻同一臺(tái)機(jī)器只能加工一個(gè)工件；

2）每個(gè)工件在某一時(shí)刻只能在一臺(tái)機(jī)器上加工，不能中途中斷每一個(gè)操作；

3）不同工件的工序之間有部分聯(lián)系；

4）不同工件具有優(yōu)先級(jí)的差別；

5）每個(gè)工件相鄰工序之間的間隔為零（準(zhǔn)備時(shí)間可計(jì)入機(jī)器的加工時(shí)間）。

AOE帶權(quán)有向無環(huán)網(wǎng)模型是描述JSP調(diào)度問題的一種行之有效的方法，如圖1所示。

圖1　加工環(huán)節(jié)示意AOE網(wǎng)

頂點(diǎn)表示事件，弧aij表示工件i的某道工序j，權(quán)表示工序加工時(shí)間（為了簡化模型，準(zhǔn)備時(shí)間包含于加工時(shí)間內(nèi)視為整體）。

分析AOE網(wǎng)可以得到生產(chǎn)過程中的關(guān)鍵路徑，對(duì)于解決生產(chǎn)調(diào)度中的瓶頸問題有很強(qiáng)的現(xiàn)實(shí)意義。通過改善關(guān)鍵活動(dòng)的工效，可以有效縮短整個(gè)工期，提高設(shè)備利用率。

車間調(diào)度分為靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度兩種。靜態(tài)調(diào)度目標(biāo)為在滿足生產(chǎn)任務(wù)交貨期的前提下，盡可能提高設(shè)備資源的利用率，減少調(diào)整時(shí)間，使生產(chǎn)周期最短。靜態(tài)調(diào)度是車間計(jì)劃進(jìn)入執(zhí)行階段的基礎(chǔ)和依據(jù)，遺傳算法（GA）在靜態(tài)調(diào)度問題中已經(jīng)有成功的應(yīng)用。動(dòng)態(tài)調(diào)度指在車間實(shí)際的運(yùn)行過程中，存在著不可預(yù)期的被稱為動(dòng)態(tài)時(shí)間的隨機(jī)擾動(dòng)，如機(jī)器故障、訂單的突然加入或取消等，因此往往需要不斷地進(jìn)行動(dòng)態(tài)重調(diào)度［11-13］。具體生產(chǎn)調(diào)度加工目標(biāo)和解決策略如下：

1）企業(yè)成本最小化、降低庫存；

2）按期交貨訂單數(shù)量最大化?？紤]縮短制造周期方面，則調(diào)用完工時(shí)間最早的工序；考慮不同交貨期方面，則計(jì)算不同完工提前期，根據(jù)事情緊急情況分別對(duì)待；

3）資源設(shè)備均衡利用。考慮減少機(jī)器負(fù)荷方面，則調(diào)用加工時(shí)間最小的工序；考慮設(shè)備能力方面，則涉及加班、外協(xié)等問題；

4）任務(wù)優(yōu)先數(shù)的考慮。在上層決策時(shí)，充分關(guān)注市場(chǎng)銷售、機(jī)器生產(chǎn)、庫存等方面問題；而裝配完成情況與加工次序緊密聯(lián)系；動(dòng)態(tài)調(diào)度事，對(duì)于缺件未能按時(shí)完工，需要優(yōu)先加工，將其優(yōu)先級(jí)增大；

5）減少調(diào)整準(zhǔn)備時(shí)間。充分考慮運(yùn)輸時(shí)間的問題，其中涉及到設(shè)備地理位置情況、工件準(zhǔn)備時(shí)間、刀具準(zhǔn)備時(shí)間等方面。

3　混合遺傳算法描述

3.1混合遺傳算法

遺傳算法（GA）是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化算法，在許多領(lǐng)域中得到了成功的應(yīng)用，如函數(shù)優(yōu)化、旅行商問題等。利用遺傳算法已經(jīng)成功解決靜態(tài)生產(chǎn)調(diào)度問題，本文重點(diǎn)針對(duì)動(dòng)態(tài)調(diào)度中的多目標(biāo)問題，采用以遺傳算法為基礎(chǔ)，結(jié)合AOE找尋關(guān)鍵路徑的混合遺傳算法來彌補(bǔ)遺傳算法的局部搜索能力的不足，根據(jù)適應(yīng)度的變化采用相應(yīng)的交叉變異算子，避免“早熟”收斂現(xiàn)象發(fā)生，對(duì)于生產(chǎn)調(diào)度中的動(dòng)態(tài)多目標(biāo)問題進(jìn)行有效的解決［11-13］。

3.2編碼方案

編碼問題是算法設(shè)計(jì)的首要和關(guān)鍵問題，常見的有二進(jìn)制編碼、格雷碼編碼、實(shí)數(shù)編碼、符號(hào)編碼、排列編碼、二倍體編碼、DNA編碼、多參數(shù)編碼、矩陣編碼等［14］。解決經(jīng)典的工作車間調(diào)度問題有基于工序的編碼、基于機(jī)器編碼、基于操作的編碼等多種方法。采用基于工序和機(jī)器的編碼［15］，工序aij用Gi來表示工件i，其出現(xiàn)的次序表示工序加工順序；機(jī)器m用Jm表示某工序加工的機(jī)器。如染色體J1G1-J2G2-J1G1-J2G1表示工件1第1道工序在機(jī)器1上加工，工件2第1道工序在機(jī)器2上加工，工件1第2道工序在機(jī)器1上加工，工件1第3道工序在機(jī)器2上加工。

3.3種子選擇

首先對(duì)各工序生成的AOE網(wǎng)進(jìn)行拓?fù)渑判蚣澳嫱負(fù)渑判蚺袛?，在該前提下求得關(guān)鍵路徑，并對(duì)關(guān)鍵活動(dòng)優(yōu)先分配機(jī)器，保證關(guān)鍵活動(dòng)的正常如期完成。將關(guān)鍵活動(dòng)基因置前，后隨機(jī)生成一定數(shù)量的不完全染色體種子，結(jié)合工序要求對(duì)非關(guān)鍵路徑上的工序進(jìn)行機(jī)器分配，形成最終的染色體。采用常用的輪盤賭方法進(jìn)行選擇適應(yīng)度高的個(gè)體，為了防止算法收斂于局部解，種群規(guī)模取30個(gè)。

為了保證所得到的最優(yōu)個(gè)體不會(huì)被交叉、變異等遺傳操作所破壞，結(jié)合使用最優(yōu)保存策略，若當(dāng)前群體中最佳個(gè)體的適應(yīng)度低于總的迄今為止的最好個(gè)體的適應(yīng)度，用迄今為止的最好個(gè)體替換掉當(dāng)前群體中的最差個(gè)體。

3.4適應(yīng)度函數(shù)

多目標(biāo)優(yōu)化問題是指一個(gè)問題存在多個(gè)需要優(yōu)化的性能指標(biāo)，每個(gè)性能指標(biāo)都有其不同約束條件，多目標(biāo)優(yōu)化就是要尋求一個(gè)在滿足各個(gè)約束條件下且能使各個(gè)需要優(yōu)化的目標(biāo)能得到優(yōu)化解［11-12］。企業(yè)生產(chǎn)調(diào)度問題是一個(gè)典型的多目標(biāo)優(yōu)化問題，生產(chǎn)系統(tǒng)的效率取決于很多因素如生產(chǎn)周期 （市場(chǎng)銷售）、機(jī)器生產(chǎn)的利用率、庫存（成本）等，上層管理決策對(duì)各目標(biāo)的考慮權(quán)重不同也直接決定著生產(chǎn)調(diào)度的結(jié)果發(fā)生變化。本文算法在交叉變異過程中使用相關(guān)參數(shù)α、β進(jìn)行環(huán)境適應(yīng)性調(diào)整，以達(dá)到多目標(biāo)綜合決策要求。

3.5交叉變異操作

交叉算法直接決定著遺傳算法的全局搜索能力，基于關(guān)鍵路徑的交叉算子操作如下；首先根據(jù)交叉概率和適應(yīng)度權(quán)重的配置選擇一對(duì)父母個(gè)體，僅對(duì)后續(xù)非關(guān)鍵基因部分進(jìn)行交叉操作；隨機(jī)選擇非關(guān)鍵活動(dòng)上的一個(gè)工件，其在父母個(gè)體中對(duì)應(yīng)的x個(gè)操作不變，父母個(gè)體剩余其他操作按順序進(jìn)行對(duì)應(yīng)變換，分別得到新的兩個(gè)子代個(gè)體。

變異算子決定了遺傳算法的局部搜索能力，良好的算子可以有效的維持群體的多樣性，防止早熟現(xiàn)象的出現(xiàn)。為了保證關(guān)鍵活動(dòng)的順利完成以及種群的多樣性，變異操作分為兩大步驟進(jìn)行：首先根據(jù)變異概率對(duì)關(guān)鍵路徑上的工序進(jìn)行機(jī)器配置變異，然后對(duì)非關(guān)鍵工序進(jìn)行局部重新定位［16-18］。

3.6算法流程

1）調(diào)度任務(wù)數(shù)據(jù)初始化；

2）建立AOE網(wǎng)，求出關(guān)鍵路徑，隨機(jī)生成初始種群；

3）計(jì)算適應(yīng)度，結(jié)合使用最優(yōu)保存策略采用輪盤賭方法進(jìn)行選擇；

4）基于關(guān)鍵路徑進(jìn)行交叉變異操作；

5）滿足終止條件，轉(zhuǎn)步驟6，否則轉(zhuǎn)步驟3；

6）輸出最終解集。

4　計(jì)算應(yīng)用實(shí)例與實(shí)驗(yàn)仿真

系統(tǒng)演示使用VisualC++編程工具完成，如下是一個(gè)標(biāo)準(zhǔn)實(shí)例：已知實(shí)際工作環(huán)境及條件：5類機(jī)床，數(shù)量分別為2、1、1、1、1臺(tái)，編號(hào)i-j表示i類機(jī)床第j臺(tái)；工件號(hào)和工序號(hào)從1開始排列，交貨期均設(shè)為零值，具體數(shù)據(jù)見表1。

表1　加工工序相關(guān)數(shù)據(jù)

利用關(guān)鍵路徑的遺傳算法得到實(shí)驗(yàn)結(jié)果仿真如圖2所示。圖中aij表示第i個(gè)工件第j工序?？梢钥闯稣w的加工順序安排合理，充分考慮了關(guān)鍵工件的加工工序，使得工期達(dá)到最短，成本最低。

圖2　實(shí)驗(yàn)數(shù)據(jù)仿真

5　結(jié)論

針對(duì)制造企業(yè)生了車間生產(chǎn)調(diào)度系統(tǒng)框架。根據(jù)生產(chǎn)調(diào)度中動(dòng)態(tài)多目標(biāo)特征，使用相應(yīng)的交叉變異算子改善了遺傳算法的搜索性能，在算法流程中考慮了同類型機(jī)床的負(fù)荷平衡優(yōu)化問題，最后使用該算法對(duì)實(shí)例進(jìn)行了調(diào)度仿真，通過分析比較，表明本文的調(diào)度算法性能良好，能夠較好的適應(yīng)制造環(huán)境實(shí)際。

［1］ 熊銳，吳澄.車間生產(chǎn)調(diào)度問題的技術(shù)現(xiàn)狀與發(fā)展趨勢(shì)［J］.清華大學(xué)學(xué)報(bào)（自然科學(xué)版），1998，10（38）：55-60.

［2］ 徐俊剛，戴國忠，王宏安.生產(chǎn)調(diào)度理論和方法研究綜述［J］.計(jì)算機(jī)研究與發(fā)展，2004，41（2）：257-267.

［3］ 余建軍，張定超，周銘新.生產(chǎn)調(diào)度綜述［J］.中國制造業(yè)信息化，2009，38（17）：13-17.

［4］ 王東成，何衛(wèi)平，王邦龍.基于混合遺傳算法的敏捷車間調(diào)度研究［J］.航空精密制造技術(shù)，2006，42（1）：43-47.

［5］ 石苓，竇延平.基于生產(chǎn)計(jì)劃排單的遺傳算法的優(yōu)化與應(yīng)用［J］.計(jì)算機(jī)仿真，2005，（4）.86-88.

［6］ 王展青，魏毅峰.求解JSP問題的改進(jìn)遺傳算法［J］.武漢理工大學(xué)學(xué)報(bào)，2006，28（2）：40-42.

［7］ 周興斌，李平.基于優(yōu)先數(shù)的智能生產(chǎn)調(diào)度系統(tǒng)［J］.計(jì)算機(jī)工程與應(yīng)用，2003，（11）：199-201.

［8］ 劉紅軍，趙帥.一種基于混合遺傳算法的車間生產(chǎn)調(diào)度的研究［J］.制造業(yè)自動(dòng)化，2011，33（9）：33-35.

［9］ 汪紅兵，徐安軍，姚琳等.應(yīng)用改進(jìn)遺傳算法求解煉鋼連鑄生產(chǎn)調(diào)度問題［J］.北京科技大學(xué)學(xué)報(bào)，2010，32（9）：1232-1237.

［10］莊新村，盧宇灝，李從心.基于遺傳算法的車間調(diào)度問題［J］.計(jì)算機(jī)工程，2006，（1）：193-194`

［11］谷峰，陳華平，盧冰原.基于遺傳算法的多目標(biāo)柔性工作車間調(diào)度問題求解［J］.運(yùn)籌與管理，2006，15（1）：134-139.

［12］趙建峰，朱曉春，汪木蘭，等.基于遺傳算法柔性制造系統(tǒng)生產(chǎn)調(diào)度的優(yōu)化與仿真.制造業(yè)自動(dòng)化，2010，32（5）：156-159.

［13］譚輝，張洪偉，朱麗.APS系統(tǒng)中基于改進(jìn)的遺傳算法的分布式排產(chǎn)研究［J］.計(jì)算機(jī)應(yīng)用研究，2005，（6）：76-78.

［14］余有明，劉玉樹，閻光偉.遺傳算法的編碼理論與應(yīng)用［J］.計(jì)算機(jī)工程與應(yīng)用，2006，（3）：86-89.

［15］韋勇福，曾盛綽.基于遺傳算法的車間生產(chǎn)調(diào)度系統(tǒng)研究［J］.2014，11：205-207.

［16］孫亮，王曉原，張運(yùn)才.自適應(yīng)超啟發(fā)式遺傳算法求解隨機(jī)型生產(chǎn)調(diào)度問題［J］.小型微型計(jì)算機(jī)系統(tǒng)，2013，34（9）：2158-2163.

［17］袁喜連，劉勇，肖翀.遺傳算法在銅板帶生產(chǎn)調(diào)度中的應(yīng)用研究［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45（27）：213-215.

［18］高家全.遺傳算法在家紡企業(yè)生產(chǎn)調(diào)度中的應(yīng)用［J］.哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2009，41（6）：229-231.

TP18