華北電力大學(xué)自動化系 白 康

1.引言

在基本的車間作業(yè)調(diào)度問題(Job Shop Problem，簡稱JSP)中，所有工件的工序都只能由指定的某一臺機(jī)器進(jìn)行加工。隨著加工技術(shù)、自動化技術(shù)的發(fā)展，特別是柔性制造系統(tǒng)的出現(xiàn)，此傳統(tǒng)限制已被突破，工件具有多個(gè)可選擇的加工路線，即路徑柔性已經(jīng)成為生產(chǎn)的實(shí)際需求。生產(chǎn)技術(shù)的進(jìn)步推動著調(diào)度理論研究的進(jìn)深，具有柔性路徑的柔性車間作業(yè)調(diào)度(Flexible Job Shop Problem，簡稱FJSP)研究也開始進(jìn)入人們的視野并引起重視[1-3]。

目前，遺傳算法以其優(yōu)良的計(jì)算性能和顯著的應(yīng)用效果，在求解JSP問題和FJSP問題中獲得了很大的成功[4-11]。本文使用遺傳算法來求解FJSP問題，提出了多維矩陣的編碼方式，以及相應(yīng)的選擇、交叉、變異操作設(shè)計(jì)，保證遺傳操作每一步產(chǎn)生的染色體都是合法的，避免了傳統(tǒng)柔性車間作業(yè)調(diào)度中繁瑣的染色體合法化修復(fù)工作。最后用一個(gè)調(diào)度實(shí)例驗(yàn)證了算法的正確性和有效性。

2.調(diào)度問題描述

n種工件J={Ji|i=1，…，n}在一個(gè)由m臺不同的加工機(jī)器組成的制造系統(tǒng)中進(jìn)行加工。加工工件Ji需要p(i)道工序，每道工序都有一個(gè)可選的機(jī)器集合，其加工時(shí)間隨機(jī)器的選擇不同而變化。調(diào)度目標(biāo)是確定每臺機(jī)器上各工件的加工順序及開工時(shí)間，使得系統(tǒng)的最大完成時(shí)間Cmax最小，同時(shí)給出滿足要求的活動調(diào)度。假設(shè)：

(1)各工件經(jīng)過準(zhǔn)備時(shí)間后即可開始加工；

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

(3)每臺機(jī)器每次只能加工一個(gè)工件；

(4)不考慮工件之間的加工優(yōu)先權(quán)。

3.遺傳算子設(shè)計(jì)

3.1 適應(yīng)度函數(shù)f(i)

染色體i的適應(yīng)度值由以下公式給出，其中C是一個(gè)大的正整數(shù)。

3.2 編碼

定義染色體為矩陣ch[3][op]，該染色體蘊(yùn)涵工序和機(jī)器選擇的雙重信息。

第一行是基于工序的編碼：數(shù)字i代表工件Ji。從左到右掃描，數(shù)字i的第j次出現(xiàn)代表工件Ji的第j道工序，記為Oij。

第二行是基于機(jī)器的編碼：[k11，k12，…，k1p(1)，…，kn1，kn2，…，knp(n)]，其中kij表示工序Oij所選擇的機(jī)器號碼。

第三行提供了加工時(shí)間的信息：[t11，t12，…，t1p(1)，…，tn1，tn2，…，tnp(n)]，其中tij代表工序Oij在機(jī)器kij上進(jìn)行加工所需要的加工時(shí)間。

3.3 交叉與變異

為了避免交叉操作之后產(chǎn)生非法個(gè)體(某道工序選擇了不可用的機(jī)器)，規(guī)定僅僅對染色體的第二行、第三行數(shù)據(jù)，以概率pc進(jìn)行兩點(diǎn)交叉操作。

設(shè)計(jì)兩種變異算子。

對染色體第一行數(shù)據(jù)，以概率pmop進(jìn)行互逆變異操作，其目的在于生成新的調(diào)度。

對染色體第二行數(shù)據(jù)，以概率pmch改變某基因的值，注意要保證選擇的機(jī)器合法。之后改變?nèi)旧w第三行相應(yīng)位置上的值，賦予其新機(jī)器上的加工時(shí)間。

以上的編碼方式結(jié)合交叉、變異操作可使得生成的染色體在工序和機(jī)器選擇方面都是合法染色體。

3.4 活動調(diào)度的調(diào)整

對染色體解碼時(shí)，從左到右依次掃描第一行基于工序的編碼串，確定工序信息Oij，之后在第二行的編碼串中找到該工序選擇的機(jī)器號碼，掃描完畢即得到了該染色體對應(yīng)的調(diào)度形式。按照這種解碼方式一般只能得到半活動調(diào)度，而不是活動調(diào)度[12]。因此，將一種插入式算法嵌入到適應(yīng)度計(jì)算過程中，在有必要時(shí)調(diào)整染色體的基因序列，使其解碼后生成活動調(diào)度。

這種插入算法針對所有工件的非首道工序進(jìn)行處理，將其插入到對應(yīng)機(jī)器上最佳可行的加工時(shí)刻安排加工，以這種方式保證所有工序都安排在最佳可行的地方，使得機(jī)器利用率最大化。

stij：當(dāng)前工序Oij的開工時(shí)間；

opij：當(dāng)前工序Oij的加工時(shí)間，j＞1；

fti(j-1)：同一工件前道工序Oi(j-1)的完工時(shí)間，j＞1；

ftm：工序Oij所選用機(jī)器目前的可用時(shí)間；

stm：同一機(jī)器上前道工序的開工時(shí)間；

在基于工序的編碼方式下，各個(gè)工件的加工已經(jīng)按照其工藝順序進(jìn)行。給定染色體，設(shè)系統(tǒng)中所有機(jī)器的可用時(shí)間為0，所有待加工工件的初始可用時(shí)間為0。從左到右掃描染色體第一行數(shù)據(jù)，確定工序Oij的加工開始時(shí)間：

圖1 活動調(diào)度的調(diào)整

{對每一道工序ch[0][k-1]，判斷其工序信息Oij；

調(diào)整過程：代表當(dāng)前工序Oi的數(shù)字為a，代表同一臺機(jī)器上前道工序的數(shù)字為b。在染色體第一行編碼串中，將a提到b之前。

圖1的甘特圖中，字符串“i–j”表示工序Oij。圖1(a)顯示：工序O11的完工時(shí)間ft11=2；工序O21在st2=5時(shí)刻開始加工，加工完畢后有ft2=8；工序O12的加工時(shí)間op12=2。因滿足條件(ft11+op12)＜st2，圖1(a)是半活動調(diào)度。將M2的加工順序調(diào)整為O12、O21，即st12=ft11，調(diào)整后并不延遲工序O12的加工，如圖1(b)所示成為活動調(diào)度。對比圖1(a)和圖1(b)可知，將非活動調(diào)度調(diào)整成活動調(diào)度后，正規(guī)性能指標(biāo)必然有所改善。

表1 6機(jī)器、4工件的加工信息表

圖2 4′6柔性車間作業(yè)活動調(diào)度結(jié)果 圖3 4′6柔性車間作業(yè)活動調(diào)度甘特圖

3.5 選擇

采用適應(yīng)度比例方法，并執(zhí)行保優(yōu)策略。即當(dāng)進(jìn)行交叉、變異等操作時(shí)，生成的子代種群和父代種群合并成一個(gè)新的種群，對新種群應(yīng)用適應(yīng)度比例方法，即輪盤賭方法進(jìn)行選擇，且保存當(dāng)代最優(yōu)個(gè)體，即適應(yīng)度最大且所有機(jī)器的總完工時(shí)間最小的染色體。

4.實(shí)例仿真

以表1所示的調(diào)度問題為例，表格中的數(shù)字代表各工序在相應(yīng)機(jī)器上的加工時(shí)間。

遺傳算法的參數(shù)設(shè)置為：交叉概率Pc=0.85，變異概率Pmop=0.012，Pmch=0.2，種群規(guī)模popsize=40，運(yùn)行次數(shù)maxrun=10，每次運(yùn)行最大進(jìn)化代數(shù)maxgen=100。最終得到的調(diào)度結(jié)果makespan=17。

觀察表1，令每道工序都選擇最小加工時(shí)間的機(jī)器，可得到工件J1、J2、J3和J4的完工時(shí)間分別為5、9、17和12，所以對于該問題，若不限制工件訪問同一臺機(jī)器的次數(shù)，且系統(tǒng)緩沖區(qū)無限，makespan=17已經(jīng)是最優(yōu)的調(diào)度結(jié)果。

在makespan=17的調(diào)度中，得到的最小的總完工時(shí)間為63。圖2中，字符串“ij＜a--b＞”表示工序Oij的開始加工時(shí)間是a，完工時(shí)間是b。調(diào)度的甘特圖見圖3，字符串“i-j”表示工序Oij。因任何工序都不可能提前操作而同時(shí)保證其他工序不延遲，因此該調(diào)度是活動調(diào)度。

5.結(jié)論

本文使用遺傳算法來求解柔性車間作業(yè)活動調(diào)度問題。首先將基于工序的編碼和基于機(jī)器的編碼方式結(jié)合，同時(shí)對交叉操作和變異操作的對象作了規(guī)定，這些改進(jìn)方法可以保證遺傳操作每一步產(chǎn)生的染色體都是合法的，避免了傳統(tǒng)柔性車間作業(yè)調(diào)度中繁瑣的染色體合法化修復(fù)工作。為了得到活動調(diào)度的形式，在適應(yīng)度計(jì)算的過程中對染色體的基因序列進(jìn)行調(diào)整。用4工件6機(jī)器的柔性車間作業(yè)調(diào)度問題為例進(jìn)行仿真，得到的調(diào)度結(jié)果為最優(yōu)；在所有最小makespan值的調(diào)度中，進(jìn)一步給出了機(jī)器總完工時(shí)間最小的調(diào)度。仿真結(jié)果表明，本文設(shè)計(jì)的遺傳算法在求解柔性車間作業(yè)調(diào)度問題時(shí)是有效的。

[1]Zribi N,Kamel AE,Borne P.Scheduling in a flexible job shop under machine availability constraints[J].APII-JESA Journal Europeen des Systemes Automatises,2007,41(6):651-671.

[2]Guohui Zhang,Liang Gao,Yang Shi.An effective genetic algorithm for the flexible job-shop scheduling problem[J].Expert Systems with Applicatio ns,2011,4(38):3563-3573.

[3]白俊杰,龔毅光,王寧生,唐敦兵.批量生產(chǎn)柔性作業(yè)車間作業(yè)優(yōu)化調(diào)度研究[J].機(jī)械科學(xué)與技術(shù),2010,3(29):293-298.

[4]Kacem I.Genetic algorithm for the flexible jobshop scheduling problem[C],IEEE International Conference on Systems,Man and Cybernetics,OCT 05-08,WASHINGTON D.C.2003,1-5:3464-3469.

[5]Kun Y,Zhu JY.Improved genetic algorithm for the flexible job-shop scheduling with multi-object[J].China Mechanical Engineering,2007,18(2):156-160.

[6]光熠,劉心報(bào),程浩.求解車間作業(yè)調(diào)度問題的一種改進(jìn)遺傳算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2007,11(17):171-174,178.

[7]陳亮,王世進(jìn),周炳海.柔性作業(yè)車間調(diào)度問題的集成啟發(fā)式算法[J].計(jì)算機(jī)工程,2008,34(1):256-258.

[8]席衛(wèi)東,喬兵,朱劍英.基于改進(jìn)遺傳算法的柔性作業(yè)車間調(diào)度[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2007,39(7):1151-1153.

[9]楊紅紅,吳智銘.混合遺傳算法在柔性系統(tǒng)動態(tài)調(diào)度中的應(yīng)用研究[J].信息與控制,2001,30(5):392-397.

[10]方紅雨,崔遜學(xué).基于遺傳算法的調(diào)度問題研究[J].電腦與信息技術(shù),2001(2):1-5.

[11]Ferrolho A,Crisostomo M.A hybrid and flexible genetic algorithm for the job-shop scheduling problem[C].IEEE International Symposium on Computational Intelligence in Robotics and Automation.IEEE Piscataway.NJ.USA Jacksonville.FI.USA,2007:421-426.

[12]王凌.車間調(diào)度及其遺傳算法[M].北京:清華大學(xué)出版社,2003.