兩階段混合算法求解集成工藝規(guī)劃與調(diào)度問(wèn)題

文笑雨 羅國(guó)富 李 浩 肖艷秋 喬?hào)|平

鄭州輕工業(yè)學(xué)院河南省機(jī)械裝備智能制造重點(diǎn)實(shí)驗(yàn)室，鄭州，450002

0 引言

工藝規(guī)劃和車(chē)間調(diào)度是制造系統(tǒng)中非常重要的子系統(tǒng)，對(duì)制造系統(tǒng)的產(chǎn)品加工能力、資源利用率以及生產(chǎn)效率有重要影響[1]。兩者雖然相互獨(dú)立，功能不同，但又相互制約。將工藝規(guī)劃和車(chē)間調(diào)度視為獨(dú)立的子系統(tǒng)單獨(dú)進(jìn)行研究，不利于提高制造系統(tǒng)的生產(chǎn)效率以及設(shè)備利用率。文獻(xiàn)[2]指出，為了匹配車(chē)間的實(shí)時(shí)狀態(tài)，必須對(duì)預(yù)先設(shè)定工藝路線的20%～30%進(jìn)行重新規(guī)劃。已有研究顯示，將工藝規(guī)劃和車(chē)間調(diào)度進(jìn)行集成研究能夠提高制造系統(tǒng)的效率[1]。

工藝規(guī)劃和車(chē)間調(diào)度本身均為NP-complete問(wèn)題，集成式工藝規(guī)劃與車(chē)間調(diào)度(integrated process planning and scheduling,IPPS)問(wèn)題更加復(fù)雜[3]。在制造企業(yè)中，工藝規(guī)劃和車(chē)間調(diào)度往往是兩個(gè)獨(dú)立的部門(mén)，將兩個(gè)部門(mén)完全進(jìn)行整合并不現(xiàn)實(shí)。考慮到這一實(shí)際問(wèn)題，工藝規(guī)劃與車(chē)間調(diào)度的集成方法主要關(guān)注如何增加工藝規(guī)劃與車(chē)間調(diào)度之間的信息交互,但是，工藝規(guī)劃與車(chē)間調(diào)度關(guān)注點(diǎn)并不相同。工藝規(guī)劃的主要任務(wù)是通過(guò)對(duì)工件加工特征、精度、材料等的分析，為工件選擇合適的加工方法和加工參數(shù)。車(chē)間調(diào)度則需要在時(shí)序上確定多個(gè)工件的不同工序在不同機(jī)器上的開(kāi)工時(shí)間。如果在工藝規(guī)劃階段僅僅考慮單個(gè)工件的工序順序以及加工資源，極容易在車(chē)間調(diào)度過(guò)程中產(chǎn)生資源沖突問(wèn)題，即工藝規(guī)劃的結(jié)果對(duì)車(chē)間調(diào)度產(chǎn)生制約。IPPS問(wèn)題存在著復(fù)雜的機(jī)器柔性、工序順序柔性和加工路徑柔性，使得問(wèn)題解空間非常龐大，求解非常困難。

基于上述IPPS問(wèn)題的復(fù)雜性和重要性，對(duì)IPPS問(wèn)題的研究已經(jīng)成為相關(guān)研究領(lǐng)域的難點(diǎn)和熱點(diǎn)。自1984年CHRYSSOLOURIS等[4]首次提出將工藝規(guī)劃與車(chē)間調(diào)度進(jìn)行集成優(yōu)化之后，涌現(xiàn)出了大量關(guān)于IPPS問(wèn)題的研究[5-6]。在這些研究中，基于元啟發(fā)式算法求解IPPS問(wèn)題是近年來(lái)的研究熱點(diǎn)，如遺傳算法(genetic algorithm,GA)[7-9]、蟻群算法(ant colony optimization，ACO)[10-14]、帝國(guó)競(jìng)爭(zhēng)算法(imperialist competitive algorithm,ICA)[15]、蜂群算法[3,16-17]等。由于IPPS問(wèn)題求解困難，越來(lái)越多的學(xué)者將不同的算法進(jìn)行優(yōu)勢(shì)互補(bǔ)，設(shè)計(jì)有效的混合算法[18-26]對(duì)IPPS問(wèn)題進(jìn)行求解。本文從工藝規(guī)劃與車(chē)間調(diào)度兩階段優(yōu)化目標(biāo)沖突的角度出發(fā)，結(jié)合不同元啟發(fā)式算法的優(yōu)點(diǎn)，設(shè)計(jì)了一種兩階段混合算法對(duì)IPPS問(wèn)題進(jìn)行求解，并采用IPPS問(wèn)題基準(zhǔn)測(cè)試集對(duì)提出的算法進(jìn)行驗(yàn)證。

1 IPPS問(wèn)題描述

本文研究的IPPS問(wèn)題可以被描述為：某加工任務(wù)共包含n個(gè)待加工工件，車(chē)間可供使用的機(jī)床共有m臺(tái)。每一個(gè)待加工工件具有多道加工特征，不同的加工特征之間存在一定的先后順序約束關(guān)系。每一道加工特征具有可選的加工工藝，不同的可選加工工藝包含的具體工序數(shù)目可能有所不同。每一道工序可以選擇在若干臺(tái)不同的加工機(jī)器上進(jìn)行加工。IPPS需要解決如下三個(gè)問(wèn)題：首先，確定每個(gè)工件的工序加工順序；然后，為每一道工序挑選合適的加工機(jī)器；最后，根據(jù)確定的工序加工順序以及工序加工機(jī)器，確定每一道工序的開(kāi)工時(shí)間和完工時(shí)間，從而使得整個(gè)系統(tǒng)的某項(xiàng)性能指標(biāo)最優(yōu)。本文中，評(píng)價(jià)整個(gè)系統(tǒng)的性能指標(biāo)為最小化工件最大完工時(shí)間(makespan)。

本文研究的IPPS問(wèn)題中，生產(chǎn)調(diào)度的方式為作業(yè)車(chē)間調(diào)度問(wèn)題(job shop scheduling problem,JSP)，并建立在如下假設(shè)條件下[3]：①在零時(shí)刻，所有的機(jī)器都可以被安排加工任務(wù);②加工工序所需要的準(zhǔn)備時(shí)間包含在每道工序的加工時(shí)間中;③不同工件具有相同的優(yōu)先級(jí)，每臺(tái)機(jī)器在同一時(shí)刻只能加工一個(gè)工件;④機(jī)器一旦開(kāi)始加工一道工序，在該道工序加工完成之前，操作不允許被打斷;⑤每個(gè)工件在同一時(shí)刻只能安排一道工序的加工任務(wù);⑥不同工件的工序之間不存在加工順序的約束關(guān)系;⑦暫不考慮工件在機(jī)器之間的傳輸時(shí)間。

表1 3個(gè)工件在5臺(tái)機(jī)器上加工的IPPS問(wèn)題

為了更具體地描述本文所研究的IPPS問(wèn)題，接下來(lái)針對(duì)一項(xiàng)具體的加工任務(wù)對(duì)該問(wèn)題進(jìn)行詳細(xì)描述。表1為3個(gè)工件在5臺(tái)機(jī)器上加工的IPPS問(wèn)題輸入信息表。如表1所示，工件1具有6個(gè)加工特征，其中加工特征1必須在其他5個(gè)加工特征之前進(jìn)行加工，加工特征4必須在加工特征6之前進(jìn)行加工。加工特征1和加工特征4分別具有兩種可選的加工工藝。加工特征1的第一種可選加工工藝只需要一道工序(O1)即可完成加工，第二種可選加工工藝則需要兩道工序(O2—O3)才可以完成加工。每一道工序具有可選加工機(jī)器，如O1具有3臺(tái)可選加工機(jī)器(M1,M2,M3)，決策者可根據(jù)不同的需求選擇其中一臺(tái)機(jī)器完成對(duì)該道工序的加工任務(wù)。從表1中可以明顯看出，每一個(gè)工件具有許多可選的工藝路線，在求解IPPS問(wèn)題時(shí)，首先需要確定每一個(gè)工件的工藝路線，然后依據(jù)確定的工藝路線，合理安排每道工序的開(kāi)工時(shí)間，從而使得最大完工時(shí)間最小化。

2 基于兩階段混合算法的IPPS問(wèn)題求解方法

2.1 算法總流程圖

針對(duì)IPPS問(wèn)題中存在的復(fù)雜機(jī)器柔性、工序順序柔性和加工路徑柔性，本文采取一種“分而治之，協(xié)同優(yōu)化”的思路，設(shè)計(jì)了基于兩階段混合算法的IPPS問(wèn)題求解方法：在工藝規(guī)劃階段，采用遺傳算法為每一個(gè)工件生成近優(yōu)的可選工藝路線集，動(dòng)態(tài)地為作業(yè)車(chē)間調(diào)度階段輸入不同的工藝路線；在作業(yè)車(chē)間調(diào)度階段，使用蜜蜂交配優(yōu)化(honey bees mating optimization,HBMO)算法優(yōu)化求解，獲得最優(yōu)調(diào)度方案。具體流程見(jiàn)圖1。

圖1 兩階段混合算法求解IPPS總流程Fig.1 Workflow of two-stage hybrid algorithm for IPPS

2.2 工藝規(guī)劃階段主要操作

本文中工藝規(guī)劃階段的目的并不是使用遺傳算法為每個(gè)工件求得一條最優(yōu)的工藝路線，而是為作業(yè)車(chē)間調(diào)度階段提供盡可能多的近優(yōu)工藝路線。采取的方法是，使用遺傳算法對(duì)每個(gè)工件的工藝路線種群進(jìn)行優(yōu)化，獲得每個(gè)工件的近優(yōu)工藝路線集，然后隨機(jī)從每個(gè)工件的近優(yōu)工藝路線集當(dāng)中挑選一條工藝路線輸入作業(yè)車(chē)間調(diào)度階段。以下詳述使用遺傳算法對(duì)工藝規(guī)劃階段進(jìn)行優(yōu)化的主要操作。

2.2.1編碼與解碼

遺傳算法種群中每一條染色體代表零件的一條具體的工藝路線，本文采用文獻(xiàn)[3]中的編碼方法對(duì)染色體進(jìn)行編碼操作。每條染色體包含3段長(zhǎng)度不同的序列。第一段為特征順序序列，第二段為可選工藝序列，這兩段序列的長(zhǎng)度均等于工件的總特征數(shù)。第三段為可選機(jī)器序列，該序列的長(zhǎng)度等于工件的總工序數(shù)。以表1中的工件1為例，一種可行的編碼方案見(jiàn)圖2。因?yàn)楣ぜ?一共包含6個(gè)加工特征，圖2中特征順序序列和可選工藝序列長(zhǎng)度均為6。特征順序序列代表的含義為該零件按照特征F1—F4—F6—F3—F2—F5的順序進(jìn)行加工?？蛇x工藝序列的第i個(gè)位置的數(shù)字k，代表了工件的特征Fi選擇第k種可選加工工藝進(jìn)行加工，如圖2中可選工藝序列中第一個(gè)位置為1，則代表特征1從它的可選工藝集{O1，O2—O3}中選擇第1種加工工藝，即O1進(jìn)行加工?？蛇x機(jī)器序列代表的第i個(gè)位置的數(shù)字k，代表了零件的工序Oi從可選加工機(jī)器集當(dāng)中選擇第k個(gè)加工機(jī)器，如圖2中可選機(jī)器序列第4個(gè)位置為3，則代表工序4從它的可選加工機(jī)器集{M2,M3,M4}中選擇了第三臺(tái)機(jī)器，即機(jī)器M4進(jìn)行加工。

圖2 工藝規(guī)劃階段染色體編碼方案Fig.2 Chromosome encoding scheme in process planning stage

該編碼方案在解碼時(shí)比較簡(jiǎn)單，首先，特征順序序列直接代表的就是特征的加工順序，只需要直接從可選工藝序列中依次確定相應(yīng)特征的加工工藝即可。圖2所示的編碼方案代表工件1工序的加工工序?yàn)镺1—O8—O10—O5—O4—O9。然后，依據(jù)可選機(jī)器序列，依次確定選中工序的加工機(jī)器，即圖2所示的編碼方案所確定工件1的工藝路線為O1(M2)—O8(M5)—O10(M4)—O5(M1)—O4(M4)—O9(M5)。

2.2.2種群初始化

遺傳算法種群中的每一條染色體代表工件的一條工藝路線。按照編碼操作，每條染色體包含三段序列，均采用隨機(jī)初始化的方法進(jìn)行初始化操作。對(duì)特征順序序列進(jìn)行初始化時(shí)，首先隨機(jī)生成零件加工特征的一種全排列序列，然后使用文獻(xiàn)[23]中的約束調(diào)整方法對(duì)特征順序序列進(jìn)行調(diào)整，將不可行序列轉(zhuǎn)換為可行序列。對(duì)可選工藝序列進(jìn)行初始化時(shí)，如果零件第i個(gè)特征的可選工藝有k種，則隨機(jī)生成1至k中的一個(gè)整數(shù)，存入可選工藝序列的第i個(gè)位置。對(duì)可選機(jī)器序列進(jìn)行初始化時(shí)，如果零件第i道工序的可選機(jī)器有k臺(tái)，則隨機(jī)生成1至k中的一個(gè)整數(shù)，存入可選機(jī)器序列的第i個(gè)位置。這種初始化方法能夠保證生成的可選工藝序列和可選機(jī)器序列均為可行的。

每條染色體按照上述方法進(jìn)行編碼操作之后，使用解碼操作對(duì)其進(jìn)行解碼，獲得具體該條染色體所對(duì)應(yīng)的工藝路線，根據(jù)確定的工藝路線，計(jì)算該工藝路線下零件的加工時(shí)間，將加工時(shí)間作為染色體進(jìn)化過(guò)程中的適應(yīng)度值。

2.2.3遺傳操作

遺傳操作主要包括選擇、交叉和變異操作。本文中采用的選擇操作為最好個(gè)體保留和輪盤(pán)賭的選擇操作。因?yàn)楣に囈?guī)劃的目的是為車(chē)間調(diào)度階段提供近優(yōu)的工藝路線，所以希望可以盡可能保留種群中比較好的個(gè)體。在進(jìn)化過(guò)程中，生成新種群時(shí)，直接保存父代種群中最好的前PcopyPPsize(Pcopy為復(fù)制概率，PPsize為工藝規(guī)劃階段種群規(guī)模)個(gè)個(gè)體到子代種群中。在生成新種群挑選進(jìn)行交叉的父代時(shí)，采用輪盤(pán)賭的選擇操作從種群中選擇父代個(gè)體，使得適應(yīng)度值較好的個(gè)體能夠以更大的概率參與生成新種群，從而保存種群中的優(yōu)良基因。本文中工藝規(guī)劃部分的編碼操作采用了三段式編碼操作，采用文獻(xiàn)[3]中的操作分別對(duì)三段染色體進(jìn)行交叉和變異操作。

2.3 作業(yè)車(chē)間調(diào)度階段主要操作

作業(yè)車(chē)間調(diào)度階段的目的是根據(jù)每個(gè)工件確定的工藝路線生成最終的可行調(diào)度方案，從而使得加工完成所有工件需要用的時(shí)間最短。本文在該階段采用能夠兼顧全局搜索和局部搜索的HBMO算法對(duì)作業(yè)車(chē)間調(diào)度階段進(jìn)行優(yōu)化求解，下面詳細(xì)描述算法的主要操作。

2.3.1編碼、解碼與初始化

本階段采用基于工序的編碼方法[3]對(duì)作業(yè)車(chē)間調(diào)度階段種群中的個(gè)體進(jìn)行編碼。以表1中的問(wèn)題為例，若在工藝規(guī)劃階段為車(chē)間調(diào)度階段輸入的工藝路線中，工件1包含6道工序，工件2包含5道工序，工件3包含4道工序，則一種可行的編碼串為[3 1 1 1 3 2 2 3 1 3 1 1 2 2 2]，編碼串的總長(zhǎng)度為所有工件包含工序的總數(shù)，即15，編碼串中1出現(xiàn)了6次，依次代表工件1的6道工序。采用文獻(xiàn)[23]中的貪婪解碼方法將編碼方案解碼為活動(dòng)調(diào)度類型，依據(jù)解碼獲得的甘特圖，計(jì)算出最大完工時(shí)間，將最大完工時(shí)間直接作為該編碼串所對(duì)應(yīng)的適應(yīng)度值。采用上述編碼、解碼和適應(yīng)度值計(jì)算的方法隨機(jī)生成初始種群。

2.3.2蜂王婚飛階段

HBMO算法的蜂王婚飛階段主要能夠保證算法的全局搜索能力。主要操作步驟如下[3]。

(1)從當(dāng)前種群中挑選適應(yīng)度值最好的個(gè)體作為蜂王，其他個(gè)體作為雄蜂。

(2)設(shè)定蜂王受精囊容量Ssize，蜂王受精囊中雄蜂基因型的個(gè)數(shù)Snum，幼蜂種群規(guī)模Bsize，蜂王速度和能量的衰減系數(shù)α(本文中設(shè)定為0.9)，蜂王婚飛時(shí)的能量閾值T，初始化蜂王的速度值S(t)和能量值E(t)，令t=0,Snum=0。

(4)使用衰減系數(shù)對(duì)蜂王的速度和能量進(jìn)行更新，令t←t+1。

(5)如果蜂王的能量E(t)>T且Snum

(6)從蜂王的受精囊中隨機(jī)挑選一個(gè)雄蜂的基因型，對(duì)蜂王和選擇的基因型使用文獻(xiàn)[27]中設(shè)計(jì)的交叉操作生成幼蜂，直到生成Bsize個(gè)幼蜂為止。

2.3.3工蜂培育幼蜂階段

HBMO算法中的工蜂培育幼蜂階段保證了算法的局部搜索能力。本文參考文獻(xiàn)[28]中對(duì)JSP問(wèn)題不同鄰域結(jié)構(gòu)尋優(yōu)性能的評(píng)估，挑選了以下3種效果比較好的鄰域結(jié)構(gòu)作為工蜂培育幼蜂的局部搜索策略。

(1)N1為隨機(jī)插入鄰域。隨機(jī)挑選幼蜂的2個(gè)不同位置的不同基因型，將其進(jìn)行互換。

(2)N2為隨機(jī)全鄰域。隨機(jī)選擇幼蜂的3個(gè)不同位置的不同基因型，對(duì)其進(jìn)行全排列生成5個(gè)新的個(gè)體，挑選其中最好的1個(gè)個(gè)體，取代原來(lái)的幼蜂。

(3)N3為N5鄰域。對(duì)于關(guān)鍵路徑上的關(guān)鍵塊，首塊只交換最后2個(gè)加工工序，相應(yīng)的尾塊只交換前2個(gè)加工工序，所有的中間塊分別交換頭2個(gè)加工工序和最后2個(gè)加工工序。

對(duì)于蜂王婚飛后生成的每個(gè)幼蜂，隨機(jī)選擇上述3種鄰域結(jié)構(gòu)中的1種對(duì)其進(jìn)行改進(jìn)，如果新生成的幼蜂適應(yīng)度值更好，則取代以前的幼蜂，直到達(dá)到工蜂培育幼蜂的最大迭代次數(shù)。

2.4 兩階段混合算法求解IPPS問(wèn)題的具體步驟

基于上述算法關(guān)鍵操作的描述，本文提出的兩階段混合算法求解IPPS問(wèn)題的具體步驟如下。

(1)算法參數(shù)設(shè)定。工藝規(guī)劃部分參數(shù)如下：算法最大迭代次數(shù)PPgen，種群規(guī)模PPsize，交叉概率Pcros，變異概率Pmuta，復(fù)制概率Pcopy。作業(yè)車(chē)間調(diào)度參數(shù)如下：蜂王的最大婚飛次數(shù)NMF，蜂王速度和能量的衰減系數(shù)α，蜂王婚飛時(shí)的能量閾值T，蜂群數(shù)目JPsize，蜂王受精囊的容量Ssize，幼蜂數(shù)目Bsize，工蜂數(shù)目Wsize，工蜂培育幼蜂迭代次數(shù)Inum。另外還需要設(shè)定兩階段混合算法整體最大迭代次數(shù)GIPPS。

(2)根據(jù)待求解IPPS問(wèn)題的輸入信息(表1所示即為IPPS問(wèn)題的輸入信息表)，采用2.2.2節(jié)描述的方法隨機(jī)初始化n個(gè)工件的柔性工藝路線種群，作為每個(gè)工件的當(dāng)前可選工藝路線集。

(3)設(shè)置算法終止準(zhǔn)則為達(dá)到算法最大迭代次數(shù)PPgen，使用2.2.3節(jié)描述的遺傳算法的操作(復(fù)制、選擇、交叉、變異)，對(duì)n個(gè)工件的柔性工藝路線種群進(jìn)行優(yōu)化，更新每個(gè)工件的可選工藝路線集。

(4)根據(jù)每個(gè)工件當(dāng)前的可選工藝路線集，隨機(jī)從中選擇一條可選工藝路線輸入到作業(yè)車(chē)間調(diào)度階段。依據(jù)每個(gè)工件確定的工藝路線，采用2.3.1節(jié)的操作，隨機(jī)生成作業(yè)車(chē)間調(diào)度階段的初始化種群。挑選種群中最好的個(gè)體作為蜂王，其他個(gè)體作為雄蜂。

(5)判斷蜂王是否達(dá)到最大婚飛次數(shù)，如果蜂王已經(jīng)達(dá)到了最大婚飛次數(shù)，則跳轉(zhuǎn)到步驟(8)。如果沒(méi)有達(dá)到，則采用2.3.2節(jié)的操作完成蜂王婚飛階段，生成幼蜂種群。

(6)采用2.3.3節(jié)的操作完成工蜂對(duì)幼蜂的培育，使用新生成的幼蜂種群對(duì)蜂王和雄蜂進(jìn)行更新。將幼蜂種群中的個(gè)體與蜂王進(jìn)行對(duì)比，如果幼蜂的適應(yīng)度值優(yōu)于蜂王，則取代蜂王。如果幼蜂的適應(yīng)度值優(yōu)于已有雄蜂種群中的個(gè)體，則取代相應(yīng)的雄蜂。

(7)更新蜂王的婚飛次數(shù)，跳轉(zhuǎn)到步驟(5)。

(8)保存進(jìn)化過(guò)程中生成的最優(yōu)解(即蜂王對(duì)應(yīng)的工藝路線方案及調(diào)度方案)。更新IPPS算法迭代次數(shù)，如果達(dá)到了最大迭代次數(shù)，則算法終止。如果沒(méi)有達(dá)到最大迭代次數(shù)，則跳轉(zhuǎn)到步驟(4)。

3 計(jì)算結(jié)果與分析

3.1 基準(zhǔn)測(cè)試集計(jì)算結(jié)果

表2 兩階段混合算法求解IPPS主要參數(shù)

由于單個(gè)工件工藝路線的最優(yōu)與最終IPPS希望達(dá)到的最優(yōu)并不是一種線性的關(guān)系，而是一種復(fù)雜的非線性關(guān)系，因此，第一階段的目的并不是提供每個(gè)工件的最優(yōu)工藝路線，而是希望找到每個(gè)工件較優(yōu)的工藝路線輸入到第二階段的車(chē)間調(diào)度環(huán)節(jié)。本文算法設(shè)計(jì)的初衷是希望保持一種探索兩階段優(yōu)化非線性關(guān)系的趨勢(shì)，因?yàn)椴⒎敲總€(gè)工件最優(yōu)的工藝路線都能夠保證IPPS找到最優(yōu)解。所以，本文中工藝規(guī)劃階段的算法對(duì)每個(gè)工件使用一樣的參數(shù)，且迭代次數(shù)較少，目的是為第二階段提供多樣化的工藝路線，以此保證種群的多樣性，實(shí)現(xiàn)找尋IPPS全局最優(yōu)解的目的。

測(cè)試集共包含15臺(tái)加工機(jī)器，18個(gè)不同的工件，根據(jù)工件的不同組合構(gòu)成了24個(gè)不同規(guī)模的測(cè)試問(wèn)題，具體數(shù)據(jù)參考文獻(xiàn)[23]的附錄部分。該測(cè)試集中每個(gè)工件均采用網(wǎng)絡(luò)圖進(jìn)行表示，包含復(fù)雜的機(jī)器柔性、工藝順序柔性和加工路徑柔性，IPPS問(wèn)題的計(jì)算結(jié)果應(yīng)該包含有每個(gè)工件的工藝路線及具體的調(diào)度方案。THA的計(jì)算結(jié)果(包含運(yùn)算時(shí)間)與已有文獻(xiàn)中其他算法的結(jié)果對(duì)比見(jiàn)表3。使用本文算法獲得問(wèn)題24的最優(yōu)解為511，該解所對(duì)應(yīng)的每個(gè)工件具體的工藝路線見(jiàn)表4，該解所對(duì)應(yīng)的甘特圖見(jiàn)圖3。甘特圖方框中的數(shù)字(i,j)代表著第i個(gè)工件在確定的工藝路線中的第j道工序。如(18,1)代表的是工件18工藝路線中的第1道工序，通過(guò)查詢表4可以獲得該工序具體的工序號(hào)O7。

表3 THA計(jì)算結(jié)果及與其他算法的對(duì)比

表4 問(wèn)題24最優(yōu)解對(duì)應(yīng)的18個(gè)工件的工藝路線

(續(xù)表)

工件工序數(shù)工藝路線413O1(M2)—O2(M12)—O3(M9)—O4(M5)—O13(M6)—O14(M10)—O7(M10)—O8(M6)—O9(M3)—O16(M7)—O10(M9)—O11(M7)—O12(M15)510O14(M8)—O1(M4)—O15(M5)—O10(M4)—O11(M14)—O12(M6)—O13(M14)—O16(M13)—O17(M3)—O18(M7)616O5(M6)—O1(M4)—O15(M14)—O17(M12)—O16(M5)—O2(M6)—O18(M10)—O6(M10)—O7(M9)—O10(M8)—O9(M11)—O14(M7)—O3(M5)—O19(M12)—O4(M5)—O20(M9)712O1(M7)—O7(M3)—O8(M5)—O9(M6)—O10(M12)—O11(M2)—O19(M2)—O20(M6)—O12(M1)—O13(M9)—O18(M13)—O21(M10)812O17(M10)—O1(M4)—O18(M7)—O20(M3)—O2(M15)—O3(M12)—O4(M4)—O5(M2)—O7(M3)—O8(M6)—O10(M5)—O11(M1)916O1(M12)—O2(M7)—O13(M2)—O16(M4)—O18(M2)—O19(M2)—O7(M13)—O14(M15)—O4(M3)—O5(M6)—O10(M14)—O6(M6)—O11(M15)—O12(M6)—O20(M4)—O15(M5)109O1(M4)—O3(M1)—O4(M13)—O5(M7)—O6(M5)—O9(M9)—O10(M3)—O2(M15)—O11(M14)119O1(M6)—O2(M14)—O3(M13)—O6(M10)—O8(M2)—O7(M1)—O4(M5)—O5(M6)—O9(M9)1216O8(M3)—O1(M11)—O13(M3)—O5(M15)—O2(M15)—O3(M5)—O6(M2)—O4(M12)—O14(M1)—O15(M9)—O9(M6)—O10(M4)—O11(M7)—O12(M10)—O18(M13)—O7(M11)138O17(M8)—O1(M11)—O12(M6)—O13(M10)—O14(M6)—O15(M4)—O16(M14)—O18(M2)1410O9(M12)—O12(M14)—O1(M9)—O10(M15)—O4(M3)—O5(M4)—O6(M4)—O8(M3)—O11(M4)—O13(M10)1513O7(M9)—O12(M7)—O1(M11)—O8(M8)—O9(M2)—O13(M1)—O3(M6)—O4(M7)—O5(M2)—O14(M9)—O6(M5)—O15(M1)—O11(M8)1613O18(M11)—O1(M11)—O20(M14)—O21(M14)—O6(M6)—O7(M5)—O8(M5)—O9(M10)—O10(M11)—O11(M8)—O15(M4)—O16(M9)—O17(M13)1714O18(M2)—O1(M11)—O13(M6)—O19(M1)—O20(M9)—O14(M3)—O2(M10)—O3(M4)—O4(M12)—O5(M7)—O7(M11)—O12(M8)—O22(M11)—O17(M2)1812O7(M3)—O8(M13)—O1(M3)—O4(M1)—O5(M9)—O12(M5)—O13(M9)—O10(M11)—O6(M5)—O16(M4)—O17(M10)—O11(M10)

圖3 問(wèn)題24最優(yōu)解對(duì)應(yīng)的甘特圖Fig.3 Corresponding Gant chart for optimal solution of problem 24

3.2 結(jié)果分析

由表3可以看出，與已有文獻(xiàn)中的6種不同的算法比較，本文提出的算法在19個(gè)問(wèn)題上取得了更好(或相同)的結(jié)果。當(dāng)問(wèn)題規(guī)模變大時(shí)(問(wèn)題22、23和24)，使用本文提出的算法獲得的計(jì)算結(jié)果明顯優(yōu)于其他6個(gè)算法。這是因?yàn)楸疚奶岢龅乃惴ú扇×恕胺侄沃钡乃枷敕謩e處理IPPS中的不同柔性問(wèn)題，當(dāng)工件數(shù)變多時(shí)，這種設(shè)計(jì)思路能夠有效地提高尋優(yōu)效率。有4個(gè)問(wèn)題(問(wèn)題13、14、18、21)的計(jì)算結(jié)果劣于已有文獻(xiàn)中GATS算法的計(jì)算結(jié)果，優(yōu)于其他對(duì)比算法。問(wèn)題8的計(jì)算結(jié)果相對(duì)較差。這是因?yàn)?，工藝?guī)劃階段為車(chē)間調(diào)度動(dòng)態(tài)輸入工藝路線時(shí)存在一定的隨機(jī)性，算法在運(yùn)行時(shí)可能會(huì)受到已定工藝路線的限制，在下一步的研究工作中，可以考慮采用一些啟發(fā)式規(guī)則，對(duì)工藝規(guī)劃階段為車(chē)間調(diào)度階段輸入工藝路線的過(guò)程進(jìn)行一定的指導(dǎo)。

總體來(lái)說(shuō)，通過(guò)基準(zhǔn)測(cè)試集的測(cè)試，證明了本文提出的THA算法在求解IPPS問(wèn)題時(shí)的有效性。本文提出的IPPS優(yōu)化方法在工藝規(guī)劃部分采用遺傳算法為每個(gè)零件生成近優(yōu)的可選工藝路線庫(kù)，在這一階段對(duì)IPPS問(wèn)題存在的3種柔性進(jìn)行了一定程度的預(yù)處理，在車(chē)間調(diào)度階段采用HBMO算法進(jìn)行優(yōu)化，能夠保證車(chē)間調(diào)度階段的全局搜索和局部搜索。

究其本質(zhì)，工藝規(guī)劃的優(yōu)化目標(biāo)和車(chē)間調(diào)度優(yōu)化目標(biāo)之間存在非常復(fù)雜的非線性關(guān)系。在一定程度上，單個(gè)零件的加工時(shí)間越短，整體加工任務(wù)的完工時(shí)間相對(duì)較少。但是，如果大量零件被集中安排在瓶頸機(jī)器上進(jìn)行加工，則必然會(huì)導(dǎo)致整體加工任務(wù)的延遲完工。本文提出的方法能夠在一定程度上解決工藝規(guī)劃和車(chē)間調(diào)度優(yōu)化目標(biāo)之間的矛盾沖突，從而實(shí)現(xiàn)了IPPS問(wèn)題的整體優(yōu)化求解。

4 結(jié)語(yǔ)

本文針對(duì)制造系統(tǒng)運(yùn)行優(yōu)化中亟需解決的IPPS問(wèn)題進(jìn)行了研究。針對(duì)IPPS問(wèn)題中存在的機(jī)器柔性、工序順序柔性和加工路徑柔性，提出了一種兩階段混合算法進(jìn)行求解。這一算法實(shí)現(xiàn)了IPPS問(wèn)題的整體優(yōu)化求解。

在今后的研究中，可以從問(wèn)題建模和算法設(shè)計(jì)兩個(gè)方面對(duì)IPPS問(wèn)題進(jìn)行更深入的研究。在問(wèn)題建模方面，可以考慮如何處理實(shí)際生產(chǎn)環(huán)境中的動(dòng)態(tài)不確定事件，研究動(dòng)態(tài)事件的描述方法，設(shè)計(jì)動(dòng)態(tài)不確定性評(píng)估指標(biāo)，構(gòu)建有效的動(dòng)態(tài)不確定環(huán)境下IPPS問(wèn)題建模方法；在算法設(shè)計(jì)方面，探討更加科學(xué)的工藝規(guī)劃和車(chē)間調(diào)度兩階段信息交互方式，進(jìn)一步提高集成效率，使得研究成果能夠更好地指導(dǎo)實(shí)際生產(chǎn)。另外，還可嘗試從綠色制造角度開(kāi)展綠色I(xiàn)PPS問(wèn)題的研究。