改進(jìn)的遺傳算法求解柔性作業(yè)車間調(diào)度問(wèn)題

劉月凡，朱 星

(大連交通大學(xué)軟件學(xué)院，遼寧 大連116028)*

0 引言

作業(yè)車間調(diào)度問(wèn)題(Job-shop scheduling problem，JSP)是研究生產(chǎn)線調(diào)度問(wèn)題最常用的模型之一［1］，也是實(shí)現(xiàn)先進(jìn)制造和提高生產(chǎn)效率的基礎(chǔ)和關(guān)鍵［2］.柔性作業(yè)車間調(diào)度問(wèn)題(Flexible jobshop scheduling problem，F(xiàn)JSP)是傳統(tǒng)作業(yè)車間調(diào)度問(wèn)題的擴(kuò)展，在傳統(tǒng)的作業(yè)車間調(diào)度問(wèn)題中，每個(gè)工件的加工工序是確定的，每一道工序的加工機(jī)器和加工時(shí)間也是確定的，而在柔性作業(yè)車間調(diào)度問(wèn)題中，每個(gè)工件的每一道工序可以在多個(gè)可選擇的加工機(jī)器上進(jìn)行加工，并且不同的加工機(jī)器所需要的加工時(shí)間是不同的，增加了調(diào)度的靈活性，比較符合生產(chǎn)的實(shí)際情況［3］.

柔性作業(yè)車間調(diào)度問(wèn)題已經(jīng)被證明是更復(fù)雜的NP-Hard問(wèn)題，因而難以取得最優(yōu)解.目前，求解FJSP的常用方法有禁忌搜索(TS)，模擬退火(SA)和遺傳算法(GA)等［4-6］.其中遺傳算法以其操作簡(jiǎn)單、魯棒性強(qiáng)、搜索全局最優(yōu)解速度快等特點(diǎn)，在生產(chǎn)調(diào)度領(lǐng)域得到了廣泛的應(yīng)用.

遺傳算法是由美國(guó)J.Holland教授于1975年提出的，是一種模擬自然進(jìn)化過(guò)程的一種優(yōu)化算法.由于傳統(tǒng)的遺傳算法存在著較大的缺陷，國(guó)內(nèi)外學(xué)者已從不同角度對(duì)其進(jìn)行了改進(jìn)，本文對(duì)傳統(tǒng)遺傳算法的初始種群進(jìn)行了改進(jìn)，以提高初始解的質(zhì)量.

1 柔性作業(yè)車間調(diào)度模型

設(shè)有 n個(gè)待加工工件 J(J1，J2，…，Jn)，在 m臺(tái)設(shè)備上加工 M(M1，M2，…，Mm)，每個(gè)工件 Ji有Pi(Pi1，Pi2，…，Pin)道工序，每道工序可在一臺(tái)或多臺(tái)設(shè)備上加工，同一道工序在不同設(shè)備上加工的時(shí)間可能不等，工序 Pik的可選機(jī)器集為Mik(Mik?M)，每臺(tái)設(shè)備的加工時(shí)間從0開始，加工完所有工件的完成時(shí)間為ETMi.本文以最小化最大完工時(shí)間為性能指標(biāo)，其目標(biāo)函數(shù)為:

f(x)=min(max(ETMi))，1≤ i≤ m

模型需滿足如下約束條件:

(1)同一工件的工序加工順序確定;

(2)每道工序必須在它的上一道工序加工完成后才能開始加工;

(3)每道工序只能選擇一臺(tái)設(shè)備進(jìn)行操作;

(4)每臺(tái)設(shè)備在同一時(shí)間只能加工一個(gè)工件的一道工序;

(5)每道工序在設(shè)備上操作時(shí)都不允許被中斷;

(6)不同工件工序之間沒(méi)有先后約束條件.一個(gè)包含3個(gè)工件、5臺(tái)機(jī)器的FJSP的問(wèn)題描述如表1所示.

表1 3×5 FJSP問(wèn)題加工時(shí)間表

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

(1)基因編碼

常用的遺傳算法編碼方案有二進(jìn)制編碼、格雷碼編碼、矩陣編碼、自然數(shù)編碼等，本文采用自然數(shù)編碼，每條染色體表示一個(gè)可行解，同時(shí)采用雙層編碼，第一層編碼為基于工件的工序編碼，編碼長(zhǎng)度為所有工件工序之和，基因值代表工件號(hào)，基因值出現(xiàn)的次數(shù)代表該工件的工序總數(shù)，第二層編碼為對(duì)應(yīng)于第一層工件工序的機(jī)器編碼，所以編碼長(zhǎng)度也為所有工件工序之和.以表1為例，圖1中染色體表示的工序順序?yàn)?(O31，O11，O12，O21，O22，O32，O13，O33)，染色體表示的機(jī)器序列為(M2，M4，M2，M1，M4，M5，M3，M4).

圖1 基于工序和機(jī)器的編碼

(2)產(chǎn)生初始種群

初始種群的優(yōu)良對(duì)生物進(jìn)化會(huì)產(chǎn)生很大的影響，本文對(duì)初始種群的機(jī)器選擇進(jìn)行了改進(jìn)，首先隨機(jī)生成初始種群的工序編碼，工序編碼生成后就要對(duì)應(yīng)生成機(jī)器編碼，每個(gè)工件工序在對(duì)應(yīng)可選機(jī)器集中選擇機(jī)器時(shí)，是以不同的概率的來(lái)選擇不同的機(jī)器，機(jī)器加工時(shí)間短的以大概率被選擇，相比之下，機(jī)器加工時(shí)間長(zhǎng)的以小概率被選擇，這樣既保證了機(jī)器選擇的隨機(jī)性，也優(yōu)化了初始種群.

(3)適應(yīng)度函數(shù)的確定

本文以最小化最大完工時(shí)間為目標(biāo)函數(shù)，故選擇全部工件完工時(shí)間作為評(píng)價(jià)種群優(yōu)劣的標(biāo)準(zhǔn)，設(shè)n個(gè)待加工工件在m(M1，M2，…，Mm)臺(tái)設(shè)備上加工，所有加工工件工序在設(shè)備上的最后完工時(shí)間為 ETMi(i=1，2，…，m)，T=max(ETMi)，則適應(yīng)度函數(shù)fi=1/T，T越小，則適應(yīng)度越大，即個(gè)體越優(yōu).

(4)選擇

選擇操作的目的是為了保留優(yōu)良個(gè)體，使他們可以遺傳到下一代.本文采用精英保留策略和輪盤賭法相結(jié)合的方法，對(duì)父代個(gè)體和子代個(gè)體進(jìn)行選擇時(shí)直接將最優(yōu)個(gè)體和次優(yōu)個(gè)體遺傳到下一代，然后對(duì)剩余的個(gè)體采用輪盤賭法進(jìn)行選擇，選擇出p-2個(gè)個(gè)體到下一代進(jìn)行遺傳操作.若種群規(guī)模為p，個(gè)體i的適應(yīng)度為fi，則個(gè)體i被選擇的概率pi為

即適應(yīng)度越高的個(gè)體被選擇的概率就越大.

(5)交叉

交叉操作是產(chǎn)生新個(gè)體的主要方法，提高全局搜索能力［7］.本文采用單點(diǎn)交叉方式，即隨機(jī)產(chǎn)生一個(gè)交叉點(diǎn)，交換交叉點(diǎn)后的基因.從種群中隨機(jī)選擇兩個(gè)個(gè)體，交換兩個(gè)個(gè)體工序編碼的交叉點(diǎn)后面的基因，將交叉后工件多余的工序替換為其他工件缺失的工序;機(jī)器部分則按交叉前工件工序所選擇的機(jī)器進(jìn)行相應(yīng)調(diào)整以保證其子代染色體的合法性.

(6)變異

變異操作的目的是改變算法的局部搜索能力，有助于維持進(jìn)化群體的多樣性，防止過(guò)早陷入局部最優(yōu)［8］.本文采用互換方式，即隨機(jī)產(chǎn)生兩個(gè)變異點(diǎn)，交換兩點(diǎn)的基因值.從種群中隨機(jī)選擇一個(gè)個(gè)體，對(duì)該個(gè)體的工序編碼部分隨機(jī)產(chǎn)生兩個(gè)變異點(diǎn)，交換兩點(diǎn)的基因值，同時(shí)將交換的基因位所對(duì)應(yīng)的機(jī)器號(hào)也進(jìn)行交換.

3 仿真實(shí)例分析

表2給出了6×6(6個(gè)工件，6臺(tái)機(jī)器)FJSP的加工工序，機(jī)器選擇和加工時(shí)間矩陣表.分別用標(biāo)準(zhǔn)遺傳算法和本文提出的改進(jìn)遺傳算法對(duì)工件最小化最大完工時(shí)間進(jìn)行優(yōu)化計(jì)算，并分析優(yōu)化計(jì)算結(jié)果.

遺傳算法采用以下參數(shù):種群規(guī)模為100，進(jìn)化代數(shù)為100，交叉概率Pc=0.8，變異概率Pm=0.1.算法運(yùn)行10次，最優(yōu)的選擇如圖2、3所示.

表2 6個(gè)工件在6臺(tái)機(jī)器上FJSP實(shí)例

從圖2，3中可以看出，標(biāo)準(zhǔn)遺傳算法的最大完工時(shí)間為20，收斂代數(shù)為75代左右;改進(jìn)遺傳算法的最大完工時(shí)間為16，收斂代數(shù)為35代左右.改進(jìn)遺傳算法既縮短了工件完工時(shí)間，也加快了收斂代數(shù).從而驗(yàn)證了改進(jìn)遺傳算法的可行性.

4 結(jié)論

傳統(tǒng)遺傳算法在進(jìn)行種群初始化時(shí)采用的大多是隨機(jī)選擇方式，而本文提出了一種新的種群初始化方法，提高了種群初始解的質(zhì)量.最后對(duì)改進(jìn)遺傳算法進(jìn)行了仿真實(shí)驗(yàn)，并將結(jié)果與標(biāo)準(zhǔn)遺傳算法進(jìn)行比較，結(jié)果表明了本算法的優(yōu)越性和可行性.

［1］JAIN A S，MEERAN S.Deterministic job-shop scheduling:Past，present and future［J］.European Journal of Operational Research，1999，113(2):390-434.

［2］彭建剛，劉明周，張銘鑫，等.基于改進(jìn)非支配排序的云模型進(jìn)化多目標(biāo)柔性作業(yè)車間調(diào)度［J］.機(jī)械工程學(xué)報(bào)，2014，50(12):198-205.

［3］張國(guó)輝，石楊.基于改進(jìn)遺傳算法求解柔性作業(yè)車間調(diào)度問(wèn)題［J］.機(jī)械科學(xué)與技術(shù)，2011，30(11):1890-1894.

［4］MASTROLILLI M，GAMBARDELLA L M.Effective neighborhood functions for the flexible job shop problem［J］.Journal of Scheduling，2000，3(1):3-20.

［5］張維存，鄭丕諤，吳曉丹.蟻群遺傳算法求解能力約束的柔性作業(yè)車間調(diào)度問(wèn)題［J］.計(jì)算機(jī)集成制造系統(tǒng)，2007，13(2):333-362.

［6］張超勇，饒運(yùn)清，李培根，等.柔性作業(yè)車間調(diào)度問(wèn)題的兩級(jí)遺傳算法［J］.機(jī)械工程學(xué)報(bào)，2007，43(4):119-124.

［7］李運(yùn)霞，杜娟，孫王路.基于多種群遺傳算法的路徑柔性車間調(diào)度問(wèn)題［J］.組合機(jī)床與自動(dòng)化加工技術(shù)，2014(3):152-155.

［8］周俊虎，平傳娟，劉建忠，等.基于遺傳算法的動(dòng)力配煤模型［J］.煤炭學(xué)報(bào)，2003，28(5):547-551.