考慮動態(tài)資源和工件批量約束的柔性車間生產(chǎn)調(diào)度

周亞勤,呂佑龍,鄭 鵬,張 潔

(1.東華大學(xué) 機械工程學(xué)院，上海 201620；2.上海交通大學(xué) 機械與動力工程學(xué)院，上海 200240)

0 引言

車間生產(chǎn)調(diào)度是現(xiàn)代制造系統(tǒng)的基礎(chǔ)，隨著車間加工中心和生產(chǎn)設(shè)備互聯(lián)互通技術(shù)的發(fā)展，實時感知設(shè)備加工狀態(tài)信息成為可能。在制定新調(diào)度周期車間生產(chǎn)調(diào)度方案時，可實時獲得設(shè)備剩余加工任務(wù)信息，進(jìn)而獲知設(shè)備在新調(diào)度周期內(nèi)的負(fù)荷能力，即設(shè)備資源的加工能力是動態(tài)變化的，調(diào)度周期內(nèi)的設(shè)備資源能力不均等?？紤]設(shè)備資源動態(tài)能力變化和工件批量性約束的柔性車間生產(chǎn)調(diào)度問題，是綜合考慮實際生產(chǎn)過程中的工件批量、調(diào)度周期內(nèi)設(shè)備資源負(fù)荷動態(tài)變化等特征，對工件進(jìn)行合理分批，確定其加工路徑，使設(shè)備負(fù)荷均勻，從而產(chǎn)生符合實際生產(chǎn)的調(diào)度方案，滿足產(chǎn)品交貨期。如何考慮調(diào)度周期內(nèi)設(shè)備資源動態(tài)變化和工件批量等約束，對柔性車間生產(chǎn)調(diào)度問題進(jìn)行有效建模與調(diào)度求解，是快速響應(yīng)市場和滿足客戶需求的關(guān)鍵，研究這類生產(chǎn)調(diào)度問題具有一定的理論意義和工程應(yīng)用價值。

近幾年來，柔性調(diào)度問題引起廣大研究者的關(guān)注[1]。Gonzalez等[2]提出基于路徑重連的分散搜索方法及基于關(guān)鍵塊的鄰域結(jié)構(gòu)設(shè)計，用于求解柔性調(diào)度問題；Mokhtari等[3]在柔性調(diào)度問題中考慮路徑柔性和隨時間變化的機器故障率，建立了柔性調(diào)度問題的混合整數(shù)線性規(guī)劃模型，并提出一種基于蒙特卡洛和模擬退火方法的混合方法進(jìn)行求解；Wang等[4]在柔性調(diào)度問題中考慮了機器故障中斷，采利用遺傳算法進(jìn)行求解；Sobeyko等[5]研究大型柔性作業(yè)車間中的工藝規(guī)劃和調(diào)度集成優(yōu)化問題，設(shè)計了可變鄰域搜索進(jìn)行工藝規(guī)劃，并設(shè)計了基于局部搜索的多啟發(fā)式規(guī)則，可在合理的時間內(nèi)求解大型柔性調(diào)度問題；張國輝等[6]利用改進(jìn)遺傳算法求解柔性作業(yè)車間調(diào)度問題；汪俊亮等[7]研究工時不確定條件下的多目標(biāo)柔性作業(yè)車間調(diào)度問題，用基于冗余處理的方法處理加工時間不確定的波動問題，建立了預(yù)調(diào)度模型，并設(shè)計了兩階段遺傳算法進(jìn)行求解；顧澤平等[8]以最大流程時間、工序分配均衡和設(shè)備評價利用率為目標(biāo)，研究不確定因素擾動下的多目標(biāo)柔性作業(yè)車間調(diào)度方法；Singh等[9]結(jié)合最大偏差理論提出一種新的粒子群優(yōu)化算法，用于求解考慮完工時間、流動時間和延遲等多個目標(biāo)的柔性作業(yè)車間調(diào)度問題；Meng等[10]提出一種混合人工蜂群算法，該算法引入動態(tài)方案自適應(yīng)地微調(diào)搜索范圍，用于求解考慮操作重疊的柔性調(diào)度問題。這些論文給出了柔性調(diào)度問題的建模和求解方法，但均未考慮工件批量約束問題。在實際生產(chǎn)過程中，工件往往具有批量性，若不進(jìn)行批量劃分，將整批工件的各道工序集中在某臺設(shè)備上加工，則可能因設(shè)備當(dāng)前調(diào)度期能力負(fù)荷不夠或工序安排在調(diào)度期后期而導(dǎo)致工件不能按期交貨。近年來，有學(xué)者在柔性調(diào)度問題中考慮批量問題。鞠全勇等[11]研究批生產(chǎn)中以生產(chǎn)周期、最大提前最大拖后時間、生產(chǎn)成本和設(shè)備利用率指標(biāo)(機床總負(fù)荷和機床最大負(fù)荷)為調(diào)度目標(biāo)的柔性作業(yè)車間優(yōu)化調(diào)度問題；Zhang等[12]考慮實際生產(chǎn)中的批量和交貨期約束，提出一種基于概率模型遺傳算法的局部搜索算法進(jìn)行求解，文中考慮了工件批量數(shù)，但沒有對具體批量進(jìn)行劃分；Ozturk等[13]提出一種分支定界算法，用于求解具有不同加工時間、釋放時間和單元大小的并行批量調(diào)度問題，其中工件批量作業(yè)數(shù)不能超過設(shè)備容量，一批工件一起加工，加工時間由該批工件中工件的最大加工時間確定，但文中未考慮批量劃分；徐本柱等[14]提出一種試探法，對柔性作業(yè)車間分批調(diào)度進(jìn)行批量劃分，并提出相同工件同批工序間和不同工序間可并行的車間調(diào)度算法進(jìn)行柔性作業(yè)車間批量劃分與調(diào)度優(yōu)化；Yu等[15]以工件的總延誤最小為目標(biāo)，研究兩階段混合流水車間的批量劃分和調(diào)度問題，提出混合整數(shù)規(guī)劃模型和3種迭代算法，進(jìn)行批次劃分和調(diào)度；王海燕等[16]和王萬良等[17]利用差分進(jìn)化算法求解柔性批量調(diào)度問題。大多數(shù)文獻(xiàn)在批次劃分和加工路徑確定時均認(rèn)為調(diào)度期內(nèi)所有設(shè)備能力負(fù)荷相等。

實際車間生產(chǎn)調(diào)度中的車間設(shè)備資源往往是動態(tài)變化的。調(diào)度周期產(chǎn)生的調(diào)度方案中，不可能所有設(shè)備上的任務(wù)都在同一時刻完成，有些設(shè)備上的任務(wù)可能會延續(xù)到下一調(diào)度周期。原有調(diào)度周期生成調(diào)度方案時，往往以交貨期和加工時間最短為目標(biāo)，在新的調(diào)度周期中應(yīng)盡量不打亂設(shè)備上剩余任務(wù)的加工順序，以免影響上一調(diào)度周期的工件交貨期。因此，在排產(chǎn)新調(diào)度周期時，首先需要分析設(shè)備上一調(diào)度周期的剩余任務(wù)，以所有設(shè)備的最早空閑時刻作為新調(diào)度周期的起始時刻，其他設(shè)備需要完成上一調(diào)度周期的任務(wù)后才可進(jìn)行下一調(diào)度周期任務(wù)的生產(chǎn)。本文考慮的動態(tài)資源即指在新的調(diào)度周期，各設(shè)備資源的加工能力因為是動態(tài)變化的，所以需要根據(jù)上一調(diào)度周期任務(wù)的完成情況確定，并非調(diào)度起始時刻都可用。本文研究考慮調(diào)度周期內(nèi)設(shè)備資源能力動態(tài)變化的柔性批量生產(chǎn)調(diào)度問題，首先構(gòu)建考慮設(shè)備資源動態(tài)變化和工件批量性約束的柔性車間生產(chǎn)調(diào)度模型，設(shè)計批量劃分和加工路徑確定規(guī)則，然后提出嵌套式遺傳算法，進(jìn)行批量劃分、加工路徑確定和生產(chǎn)調(diào)度的綜合優(yōu)化，在滿足設(shè)備能力負(fù)荷約束的同時使工件完工時間最小，并滿足工件交貨期要求。

1 考慮動態(tài)資源和工件批量約束的柔性車間生產(chǎn)調(diào)度模型

1.1 考慮動態(tài)資源和工件批量約束的柔性車間生產(chǎn)調(diào)度問題的定義

考慮動態(tài)資源和工件批量約束的柔性車間生產(chǎn)調(diào)度問題可以定義為：考慮設(shè)備資源上一調(diào)度周期的剩余加工任務(wù)負(fù)荷約束，確定新調(diào)度周期內(nèi)設(shè)備資源的動態(tài)加工能力值，對新調(diào)度周期中的工件任務(wù)進(jìn)行調(diào)度，工件具有批量性，且工件的每道工序可在多臺設(shè)備中選擇一臺設(shè)備進(jìn)行加工，具有柔性的加工路徑。如何在設(shè)備動態(tài)資源約束、工件批量和柔性加工路徑等約束下，針對生產(chǎn)任務(wù)進(jìn)行批量劃分和確定加工路徑，并優(yōu)化設(shè)備上工件的加工順序，使工件能夠按期交貨，且使機床負(fù)荷均衡化，工件的完工時間最小，是柔性車間批量生產(chǎn)調(diào)度需要解決的問題。

考慮設(shè)備動態(tài)資源和工件批量約束的柔性車間生產(chǎn)調(diào)度問題可以描述為：有n種工件{J1,J2,…,Ji,…,Jn}，每種工件有一定的批量數(shù)Bi，工件的交貨期約束為DTi(i=1,2,…,n)；每種工件均由一系列工序Oij(j=1,2,…,TOi)組成，其中TOi表示工件Ji的總工序數(shù)，Oij表示工件Ji的第j道工序，工序Oij在設(shè)備集Mij上加工，Mij∈M={M1，M2，…，Mk，…,Mm}，在設(shè)備組中Mk上的準(zhǔn)備時間和加工時間分別為ATijk和PTijk。設(shè)備Mk的上一調(diào)度周期剩余生產(chǎn)任務(wù)所占的時間負(fù)荷為Uk，當(dāng)前調(diào)度周期的總時間跨度為TC，則在當(dāng)前調(diào)度周期內(nèi)設(shè)備Mk的動態(tài)加工能力為Ck，Ck=TC-Uk，各設(shè)備資源的加工能力隨上一調(diào)度周期剩余任務(wù)的負(fù)荷而定，是動態(tài)變化的，即調(diào)度周期內(nèi)有動態(tài)資源。問題的求解是對每種工件進(jìn)行子批量劃分，為了區(qū)分子批量劃分后的工件，將同一子批的工件定義為同一批次工件，需要確定每種工件的批次數(shù)BNi及每批次包含的工件批量數(shù)BSil，即將每種工件Ji劃分為BNi個批次，Ji={Ji1，Ji2，…，Jil，…，JiBNi}，各批次的子批量數(shù)分別為{BSi1，BSi2，…，BSil，…，BSiBNi}，其中Ji1為工件Ji的第一批次的工件代號，BSi1為工件Ji第1批次工件Ji1包含的工件批量數(shù)。例如工件J1的批量數(shù)為100，即B1=100，將工件劃分為5個批次，即BN1=5，工件J1={J11，J12，…，J15}；各批次的批量數(shù)分別為20，15，20，20，25，即BS11=20，以此類推，BS15=25。子批劃分后，需要為不同批次工件的各道工序分配設(shè)備組Mij中的加工設(shè)備，即Milj=Mk∈Mij，同種工件不同批次的同一工序可以在不同設(shè)備上加工，因此工件可并行加工，從而縮短同種工件的完工時間?？紤]設(shè)備資源動態(tài)加工能力約束，排定各工序在設(shè)備上的加工順序和起始加工時間，使各設(shè)備負(fù)荷均衡，工件能夠按期交貨，而且設(shè)備的利用率最大，所有工件的總完工時間最小。工件分子批后，不同批次的工件依然遵守該種工件的交貨期要求。

考慮設(shè)備動態(tài)資源和工件批量約束的柔性車間生產(chǎn)調(diào)度問題同時滿足下列假設(shè)條件：

(1)已知每種工件的總批量數(shù)，劃分子批后，同一批次的工件安排在一起加工。

(2)已知當(dāng)前調(diào)度周期的總時間跨度，以及設(shè)備的上一調(diào)度周期剩余生產(chǎn)任務(wù)所占用的時間負(fù)荷。

(3)同種工件不同子批的工序可以在工序的設(shè)備組中選擇不同設(shè)備進(jìn)行加工。

(4)已知每種工件單個工件各道工序在相應(yīng)設(shè)備上的加工時間和輔助時間，分子批后，單個工件工序時間不變。

(5)某一時刻，每臺設(shè)備只能加工工件某批次的一道工序。

(6)某一時刻，每個子批次工件只能有一道工序正在被加工。

(7)某道工序一旦在設(shè)備上開始加工，則不允許中斷，除非機床故障。

(8)新調(diào)度周期內(nèi)，保留設(shè)備上剩余任務(wù)的加工順序，不對剩余任務(wù)進(jìn)行重排。

解決上述問題的混合整數(shù)規(guī)劃中用到的標(biāo)識及其定義如下：

STilj為第i種工件第l個子批第j道工序的起始加工時間；

ETilj為第i種工件第l個子批第j道工序的結(jié)束加工時間；

Xiljk為第i種工件第l個子批第j道工序是否在設(shè)備Mk上加工過的標(biāo)識；

CTi為第i種工件的完工時間

CTmax為所有工件的完工時間；

OTk為當(dāng)前調(diào)度周期內(nèi)設(shè)備Mk加工工件的總時間；

NTk為當(dāng)前調(diào)度周期內(nèi)設(shè)備Mk下一可加工工件的時刻。

1.2 約束和目標(biāo)函數(shù)

考慮設(shè)備動態(tài)資源和工件批量性約束的柔性車間生產(chǎn)調(diào)度問題滿足以下約束：

(1)任何一種工件分子批后，工件的總批量數(shù)不變，工件各子批次的子批量數(shù)和等于工件的總批量數(shù)，即

(1)

(2)每種工件各子批的每道工序安排在一臺設(shè)備上加工，不再分批，即

(2)

如果工序Milj=Mk，則xiljk=1；否則，xiljk=0。

(3)調(diào)度周期內(nèi)，機床Mk上加工工件的總時間約束為

(3)

(4)第i種工件第l個子批的第j道工序在機床k上加工，工序起始加工時間STiljk和工序結(jié)束加工時間ETiljk存在約束，如式(4)所示。同一子批的某道工序在設(shè)備k上的準(zhǔn)備時間等于單個工件的準(zhǔn)備時間，加工時間等于單個工件工序加工時間乘以子批量數(shù)。

ETiljk=STiljk+ATijk+PTijk×BSil。

(4)

(5)工件分子批后，同一批次工件各道工序間仍然遵守特定的工藝路線，即

STil(j+1)≥ETilj。

(5)

(6)第i種工件的完工時間等于各子批工件最后一道工序完工時間的最大值，即

CTi=max(ETil(TOi))，l=1,2,…,BNi。

(6)

考慮動態(tài)資源的柔性批量車間生產(chǎn)調(diào)度問題的目標(biāo)函數(shù)如下：

(1)所有工件分子批的總批次數(shù)量

(7)

(2)所有設(shè)備加工工件的總時間數(shù)超出當(dāng)前調(diào)度周期設(shè)備的加工能力值，即

(8)

如果OTk>Ck，則xk=1；否則，xk=0。

(3)考慮各臺設(shè)備的加工負(fù)荷均衡，有

(9)

(4)工件滿足交貨期要求，設(shè)工件超出交貨期時間為

(10)

如果CTi>DTi，則yi=1;否則,yi=0。

(5)工件的總完工時間

f5=max(CTi，i=1,2,…,n)。

(11)

一批工件盡可能安排在一起加工，不分子批時，調(diào)度周期內(nèi)設(shè)備的總加工時間可能會超出設(shè)備的能力負(fù)荷，需對工件劃分子批，不僅可以為不同子批選擇不同的具有富余能力的設(shè)備，還可以均衡設(shè)備負(fù)荷。因此，在劃分子批并確定柔性工藝路徑時，主要考慮的目標(biāo)函數(shù)是使所有工件分子批的總批次數(shù)量f1最小、設(shè)備加工總時間超出設(shè)備能力值f2最小和各臺設(shè)備加工負(fù)荷均衡，即加工負(fù)荷均方差值f3最小。在子批劃分和工藝路徑確定后生成車間調(diào)度方案時，主要考慮工件按期交貨，即工件超出交貨期時間數(shù)f4和工件的總完工時間f5最小。

2 考慮動態(tài)資源和工件批量約束的柔性車間生產(chǎn)調(diào)度的求解方法

2.1 批量分解規(guī)則

求解柔性車間批量生產(chǎn)調(diào)度問題，首先要對零件進(jìn)行合理地批量劃分。若工件子批次批量數(shù)太大，則可能導(dǎo)致當(dāng)前調(diào)度期的設(shè)備能力負(fù)荷超載，或工件延期交貨；若各子批次工件批量數(shù)太小，工件批次數(shù)增加，則會增加各子批次工件工序之間的調(diào)整準(zhǔn)備時間，以及后續(xù)調(diào)度問題的復(fù)雜性。利用遺傳算法求解工件批量合理劃分前，制定以下批量分解規(guī)則對工件批量劃分求解進(jìn)行約束：

規(guī)則1若某工件的總批量數(shù)小于等于3，則不對該工件劃分批量批次。

規(guī)則2若某工件總批量的設(shè)備占用時間(準(zhǔn)備時間加上工序加工時間)較少，小于等于5個時間單位，則不對該工件劃分批量批次。

規(guī)則3當(dāng)考慮批量的柔性工藝路徑確定時，在滿足機床能力負(fù)荷約束下，工件所分的批次數(shù)盡量小，應(yīng)滿足目標(biāo)1，即工件的總子批次數(shù)量盡可能小。

規(guī)則4各工件分批批次數(shù)量的上限值可由決策者確定。

2.2 動態(tài)資源約束下的加工路徑確定規(guī)則

規(guī)則5考慮上一調(diào)度周期設(shè)備的剩余負(fù)荷，基于設(shè)備的動態(tài)資源約束，在工序的可加工設(shè)備中選擇具有最大富余度的設(shè)備進(jìn)行本道工序加工。定義每臺設(shè)備的能力富余度為

(12)

規(guī)則6對于交貨期要求比較緊急的工件，不同子批次的同一工序盡量選擇在不同的設(shè)備上加工。該規(guī)則可以并行加工同種但不同批次的工件，從而避免因設(shè)備集中加工而導(dǎo)致設(shè)備能力不足或工件不能按期交貨。

規(guī)則7在設(shè)備能力負(fù)荷能夠滿足要求時，同一子批的相鄰工序如果可以在同一設(shè)備上加工，則相鄰工序盡量選擇在同一設(shè)備上加工，以減少設(shè)備的準(zhǔn)備時間。

2.3 求解柔性車間批量調(diào)度問題的嵌套式遺傳算法

2.3.1 求解柔性車間批量調(diào)度問題的嵌套式遺傳算法流程

求解柔性車間批量生產(chǎn)調(diào)度問題的嵌套式遺傳算法流程如圖1所示，外層優(yōu)化劃分工件批量并優(yōu)化各子批零件的柔性工藝路徑，目的是使所有工件分子批的總批次數(shù)量f1最小、設(shè)備加工總時間超出設(shè)備能力值f2最小和各設(shè)備加工負(fù)荷均衡，即加工負(fù)荷均方差值f3最小。內(nèi)層優(yōu)化是在外層優(yōu)化確定的批量劃分和工藝路徑約束條件下，對設(shè)備加工調(diào)度方案進(jìn)行優(yōu)化，以滿足各零件的交貨期約束，同時使最終的總加工時間最短，優(yōu)化目標(biāo)為f4和f5。當(dāng)同時滿足嵌套式遺傳算法內(nèi)層優(yōu)化和外層優(yōu)化的終止條件時，輸出記憶細(xì)胞中的優(yōu)化結(jié)果，即各工件的子批量劃分方案、各子批工件的加工路徑約束及各設(shè)備上的加工調(diào)度方案。

2.3.2 求解批量劃分與路徑優(yōu)化的遺傳算法

(1)種群初始化及染色體編碼方式

在求解批量劃分和路徑優(yōu)化的遺傳算法中，采用隨機生成方法產(chǎn)生大部分初始種群個體，采用批量分解規(guī)則生成小部分初始種群個體。染色體采用二進(jìn)制編碼，染色體的長度等于調(diào)度周期內(nèi)的所有工件數(shù)。按照工件種類數(shù)將染色體分成若干片段，每個片段染色體對應(yīng)為每種工件的批量劃分方案，每個片段基因位數(shù)等于該種類工件的批量數(shù)，基因位上的1/0分別表示該處工件是否進(jìn)行批次分割。例如某片段染色體為0100100，其對應(yīng)種類的工件將分為3個子批次，各子批次批量數(shù)分別為2，3，2。

(2)交叉算子和變異算子

根據(jù)子批劃分問題的染色體編碼特征，交叉算子采用兩個父染色體的同種類工件編碼片段進(jìn)行交叉，具體為在兩個父染色體若干片段中隨機選擇一種工件片段，判斷兩個片段是否相同，不同則交換兩個父染色體的同一片段基因段產(chǎn)生兩個新染色體，相同則重新選擇染色體片段。

變異算子采用多位基因位值變異的方法，在父代染色體的每個片段基因中隨機選擇一個基因位，將基因位上的數(shù)值進(jìn)行0-1互換。

(3)基于設(shè)備順序優(yōu)選法的解碼算子設(shè)計

基于設(shè)備順序優(yōu)選法解碼算子設(shè)計的具體步驟如下：

步驟1首先對染色體進(jìn)行解釋，翻譯記錄成工件的批量劃分方案，記錄每種工件的批次數(shù)BNi及每批次的批量數(shù)BSil，將每種工件劃分為BNi個批次，即Ji={Ji1，Ji2，…，Jil，…，JiBNi}，由此得到新的工件集合J={J11，…,J1BN1，…，Jil，…，JnBNn}，批量數(shù)為{BS11，…,BS1BN1，…，BSil，…，BSnBNn}，新的總工件批次數(shù)NN=∑BNi。

步驟2基于設(shè)備分配規(guī)則為每子批工件各道工序分配設(shè)備，確定染色體對應(yīng)的各子批工件的工藝路線。

本文設(shè)計一種對工序進(jìn)行設(shè)備分配并確定工件工藝路線的快速算法，算法流程如下：

(2)定義WaitO為待分配設(shè)備的工序集合，WaitO={vi}，vi為UrgentJ集合中所有工件待分配的工序，采用兩種方法形成vi的排序：①將工件集合UrgentJ中的所有工件順序排列，形成vi的排序，按順序分配完一個子批工件所有工序的設(shè)備，再分配下一子批工件的所有工序，直至分配完，即WaitO1={O111，…，O11TO1,O121,…,O12TO1,…,OnBNn1,…,OnBNnTOn}；②將新工件集合UrgentJ中工件的每道工序進(jìn)行排序，形成vi的排序，按順序先分配所有子批工件的第一道工序，再分配第二道工序，直至安排完所有工序，即WaitO2={O111，O121,…，OnBNn1,O112,…,OnBNn2,…,O11TO1,…,OnBNnTOn}。定義MO為WaitO中工序所分配的機床集合，MO={Mi}。

(3)利用設(shè)備分配規(guī)則分配工序vi的設(shè)備，依次選取集合WaitO中的每一個待分配設(shè)備工序vi，計算可加工工序vi的機床集合中每臺設(shè)備的富余度A(Mk)。設(shè)備分配規(guī)則的調(diào)用策略如下：如果工序vi所屬工件屬于交貨期緊急的工件且為同類工件的非第一子批，則調(diào)用規(guī)則6，選擇與同類工件其他批次已排設(shè)備不同的剩下設(shè)備中富余度Ak最高的設(shè)備，否則調(diào)用規(guī)則7；若同批次中前道工序的設(shè)備剩余能力足夠，則選擇該設(shè)備，否則按照規(guī)則5選擇可加工機床集合中Ak最高的設(shè)備。完成所有工序的設(shè)備選擇后，得到染色體對應(yīng)的新工件集合的設(shè)備分配結(jié)果MO，其偽程序代碼如下：

While (WaitO≠?) do

{vi=WaitO(1)=Oilj

IFJ(vi)∈UrgentJ and l>1

M(vi)=Mk=argmax(A(Mk))，Mk∈{M(vi)}且Mk≠M(Oi(l-1)j)

ELSE

{

IF j=1M(vi)=Mk=argmax(A(Mk))，Mk∈{M(vi)}

ELSE

{k=M(Oil(j-1))

IF Ck-OTk>ATvi+BSil×PTviM(vi)=Mk=M(Oil(j-1))

ELSE M(vi)=Mk=argmax(A(Mk))，Mk∈{M(vi)}

/}

/}

MO=MO+Mk//Mk添加到記錄設(shè)備分配的集合

OTk=OTk+ATvi+BSil×PTvi//更新設(shè)備Mk負(fù)荷

Delete viFrom WaitO

/}

(4)適應(yīng)值函數(shù)

染色體解碼后得到各工件批次數(shù)、各子批數(shù)量和各子批工件工序分配的設(shè)備，每個染色體對應(yīng)的分批結(jié)果、新工件集合和各工件工序設(shè)備的分配集合MO作為內(nèi)層遺傳算法工件的約束輸入，調(diào)用內(nèi)層遺傳算法，產(chǎn)生染色體對應(yīng)工件工藝路線約束下的生產(chǎn)調(diào)度方案，由此計算外層各染色體對應(yīng)的目標(biāo)值。

本文采用基于分解的多目標(biāo)進(jìn)化算法[18-19]，將批量柔性調(diào)度問題分解為工件分批、工藝路徑確定和工件調(diào)度3個子問題，分別對應(yīng)目標(biāo)函數(shù)中的分批數(shù)量f1、設(shè)備加工總時間超出設(shè)備能力值f2、各臺設(shè)備加工負(fù)荷均方差值f3、工件超出交貨期時間數(shù)f4和工件的總完工時間f5，對這些目標(biāo)函數(shù)進(jìn)行歸一化處理并加權(quán)求和取倒數(shù)，作為染色體的適應(yīng)值函數(shù)，即

(13)

適應(yīng)度值越高的個體越可能被選擇進(jìn)行交叉、變異操作，生成新種群個體，對當(dāng)代染色體按適應(yīng)度值f從大到小排序，采用輪盤賭和精英保留策略相結(jié)合的方法選擇染色體。

2.3.3 求解調(diào)度子問題的遺傳算法

外層遺傳算法確定工件分批和加工路徑設(shè)備方案后，調(diào)用內(nèi)層遺傳算法求解典型調(diào)度問題。遺傳算法已廣泛應(yīng)用于生產(chǎn)調(diào)度問題的求解中，本文采用文獻(xiàn)[20]中提出的基于工序的編碼方法(每個染色體均可解碼成合理的解)、基于線性次序交叉方法和變異互換基因的變異方法對調(diào)度問題求進(jìn)行解。下面介紹算法中涉及的解碼方法和鄰域結(jié)構(gòu)設(shè)計。

(1)解碼方法

在調(diào)度方案內(nèi)層遺傳算法的求解過程中，解碼方法是關(guān)鍵。解碼時考慮外層設(shè)定好的工件分批和設(shè)備選擇約束，對種群中的個體進(jìn)行解碼，生成當(dāng)前調(diào)度方案下設(shè)備上各工件工序的加工順序和加工起始結(jié)束時間，從而求得各類工件的交貨期延誤時間和工件的總完工時間。根據(jù)外層遺傳算法產(chǎn)生的工件分批形成的新工件集合J、工件批次數(shù)BNi、每批次的批量數(shù)BSil、工序的設(shè)備選擇集合MO和對應(yīng)的工序加工時間矩陣Jt，對種群中的每個染色體進(jìn)行解碼，具體操作步驟如下：

步驟1染色體的基因位數(shù)值i表示工件Ji的某道工序，依次獲取i并判斷i出現(xiàn)的次數(shù)，第j次出現(xiàn)的i表示工件Ji的第j道工序。

步驟2根據(jù)新工件集合、子批批量數(shù)、設(shè)備和加工時間約束，利用式(4)和式(5)確定工序Oij的加工開始時間和結(jié)束時間，并更新記錄各設(shè)備上的工序加工順序。

步驟3重復(fù)步驟1和步驟2，直到染色體所有基因位數(shù)值解碼結(jié)束，根據(jù)式(10)和式(11)分別計算當(dāng)前抗體所對應(yīng)調(diào)度方案的交貨期超出時間和總完工時間。

(2)考慮多選設(shè)備的鄰域結(jié)構(gòu)設(shè)計

工件分批解碼生成加工路徑時未考慮調(diào)度過程，在確定各設(shè)備上的工件加工順序、產(chǎn)生調(diào)度方案的過程中，由于同一批次工件工序路線的前后約束關(guān)系，每道工序必須在同批次工件的前道工序和所加工設(shè)備上的前道工序結(jié)束后才能開始加工。在當(dāng)前設(shè)備選擇方案下，可能導(dǎo)致部分工件不能按期交貨，因此采用改變工序的設(shè)備分配來改善調(diào)度方案。Mastroli等[1]已經(jīng)證明了該方法的可行性。

根據(jù)外層遺傳算法解碼，用MO表示工件分批后的設(shè)備分配，Sequence表示由遺傳算法產(chǎn)生的調(diào)度方案。在Sequence表達(dá)的調(diào)度方案中，若工件Ji不能按期交貨，即CTi>DTi，則在工序中找到STij>ETi(j-1)的工序Oij，改變工序的設(shè)備，M(Oij)=Mk∈Mij,k≠v=MO(Oij)，并按照工序約束將工序Oij插入設(shè)備Mk上的最早可開始加工時刻，選擇ETi(j-1)≤STijk

(3)考慮調(diào)度方案的鄰域結(jié)構(gòu)設(shè)計

為了增加遺傳算法進(jìn)化過程中染色體的多樣性，設(shè)計考慮調(diào)度方案的鄰域結(jié)構(gòu)。對于調(diào)度方案Sequence，選擇負(fù)荷最大的設(shè)備，交換設(shè)備上兩道屬于不同工件的工序。例如，對于Sequence={…,Oij,…,Oqs,…}，?ETi(j-1)>ETq(s-1)，MO(Oij)=MO(Oqs)，則交換設(shè)備上工序Oij和Oqs得到鄰域解Sequence′={…,Oqs,…,Oij,…}。對鄰域解進(jìn)行解碼，求解鄰域解對應(yīng)的目標(biāo)函數(shù)值。

(4)保存并反饋近優(yōu)解

求解內(nèi)層遺傳算法得到近優(yōu)解，將調(diào)度方案的完工時間和超出交貨期時間目標(biāo)值反饋到外層遺傳算法，綜合評估當(dāng)前分批和加工路徑方案的性能。按照式(13)計算分批和加工路徑方案的適應(yīng)值函數(shù)，進(jìn)一步進(jìn)行選擇和交叉進(jìn)化。

3 調(diào)度案例測試與分析

3.1 考慮批量的測試

采用文獻(xiàn)[21]中標(biāo)準(zhǔn)10×10的完全柔性調(diào)度案例進(jìn)行測試，該調(diào)度問題包括10種工件，每種工件包括3道工序，每道工序可在10臺不同的機床設(shè)備上加工，加工時間隨設(shè)備的不同而不同，已知文獻(xiàn)中該案例的最優(yōu)解makespan=7。在該標(biāo)準(zhǔn)案例中，首先假設(shè)工件的批量統(tǒng)一為10，若將10個工件作為一個整體不進(jìn)行分批，則相當(dāng)于原來的工件加工時間增加10倍，最優(yōu)解makespan=70。

結(jié)合本文提出的批量分解和加工路徑確定規(guī)則，調(diào)用嵌套式遺傳算法對標(biāo)準(zhǔn)10×10案例進(jìn)行求解，其中批量數(shù)為10。文獻(xiàn)[22]研究指出，對于中等規(guī)模的調(diào)度問題，種群規(guī)模一般設(shè)置為20～50，迭代次數(shù)一般設(shè)置為200～500代，交叉率取值0.7～0.9，變異率取值0.01～0.2。本文利用遺傳算法進(jìn)行批量劃分和路徑確定時，算法參數(shù)設(shè)置為：種群規(guī)模Psize=50，迭代次數(shù)NG=200，交叉率Pc=0.8，變異因子Pi=0.1。最終獲得優(yōu)化解的分批方案為{2 3 3 4 1 2 3 2 4 3}，即第1種到第10種工件分別分成2，3，…，3批，每種工件各批次的批量數(shù)及分批后指定的機床如表1所示，工件分批后，每道工序?qū)?yīng)的加工時間為文獻(xiàn)[21]的原始時間數(shù)據(jù)乘以該批次工件對應(yīng)的工件批量數(shù)。優(yōu)化解對應(yīng)的總完工時間makespan=62，比工件不分批時的最優(yōu)解完工時間70減少了11.4%。若將各工件進(jìn)行平均分批，即每種工件劃分為2個子批，每個子批中的工件批量數(shù)為5，則可求得這種子批劃分下最優(yōu)解的總完工時間makespan=65，而調(diào)用本文嵌入式遺傳算法，通過批量劃分和路徑確定后，最優(yōu)解對應(yīng)的總完工時間為makespan=62，驗證了本文算法的優(yōu)越性。

表1 工件各批次的批量數(shù)及分批后指定的機床

嵌套式遺傳算法求解批量柔性調(diào)度問題時，外層遺傳算法確定子批和工藝路徑，內(nèi)層遺傳算法求解當(dāng)前批量和工藝路徑約束下的調(diào)度方案，并將makespan反饋到外層遺傳算法中，外層遺傳算法是主進(jìn)化過程。外層遺傳算法中確定批量劃分和工藝路徑方案時，工件的總完工時間makespan值隨算法迭代次數(shù)的收斂趨勢如圖2a所示，可見在第70代附近，算法收斂得到makespan的優(yōu)化解。對應(yīng)外層遺傳算法第50代時的批量劃分和工藝路徑，調(diào)用內(nèi)層遺傳算法求解當(dāng)前批量劃分下的makespan=72，內(nèi)層遺傳算法求解過程中工件的總完工時間makespan值隨算法迭代次數(shù)的收斂趨勢如圖2b所示，可見在第80代附近，內(nèi)層遺傳算法收斂到外層遺傳算法第50代所對應(yīng)的批量劃分和工藝路徑狀態(tài)下的makespan為最優(yōu)解。

嵌套式遺傳算法求解得到的優(yōu)化解對應(yīng)調(diào)度方案的甘特圖如圖3所示。圖中，O321表示工件J3的第2子批工件J32的第1道工序，該工序選擇設(shè)備M10加工，加工的起始和結(jié)束時間分別為0和2，其他符號類似。從圖中可以看出，同種工件不同批次的同一工序可以選擇不同設(shè)備，并可同時加工，減少了總完工時間，例如工件J4的第1，2，3，4子批的第1道工序分別選擇了加工時間最短的設(shè)備M7，M7，M7，M9，而且在安排生產(chǎn)調(diào)度方案時盡可能將同一種工件的同一道工序安排在一起加工，機床M7上的O411，O421，O431在一起加工，M7和M9上同一種工件不同批次的同一工序O411和O441同時加工，從而在分批后減小工件J4第1道工序的完工時間，改善了總完工時間。因此，本文所提啟發(fā)式規(guī)則對改善解的性能起到了很好的作用。

3.2 考慮設(shè)備資源和交貨期約束的柔性批量調(diào)度測試

在上面測試案例的基礎(chǔ)上，考慮設(shè)備上一調(diào)度周期的剩余任務(wù)，進(jìn)行設(shè)備動態(tài)資源和工件交貨期約束下的柔性批量調(diào)度測試。假設(shè)當(dāng)前調(diào)度周期的總時間跨度為70，設(shè)備{M1，M2，…，M10}的上一調(diào)度周期剩余生產(chǎn)任務(wù)所占用的時間為{0,5,0,6,0,5,0,10,0,5}，則在新的調(diào)度周期，設(shè)備{M1，M2，…，M10}的動態(tài)資源加工能力分別為{70,65,70,64,70,65,70,60,70,65}，假設(shè)工件{J1，J2，…，J10}的交貨期要求為{60,60,50,70,60,70,70,60,40,60}。

調(diào)用本文所提規(guī)則和嵌套式遺傳算法，在設(shè)備動態(tài)資源和工件交貨期約束下，求得優(yōu)化解的分批方案為{2 3 3 4 1 2 3 2 3 3}，每種工件各批次的批量數(shù)及分批后指定的機床如表2所示，工件分批后，每道工序?qū)?yīng)的加工時間為文獻(xiàn)[21]的原始時間數(shù)據(jù)乘以該批次工件對應(yīng)的工件批量數(shù)。優(yōu)化調(diào)度方案的makespan=62，調(diào)度方案對應(yīng)的其他目標(biāo)函數(shù)值分別為：f1=26，f2=0，f3=0.2，f4=0，f5=62。優(yōu)化解的甘特圖如圖4所示，圖中陰影部分為各設(shè)備上一調(diào)度周期剩余任務(wù)所占用的時間。從圖中可見，算法在確定分批和路徑時考慮設(shè)備負(fù)荷，在排定生產(chǎn)調(diào)度方案時考慮工件交貨期約束，重新進(jìn)行了工件批量劃分、路徑確定和生產(chǎn)調(diào)度，所得優(yōu)化解在保證makespan不變的同時，滿足了設(shè)備負(fù)荷和工件交貨期的要求，證明了所提算法能夠獲得綜合性能最優(yōu)的調(diào)度方案。

表2 工件各批次的批量數(shù)、分批后指定的機床和工件完成時間

續(xù)表2

續(xù)表2

4 結(jié)束語

本文對考慮調(diào)度周期內(nèi)設(shè)備資源受上一調(diào)度周期剩余任務(wù)動態(tài)影響的柔性批量車間調(diào)度進(jìn)行了研究，提出嵌套式混合遺傳算法求解考慮動態(tài)資源約束的柔性批量調(diào)度問題，論文工作總結(jié)如下：

(1)對車間實際生產(chǎn)約束進(jìn)行抽象，構(gòu)建了考慮設(shè)備資源動態(tài)變化、工件批量特性、工序加工設(shè)備柔性等約束的柔性批量車間調(diào)度問題模型，更符合實際生產(chǎn)約束。

(2)采用嵌套式混合遺傳算法進(jìn)行求解，調(diào)度的最終目標(biāo)是任務(wù)的總完工時間最小和工件按期交貨，在利用外層遺傳算法確定工件分批和工序加工設(shè)備的同時，綜合考慮內(nèi)層遺傳算法產(chǎn)生的調(diào)度方案的總完工時間和工件交貨期延誤時間，進(jìn)一步更新外層遺傳算法個體，改善了算法的進(jìn)化效果。

(3)通過案例庫實例驗證了算法的可行性和有效性，并在標(biāo)準(zhǔn)案例基礎(chǔ)上對增加批量、設(shè)備上一周期負(fù)荷、工件交貨期等實際約束進(jìn)行測試，測試結(jié)果驗證了算法可以很好地解決動態(tài)資源約束下的柔性批量調(diào)度問題，具有一定的工程應(yīng)用前景，并能產(chǎn)生指導(dǎo)實際生產(chǎn)且綜合性能最優(yōu)的調(diào)度方案。

未來可綜合考慮車間設(shè)備故障、緊急加工任務(wù)插入等動態(tài)擾動事件，進(jìn)一步研究動態(tài)擾動下的柔性車間動態(tài)調(diào)度方法，從而更好地指導(dǎo)柔性車間實際生產(chǎn)調(diào)度。