劉雪紅，段 程，王 磊+

(1.武漢理工大學(xué) 機(jī)電工程學(xué)院，湖北 武漢 430070；2.數(shù)字制造湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430070)

0 引言

在現(xiàn)實(shí)生產(chǎn)中，大規(guī)模制造的柔性作業(yè)車間通常采用提高技術(shù)或通過組織安排的方式來提高資源利用能力，如事先預(yù)測、工序并行、分批調(diào)度生產(chǎn)等[1]，其中分批調(diào)度是解決柔性作業(yè)車間問題的主要手段。分批調(diào)度指在加工過程中由于物料和工序的性質(zhì)，允許分批傳輸和生產(chǎn)，從而使后續(xù)工序提前加工，縮短完工時(shí)間。

本文主要研究柔性作業(yè)車間內(nèi)的分批調(diào)度問題(Flexible Job-shop Scheduling Problem with Lot Streaming, FJSP-LS)。根據(jù)批量劃分方式的不同分為一致子批(consistent sublots)和可變子批(variable sublots)[2]。目前大多數(shù)分批調(diào)度研究，將一致子批的劃分策略應(yīng)用到流水車間[3-7]、作業(yè)車間[8-11]和柔性作業(yè)車間[12-14]，可變子批因其復(fù)雜性而研究較少,主要研究是將可變子批策略應(yīng)用于流水車間[15]和柔性作業(yè)[1]，通過將最小批量進(jìn)行批次劃分后確定最優(yōu)調(diào)度方案，再優(yōu)化批量，從而在不影響制造時(shí)間的前提下優(yōu)化批次數(shù)目,但是為了不減少制造時(shí)間，往往需要更多的批次數(shù)目，導(dǎo)致傳輸次數(shù)增加、生產(chǎn)成本增大，因此必須考慮批次數(shù)目與制造時(shí)間之間的關(guān)系，才能提出更合理的生產(chǎn)方案。

在FJSP-LS求解方法上，現(xiàn)有研究主要采用元啟發(fā)式算法，如遺傳算法[12]、差分算法[16]、禁忌搜索[1,8]和粒子群算法[14]等,大多側(cè)重于調(diào)度方案的優(yōu)化，對批次劃分方案的制定缺乏深入研究。候鳥優(yōu)化(Migrating Birds Optimization, MBO)算法是DUMAN等[17]于2011年首先提出的自然啟發(fā)的元啟發(fā)式算法，具有參數(shù)少、易于理解、結(jié)構(gòu)簡單等優(yōu)點(diǎn)，成功用于多種優(yōu)化問題，尤其是求解二次分配問題時(shí)，該算法獲得了比模擬退火算法、禁忌搜索算法和指導(dǎo)的進(jìn)化模擬退火算法質(zhì)量更高的解。同時(shí)，越來越多的學(xué)者嘗試將MBO運(yùn)用到生產(chǎn)線調(diào)度上，同樣獲得了高質(zhì)量的解[7,18-19]。

因此，本文以最小制造時(shí)間和最小批次數(shù)目為優(yōu)化目標(biāo)，采用可變批次的劃分策略開展多目標(biāo)柔性作業(yè)車間分批調(diào)度研究。針對可變子批下的柔性作業(yè)車間分批調(diào)度問題(Flexible Job-shop Scheduling Problem with Variable Sublots, FJSP-VS)，本文設(shè)計(jì)了一種改進(jìn)的候鳥優(yōu)化(Improved Migrating Birds Optimization, IMBO)算法，并結(jié)合柔性作業(yè)車間分批調(diào)度析取圖的特點(diǎn)，提出精英分批與可行鄰域結(jié)構(gòu)策略，以實(shí)現(xiàn)制造時(shí)間和批次數(shù)目協(xié)同優(yōu)化。

1 問題描述及數(shù)學(xué)模型

1.1 問題描述及符號定義

FJSP-VS描述如下：在某車間內(nèi)，n種零件在m臺機(jī)器加工，每個零件有多道工序，每種零件的各道工序可以在多臺機(jī)器上選擇加工，零件工序的先后順序不能發(fā)生改變。另外，還需要滿足以下假設(shè)：

(1)每種零件的每道工序最終只能安排在一臺機(jī)器上加工。

(2)機(jī)器在加工一類零件的各個子批任務(wù)時(shí)，不允許加工其他零件的子批。

(3)零件在每臺機(jī)器上的加工時(shí)間不變。

(4)一道工序的加工過程一旦開始，便不可中斷。

為便于描述模型，文中使用的符號定義如表1所示。

表1 模型參數(shù)符號及說明

1.2 數(shù)學(xué)模型

本文所研究的調(diào)度問題的優(yōu)化目標(biāo)是：最小化最大完工時(shí)間和最小化批次數(shù)量。在文獻(xiàn)[12]一致子批數(shù)學(xué)模型的基礎(chǔ)上，根據(jù)問題描述和參數(shù)設(shè)置，構(gòu)建多目標(biāo)FJSP-VS的數(shù)學(xué)模型：

f={minCmax,minS}；

(1)

Cmax=max(Cj,o,s,m);?(j,o,s,m)。

(2)

(3)

s.t.

Cr,m≥Cj,o,s,m+Ω×Xr,m,j,o,s-Ω; ?(r,j,o,s,m)；

(4)

bj,o,s∈R;?(j,o)；

(5)

C1,m-bj,o,1×Tj,o,m-Sj,o,m-Ω×X1,m,j,o,1+Ω≥0;

?(m,j,o)；

(6)

Cr,m-bj,o,1×Tj,o,m-So,j,m,o′,j′-

Ω×(Xr,m,j,o,1+Xr-1,m,j′,o′,Sj′,o′)+2Ω≥Cr-1,m;

?(r,m,j,o,j′,o′)|(r>1);

(7)

?(j,o,m,r,s,m′,r′)|(o>1)；

(8)

Cr,m-bj,o,s×Tj,o,m-Tm,m′-

Ω×(Xr,m,j,o,s+Xr′,m′,j,o-1,bfj,o,s)+2Ω≥Cr′,m′;

?(r,r′,m,m′,j,o,s)|(o>1);

(9)

Xr,m,j,o,s≤Pj,o,m;?(r,m,j,o,s)；

(10)

(11)

Xr,m,j,o,s=Xr-1,m,j,o,s-1=Xr+1,m,j,o,s+1;

?(r,j,m,s)|{(r>1)∧s∈(1,Sj)}；

(12)

Xr′,m,j,o,s′≤1-Xr,m,j,o,s;

?(r,r′,m,o,o′,s,s′,j)|{(o′>o)∧(r′

(13)

(14)

Zr+1,m≤Zr,m;?(r,m)。

(15)

其中：式(1)為目標(biāo)函數(shù)，表示最小化最大完工時(shí)間和最小化劃分批次數(shù)量；式(2)表示最大完成時(shí)間是最后完成批次的完成時(shí)間；式(3)表示劃分批次的數(shù)目為批量不為0的批次數(shù)總和；式(4)表示機(jī)器m上第r個任務(wù)的完成時(shí)間大于等于被分配批次的完成時(shí)間；式(5)為批次劃分約束，批次大小在上下界內(nèi)；式(6)和式(7)為加工機(jī)器約束，安裝準(zhǔn)備操作在子批任務(wù)到達(dá)之前就能進(jìn)行；式(8)和式(9)為工藝順序約束，只有在待加工子批所包含的批量在上一道工序加工結(jié)束并運(yùn)送到加工機(jī)器上，才可以開始加工；式(10)和式(11)確保每一個工序的批次分配到唯一一臺具有加工能力的機(jī)器上；式(12)表示不允許混流加工；式(13)表示如果批次Oj,o,s是機(jī)器m執(zhí)行的第r個任務(wù)，則工序Oj,o的后續(xù)工序不能在機(jī)器m上第r個任務(wù)之前加工；式(14)和式(15)確保機(jī)器m上第r個任務(wù)只能分配一個批次，且將任務(wù)r分配后才可以分配任務(wù)r+1。

1.3 析取圖模型

析取圖模型已經(jīng)成為研究車間調(diào)度問題的標(biāo)準(zhǔn)模型，在此采用析取圖模型G=(V,A,E)可以更好地理解FJSP-VS的結(jié)構(gòu)。本文構(gòu)建的析取圖組成如下：

(16)

(17)

Pj,o,m=Pj′,o′,m=1;

(18)

(19)

Oj,o,s=πm,r,Oj′,o′,s′=πm,r+1。

(20)

其中：式(16)表示節(jié)點(diǎn)V由集合V1和V2組成，V1是起始節(jié)點(diǎn)0和終止節(jié)點(diǎn)*兩個虛擬節(jié)點(diǎn)的集合，V2是所有批次的工序節(jié)點(diǎn)集合，二者權(quán)重為批次的加工時(shí)間；式(17)表示有向?qū)嵕€弧集合A包括集合A1和A2，A1是批次的首道工序與起始節(jié)點(diǎn)或末道工序與終止節(jié)點(diǎn)的連接弧，A2表示所有批次加工工序的約束關(guān)系，其中弧的權(quán)重表示傳輸時(shí)間；式(18)表示虛線弧集合E包括集合E1，E2，E3，E1表示機(jī)器的首個任務(wù)與起始節(jié)點(diǎn)之間的虛線弧，E2表示機(jī)器上可加工工序之間的虛線弧，E3表示同工序不同批次之間的虛線弧，其中弧的權(quán)重為機(jī)器之間任務(wù)的準(zhǔn)備時(shí)間；式(19)表示每一個批次各道工序的機(jī)器指派已經(jīng)確定，此時(shí)將多余的虛線弧去掉后，一個調(diào)度方案就可以通過析取圖展現(xiàn)出來；式(20)為一個解形式的虛線弧集合。表2所示為一個FJSP-VS例子，圖1a和圖1b分別為該問題的析取圖模型和一個可行解形式，此時(shí)解形式的析取圖是無循環(huán)的，說明調(diào)度方案滿足加工約束，它是一個可行解。

表2 析取圖演示案例

關(guān)鍵路徑指兩個虛擬節(jié)點(diǎn)之間的最長路線，路線的權(quán)重之和即為該方案的完工時(shí)間。從起始節(jié)點(diǎn)到關(guān)鍵路徑上的某個關(guān)鍵操作o的權(quán)重用Ho表示，該關(guān)鍵操作到終止節(jié)點(diǎn)的權(quán)重用To表示：

(Vj,o-1,bfj,o,s,Vj,o,s)∈A；

(Vj′,o′,s′,Vj,o,s)∈F；

(21)

(Vj,o,s,Vj,o+1,s′)∈A；

(Vj,o,s,Vj′,o′,s′)∈F；

(22)

Cmax=max{Hj,o,s+Bj,o,s×Tj,o,m+Tj,o,s};

?Vj,o,s∈V∧Xr,m,j,o,s=1。

(23)

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

2.1 編碼方案和種群初始化

2.1.1 編碼方案

針對FJSP-VS的特性，本文根據(jù)文獻(xiàn)[12]的編碼方式設(shè)計(jì)了一種兩階段編碼方法，每一個可行解編碼形式如圖2所示，圖中左側(cè)表示批次劃分方案，右側(cè)表示調(diào)度方案。在批次劃分編碼中，由于每個批次有批量下限，根據(jù)式(24)可得每種零件每個工序的最大批次劃分?jǐn)?shù)L，從而確定批次劃分編碼長度。用L個范圍為[0,1]、精度為0.1的隨機(jī)數(shù)aj,o,s，通過式(25)得到每個批次的批量數(shù)，如果aj,o,s=0，則批量為0。在調(diào)度編碼中，(j,o,m)表示第j個零件的第o道工序在第m臺機(jī)器上加工，從而根據(jù)調(diào)度編碼確定每一臺機(jī)器的序列任務(wù)。生產(chǎn)時(shí)，每道工序的批次按順序依次加工。為滿足約束式(12)，基因(j,o,m)的位置需要始終在基因(j,o′,m)前,其中o′>o。

(24)

(25)

2.1.2 種群初始化

初始解的質(zhì)量對算法的求解速度和求解質(zhì)量有很大影響，為了提高初始解的質(zhì)量并兼顧搜索能力，本文基于FJSP-LS的特點(diǎn)提出3種策略用于初始化種群。對于批次劃分編碼，采用生成隨機(jī)數(shù)的策略確定隨機(jī)劃分方案；對于調(diào)度編碼，50%的個體采用隨機(jī)生成策略，20%的個體采用先到先加工的機(jī)器選擇策略，30%的個體按照選擇最先結(jié)束加工機(jī)器的原則。對非支配解進(jìn)行擁擠度距離排序，選擇擁擠度距離最大的非支配解作為種群的領(lǐng)飛鳥。

2.2 精英分批策略

證明當(dāng)工序滿足上述兩個條件時(shí)，該工序的加工受到機(jī)器約束，即使采用最小批量加工，也不會提前加工，而后續(xù)工序因?yàn)橐彩艿较嗤s束，加工任務(wù)的批次劃分不會導(dǎo)致后續(xù)工序提前加工，所以其分批操作將不會減少最大完工時(shí)間。只滿足條件①時(shí)(如圖3a)，工序Oj,o的分批可使后續(xù)工序Oj,o+1提前開工；只滿足條件②時(shí)(如圖3b)，工序Oj,o-1與其后續(xù)工序Oj,o可以通過分批使Oj,o提前開工，從而達(dá)到縮短完工時(shí)間的目的；當(dāng)同時(shí)滿足條件①和②時(shí)，工序Oj,o的分批操作不會影響最終完工時(shí)間。不滿足上述條件的工序稱為精英工序，其分批操作可以影響最終完工時(shí)間。

結(jié)合上述證明，本文提出一種精英分批策略：在生成鄰域結(jié)構(gòu)前，先取消領(lǐng)飛鳥或跟飛鳥不必要的批次劃分，從而在不影響最終完成時(shí)間的前提下減少批次數(shù)目；選取精英工序生成鄰域結(jié)構(gòu)，從而通過改變批次劃分方案來減少最終完工時(shí)間。

2.3 鄰域結(jié)構(gòu)設(shè)計(jì)

鄰域結(jié)構(gòu)設(shè)計(jì)是為了讓種群向所期望的方向進(jìn)化。在MBO算法中，除領(lǐng)飛鳥外，其他所有個體的鄰域解集均由其自身產(chǎn)生的鄰域解和前面?zhèn)€體未使用的鄰域解兩部分組成。針對本文編碼結(jié)構(gòu)的特殊性，分別對批次劃分和調(diào)度編碼設(shè)置相應(yīng)的鄰域結(jié)構(gòu)。

2.3.1 批次劃分編碼的鄰域結(jié)構(gòu)

本文針對精英工序的批次劃分編碼設(shè)計(jì)3種操作，對應(yīng)3種鄰域結(jié)構(gòu)：

(1)批量突變 將精英工序?qū)?yīng)的批次編碼基因突變?yōu)椴煌碾S機(jī)數(shù)，從而改變批量大小，影響最大完工時(shí)間。此時(shí)允許其突變?yōu)?，以減少批次數(shù)量。

(2)批次合并 將精英工序?qū)?yīng)的批次編碼與同操作的其他批次編碼求和，將同操作的其他批次編碼設(shè)置為0，以減少批次數(shù)量。

(3)批次置換 將精英工序?qū)?yīng)的批次編碼與同操作的其他批次編碼互換，從而改變批次的加工順序。

2.3.2 調(diào)度編碼的鄰域結(jié)構(gòu)

在批次劃分編碼的鄰域結(jié)構(gòu)中會導(dǎo)致同工序不同批次之間互換，因?yàn)楸疚牟豢紤]混流和并行的情況，所以調(diào)度編碼只針對工序生成鄰域結(jié)構(gòu)?？紤]到柔性車間中調(diào)度編碼生成鄰域結(jié)構(gòu)的操作可能會導(dǎo)致不可行解，本文提出基于關(guān)鍵路徑的可行鄰域結(jié)構(gòu)。

(1)可行鄰域

柔性作業(yè)車間析取圖中，如果存在弧線循環(huán)，則表示該調(diào)度方案不可行，因此所生成鄰域解的析取圖中，弧線不應(yīng)出現(xiàn)循環(huán)。在柔性作業(yè)車間可行域研究的基礎(chǔ)上[20-21]，針對FJSP-LS，同時(shí)考慮安裝時(shí)間和運(yùn)輸時(shí)間，提出以下定理：

定理2當(dāng)滿足條件①和條件②后，工序Oj，o可以移動到工序Ov，v′和Ow，w′之間進(jìn)行組織生產(chǎn)，該調(diào)度方案一定是可行方案。

①max{Hx,x′,Sx,Hv,v′-1,Sv}

②min{Hy,y′,Sy+by,y′,Sy×Ty,y′,m′,Hw,w+1,Sw+bw,w+1,Sw×Tw,w+1,m}>Hu,u′-1,Su;(Vu,u′-1,Su,Vu,u′,Su),(Vw,w,Sw,Vw,w+1,Sw)∈A;(Vw,w,Sw,Vy,y′,1)∈E。

證明如圖4所示，當(dāng)工序Oj，o插入工序Ov，v′和Ow，w′之后，原先相關(guān)的虛線弧就會取消(如虛線1)，而生成新的虛線弧，如虛線2和虛線3所示。當(dāng)不滿足條件①時(shí)，工序Oj，o的后續(xù)工序Oj，o+1可能和Ov，v′的前任工序Ov，v′-1或機(jī)器前任務(wù)Ou，u′之間存在虛線弧(如虛線弧4和虛線弧5)，即工序Oj，o+1在Ov，v′-1或Ou，u′之前加工，從而使析取圖中出現(xiàn)循環(huán)(Oj，o，Oj，o+1，Ov，v′-1，Ov，v′，Oj，o)或(Oj，o，Oj，o+1，Ou，u′，Ov，v′，Oj，o)。因此，當(dāng)滿足條件①時(shí)，能夠保證工序Ov，v′-1和Ou，u′執(zhí)行后，Oj，o+1才會執(zhí)行，防止出現(xiàn)虛線弧4和虛線弧5；當(dāng)滿足條件②時(shí)，能夠保證工序Oj，o-1不會在Ow，w′+1和Oy，y′執(zhí)行后開始執(zhí)行，防止出現(xiàn)虛線弧6和虛線弧7。由此可以避免循環(huán)的出現(xiàn)。

(2)鄰域結(jié)構(gòu)

在滿足定理2的基礎(chǔ)上，本文基于關(guān)鍵工序并考慮可行鄰域，隨機(jī)選取一道關(guān)鍵工序，采用同機(jī)器的一次插入操作，或者選取在其他可行機(jī)器上執(zhí)行一次插入操作，分別計(jì)算新解的最大完工時(shí)間，從而在批次數(shù)不變的基礎(chǔ)上獲取完工時(shí)間最小的解，進(jìn)而優(yōu)化調(diào)度方案。

2.4 局部搜索和跳躍機(jī)制

2.4.1 局部搜索策略

由于每個個體每次生成的鄰域解數(shù)受算法參數(shù)的限制，為進(jìn)一步地挖掘更好解，本文對一部分跟飛鳥進(jìn)行局部搜索優(yōu)化，參考上述可行鄰域的思想，對一部分關(guān)鍵工序執(zhí)行同機(jī)器和異機(jī)器的插入操作，從而尋找更優(yōu)調(diào)度方案。

2.4.2 跳躍機(jī)制

為了避免算法陷入早熟收斂狀態(tài)，設(shè)計(jì)一種跳躍機(jī)制。如果種群中的個體超過設(shè)定的limit代沒有得到改善，則在其鄰域解中選擇擁擠度距離最大的鄰域解作為新的個體，從而提高算法搜索的多樣性。

2.5 改進(jìn)候鳥優(yōu)化算法流程

為了方便描述算法，引入以下符號：Psize為初始鳥群的個體數(shù)；k為每個個體產(chǎn)生的自身鄰域解數(shù)；x為每個個體傳給下一個體的鄰域解數(shù)量；G為巡回次數(shù)；limit為跳躍代數(shù)；a為采用批次鄰域搜索的概率(1-a表示采用調(diào)度鄰域搜索的概率)；b為局部搜索的個體占跟飛鳥數(shù)的百分比。結(jié)合上文對算法的論述，IMBO算法流程如圖5所示。

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

3.1 測試算例

本文采用隨機(jī)生成的12組算例，如表3所示，其中LB和UB分別表示取值的下限與上限，D表示任務(wù)種類個數(shù)，M表示機(jī)器個數(shù)，同時(shí)設(shè)定加工時(shí)間To,j,m∈U(1,8)、準(zhǔn)備時(shí)間So,j,m(So,j,m，o′,j′)∈U(10,15)、傳輸時(shí)間Tm,m′∈U(5,10)、可選機(jī)器數(shù)U(1,5)。算法的運(yùn)行環(huán)境為2.20 GHz PC，12 GB RAM，Windows 7，64位操作系統(tǒng)，編程語言為MATLAB。

表3 測試算例數(shù)據(jù)

3.2 性能指標(biāo)與參數(shù)設(shè)置

為了評價(jià)算法獲得解集的收斂性和多樣性，采用反轉(zhuǎn)世代距離[22]IGD和錯誤率[23]ER作為多目標(biāo)進(jìn)化算法性能的評估標(biāo)準(zhǔn)：

(26)

(27)

式中：N*為真實(shí)Pareto前沿點(diǎn)集的規(guī)模；di為第i個真實(shí)前沿點(diǎn)到真實(shí)Pareto前沿的最近歐氏距離；N為最優(yōu)解集；若最優(yōu)解集中第i個解在真實(shí)Pareto前沿點(diǎn)集上則ei=0，否則ei=1。

算法參數(shù)的設(shè)置通常對元啟發(fā)式算法的有效性具有重要作用。影響IMBO算法性能的主要參數(shù)包括種群大小Psize、巡回次數(shù)G、領(lǐng)飛鳥產(chǎn)生的鄰域解的數(shù)量k、每個個體傳給下一代的鄰域解的數(shù)量x、跳躍代數(shù)limit、最大迭代次數(shù)Gmax、生成批次鄰域的概率a和局部搜索的百分比b。為了找到較優(yōu)秀參數(shù)的組合，本文采用正交實(shí)驗(yàn)法對參數(shù)進(jìn)行優(yōu)化配置。因?yàn)閗與x之間存在相互約束，不適合采用正交實(shí)驗(yàn)[23]，所以本文參考文獻(xiàn)[7,18-19]并結(jié)合大量測試，設(shè)置k=5，x=1。其他參數(shù)的因素水平表如表4所示。

表4 因素水平表

表5 正交實(shí)驗(yàn)表

續(xù)表5

3.3 分批方式對比

為了對比可變子批和一致子批兩種劃分策略，對算例5和算例6的測試數(shù)據(jù)分別采用兩種不同的分批策略，獨(dú)立運(yùn)行10次，每次運(yùn)行時(shí)間為M×D×10 s，兩種策略得到的Pareto前沿如圖6所示。

由圖中結(jié)果發(fā)現(xiàn)，當(dāng)批次數(shù)相同時(shí)，可變批次與一致子批相比可以更好地發(fā)揮分批作用。由于可變子批策略是對各道工序進(jìn)行批量劃分，劃分方案靈活多變，可以通過較少的批次數(shù)目縮短制造時(shí)間，而且可以更好地展現(xiàn)批次劃分與制造時(shí)間的關(guān)系，從而指導(dǎo)決策者做出合理的批次劃分和調(diào)度方案。

3.4 算法對比

為了驗(yàn)證本文IMBO算法的性能，分別選擇改進(jìn)的遺傳算法(Improved Genetic Algorithm, IGA)[24]、模擬退火混合的離散粒子群優(yōu)化算法(Hybrid Discrete Particle Swarm Optimization integrated with Simulated Annealing algorithm, HDPSO-SA)[25]和改進(jìn)的差分進(jìn)化模擬退火算法(Improved Differential Evolution Simulated Annealing Algorithm，IDESAA)[26]3種解決柔性作業(yè)車間多目標(biāo)問題的算法，開展對比試驗(yàn)，以錯誤率ER和反世代距離IGD作為評價(jià)指標(biāo)，ER和IGD越小，算法綜合性能越好。

將4種算法在每組測試數(shù)據(jù)下獨(dú)立運(yùn)行10次，每次運(yùn)行時(shí)間為M×D×10 s，取各指標(biāo)平均值作為最終測試結(jié)果，如表6所示。根據(jù)算法對比結(jié)果，IMBO算法的評價(jià)指標(biāo)IGD和ER在絕大數(shù)算例中優(yōu)于其他算法，說明相同測試條件下，在解決柔性作業(yè)車間的可變批次問題方面，IMBO算法得到的近似Pareto前沿比其他算法更接近真實(shí)的Pareto前沿，從而驗(yàn)證了IMBO算法改進(jìn)機(jī)制的合理性與有效性。

表6 算法對比測試結(jié)果

4 結(jié)束語

本文研究了可變批次劃分下的柔性作業(yè)車間分批調(diào)度問題，以最小化最大完工時(shí)間和最小化批次數(shù)目為優(yōu)化目標(biāo)建立了相應(yīng)的數(shù)學(xué)模型和析取圖模型。其次，針對該問題的特點(diǎn)并結(jié)合析取圖模型，提出一種IMBO算法，從可行鄰域和精英分批等方面提高了算法的尋優(yōu)能力。最后，通過算例比較了可變子批和一致子批兩種劃分方式的不同，證明可變批次的劃分方式可以更好地發(fā)揮分批策略的作用，并與其他求解分批問題的元啟發(fā)式算法進(jìn)行對比，有效驗(yàn)證了本文所提IMBO算法求解復(fù)雜分批調(diào)度問題的有效性。