柔性作業(yè)車間多品種小批量調(diào)度算法研究

吳秀麗 李蘇劍 杜彥華

北京科技大學,北京,100083

0 引言

目前,車間調(diào)度問題正朝著實用化、動態(tài)化和多目標方向發(fā)展。經(jīng)典作業(yè)車間調(diào)度(job shop scheduling problem,JSP)模型由于對生產(chǎn)實踐的假設太多,嚴重脫離實踐,無法真正指導生產(chǎn)實踐。柔性作業(yè)車間調(diào)度問題(flexible job shop scheduling problem,FJSP)由于放開了資源唯一性的約束,故更加貼近實際,但是其求解難度也更大。文獻中研究JSP的比較多,關于FJSP的研究相對較少。1990年Bruker等[1]首先研究了FJSP。目前對此類問題的求解方法可歸納為分步法和集成法兩類。分步法是由Brandimarte[2]首先提出,其基本思想是將復雜問題分解為幾個子問題,以降低其復雜性。在FJSP調(diào)度中,將機器分配問題和調(diào)度問題分開考慮,這也源于FJSP調(diào)度的本質(zhì)。集成法是將機器分配問題和調(diào)度問題同時解決,如Mati等[3]采用貪婪算法、Hapke[4]采用模擬退火算法、Rigao[5]和 Dauzere—Peres等[6]采用禁忌搜索法、Mastrolilli等[7]采用局部搜索法等研究都屬于集成法。

由于企業(yè)的生產(chǎn)模式已由過去的單一品種、大批量生產(chǎn)模式轉(zhuǎn)化為多品種、小批量的模式,因此,如果在FJSP調(diào)度問題中,考慮工件批量加工中輔助生產(chǎn)時間的影響,將使得研究的結(jié)論更貼近實際,對生產(chǎn)更有指導意義。研究證明,除了少數(shù)小規(guī)模的JSP可以精確求解外,絕大多數(shù)JSP問題都是NP難題,增加了機器可選約束和工件批量的FJSP調(diào)度優(yōu)化更是NP難題。因此,本文采用集成法的思想,提出了一種標準遺傳算法和小生境技術(shù)集成的混合算法求解柔性作業(yè)車間多品種小批量調(diào)度問題。

1 調(diào)度問題定義

在M臺機器上加工N種工件,每種工件Jj的加工有nj道工序,nj道工序之間有工藝的先后約束,工件的每道工序可由M臺機器中的多臺機器加工,用Mij表示第j種工件的第i道工序可用機器集合(Mij?{1,2,…,M}),Oij k表示第j種工件的第i道工序可用機器k,pi jk表示第j種工件的第i道工序在第k臺機器上加工需要的時間,j=1,2,…,N;i=1,2,…,nj;k=1,2,…,M 。每種工件Jj的生產(chǎn)批量Qj不等,如果對任意的i、j,都有Qi=Qj=1,則該問題轉(zhuǎn)化為單件FJSP問題。調(diào)度的任務是在M臺機器上安排個工件的加工任務,使得Makespan和安裝準備成本指標同時最優(yōu),并滿足一些必要的約束條件。

假設條件如下:①所有機器在t=0時刻都可用;②所有工件在t=0時刻都可被加工;③所有工件的工藝計劃是固定不變的;④工序在可供選擇的機器上的加工時間已確定;⑤每個工件在固定時刻只能在一臺機器上加工;⑥加工是非搶占式的,工件的加工不允許中斷。表1所示是一個3×4的FJSP問題描述。表1中的數(shù)字表示pijk,空白表示不能加工,每一行的數(shù)據(jù)組成集合Mij。

表1 3×4 FJSP問題描述

根據(jù)上述問題定義,該類問題可分為兩類[3]:①完全FJSP(T—FJSP)。對于Oi j,Mij=M,表示工件Jj的i道工序可以在所有機器上加工;②部分FJSP(P—FJSP)。對于Oij,Mij?M,表示存在工件Jj,其第i道工序不能由全部M臺機器加工。

2 基于混合遺傳算法的調(diào)度優(yōu)化方法

2.1 算法的總體流程圖

單以Makespan進行優(yōu)化,文獻[8]已經(jīng)給出結(jié)論,忽略生產(chǎn)批量,把每批中的每個工件都視為一個獨立的工件安排加工,可以充分利用每臺機器,使得Makespan最小。但是,現(xiàn)在很多加工機器是數(shù)控機床,加工不同的工件時需要很多輔助工作,如調(diào)整機床、更換夾具、刀具等,這些工作與工件類型相關,對同一種工件,只需要進行一次同樣的工作。這些輔助工作需要消耗較高的安裝準備成本,如果單以安裝準備成本進行優(yōu)化,雖然減少安裝準備次數(shù)效果最好(因為成批的零件按順序依次在一臺機器上加工完畢后,再更改機器設置,加工另外一個零件,從而使得安裝成本最小),但是按照文獻[8]的結(jié)論,此時Makespan最大。可見這兩個目標相互矛盾,無法保證兩者同時最優(yōu),只能尋求兩者的權(quán)衡與折中,即尋求問題的Pareto解集[9]。

本文提出集成權(quán)重系數(shù)變化法和小生境技術(shù)的混合遺傳算法求解該問題。在給出算法之前,先劃分兩個概念:①生產(chǎn)批,指給定生產(chǎn)調(diào)度任務中的各種工件的批量,同一生產(chǎn)批的工件,各種加工要求和交貨時間是相同的;②調(diào)度批,為了優(yōu)化調(diào)度的總目標,必須將生產(chǎn)批分成更小的批量來安排調(diào)度,即實際參與生產(chǎn)的批量為調(diào)度批?？梢娬{(diào)度批小于或等于生產(chǎn)批。

該類問題其實包含了兩個子問題。第一個子問題是在總優(yōu)化目標約束下,將工件的生產(chǎn)批分解為調(diào)度批;第二個子問題是對在調(diào)度批內(nèi)工件的工序進行調(diào)度。這兩個子問題可以分步求解,也可以同時解決,本文利用遺傳算法的強大搜索解空間能力,同時解決這兩個問題,算法的流程如圖1所示。其中,T為最大代數(shù)。

2.2 算法的詳細設計

2.2.1 編碼

編碼問題是設計遺傳算法的首要和關鍵問題[10]。FJSP調(diào)度優(yōu)化采用基于擴展工序的編碼方式,每個染色體由N×maxnj個自然數(shù)組成,各工件均出現(xiàn)maxnj次。對于工序數(shù)少于maxnj的工件,多余的部分表示“虛工序”,解碼時將其加工時間均設為0,而這并不影響問題本身。這種方法一方面能體現(xiàn)FJSP問題的機器分配特征,另一方面也是為了在以處理矩陣為特長的MATLAB仿真環(huán)境下運行而設計的。如上述3×4的例子,一個可行的編碼為[2 1 1 1 2 2 3 3 3]。

這種編碼方式的特點可歸納為:半Lamarkian特性;兩類解碼復雜性;任意基因串的置換排列均能表示活動調(diào)度;碼長不小于標準長度。

2.2.2 算法參數(shù)與初始化

遺傳算法最重要的參數(shù)包括:種群規(guī)模N、交叉概率C、變異概率P、最大代數(shù)T。種群規(guī)模與優(yōu)化函數(shù)的性質(zhì)、維數(shù)、復雜程度以及編碼精度等有直接的關系。在計算量許可的情況下,要盡量選擇較大規(guī)模的群體,保證群體的多樣性及其進化能力,避免群體早熟現(xiàn)象的發(fā)生。交叉概率與變異概率的確定是個復雜的問題,其本身優(yōu)化就是一個極其復雜的問題,需要經(jīng)多次仿真實驗得到。一般來講,交叉概率C∈(0.4,0.9),變異概率 P∈(0.005,0.1)。最大代數(shù) T為算法進化終止的條件。

2.2.3 解碼操作

為了提高調(diào)度方案的質(zhì)量,采用不同指標分別解碼的方法產(chǎn)生多種活動化調(diào)度方案,即分別按照Makespan最小和安裝準備成本最小兩個指標解碼,每個染色體可以得出兩種調(diào)度方案。下面以Makespan最小給出解碼算法。

定義1 機器順序陣JMJM(i,j)表示加工i工件的第j道工序的機器號。用JM(i,)表示i工件的所有工序按優(yōu)先順序加工的各機器號的排列。對于FJSP問題,任意工件i的j工序可用機器數(shù)不止1個,所以該排列的長度是max(ni)×M(i=1,2,…,N),每道工序的可用機器集用M個機器號表示,稱為一個子片斷,P—FJSP中機器不可用時用0補齊M個子片斷(機器編號從1開始)。當每個工件的總工序數(shù)不同時,取最大工序數(shù)作為子片斷數(shù),工序數(shù)少于最大工序數(shù)的工件,按照上述規(guī)則排列出機器號后,接著補齊數(shù)全為0的max(ni)—ni個子片斷。從而構(gòu)成維數(shù) N×(max(ni)×M)的二維矩陣。如上述提及的3×4例子中,機器順序陣為

定義2 加工時間陣T T(i,j)為i工件在j機器上的加工時間。對于FJSP問題,T(i,j)與JM(i,j)一一對應,當JM(i,j)是0時,T(i,j)也為0。還是上述3×4的例子,加工時間陣為

在解碼之前,需進行預處理:將調(diào)度批的同類工件作為一個工件看待,調(diào)度批內(nèi)的工件依次連續(xù)加工,中間不需要對機器進行重新調(diào)整參數(shù),不耗費安裝準備成本,因此,根據(jù)當前的調(diào)度批規(guī)模,修改機器順序陣JM和加工時間陣T,即JM中的JM(i,j)中的i表示的是每個工件的調(diào)度批,j表示該調(diào)度批的工序。相應地,加工時間陣T中的每個元素T(i,j)的值由單件加工時間調(diào)整為調(diào)度批的倍數(shù)。

解碼算法流程如下:①初始化工件加工工序向量,k(Ji)=1,i=1,2,…,N;②從染色體讀取要加工的工件;③在JM(Ji,k(Ji))查找當前工序k(Ji)的所有可用機器序列,選擇當前工序加工結(jié)束時間最早的機器,如果存在結(jié)束時間相同的機器,取加工時間較短的;④比較該機器的空閑時間段,如果工序可以插入到機器的中間空閑時間段,則轉(zhuǎn)入步驟⑤,否則進步驟⑥;⑤插入該工序,并更新產(chǎn)品工序的當前工序結(jié)束時間,更新機器的開始時間和空閑時間;⑥在機器加工序列的末尾接著安排該工序,更新機器的當前結(jié)束時間和產(chǎn)品當前工序的結(jié)束時間;⑦工件Ji的工序號k(Ji)加1,返回步驟 ②,直到處理完該染色體中的所有工序;⑧結(jié)束循環(huán),生成可行解。

算法中,工件Ji能在空閑時間段[t1,t2]插入加工的條件為

式中,t1、t2分別為空閑時間段的起點和終點;t(i)為工件Ji當前工序的最早允許加工時間;pti為工件的當前工序在選擇機器上的加工時間。

當用機器安裝準備成本指標解碼時,解碼算法與上述類似,區(qū)別在于步驟 ③中“選擇結(jié)束時間最早的機器”改為選擇“選擇安裝準備成本最小的機器”即可。

經(jīng)過解碼,針對當前調(diào)度批規(guī)模,每個染色體生成兩種調(diào)度方案。

2.2.4 適應度計算

適應度體現(xiàn)了優(yōu)化模型的目標函數(shù)。這里采用權(quán)重系數(shù)變化法計算個體的適應度:根據(jù)兩個目標函數(shù),每個染色體可以解碼為兩種方案,因此每代進化評價染色體優(yōu)劣時,分別為每種方案的各目標函數(shù)賦予隨機數(shù)權(quán)重,然后線性相加即為該方案的適應度,選擇兩種方案的適應度最大者作為該染色體的適應度。計算如下:

式中,p為目標函數(shù)個數(shù);randnum(i)為隨機數(shù);fi(x)為第i個目標函數(shù)值。

2.2.5 選擇操作

選擇操作用于實現(xiàn)優(yōu)勝劣汰,選擇出優(yōu)秀個體以較高的概率保留在進化種群中,從而提高全局收斂性和計算效率,是保證染色體不斷進化的關鍵。這里采用輪盤賭選擇方法,即設群體大小為N,其中個體i的適應度為fi,則該個體被選中的概率 Pi為

概率Pi反映了個體i的適應值在整個個體適應值總和中所占的比例,占比例越大的個體,所代表的基因結(jié)構(gòu)被遺傳到下一代中的可能性也越大。

為了保證優(yōu)秀個體不會因為交叉變異被破壞掉,采用精英保留策略,即當前群體中的適應度最高的個體不參與交叉和變異,而是用它來替換本代群體中經(jīng)過交叉、變異等遺傳操作后所產(chǎn)生的適應度最低的個體。

另外,多目標優(yōu)化的一個關鍵問題是保證Pareto解的多樣性,因此每代進化過程中對適應度值非常接近的個體使用小生境技術(shù)[11]進行處理。小生境的構(gòu)造直接影響多樣性的質(zhì)量,本文改進了Hyun等[11]提出的小生境環(huán)境設計方法。某個個體所在的小生境域的定義如下:以該個體為中心,由周圍各邊界圍成一個空間,各邊界大小的計算公式為

式中,max(lt)和min(lt)分別為進化到t代時第l個目標的最大值和最小值;m為目標個數(shù);pop_Size為種群規(guī)模。

小生境域密度越小的個體被遺傳下去的概率越大。圖2中,個體X1比個體X2被選擇的概率大。仿真過程中,發(fā)現(xiàn)該邊界太大,淘汰掉了不應該淘汰的最優(yōu)解,經(jīng)過多次仿真,得到如下修正公式:

2.2.6 交叉操作

在遺傳算法(GA)中,交叉操作的作用非常重要,一方面,它使原來群體中優(yōu)良個體的特性能夠在一定程度上得以保持;另一方面,它使算法能夠探索新的基因空間,從而使新的群體中的個體具有多樣性。在基于擴展工序的編碼方式下,交叉操作需要特殊設計。本文采用線性次序交叉:首先隨機確定兩個交叉位置,并交換交叉點之間的片段,并在原先父代個體中刪除從另一父代個體交換過來的基因,然后從第一個基因位置起依次在兩交叉位置外填入剩余基因。如圖3所示,兩個父代染色體P1和P2,第一步交叉后,形成的兩個子染色體C11和C12,可以看出基因有丟失和重復,按照上述方法對基因修補后得到合法的染色體C1和C2。

2.2.7 變異操作

變異操作可以幫助收斂過程跳出局部最優(yōu)點,增加種群的多樣性。本文采用互換操作變異方法,即隨機交換染色體中兩不同基因的位置。如圖3染色體P1,如果變異位置選為3和6,則新的染色體變?yōu)?2 6 5 7 3 4 6 9 1)。

2.2.8 終止條件

通過設定最大進化代數(shù)T,當運行代數(shù)達到T時,進化終止。

3 仿真實驗

3.1 運行環(huán)境

在Pentium 4、CPU主頻為 2.13GHz、1GB內(nèi)存、Windows XP操作系統(tǒng)下,利用 MAT LAB 6.5仿真工具編程實現(xiàn)上述算法。經(jīng)過多次測試驗證,選定的比較理想的混合遺傳算法參數(shù)如下:種群大小為50,最大代數(shù)為20,交叉概率為0.6,變異概率為0.1。每臺機器的安裝成本數(shù)據(jù)由系統(tǒng)隨機產(chǎn)生,不影響算法性能的驗證。

鑒于目前國內(nèi)外尚無多品種小批量柔性作業(yè)車間調(diào)度的標準算例,因此,本文分別從算法的多目標優(yōu)化性能和批量調(diào)度性能兩個角度進行算法性能比較分析。

3.2 算法多目標優(yōu)化性能比較

對文獻[12]中的 8工件、8機器,27工序的部分FJSP問題進行了仿真實驗。某些工序只有部分工序可供選擇?！啊痢北硎驹摍C器不可選,解碼時將其時間置為“0”。運行10次,均在4.5s內(nèi)7次得到最優(yōu)解,與文獻[12]中的結(jié)果進行比較,如表2所示。其中,SPT表示最短處理時間優(yōu)先規(guī)則,AL表示局部搜索算法,CGA表示復合遺傳算法,PSO表示微粒群算法,SA表示模擬退火算法。Makespan指標比文獻中最好的結(jié)果降低一個單位,性能提高約6%,最大負荷指標比文獻中的結(jié)果降低2個單位,性能提高約14%,總負荷指標略遜一籌,比最好的指標高4個單位,性能降低約5%?？傮w來看,該算法的性能還是相當不錯,尤其在JIT生產(chǎn)模式中時間要求很嚴格的情況下,能體現(xiàn)其優(yōu)越性。

表2 針對8×8問題的不同算法結(jié)果比較

為了驗證該算法求解大規(guī)模問題的性能,對文獻[14]中提及的15工件、10機器、56工序的完全FJSP進行了仿真實驗。運行10次,均在5.5s內(nèi)6次得到表3所示的最佳結(jié)果,并與文獻中的最佳結(jié)果進行了對比。從結(jié)果中可以看出,Makespan指標和最大負荷指標與文獻中最好的結(jié)果一致,總負荷指標略遜一籌,比最好的指標高2個單位,性能降低約2%。

表3 針對15×10問題的不同算法結(jié)果比較

由以上兩個標準算例的計算結(jié)果可以看出,本文提出的算法對于優(yōu)化多目標問題可以取得良好效果。

3.3 算法批量調(diào)度性能比較

為了驗證算法求解批量調(diào)度問題的性能,對文獻[8]中的提及的4工件、6機器,批量為5的P—FJSP問題進行了仿真實驗。運行10次,均在5s內(nèi)8次得到最優(yōu)解。最佳方案的甘特圖見圖4,甘特圖中的字母表示每種工件的調(diào)度批,對應關系如表4所示,按照同一符號出現(xiàn)的先后順序表示該調(diào)度批的各工序加工順序。Makespan指標等于50,比文獻[8]中提到的遺傳算法得到的結(jié)果61要優(yōu)越,總的安裝準備成本為289。4個工件的調(diào)度批為[2,3,2,3],即工件1每2個組成1個調(diào)度批連續(xù)加工,工件2每3個組成1個調(diào)度批連續(xù)加工,工件3每2個組成1個調(diào)度批連續(xù)加工,工件4每3個組成1個調(diào)度批連續(xù)加工。不夠調(diào)度批規(guī)模的剩余工件作為1個調(diào)度批單獨處理。

表4 調(diào)度批符號表示

4 結(jié)束語

柔性作業(yè)車間多品種小批量調(diào)度模型突破了經(jīng)典JSP的可用資源唯一性限制,并把批量生產(chǎn)的現(xiàn)狀考慮進來,同時面向多個指標進行優(yōu)化求解,因此比單目標的經(jīng)典JSP調(diào)度優(yōu)化模型更符合車間調(diào)度現(xiàn)狀,更能起到指導生產(chǎn)實踐的作用。本文采用混合遺傳算法對該類問題進行了優(yōu)化求解,仿真結(jié)果證明了算法設計的合理性。目前國內(nèi)外對該問題的研究較少,很多問題有待進一步研究。將來可以從三個方向展開深入研究:①進一步優(yōu)化遺傳算法,提高其搜索效率;②考慮采用其他方法求解該模型,如免疫算法等;③考慮更多生產(chǎn)實際情況。

[1]Bruker P,Schlie R.Job—shop Scheduling with Multi—purpose Machines[J].Computing,1990,45(4):369-375.

[2]Brandimarte P.Routing and Scheduling in a Flexible Job Shop by Tabu Search[J].Annals of Operations Research,1993,41(3):157-183.

[3]Mati Y,Rezg N,Xie X L.An Integrated Greedy Heuristic for a Flexible Job Shop Scheduling Problem[C]//2001 IEEE International Conference on Systems,Man,and Cybernetics.Tucson,AZ:IEEE,2001:2534-2539.

[4]Hapke M.Pareto Simulated Annealing for Fuzzy Multi—objective Combinatorial Optimization[J].Journal of Heuristics,2000,6(3):329-345.

[5]Rigao C.Tardiness Minimization in a Flexible Job Shop:a Tabu Search Approach[J].Journal of Intelligent Manufacturing,2004,15(1):103-115.

[6]Dauzere—Peres S,Paulli J.An Integrated Approach for Modeling and Solving the General M ultiprocessor Job—shop Scheduling Problem Using Tabu Search[J].Annals of Operations Research,1997,70:281-306.

[7]Mastrolilli M,Gambardella L M.Effective Neighborhood Functions for the Flexible Job Shop Problem[J].Journal of Scheduling,2002,3(1):3-20.

[8]孫志峻,喬冰,潘全科,等.具有柔性加工路徑的作業(yè)車間批量調(diào)度優(yōu)化研究[J].機械科學與技術(shù),2002,21(3):348-350.

[9]Silva D L.An Introduction to Multiobjective Metaheuristics for Scheduling and Timetabling[M].Nottingham:ISN Workshop,2004.

[10]周明,孫樹棟.遺傳算法原理及應用[M].北京:國防工業(yè)出版社,1999.

[11]Hyun C J,Kim Y,Kim Y K.A Genetic Algorithm for Multiple ObjectiveSequencing Problems in Mixed Model Assembly Lines[J].Computers&Operations Research,1998,25(7/8):675-690.

[12]Kacem I,Hammadi S,Borne P.Approach by Localization and Multiobjective Evolutionary Optimization for Flexible Job—shop Scheduling Problems[J].IEEE T ransactions on Systems,Man and Cybernetics,Part C,2002,32(1):408-419.

[13]夏蔚軍,吳智銘.基于混合微粒群優(yōu)化的多目標柔性 Job—shop調(diào)度[J].控制與決策,2005,20(2):137-141.

[14]Kacem I,Hammadi S,Borne P.Pareto—optimality Approach for Flexible Job—shop Scheduling Problems:Hybridization ofEvolutionaryAlgorithms and Fuzzy Logic[J].Mathematics and Computers in Simulation,2002,60:245-276.

[15]鞠全勇,朱劍英.多目標批量生產(chǎn)柔性作業(yè)車間調(diào)度優(yōu)化研究[J].機械工程學報,2007,43(8):148-154.