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

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

0 引言

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

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

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

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

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

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

考慮設備動態(tài)資源和工件批量約束的柔性車間生產調度問題可以描述為：有n種工件{J1,J2,…,Ji,…,Jn}，每種工件有一定的批量數(shù)Bi，工件的交貨期約束為DTi(i=1,2,…,n)；每種工件均由一系列工序Oij(j=1,2,…,TOi)組成，其中TOi表示工件Ji的總工序數(shù)，Oij表示工件Ji的第j道工序，工序Oij在設備集Mij上加工，Mij∈M={M1，M2，…，Mk，…,Mm}，在設備組中Mk上的準備時間和加工時間分別為ATijk和PTijk。設備Mk的上一調度周期剩余生產任務所占的時間負荷為Uk，當前調度周期的總時間跨度為TC，則在當前調度周期內設備Mk的動態(tài)加工能力為Ck，Ck=TC-Uk，各設備資源的加工能力隨上一調度周期剩余任務的負荷而定，是動態(tài)變化的，即調度周期內有動態(tài)資源。問題的求解是對每種工件進行子批量劃分，為了區(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。子批劃分后，需要為不同批次工件的各道工序分配設備組Mij中的加工設備，即Milj=Mk∈Mij，同種工件不同批次的同一工序可以在不同設備上加工，因此工件可并行加工，從而縮短同種工件的完工時間?？紤]設備資源動態(tài)加工能力約束，排定各工序在設備上的加工順序和起始加工時間，使各設備負荷均衡，工件能夠按期交貨，而且設備的利用率最大，所有工件的總完工時間最小。工件分子批后，不同批次的工件依然遵守該種工件的交貨期要求。

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

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

(2)已知當前調度周期的總時間跨度，以及設備的上一調度周期剩余生產任務所占用的時間負荷。

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

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

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

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

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

(8)新調度周期內，保留設備上剩余任務的加工順序，不對剩余任務進行重排。

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

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

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

Xiljk為第i種工件第l個子批第j道工序是否在設備Mk上加工過的標識；

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

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

OTk為當前調度周期內設備Mk加工工件的總時間；

NTk為當前調度周期內設備Mk下一可加工工件的時刻。

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

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

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

(1)

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

(2)

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

(3)調度周期內，機床Mk上加工工件的總時間約束為

(3)

(4)第i種工件第l個子批的第j道工序在機床k上加工，工序起始加工時間STiljk和工序結束加工時間ETiljk存在約束，如式(4)所示。同一子批的某道工序在設備k上的準備時間等于單個工件的準備時間，加工時間等于單個工件工序加工時間乘以子批量數(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)資源的柔性批量車間生產調度問題的目標函數(shù)如下：

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

(7)

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

(8)

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

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

(9)

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

(10)

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

(5)工件的總完工時間

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

(11)

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

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

2.1 批量分解規(guī)則

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

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

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

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

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

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

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

(12)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

OTk=OTk+ATvi+BSil×PTvi//更新設備Mk負荷

Delete viFrom WaitO

/}

(4)適應值函數(shù)

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

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

(13)

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

2.3.3 求解調度子問題的遺傳算法

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

(1)解碼方法

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

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

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

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

(2)考慮多選設備的鄰域結構設計

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

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

(3)考慮調度方案的鄰域結構設計

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

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

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

3 調度案例測試與分析

3.1 考慮批量的測試

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

結合本文提出的批量分解和加工路徑確定規(guī)則，調用嵌套式遺傳算法對標準10×10案例進行求解，其中批量數(shù)為10。文獻[22]研究指出，對于中等規(guī)模的調度問題，種群規(guī)模一般設置為20～50，迭代次數(shù)一般設置為200～500代，交叉率取值0.7～0.9，變異率取值0.01～0.2。本文利用遺傳算法進行批量劃分和路徑確定時，算法參數(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所示，工件分批后，每道工序對應的加工時間為文獻[21]的原始時間數(shù)據(jù)乘以該批次工件對應的工件批量數(shù)。優(yōu)化解對應的總完工時間makespan=62，比工件不分批時的最優(yōu)解完工時間70減少了11.4%。若將各工件進行平均分批，即每種工件劃分為2個子批，每個子批中的工件批量數(shù)為5，則可求得這種子批劃分下最優(yōu)解的總完工時間makespan=65，而調用本文嵌入式遺傳算法，通過批量劃分和路徑確定后，最優(yōu)解對應的總完工時間為makespan=62，驗證了本文算法的優(yōu)越性。

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

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

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

3.2 考慮設備資源和交貨期約束的柔性批量調度測試

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

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

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

續(xù)表2

續(xù)表2

4 結束語

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

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

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

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

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