基于人工蜂群算法的柔性工藝與車間調度集成優化

宋栓軍，楊佩莉，石雯麗

(西安工程大學 機電工程學院，西安 710048)

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

基于人工蜂群算法的柔性工藝與車間調度集成優化

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

(西安工程大學 機電工程學院，西安 710048)

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

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

柔性工藝規劃；車間調度；人工蜂群算法

0 引言

工藝規劃與車間調度集成(Integrated Process Planning and Scheduling，IPPS)是制造系統中急需解決的關鍵問題之一。在傳統的企業生產過程中，工藝規劃和車間調度往往被當作獨立的系統進行研究，導致了工藝與調度的脫節[1]。如果將工藝規劃和車間調度系統進行集成，則可避免制造資源的浪費，優化生產節拍，提高制造系統的工作效率[2-3]。

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

1 IFPPS優化數學模型

本文以單目標IFPPS問題為例，以加工任務的最大完工時間(makespan)最小為目標進行優化研究，車間調度問題為作業車間調度。在建立優化數學模型前作如下假設[15-16]：

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

2)在進行排產優化時，不同工件相互之間沒有優先級，不同工件的加工工序之間也沒有優先級，同一工件的各個工序之間存在優先級；

3)在同一時間，每臺機器僅可加工一道工序；

4)所有工序的加工時間是指其實際加工與其準備加工時間之和。

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

Yijlpqsk=

目標函數如式(1)所示：

f1=min{makespan=max(ci)}

(1)

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

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

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

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

(2)

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

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

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

(3)

3)一個工件同一時刻僅可有一道工序被加工：

(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)每臺機器同一時刻僅可加工一道工序：

(5)

5)工件i僅可選取一條工藝路線輸入到調度系統：

(6)

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

(7)

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

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

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

(8)

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

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

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

(9)

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

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優化算法設計

2.1 柔性工藝調度的編碼及解碼

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

根據工藝的柔性特征，本文創新性地提出一種序列編碼方式對工藝規劃部分的各個序列進行編碼，表1為工件1的加工工藝信息。對工件1加工工藝信息進行序列編碼，編碼結果如圖1所示。

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

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

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

2)車間調度編碼及解碼。

在車間調度編碼的相關研究中，用得最多的是基于工序的編碼方法，本文也利用此方式對個體進行編碼[17]。設一個企業制造車間中的待加工工件數為4，在初始工藝路線中按照適應度函數值挑選出各工件較優的路線后，就可以知道要加工的工序總數。假設工件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]就為一種可行的調度編碼方案。在此方案中，工件序號出現的次數與其所包含的工序數相同，例如工件1包含6道工序，那么1就在調度編碼方案中一共出現6次。此外方案中第6個位置上的4是從左到右數數字4出現的第2次，所以第6個位置代表了工件4的工藝路線中第2道要加工的工序。

由于本文選用的優化目標為最小化最大完工時間，屬于正規調度指標，并且基于工序的編碼方式產生的調度方案均為可行的調度方案，因此選擇使用文獻[18]中的貪婪解碼方法將編碼方案解碼為活動調度類型。貪婪解碼方法的具體步驟可由文獻[18]獲得，此處不再贅述。

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

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

1)蜂群初始化。

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

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

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

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

步驟1 將特征序列中兩個隨機位置的數值進行交換，產生新的特征序列，并通過約束調整方法對其進行調整，使其符合特征之間的次序約束條件；

步驟2 將工藝序列中一個隨機位置所選擇的加工工藝轉變成另一種可選加工工藝；

步驟3 將機器序列中一個隨機位置所選擇的加工機器轉變成另一種可選加工機器。

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

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

步驟2 在蜜源的序列中隨機選擇兩個交叉點，特征序列用步驟3交叉操作，工藝序列和機器序列用步驟4進行交叉操作。

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

步驟4 將工藝序列1交叉點中斷參數信息復制到新工藝序列的相應位置，將工藝序列2的交叉點兩端的參數信息按順序填入新工藝序列的空位置中，這樣就生成了新的工藝序列，機器序列同工藝序列。

3)調度種群交叉變異操作。

在調度系統的優化流程迭代中，需要不斷尋找新的調度方案，對調度種群進行更新。針對基于工序的調度編碼方式，本文提出一種調度種群交叉變異操作進行種群更新。

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

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

步驟1 在調度種群中隨機挑選兩個蜜源(可行解)；

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

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

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

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

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

3 IFPPS優化流程設計

本文采用集成式優化策略，以最大完工時間最小化為優化目標，由于人工蜂群算法中適應度值越大代表蜜源越好，因此使適應度函數等于目標函數的倒數，如式(11)所示,f是目標函數值，Fitness是適應度函數值。

Fitness=1/f

(11)

根據上述基于交叉變異的人工蜂群算法，對工藝規劃系統和車間調度系統進行集成優化，最終確定各個工件的最優工藝路線和車間調度方案，具體流程如圖3所示。

圖3 優化策略流程

求解步驟如下：

步驟1 設加工工件數為n，根據各工件的工藝信息，初始化n個工藝種群。

步驟2 計算每個工件初始路線的適應度函數值，選擇值最大的一條工藝路線。

步驟3 把各工件所選擇的工藝路線輸入車間調度系統。

步驟4 通過基于交叉變異的人工蜂群算法對車間調度系統進行優化，主要包含以下步驟:

1)根據工藝系統輸送的工藝路線，初始化調度種群。

2)計算種群中所有個體的適應度值，并將值最大的調度方案記為最優調度方案。

3)判斷是否達到車間調度系統優化的終止條件(達到調度系統最大迭代次數時算法結束)：如果是，就輸出最優調度方案和各工件對應的工藝路線，并將其記為最優解，之后進行步驟5；不是就進行步驟4中的4)。

4)根據本文2.2節，利用調度種群的交叉變異操作產生新的調度種群。

5)轉步驟4中的2)，迭代次數加1。

步驟5 根據基本ABC算法的貪婪準則更新最優解。

步驟6 判斷是否滿足集成系統的終止條件(達到集成系統最大運行次數時算法結束)，如果是，就輸出最優解，不是就轉到步驟7。

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

步驟8 轉到步驟2，迭代次數加1。

4 實例驗證

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

4.1 集成必要性驗證

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

從對比結果可以看出，單就工藝路線優化而言，非集成式中的工件1、工件2、工件4及工件5的最優工藝路線對應的加工時間小于集成式中對應的加工時間，而集成式柔性工藝規劃與車間調度的最優調度方案的完工時間小于非集成式柔性工藝規劃與車間調度。這是因為在傳統的車間生產系統中，車間調度方案往往是在工藝規劃之后進行的，在執行調度時，工藝規劃必須限定在之前所產生的工藝路線之中，這樣車間調度不可避免會受到工藝路線的約束，從而就會限制調度系統產生優化方案的效果。對柔性工藝規劃與車間調度進行集成優化研究可以同時考慮工件的工藝路線優化和車間調度優化，不僅能夠增加車間生產系統的柔性，同時能夠減少工藝路線對調度優化的限制，因此即使單個工件的工藝路線不是最優，但是整體的調度方案卻是最優的。由此說明研究柔性工藝規劃與車間調度集成優化問題是十分必要的。

4.2 算法有效性驗證

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

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

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

表3 工件在不同機器之間的轉換時間(測試1)

表4 集成必要性驗證測試結果(測試1)

圖4 集成式最優調度方案甘特圖(測試1)

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

Tab.5Processinformationofworkpieces(test2)

工件加工特征加工工藝可選加工機器對應加工時間工件加工特征加工工藝可選加工機器對應加工時間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 車間調度甘特圖(makespan=31) (測試2)

表6 算法有效性驗證測試結果(測試2)

Tab.6 Algorithm verification results (test 2)

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

5 結語

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

References)

[1] 高亮，李新宇.工藝規劃與車間調度集成研究現狀及進展[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] 宋栓軍，楊佩莉,石雯麗.考慮多目標的柔性工藝與調度集成優化算法[J/OL].計算機應用研究，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] 巴黎，李言，楊明順，等.考慮不確定加工時間的工藝規劃與調度集成問題研究[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] 劉倩雯.人工蜂群算法及其在調度問題中的應用研究[D].北京: 北京交通大學，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] 瞿璨.面向綠色制造的工藝規劃決策研究[D].武漢: 華中科技大學，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] 呂盛坪，喬立紅.工藝規劃與車間調度及兩者集成的研究現狀和發展趨勢[J].計算機集成制造系統，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] 呂盛坪，喬立紅.工藝規劃與車間調度復合式集成模型[J].計算機集成制造系統，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] 崔曉康，肖艷秋，王磊,等.面向工藝規劃與車間調度的集成方法研究[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].東南大學學報(自然科學版)，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] 文笑雨.多目標集成式工藝規劃與車間調度問題的求解方法研究[D].武漢:華中科技大學，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] 江銘炎，袁東風.人工蜂群算法及其應用[M].北京：科學出版,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].計算機應用研究，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].計算機應用研究，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] 李新宇.工藝規劃與車間調度集成問題的求解方法研究[D].武漢:華中科技大學，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。 基金項目:陜西省教育廳科研基金資助項目(15JK1311)；西安工程大學博士科研啟動基金資助項目(BS1301)；西安工程大學研究生創新基金資助項目(CX201628)。

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

1001- 9081(2017)02- 0523- 07

10.11772/j.issn.1001- 9081.2017.02.0523

TH166;TP

A