宋栓軍，楊佩莉，石雯麗

(西安工程大學(xué) 機(jī)電工程學(xué)院，西安 710048)

(*通信作者電子郵箱447090664@qq.com)

基于人工蜂群算法的柔性工藝與車間調(diào)度集成優(yōu)化

宋栓軍，楊佩莉*，石雯麗

(西安工程大學(xué) 機(jī)電工程學(xué)院，西安 710048)

(*通信作者電子郵箱447090664@qq.com)

為實(shí)現(xiàn)柔性工藝與車間調(diào)度集成優(yōu)化，在考慮工件特征的加工工藝、次序及加工機(jī)器的柔性基礎(chǔ)上，以最小化最大完工時(shí)間為優(yōu)化目標(biāo)，提出一種基于交叉變異的人工蜂群算法。該算法針對柔性工藝與車間調(diào)度集成問題的離散性特征，對工藝路線進(jìn)行序列編碼，工件調(diào)度采用基于工序的編碼方式。通過工藝種群與調(diào)度種群的交叉變異操作，分別使采蜜蜂及觀察蜂進(jìn)行局部尋優(yōu)，偵查蜂進(jìn)行全局尋優(yōu)，以此提高算法性能。在此基礎(chǔ)上用兩部分測試實(shí)例分別驗(yàn)證了集成研究的必要性及改進(jìn)算法的有效性。

柔性工藝規(guī)劃；車間調(diào)度；人工蜂群算法

0 引言

工藝規(guī)劃與車間調(diào)度集成(Integrated Process Planning and Scheduling，IPPS)是制造系統(tǒng)中急需解決的關(guān)鍵問題之一。在傳統(tǒng)的企業(yè)生產(chǎn)過程中，工藝規(guī)劃和車間調(diào)度往往被當(dāng)作獨(dú)立的系統(tǒng)進(jìn)行研究，導(dǎo)致了工藝與調(diào)度的脫節(jié)[1]。如果將工藝規(guī)劃和車間調(diào)度系統(tǒng)進(jìn)行集成，則可避免制造資源的浪費(fèi)，優(yōu)化生產(chǎn)節(jié)拍，提高制造系統(tǒng)的工作效率[2-3]。

Chryssolouris等[4]首先提出了工藝規(guī)劃與車間調(diào)度集成的構(gòu)想；之后Beckendorff等[5]在二者集成時(shí)考慮了工藝路線的柔性問題，首次在IPPS問題中考慮到工藝的柔性特點(diǎn)。上述研究使學(xué)者們開始關(guān)注工藝與調(diào)度集成問題的研究。劉倩雯[6]利用人工蜂群算法(Artificial Bee Colony， ABC)求解作業(yè)車間調(diào)度問題，通過仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性；瞿璨[7]將人工蜂群與模擬退火算法相結(jié)合求解面向綠色制造的工藝路線優(yōu)化，通過算例測試獲得了高效穩(wěn)定的解。這兩個(gè)研究都是將工藝與調(diào)度系統(tǒng)進(jìn)行獨(dú)立研究。呂盛坪等[8-9]對工藝規(guī)劃與車間調(diào)度集成現(xiàn)狀和趨勢以及集成模型作了分析，為IPPS問題的后續(xù)研究奠定基礎(chǔ)；崔曉康等[10]提出三階段工藝與調(diào)度的集成方法，并通過實(shí)例驗(yàn)證了方法的有效性；王進(jìn)峰等[11]對蟻群算法中信息素?fù)]發(fā)速度以及螞蟻轉(zhuǎn)移概率進(jìn)行改進(jìn)，將其應(yīng)用于IPPS優(yōu)化中，最后通過仿真實(shí)例表明了算法的有效性。這四個(gè)研究都是針對單目標(biāo)IPPS問題，并且沒有考慮工藝的柔性特征。Liu等[12]提出一種多目標(biāo)微型人工蜂群算法，對有約束條件的多目標(biāo)彈性作業(yè)車間調(diào)度問題求解，優(yōu)化目標(biāo)是盡量減少機(jī)器的工作量以及生產(chǎn)周期；文笑雨[13]采用蜜蜂繁殖優(yōu)化算法，分別對多目標(biāo)及多目標(biāo)不確定性IPPS問題進(jìn)行研究，之后研究了多目標(biāo)IPPS決策方法，最后通過實(shí)例驗(yàn)證算法的有效性。這兩篇文章都是針對多目標(biāo)IPPS問題進(jìn)行研究。從上述研究看，雖然針對IPPS的研究較多，但考慮到工藝柔性的較少；人工蜂群算法本身具備全局收斂優(yōu)勢[14]，通過三種蜂的轉(zhuǎn)換，借助啟發(fā)式搜索策略，具有很好的局部搜索及全局尋優(yōu)的能力，因此本文在研究以上方法的基礎(chǔ)上，考慮到工件的柔性特征，提出了一種基于交叉變異的人工蜂群算法，對柔性工藝與車間調(diào)度集成(Integrated Flexible Process Planning and Scheduling，IFPPS)問題進(jìn)行優(yōu)化求解，并通過工藝的序列編碼及基于工序的調(diào)度編碼使算法能夠適應(yīng)IFPPS問題的離散性特征，提出工藝種群與調(diào)度種群的交叉變異操作，不僅使產(chǎn)生的新解能夠滿足工序的順序約束，還能夠通過此算法最終獲得更優(yōu)的加工路線和調(diào)度方案。

1 IFPPS優(yōu)化數(shù)學(xué)模型

本文以單目標(biāo)IFPPS問題為例，以加工任務(wù)的最大完工時(shí)間(makespan)最小為目標(biāo)進(jìn)行優(yōu)化研究，車間調(diào)度問題為作業(yè)車間調(diào)度。在建立優(yōu)化數(shù)學(xué)模型前作如下假設(shè)[15-16]：

1)初始時(shí)刻，制造車間的所有機(jī)器均可正常使用；

2)在進(jìn)行排產(chǎn)優(yōu)化時(shí)，不同工件相互之間沒有優(yōu)先級，不同工件的加工工序之間也沒有優(yōu)先級，同一工件的各個(gè)工序之間存在優(yōu)先級；

3)在同一時(shí)間，每臺機(jī)器僅可加工一道工序；

4)所有工序的加工時(shí)間是指其實(shí)際加工與其準(zhǔn)備加工時(shí)間之和。

基于以上假設(shè)，本文研究的IFPPS數(shù)學(xué)模型如下所示，其中：A表示一個(gè)非常大的正數(shù)；n表示需要加工的工件總數(shù)；m表示機(jī)器數(shù)；gi表示工件i可選工藝路線數(shù)；pil表示工件i的第l條工藝路線中的工序數(shù)；oijl表示工件i在第l條工藝路線下的第j道工序；k表示工序oijl的可選加工機(jī)器；bijlk表示工序oijl在機(jī)器k上的開工時(shí)間；tijlk表示工序oijl在機(jī)器k上的加工時(shí)間；cijlk表示工序oijl在機(jī)器k上的完工時(shí)間；ci(j-1)lq表示工序oijl的上一道加工工序oi(j-1)l在其加工機(jī)器q上的完工時(shí)間；cxylk表示機(jī)器k上排在工序oijl緊前加工的工序oxyl的完工時(shí)間；zi(j-1，j)l(q，k)表示工序oi(j-1)l的加工機(jī)器q轉(zhuǎn)向工序oijl的加工機(jī)器k的機(jī)器轉(zhuǎn)換時(shí)間；ci表示工件i的完工時(shí)間；vijlk表示工序oijl在機(jī)器k上的加工成本；

Yijlpqsk=

目標(biāo)函數(shù)如式(1)所示：

f1=min{makespan=max(ci)}

(1)

約束條件如式(2)～(10)所示：

1)工件i第l條工藝路線的首道加工工序的最早完工時(shí)間大于或等于其加工時(shí)間：

(ci1lk×Zi1lk×Xil)+A(1-Xil)≥(ti1lk×Zi1lk×Xil);

?i∈[1,n], ?l∈[1,gi], ?k∈[1,m]

(2)

2)工件i第l條工藝路線的末道加工工序的最早完工時(shí)間小于或等于工件i的最大完工時(shí)間：

(cipillk×Zipillk×Xil)-A(1-Xil)≤makespan;

?i∈[1,n], ?l∈[1,gi], ?k∈[1,m]

(3)

3)一個(gè)工件同一時(shí)刻僅可有一道工序被加工：

(cijlk×Zijlk×Xil)-(ci(j-1)lk1×Zi(j-1)lk1×Xil)+

A(1-Xil)≥(tijlk×Zijlk×Xil); ?i∈[1,n],

?j∈[1,pil], ?l∈[1,gi], ?k,k1∈[1,m]

(4)

4)每臺機(jī)器同一時(shí)刻僅可加工一道工序：

(5)

5)工件i僅可選取一條工藝路線輸入到調(diào)度系統(tǒng)：

(6)

6)一道工序僅可選取一臺加工機(jī)器：

(7)

7)所有工序的開工時(shí)間大于或等于0：

bijlk×Zijlk×Xil≥0; ?i∈[1,n], ?j∈[1,pil],

?l∈[1,gi], ?k∈[1,m]

(8)

8)工序oijl在機(jī)器k上的完工時(shí)間等于其開工時(shí)間與加工時(shí)間之和：

cijlk×Zijlk×Xil=(bijlk+tijlk×Zijlk×Xil; ?i∈[1,n],

?j∈[1,pil], ?l∈[1,gi], ?k∈[1,m]

(9)

9)工序oijl在機(jī)器k上的開工時(shí)間等于工序oi(j-1)l在其加工機(jī)器q上的完工時(shí)間與工序oi(j-1)l的加工機(jī)器q轉(zhuǎn)向工序oijl的加工機(jī)器k的機(jī)器轉(zhuǎn)換時(shí)間之和以及之前最后一個(gè)在加工機(jī)器k上進(jìn)行加工的工序完工時(shí)間中較大的數(shù)：

bijlk=max(oi(j-1)lq+zi(j-1, j),l(q,k),cxylk); ?i∈[1,n],

?j∈[2,pil], ?l∈[1,gi], ?k,q∈[1,m]

(10)

2 IFPPS優(yōu)化算法設(shè)計(jì)

2.1 柔性工藝調(diào)度的編碼及解碼

1)柔性工藝規(guī)劃編碼及解碼。

根據(jù)工藝的柔性特征，本文創(chuàng)新性地提出一種序列編碼方式對工藝規(guī)劃部分的各個(gè)序列進(jìn)行編碼，表1為工件1的加工工藝信息。對工件1加工工藝信息進(jìn)行序列編碼，編碼結(jié)果如圖1所示。

表1 工件1加工工藝信息表

圖1 工件1加工工藝信息序列編碼方案

特征序列中的第n個(gè)數(shù)字m表示特征m的加工順序是n；工序序列中的第a個(gè)數(shù)字b表示工件第a個(gè)特征選擇第b種可選工藝加工；機(jī)器序列中的第i個(gè)數(shù)字j表示第i個(gè)工藝用j號機(jī)器進(jìn)行加工。用序列編碼方式很容易實(shí)現(xiàn)解碼，首先根據(jù)特征序列，可以獲得工件1各個(gè)特征的加工順序?yàn)镕4—F2—F1—F6—F3—F5；然后根據(jù)工序序列獲得各特征所選的加工工藝，再按照特征順序進(jìn)行排列，可以得到工件1具體的加工工序序列為O5—O2—O1—O7—O4—O6；最后根據(jù)機(jī)器序列，結(jié)合加工工藝得到各個(gè)工藝所選擇的加工機(jī)器，從而確定出該工件的一條可行工藝路線O5(M3)—O2(M4)—O1(M1)—O7(M1)—O4(M1)—O6(M4)。

2)車間調(diào)度編碼及解碼。

在車間調(diào)度編碼的相關(guān)研究中，用得最多的是基于工序的編碼方法，本文也利用此方式對個(gè)體進(jìn)行編碼[17]。設(shè)一個(gè)企業(yè)制造車間中的待加工工件數(shù)為4，在初始工藝路線中按照適應(yīng)度函數(shù)值挑選出各工件較優(yōu)的路線后，就可以知道要加工的工序總數(shù)。假設(shè)工件1共包含6道工序，工件2包含5道工序，工件3包含3道工序，工件4包含5道工序， 那么[1 1 2 3 4 4 2 4 1 1 2 4 2 1 1 4 2 3 3]就為一種可行的調(diào)度編碼方案。在此方案中，工件序號出現(xiàn)的次數(shù)與其所包含的工序數(shù)相同，例如工件1包含6道工序，那么1就在調(diào)度編碼方案中一共出現(xiàn)6次。此外方案中第6個(gè)位置上的4是從左到右數(shù)數(shù)字4出現(xiàn)的第2次，所以第6個(gè)位置代表了工件4的工藝路線中第2道要加工的工序。

由于本文選用的優(yōu)化目標(biāo)為最小化最大完工時(shí)間，屬于正規(guī)調(diào)度指標(biāo)，并且基于工序的編碼方式產(chǎn)生的調(diào)度方案均為可行的調(diào)度方案，因此選擇使用文獻(xiàn)[18]中的貪婪解碼方法將編碼方案解碼為活動調(diào)度類型。貪婪解碼方法的具體步驟可由文獻(xiàn)[18]獲得，此處不再贅述。

2.2 基于交叉變異的人工蜂群算法

使用人工蜂群算法求解IFPPS優(yōu)化問題時(shí)，每個(gè)蜜源代表一個(gè)可行的調(diào)度方案，每個(gè)蜜源的參數(shù)從開始到結(jié)束代表某個(gè)任務(wù)中各工序可能的工作順序，因此可由改變蜜源參數(shù)來改變各工序的加工順序，并計(jì)算其完工時(shí)間，尋找最優(yōu)方案[14]。為了保證種群的多樣性，本文對基本人工蜂群算法進(jìn)行改進(jìn)，提出了一種基于交叉變異的人工蜂群算法，并設(shè)計(jì)了算法求解的主要內(nèi)容。

1)蜂群初始化。

由于工藝及工件順序的表示需要是一個(gè)大于或等于1的整數(shù)，而基本人工蜂群算法中，種群初始化方法是產(chǎn)生連續(xù)的隨機(jī)數(shù)，會出現(xiàn)非整數(shù)的情況，因此本文對人工蜂群算法的初始化方式進(jìn)行了改進(jìn)。通過Matlab程序直接產(chǎn)生符合要求的可行性隨機(jī)解，在工藝規(guī)劃階段，由于工序有次序約束，因此隨機(jī)生成的特征序列可能不符合要求，采用文獻(xiàn)[18]中的約束調(diào)整方法對特征序列進(jìn)行調(diào)整，使生成的各工件的初始工藝路線可行。由于基于工序的編碼方式不會生成不可行解，因此本文對車間調(diào)度部分的初始化蜂群進(jìn)行隨機(jī)生成，然后將編碼方案解碼后，計(jì)算蜂群中每個(gè)蜜蜂所代表的IFPPS方案的完工時(shí)間。

2)工藝種群交叉變異操作。

為了使工藝規(guī)劃系統(tǒng)可以源源不斷地為調(diào)度系統(tǒng)輸入各個(gè)工件不同的工藝路線方案，在進(jìn)行柔性工藝規(guī)劃與車間調(diào)度集成優(yōu)化時(shí)，集成優(yōu)化總流程每迭代一次，就需要對工藝種群更新一次。針對工藝的序列編碼方式，本文提出工藝種群交叉變異操作對其進(jìn)行種群更新，保證種群的多樣性。

在工藝種群交叉變異操作中，使采蜜蜂和觀察蜂利用變異操作進(jìn)行局部搜索。具體步驟如下：

步驟1 將特征序列中兩個(gè)隨機(jī)位置的數(shù)值進(jìn)行交換，產(chǎn)生新的特征序列，并通過約束調(diào)整方法對其進(jìn)行調(diào)整，使其符合特征之間的次序約束條件；

步驟2 將工藝序列中一個(gè)隨機(jī)位置所選擇的加工工藝轉(zhuǎn)變成另一種可選加工工藝；

步驟3 將機(jī)器序列中一個(gè)隨機(jī)位置所選擇的加工機(jī)器轉(zhuǎn)變成另一種可選加工機(jī)器。

在工藝種群交叉變異操作中，使偵查蜂利用交叉操作進(jìn)行全局搜索。當(dāng)偵查蜂進(jìn)行全局搜索隨機(jī)產(chǎn)生新蜜源時(shí)，由于算法初始化已經(jīng)產(chǎn)生了符合工件特征順序約束的序列，優(yōu)化過程就是適當(dāng)調(diào)整這個(gè)序列中參數(shù)的順序，以得到一個(gè)能夠使某個(gè)目標(biāo)值達(dá)到最優(yōu)的順序，而不需要重新生成任何參數(shù)或信息，因此采用兩點(diǎn)交叉操作來對其進(jìn)行調(diào)整，能夠使產(chǎn)生的新序列滿足工件的特征次序約束。在偵查蜂進(jìn)行交叉操作時(shí)，分別對工件的三個(gè)序列進(jìn)行兩點(diǎn)交叉操作，產(chǎn)生新的可行工藝路線。在文獻(xiàn)[2]的基礎(chǔ)上，對其特征序列交叉操作進(jìn)行改進(jìn)，將原始的復(fù)制交叉點(diǎn)中斷的參數(shù)信息到新的特征序列相應(yīng)位置改為復(fù)制交叉點(diǎn)兩端的參數(shù)信息到新的特征序列的相應(yīng)位置，此方式可以確保生成的新的可行解滿足工序的次序約束條件，具體步驟如下：

步驟1 隨機(jī)挑選兩個(gè)蜜源(蜜源1、蜜源2)，對其三個(gè)序列分別進(jìn)行交叉操作。

步驟2 在蜜源的序列中隨機(jī)選擇兩個(gè)交叉點(diǎn)，特征序列用步驟3交叉操作，工藝序列和機(jī)器序列用步驟4進(jìn)行交叉操作。

步驟3 將特征序列1交叉點(diǎn)兩端參數(shù)信息復(fù)制給新特征序列的相應(yīng)位置，刪掉特征序列2中新特征序列中已有的特征數(shù)值，將特征序列2中剩余的數(shù)值按順序依次填入到新特征序列的空位置中，這樣就生成了新的特征序列。

步驟4 將工藝序列1交叉點(diǎn)中斷參數(shù)信息復(fù)制到新工藝序列的相應(yīng)位置，將工藝序列2的交叉點(diǎn)兩端的參數(shù)信息按順序填入新工藝序列的空位置中，這樣就生成了新的工藝序列，機(jī)器序列同工藝序列。

3)調(diào)度種群交叉變異操作。

在調(diào)度系統(tǒng)的優(yōu)化流程迭代中，需要不斷尋找新的調(diào)度方案，對調(diào)度種群進(jìn)行更新。針對基于工序的調(diào)度編碼方式，本文提出一種調(diào)度種群交叉變異操作進(jìn)行種群更新。

在調(diào)度種群交叉變異操作中，使采蜜蜂及觀察蜂利用變異操作進(jìn)行局部搜索。即在原來的調(diào)度方案中，隨機(jī)挑選兩個(gè)不同的參數(shù)，將其位置進(jìn)行互換，即可得到變異后的調(diào)度方案。

在調(diào)度種群交叉變異操作中，使偵查蜂利用交叉操作進(jìn)行全局搜索。本文采用基于工序先后順序的交叉操作[2]，具體步驟如下：

步驟1 在調(diào)度種群中隨機(jī)挑選兩個(gè)蜜源(可行解)；

步驟2 將工件集{1,2,…，n}隨機(jī)劃分為兩個(gè)非空子集JobSet1和JobSet2；

步驟3 將蜜源1、蜜源2中與JobSet1相同的工件分別復(fù)制到新蜜源1、新蜜源2的對應(yīng)位置，并保持順序不變；

步驟4 將蜜源1、蜜源2中與JobSet2相同的工件分別復(fù)制到新蜜源2、新蜜源1中，并保持順序不變。

以圖1的編碼方案為例，對上述蜜源進(jìn)行交叉操作，結(jié)果如圖2所示。

圖2 基于工序先后順序的交叉操作

3 IFPPS優(yōu)化流程設(shè)計(jì)

本文采用集成式優(yōu)化策略，以最大完工時(shí)間最小化為優(yōu)化目標(biāo)，由于人工蜂群算法中適應(yīng)度值越大代表蜜源越好，因此使適應(yīng)度函數(shù)等于目標(biāo)函數(shù)的倒數(shù)，如式(11)所示,f是目標(biāo)函數(shù)值，F(xiàn)itness是適應(yīng)度函數(shù)值。

Fitness=1/f

(11)

根據(jù)上述基于交叉變異的人工蜂群算法，對工藝規(guī)劃系統(tǒng)和車間調(diào)度系統(tǒng)進(jìn)行集成優(yōu)化，最終確定各個(gè)工件的最優(yōu)工藝路線和車間調(diào)度方案，具體流程如圖3所示。

圖3 優(yōu)化策略流程

求解步驟如下：

步驟1 設(shè)加工工件數(shù)為n，根據(jù)各工件的工藝信息，初始化n個(gè)工藝種群。

步驟2 計(jì)算每個(gè)工件初始路線的適應(yīng)度函數(shù)值，選擇值最大的一條工藝路線。

步驟3 把各工件所選擇的工藝路線輸入車間調(diào)度系統(tǒng)。

步驟4 通過基于交叉變異的人工蜂群算法對車間調(diào)度系統(tǒng)進(jìn)行優(yōu)化，主要包含以下步驟:

1)根據(jù)工藝系統(tǒng)輸送的工藝路線，初始化調(diào)度種群。

2)計(jì)算種群中所有個(gè)體的適應(yīng)度值，并將值最大的調(diào)度方案記為最優(yōu)調(diào)度方案。

3)判斷是否達(dá)到車間調(diào)度系統(tǒng)優(yōu)化的終止條件(達(dá)到調(diào)度系統(tǒng)最大迭代次數(shù)時(shí)算法結(jié)束)：如果是，就輸出最優(yōu)調(diào)度方案和各工件對應(yīng)的工藝路線，并將其記為最優(yōu)解，之后進(jìn)行步驟5；不是就進(jìn)行步驟4中的4)。

4)根據(jù)本文2.2節(jié)，利用調(diào)度種群的交叉變異操作產(chǎn)生新的調(diào)度種群。

5)轉(zhuǎn)步驟4中的2)，迭代次數(shù)加1。

步驟5 根據(jù)基本ABC算法的貪婪準(zhǔn)則更新最優(yōu)解。

步驟6 判斷是否滿足集成系統(tǒng)的終止條件(達(dá)到集成系統(tǒng)最大運(yùn)行次數(shù)時(shí)算法結(jié)束)，如果是，就輸出最優(yōu)解，不是就轉(zhuǎn)到步驟7。

步驟7 根據(jù)本文2.2節(jié)工藝種群交叉變異操作方法，更新所有工藝種群。

步驟8 轉(zhuǎn)到步驟2，迭代次數(shù)加1。

4 實(shí)例驗(yàn)證

本文進(jìn)行了兩組實(shí)例測試：第一組是為了驗(yàn)證柔性工藝規(guī)劃與車間調(diào)度集成問題的必要性，對基于交叉變異的人工蜂群算法用于求解柔性工藝規(guī)劃與車間調(diào)度集成和非集成的柔性工藝規(guī)劃與車間調(diào)度(NonIFPPS)的結(jié)果進(jìn)行比較；第二組是為了評估本文基于交叉變異的人工蜂群算法求解該集成問題的有效性，將本文算法求解結(jié)果與目前較好的其他算法進(jìn)行比較。兩部分實(shí)例算法參數(shù)設(shè)置如下：初始化蜜蜂總數(shù)NP=100(工藝系統(tǒng)與調(diào)度系統(tǒng)相同);采蜜蜂數(shù)量FoodNumber=NP/2(工藝系統(tǒng)與調(diào)度系統(tǒng)相同);偵查蜂數(shù)量SearchNumber=5(工藝系統(tǒng)與調(diào)度系統(tǒng)相同);集成最大運(yùn)行次數(shù)RunTime=200;調(diào)度系統(tǒng)最大迭代次數(shù)maxCycle=50;蜜源最大開采次數(shù)Limit=5(工藝系統(tǒng)與調(diào)度系統(tǒng)相同)。

4.1 集成必要性驗(yàn)證

為了驗(yàn)證研究柔性工藝規(guī)劃與車間調(diào)度集成問題的必要性，以六種工件在五臺機(jī)器上加工的IFPPS問題為例進(jìn)行分析，工件的參數(shù)信息如表1～3所示。通過Matlab對算法進(jìn)行編程，柔性工藝規(guī)劃與車間調(diào)度集成優(yōu)化與非集成優(yōu)化具體的測試結(jié)果對比如表4所示，集成式最優(yōu)調(diào)度方案甘特圖如圖4所示。

從對比結(jié)果可以看出，單就工藝路線優(yōu)化而言，非集成式中的工件1、工件2、工件4及工件5的最優(yōu)工藝路線對應(yīng)的加工時(shí)間小于集成式中對應(yīng)的加工時(shí)間，而集成式柔性工藝規(guī)劃與車間調(diào)度的最優(yōu)調(diào)度方案的完工時(shí)間小于非集成式柔性工藝規(guī)劃與車間調(diào)度。這是因?yàn)樵趥鹘y(tǒng)的車間生產(chǎn)系統(tǒng)中，車間調(diào)度方案往往是在工藝規(guī)劃之后進(jìn)行的，在執(zhí)行調(diào)度時(shí)，工藝規(guī)劃必須限定在之前所產(chǎn)生的工藝路線之中，這樣車間調(diào)度不可避免會受到工藝路線的約束，從而就會限制調(diào)度系統(tǒng)產(chǎn)生優(yōu)化方案的效果。對柔性工藝規(guī)劃與車間調(diào)度進(jìn)行集成優(yōu)化研究可以同時(shí)考慮工件的工藝路線優(yōu)化和車間調(diào)度優(yōu)化，不僅能夠增加車間生產(chǎn)系統(tǒng)的柔性，同時(shí)能夠減少工藝路線對調(diào)度優(yōu)化的限制，因此即使單個(gè)工件的工藝路線不是最優(yōu)，但是整體的調(diào)度方案卻是最優(yōu)的。由此說明研究柔性工藝規(guī)劃與車間調(diào)度集成優(yōu)化問題是十分必要的。

4.2 算法有效性驗(yàn)證

由于現(xiàn)有單目標(biāo)工藝規(guī)劃與車間調(diào)度集成優(yōu)化研究中，缺乏同時(shí)考慮工藝規(guī)劃多種柔性特征的實(shí)例，因此，選用Morad等[19]文章中的一個(gè)實(shí)例，該實(shí)例是5個(gè)工件在5臺機(jī)器上進(jìn)行加工，每個(gè)工件不存在加工工藝柔性及特征次序柔性，只存在加工機(jī)器柔性，并且工件在不同機(jī)器之間的轉(zhuǎn)換時(shí)間忽略不計(jì)。具體工件的工藝信息如表5所示。

通過Matlab對實(shí)例進(jìn)行編程，本文基于交叉變異的人工蜂群算法求得的優(yōu)化結(jié)果為makespan=31，與其他優(yōu)化算法求解結(jié)果對比如表6所示。從表6中可以看出，本文人工蜂群算法的優(yōu)化結(jié)果優(yōu)于其他算法，主要原因在于本文針對柔性工藝規(guī)劃與車間調(diào)度集成優(yōu)化問題設(shè)計(jì)了較好的編碼方法與搜索策略，使得算法在求解效率及搜索能力上得到增強(qiáng)，因此驗(yàn)證了本文人工蜂群算法的有效性及優(yōu)越性。本文算法求得的最優(yōu)調(diào)度方案甘特圖如圖5所示。

表2 工件的加工工藝信息表(測試1)

表3 工件在不同機(jī)器之間的轉(zhuǎn)換時(shí)間(測試1)

表4 集成必要性驗(yàn)證測試結(jié)果(測試1)

圖4 集成式最優(yōu)調(diào)度方案甘特圖(測試1)

表5 工件的工藝信息[19](測試2)

Tab.5Processinformationofworkpieces(test2)

工件加工特征加工工藝可選加工機(jī)器對應(yīng)加工時(shí)間工件加工特征加工工藝可選加工機(jī)器對應(yīng)加工時(shí)間1F1O1M1，M25，3F2O2M27F3O3M26F4O4M4，M53，44F1O1M2，M32，6F2O2M38F3O3M3，M43，8F4O4M4，M57，42F1O1M17F2O2M2，M34，6F3O3M3，M47，7F4O4M5105F1O1M1，M33，5F2O2M37F3O3M4，M59，6F4O4M533F1O1M1，M2，M34，5，8F2O2M45F3O3M2，M36，5F4O4M54

圖5 車間調(diào)度甘特圖(makespan=31) (測試2)

表6 算法有效性驗(yàn)證測試結(jié)果(測試2)

Tab.6 Algorithm verification results (test 2)

方法makespan方法makespanHeuristic[19]38IGA[1]33SA[19]33ABC31Agent?based[20]33

5 結(jié)語

為了使制造車間能夠及時(shí)響應(yīng)訂單的個(gè)性化需求，消除缺乏柔性的缺陷，提高其生產(chǎn)效率，本文提出一種基于交叉變異的人工蜂群算法對柔性工藝規(guī)劃與車間調(diào)度集成進(jìn)行優(yōu)化求解，重點(diǎn)對算法的具體操作及工藝與調(diào)度集成優(yōu)化流程進(jìn)行了設(shè)計(jì)，最后選取最小化最大完工時(shí)間為優(yōu)化目標(biāo)，通過兩部分實(shí)例對集成研究的必要性以及算法求解的有效性進(jìn)行了驗(yàn)證。

References)

[1] 高亮，李新宇.工藝規(guī)劃與車間調(diào)度集成研究現(xiàn)狀及進(jìn)展[J].中國機(jī)械工程，2011，22(8): 1001-1007.(GAO L, LI X Y.Current research on integrated process planning and scheduling [J].China Mechanical Engineering, 2011, 22(8): 1001-1007.)

[2] 宋栓軍，楊佩莉,石雯麗.考慮多目標(biāo)的柔性工藝與調(diào)度集成優(yōu)化算法[J/OL].計(jì)算機(jī)應(yīng)用研究，2017 [2016- 08- 05].http://www.arocmag.com/getarticle?aid=912497cbe6174f12.(SONG S J, YANG P L, SHI W L.Integrated optimization algorithm of flexible process planning and shop scheduling with consideration of multi-objectives [J/OL].Application Research of Computers, 2017 [2016- 08- 05].http://www.arocmag.com/getarticle?aid=912497cbe6174f12.

[3] 巴黎，李言，楊明順，等.考慮不確定加工時(shí)間的工藝規(guī)劃與調(diào)度集成問題研究[J].中國機(jī)械工程，2015，26(24):3348-3355.(BA L, LI Y, YANG M S, et al.Research on integrated process planning and scheduling problem with consideration of uncertain processing time [J].China Mechanical Engineering, 2015, 26(24): 3348-3355.)

[4] CHRYSSOLOURIS G, CHAN S, SUH N P.An integrated approach to process planning and scheduling [J].CIRP Annals — Manufacturing Technology, 1985, 34(1): 413- 417.

[5] BECKENDORFF U, KREUTZFELDT J.Reactive workshop scheduling based on alternative routings [C]// Proceedings of a Conference on Factory Automation and Information Management.Bocaraton, Florida: CRC Press, 1991: 875-885.

[6] 劉倩雯.人工蜂群算法及其在調(diào)度問題中的應(yīng)用研究[D].北京: 北京交通大學(xué)，2014: 5-61.(LIU Q W.Research on artificial bee colony and its application in scheduling problems [D].Beijing: Beijing Jiaotong University, 2014: 5-61.)

[7] 瞿璨.面向綠色制造的工藝規(guī)劃決策研究[D].武漢: 華中科技大學(xué)，2013:2-54.(QU C.Study on the process planning for green manufacturing [D].Wuhan: Huazhong University of Science and Technology, 2013: 2-54.)

[8] 呂盛坪，喬立紅.工藝規(guī)劃與車間調(diào)度及兩者集成的研究現(xiàn)狀和發(fā)展趨勢[J].計(jì)算機(jī)集成制造系統(tǒng)，2014，20(2):290-300.(LYU S P, QIAO L H.Current status and developing trend of process planning and job shop scheduling [J].Computer Integrated Manufacturing Systems, 2014, 20(2): 290-300.)

[9] 呂盛坪，喬立紅.工藝規(guī)劃與車間調(diào)度復(fù)合式集成模型[J].計(jì)算機(jī)集成制造系統(tǒng)，2014，20(1):111-120.(LYU S P, QIAO L H.Hybrid integration model for process planning and scheduling [J].Computer Integrated Manufacturing Systems, 2014, 20(1): 111-120.)

[10] 崔曉康，肖艷秋，王磊,等.面向工藝規(guī)劃與車間調(diào)度的集成方法研究[J].機(jī)床與液壓，2015，43(3): 134-137.(CUI X K, XIAO Y Q, WANG L, et al.Research on integrated method of process planning and job-shop scheduling [J].Machine Tool & Hydraulics, 2015, 43(3): 134-137.)

[11] 王進(jìn)峰，陰國富，雷前召，等.蟻群算法在工藝規(guī)劃與車間調(diào)度集成優(yōu)化中的應(yīng)用[J].東南大學(xué)學(xué)報(bào)(自然科學(xué)版)，2012，42(S1): 173-177.(WANG J F, YIN G F, LEI Q Z, et al.Integrated process planning and scheduling based on an ant colony algorithm [J].Journal of Southeast Universit (Natural Science Edition), 2012, 42(S1): 173-177.)

[12] LIU Z, MA S, SHI Y, et al.Solving multi-objective flexible job shop scheduling with transportation constraints using a micro artificial bee colony algorithm [C]// Proceedings of the 2013 IEEE 17th International Conference on Computer Supported Cooperative Work in Design.Piscataway, NJ: IEEE, 2013: 427-432.

[13] 文笑雨.多目標(biāo)集成式工藝規(guī)劃與車間調(diào)度問題的求解方法研究[D].武漢:華中科技大學(xué)，2014: 5-61.(WEN X Y.Research on the solution methods for multi-objective integrated process planning and scheduling problem [D].Wuhan: Huazhong University of Science and Technology, 2014: 5-61.)

[14] 江銘炎，袁東風(fēng).人工蜂群算法及其應(yīng)用[M].北京：科學(xué)出版,2014:16-264.(JIANG M Y, YUAN D F.Artificial Bee Colony Algorithm and Its Application [M].Beijing: Science Press, 2014: 16-264.)

[15] 吳正佳，羅月勝，周玉瓊,等.一種求解典型JSP的改進(jìn)離散粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究，2013，30(8):2405-2409.(WU Z J, LUO Y S, ZHOU Y Q, et al.Improved discrete particle swarm optimization algorithm for typical Job-Shop scheduling problem [J].Application Research of Computers, 2013, 30(8): 2405-2409.)

[16] 張國輝，張凌杰，吳立輝,等.精英進(jìn)化策略求解柔性作業(yè)車間調(diào)度問題[J].計(jì)算機(jī)應(yīng)用研究，2016，33(12): 1-5.(ZHANG G H, ZHANG L J, WU L H, et al.Solving flexible Job-Shop scheduling with elite evolution strategy [J].Application Research of Computers, 2016, 33(12): 1-5.)

[17] 李新宇.工藝規(guī)劃與車間調(diào)度集成問題的求解方法研究[D].武漢:華中科技大學(xué)，2009:58.(LI X Y.Research on the solution methods of integrated process planning and scheduling [D].Wuhan: Huazhong University of Science and Technology, 2009: 58.)[18] FANG H-L, ROSS P, CORNE D.A promising genetic algorithm approach to job-shop scheduling, re-scheduling and open-shop scheduling problems [C]// Proceedings of the 5th International Conference on Genetic Algorithms.San Mateo, CA: Morgan Kaufmann Publishers, 1993: 375-382.

[19] MORAD N, ZALZALA A M S.Genetic algorithms in integrated process planning and scheduling [J].Journal of Intelligent Manufacturing, 1999, 10(2): 169-179.

[20] FUJI N, INOUE R, UEDA K.Integration of process planning and scheduling using multi-Agent learning [C]// Proceedings of the 41st CIRP Conference on Manufacturing Systems.Berlin: Springer-Verlag, 2008: 297-300.

This work is partially supported by the Scientific Research Fund by Shaanxi Provincial Education Department (15JK1311), Research Start-up Fund for Doctor of Xi’an Polytechnic University (BS1301), Innovation Fund for Graduate Students of Xi’an Polytechnic University (CX201628).

SONG Shuanjun, born in 1974, Ph.D., associate professor.His research interests include optimization of production system, supply chain management.

YANG Peili, born in 1992, M.S.candidate.Her research interests include optimization of production system.

SHI Wenli, born in 1991, M.S.candidate.Her research interests include supply chain management.

Optimization of integrated flexible process planning and job shop scheduling based on artificial bee colony

SONG Shuanjun, YANG Peili*, SHI Wenli

(CollegeofMechanicalandElectricalEngineering,Xi’anPolytechnicUniversity,Xi’anShaanxi710048,China)

To achieve the optimization of integrated flexible process planning and job shop scheduling, taking the flexibility of manufacturing process and order and manufacturing machine of the workpieces into account, for minimizing the maximum completion time of the product processing task, an artificial bee colony algorithm based on crossover and mutation was proposed.Aiming at the discrete characteristics of integrated flexible process and job shop scheduling, the process route was coded in sequence, and the job scheduling was based on the working procedure.To improve the performance of the algorithm, by means of crossover and mutation operation of process population and scheduling population, the employed foragers and onlookers bees seeked local optimality, and the scouts seeked global optimality.On this basis, the necessity of the integration research and the effectiveness of the improved algorithm were verified by two test cases.

flexible process planning; job shop scheduling; Artificial Bee Colony (ABC)

2016- 07- 18;

2016- 08- 24。 基金項(xiàng)目:陜西省教育廳科研基金資助項(xiàng)目(15JK1311)；西安工程大學(xué)博士科研啟動基金資助項(xiàng)目(BS1301)；西安工程大學(xué)研究生創(chuàng)新基金資助項(xiàng)目(CX201628)。

宋栓軍(1974—)，男，陜西西安人，副教授，博士，主要研究方向：生產(chǎn)系統(tǒng)優(yōu)化、供應(yīng)鏈管理； 楊佩莉(1992—)，女，陜西興平人，碩士研究生，主要研究方向：生產(chǎn)系統(tǒng)優(yōu)化； 石雯麗(1991—)，女，甘肅隴南人，碩士研究生，主要研究方向：供應(yīng)鏈管理。

1001- 9081(2017)02- 0523- 07

10.11772/j.issn.1001- 9081.2017.02.0523

TH166;TP

A