吳秀麗 李蘇劍 杜彥華

北京科技大學(xué),北京,100083

0 引言

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

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

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

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

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

表1 3×4 FJSP問題描述

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

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

2.1 算法的總體流程圖

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

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

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

2.2 算法的詳細(xì)設(shè)計(jì)

2.2.1 編碼

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

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

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

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

2.2.3 解碼操作

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

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

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

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

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

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

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

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

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

2.2.4 適應(yīng)度計(jì)算

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

式中,p為目標(biāo)函數(shù)個(gè)數(shù);randnum(i)為隨機(jī)數(shù);fi(x)為第i個(gè)目標(biāo)函數(shù)值。

2.2.5 選擇操作

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

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

為了保證優(yōu)秀個(gè)體不會(huì)因?yàn)榻徊孀儺惐黄茐牡?采用精英保留策略,即當(dāng)前群體中的適應(yīng)度最高的個(gè)體不參與交叉和變異,而是用它來替換本代群體中經(jīng)過交叉、變異等遺傳操作后所產(chǎn)生的適應(yīng)度最低的個(gè)體。

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

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

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

2.2.6 交叉操作

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

2.2.7 變異操作

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

2.2.8 終止條件

通過設(shè)定最大進(jìn)化代數(shù)T,當(dāng)運(yùn)行代數(shù)達(dá)到T時(shí),進(jìn)化終止。

3 仿真實(shí)驗(yàn)

3.1 運(yùn)行環(huán)境

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

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

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

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

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

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

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

由以上兩個(gè)標(biāo)準(zhǔn)算例的計(jì)算結(jié)果可以看出,本文提出的算法對(duì)于優(yōu)化多目標(biāo)問題可以取得良好效果。

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

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

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

4 結(jié)束語

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

[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].機(jī)械科學(xué)與技術(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]周明,孫樹棟.遺傳算法原理及應(yīng)用[M].北京:國(guó)防工業(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)化的多目標(biāo)柔性 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]鞠全勇,朱劍英.多目標(biāo)批量生產(chǎn)柔性作業(yè)車間調(diào)度優(yōu)化研究[J].機(jī)械工程學(xué)報(bào),2007,43(8):148-154.