差異工件流水車間批調(diào)度問題的求解

朱頎，陳成棟，陳華平

中國科學(xué)技術(shù)大學(xué) 管理學(xué)院，合肥 230026

差異工件流水車間批調(diào)度問題的求解

朱頎，陳成棟，陳華平

中國科學(xué)技術(shù)大學(xué) 管理學(xué)院，合肥 230026

1 引言

差異工件流水車間批調(diào)度問題是工業(yè)生產(chǎn)中一類典型的調(diào)度問題。它是對(duì)傳統(tǒng)流水車間問題的進(jìn)一步擴(kuò)展，即在流水車間的每個(gè)階段均是批處理機(jī)。求解該問題分為兩個(gè)步驟：首先工件遵循特定分批規(guī)則成批，然后將形成的批按照相同的加工順序在各批處理機(jī)上逐個(gè)進(jìn)行加工。這類組合優(yōu)化問題在實(shí)際應(yīng)用中很常見，如電子工業(yè)的環(huán)境應(yīng)力篩選過程就可抽象為一個(gè)典型的流水車間批調(diào)度問題。環(huán)境應(yīng)力篩選由半導(dǎo)體工業(yè)的老化實(shí)驗(yàn)發(fā)展而來，整個(gè)產(chǎn)品需要在用戶設(shè)定的不同環(huán)境下進(jìn)行測(cè)試，每個(gè)篩選實(shí)驗(yàn)箱可以看做一個(gè)批處理機(jī)，數(shù)量由待測(cè)試的裝配車間的數(shù)量以及特定裝備車間的測(cè)試數(shù)量決定。該問題的研究具有很好的現(xiàn)實(shí)意義。

目前關(guān)于求解流水車間批調(diào)度問題的研究大部分限于兩臺(tái)機(jī)器的情況，求解目標(biāo)多為最小化制造跨度（Makespan）。如Mirsanei等[1]在ARA和FLA兩種啟發(fā)式算法以及模擬退火算法（SA）的基礎(chǔ)上提出ARSA和FLSA兩種改進(jìn)算法；Purushothaman等[2]采用遺傳算法（GA）進(jìn)行了求解；Alebachew等[3]在工件順序的模糊調(diào)度模型基礎(chǔ)上提出了基于GA的求解思路；Liao等[4]采用禁忌搜索算法（TS）對(duì)問題進(jìn)行了求解，并與混合整數(shù)線性規(guī)劃進(jìn)行了比較；針對(duì)多機(jī)器的情況（即3臺(tái)批處理機(jī)及以上），Ali等[5]提出了一種改進(jìn)的混合整數(shù)線性規(guī)劃方法（Mixed Integer Linear Formulation），在小規(guī)模工件的情況下進(jìn)行了求解。目前鮮有利用智能算法對(duì)此問題的求解。

本文研究了流水車間批調(diào)度問題在大規(guī)模工件情況下的求解，考慮到群智能算法在求解大規(guī)模工件問題上的優(yōu)勢(shì)，將微粒群算法（PSO）[6]引入差異工件流水車間批調(diào)度問題的求解，提出了一種改進(jìn)的微粒群算法。為保證種群具備一定的分散度和質(zhì)量，采用基于NEH方法的種群初始化方法，并利用ROV規(guī)則[7]將微粒的連續(xù)位置轉(zhuǎn)化為離散的加工順序。由于傳統(tǒng)微粒群算法容易陷入局部最優(yōu)，形成早熟收斂的情況，在粒子群算法每次迭代過程中引入一種局部搜索技術(shù)（Variable Neighborhood Search，VNS）[8]，并采用了一種自適應(yīng)慣性權(quán)系數(shù)（Adaptive Inertia Weight Factor，AIWF）[8]改進(jìn)原慣性權(quán)系數(shù)。最后通過生成的基準(zhǔn)測(cè)試算例，將改進(jìn)的PSO算法與該問題的一個(gè)下界（Lower Bound，LB）[5]和啟發(fā)式算法中效果最好的Nawaz-Enscore-Ham（NEH）算法[9]，以及標(biāo)準(zhǔn)的PSO算法進(jìn)行了比較，并驗(yàn)證了算法的有效性。

2 問題描述

差異工件的流水車間批調(diào)度問題的具體描述如下：

（1）流水車間的每個(gè)階段均是一臺(tái)批處理機(jī)，可同時(shí)將多個(gè)工件作為一批同時(shí)進(jìn)行加工；

（2）工件遵循特定分批規(guī)則加入相應(yīng)批后按照相同的加工順序同時(shí)在批處理機(jī)上進(jìn)行加工，一旦形成特定的批則工件不能加入或者移除出批；

（3）每個(gè)批的最大容量均相同，批中工件的尺寸之和不能超過批的最大容量限制；

（4）批的加工時(shí)間為批中加工時(shí)間最長的工件的加工時(shí)間；

（5）批在加工時(shí)不允許中斷；

（6）假定每個(gè)批之間存在一個(gè)無限大的緩沖區(qū)。

根據(jù)調(diào)度問題的三參數(shù)表示法，該問題可表示為Fm|B，sj| Cmax，數(shù)學(xué)模型如下：

式（1）中，Cmax表示最大制造跨度，即Makespan。式（2）確保每個(gè)工件都在一個(gè)特定的批中，若工件j在批b中，則Xjb=1，否則Xjb=0。式（3）中，sj為工件j的尺寸，B為批容量，確保批中的工件尺寸總和不超過批容量。式（4）給出了批加工時(shí)間的約束條件，Pij表示批i在第j臺(tái)批處理機(jī)上的加工時(shí)間，pij為工件i在第j臺(tái)機(jī)器上的加工時(shí)間，表示批的加工時(shí)間為批中加工時(shí)間最長的工件的加工時(shí)間。式（5）和式（6）確保批b只能在加工次序的某個(gè)位置，并且每個(gè)加工次序的某個(gè)位置上只能有一個(gè)批；若批b在加工次序i調(diào)度，Zbi=1，否則Zbi=0。式（7）決定了在機(jī)器i上的第b批的加工時(shí)間，Qbi表示第b批在機(jī)器i上的加工時(shí)間。如果Zbi=1，則Qbi≥Pbi，由于問題目標(biāo)是求出最小的時(shí)間跨度，因此Qbi=Pbi；如果Zbk=0，則Qbi≥Pbi-BigM，若想得到最小的Cmax，Qbi=0。式（8）表示了工件在機(jī)器1上第b階段的加工時(shí)間；Cb1表示第b批在機(jī)器1上的完成時(shí)間，Qk′1表示第k′批在機(jī)器1上的加工時(shí)間。式（9）～式（11）給出了求解最小制造跨度的遞歸方程，式（9）中C1i表示第1臺(tái)機(jī)器上第i批的完成時(shí)間，Q1i′表示第1臺(tái)機(jī)器上第i′批的加工時(shí)間。式（10）表示第i批在機(jī)器l上的完成時(shí)間Cli，為第i-1批在機(jī)器i上的完成時(shí)間Cl，i-1與第i批在機(jī)器l上的加工時(shí)間Qli之和。同理，式（11）表示第i批在機(jī)器l上的完成時(shí)間Cli，為第i批在第l-1臺(tái)機(jī)器上的加工時(shí)間Cl-1，i與第i批在機(jī)器l上的加工時(shí)間Qli之和。式（12）表示制造跨度Cmax為最后完成的加工批的完成時(shí)間。

3 流水車間批調(diào)度問題的求解

差異工件流水車間批調(diào)度問題的求解可分為兩個(gè)部分。首先是對(duì)差異工件進(jìn)行分批，差異工件的批調(diào)度問題是由Uzsoy在1994年首先提出，并證明了該問題是NP難的[10]。考慮到差異工件分批可能導(dǎo)致的批的加工時(shí)間分配不合理以及批的空間浪費(fèi)問題，采用Palmer啟發(fā)式算法[11]對(duì)工件進(jìn)行初始排序，然后利用BF（Best Fit）分批規(guī)則對(duì)其進(jìn)行分批。

由于成批后不能加入新工件或者將批內(nèi)工件移除出批，則每個(gè)批可看做一個(gè)獨(dú)立的工件，因此后續(xù)的加工問題等價(jià)于置換流水車間調(diào)度問題，即批的排序問題。當(dāng)流水車間的機(jī)器數(shù)量為2臺(tái)時(shí)，可在多項(xiàng)式時(shí)間內(nèi)得到解答，而機(jī)器數(shù)量大于2臺(tái)的情況已被證明為NP難題[12]。近年來PSO算法在求解大規(guī)模優(yōu)化問題上獲得了廣泛應(yīng)用和認(rèn)同，本文對(duì)傳統(tǒng)的PSO算法進(jìn)行了改進(jìn)，來對(duì)批的排序進(jìn)行求解。

3.1 差異工件的分批

為了提高分批質(zhì)量，采用目前分批效果較好的BF分批規(guī)則進(jìn)行分批，并在分批之前采用Palmer啟發(fā)式算法初始化工件序列。

Palmer算法是基于斜度指標(biāo)（Slope Index）排序工件的啟發(fā)式算法。根據(jù)流水車間工件的加工順序，加工時(shí)間趨于增加的工件被賦予較大的優(yōu)先權(quán)數(shù)。工件i的斜度指標(biāo)（Slope Index）Si定義為：

其中，m為機(jī)器數(shù)目，pij為第i個(gè)工件在第j臺(tái)機(jī)器上的加工時(shí)間。按照Si遞減的順序?qū)ぜM(jìn)行初始排序。

對(duì)獲得初始排序的工件序列采用BF規(guī)則進(jìn)行分批，得到初始批序列。BF分批規(guī)則為：選擇處于工件序列頂端的工件，并將之放入之前形成的批序列中剩余空間最小的批中。如果工件無法放入任何一個(gè)存在的批中，則創(chuàng)建新的批，直到工件序列中的工件全部加入批為止。形成的批序列即為初始批序列。由于工件均遵循相同的加工順序，則每個(gè)批在每臺(tái)機(jī)器上的加工順序也是相同的。批在每臺(tái)機(jī)器上的加工時(shí)間為批中在每臺(tái)機(jī)器上加工時(shí)間最長的工件的加工時(shí)間。此時(shí)問題轉(zhuǎn)化為置換流水車間調(diào)度問題。

3.2 基于改進(jìn)的PSO算法的批排序方法

微粒群算法是基于群智能理論的一種新型演化計(jì)算技術(shù)。其基本思想是通過群體中個(gè)體之間的協(xié)作與信息共享來搜索最優(yōu)解，本質(zhì)上是一種并行的全局性隨機(jī)搜索算法，搜索過程保留了局部個(gè)體和群體的最優(yōu)信息，體現(xiàn)了協(xié)同搜索的優(yōu)勢(shì)。但是微粒群算法也有局部搜索能力較差，易陷入局部極小解等缺點(diǎn)。考慮到變鄰域搜索算法能夠幫助微粒在更大的解空間進(jìn)行搜索，同時(shí)結(jié)合流水車間調(diào)度問題的自身特點(diǎn)，提出了基于自然數(shù)編碼的改進(jìn)微粒群算法。算法的總體結(jié)構(gòu)，如圖1所示。

圖1 算法總體結(jié)構(gòu)圖

3.2.1 微粒編碼

流水車間批調(diào)度問題的編碼方式類似置換流水車間，這里采用最常用的編碼方式，即直接采用批的排序。對(duì)于批的個(gè)數(shù)為n的問題，微粒采用n維向量表示，每個(gè)批對(duì)應(yīng)微粒的某一維度。由于微粒群算法的微粒的位置為連續(xù)值矢量，標(biāo)準(zhǔn)微粒群算法是無法實(shí)現(xiàn)批的排序更新的。因此這里構(gòu)造從微粒的位置矢量到批的排序的映射機(jī)制，利用微粒的位置值的大小關(guān)系，結(jié)合隨機(jī)鍵編碼，將微粒的連續(xù)位置Xi=[xi，1，xi，2，…，xi，n]轉(zhuǎn)換為離散的加工順序π=[πi，1，πi，2，…，πi，n]，即每個(gè)批在機(jī)器上的加工順序。

應(yīng)用ROV規(guī)則實(shí)現(xiàn)微粒位置矢量到批的排序的映射。該規(guī)則具體描述如下：對(duì)于某個(gè)微粒的位置矢量，首先將最小的位置矢量賦予ROV值1，將第二小的位置矢量賦予ROV值2，依此類推，直到所有的位置矢量均獲得唯一的ROV值，從而基于ROV值可得到批的一個(gè)加工順序。

例假設(shè)微粒Xi的位置為5維矢量，即Xi=[4.27，1.83，0.99，3.25，0.07]，則首先賦予最小值xi，5的ROV值為1，同理，賦予xi，3的ROV值為2，依此類推，可得批的加工順序π=[5，3，2，4，1]，如表1所示。

表1 微粒位置矢量對(duì)應(yīng)的ROV值

對(duì)于每個(gè)微粒，根據(jù)其位置矢量對(duì)應(yīng)的ROV值確定每個(gè)批的加工順序，在m臺(tái)機(jī)器的情況下，加工順序遵循j1，j2，…，jn的流水車間批調(diào)度問題，可由如下遞歸方程得到問題的Makespan：

其中，Ci，j1表示在機(jī)器i上第j1個(gè)批的完成時(shí)間；pi，jk表示第i臺(tái)機(jī)器上第jk個(gè)批的加工時(shí)間。

3.2.2 微粒的位置更新公式

微粒群算法中，每個(gè)粒子均在n維空間中以一定的速度飛行，每個(gè)微粒根據(jù)自身以及其他粒子的飛行經(jīng)驗(yàn)動(dòng)態(tài)調(diào)整自身的位置和速度。n維搜索空間中第i個(gè)微粒的位置和速度可分別表示為Xi=[xi1,xi2,…，xin]和Vi=[vi1，vi2，…，vin]。通過評(píng)價(jià)各個(gè)微粒的目標(biāo)函數(shù)，確定第k次迭代每個(gè)微粒所經(jīng)過的最佳位置（pbest）Pi=[pi1，pi2，…，pin]及微粒群體所發(fā)現(xiàn)的最佳位置（gbest）Pg，再按照如下公式更新各個(gè)微粒的速度和位置：

其中w為慣性權(quán)系數(shù)，r1和r2為0到1的隨機(jī)數(shù)，c1和c2為正的加速常數(shù)。

3.2.3 微粒的初始化和參數(shù)設(shè)置

標(biāo)準(zhǔn)的微粒群算法通常采用隨機(jī)生成微粒的方式進(jìn)行初始化。但是為了使初始種群具備一定的分散度和質(zhì)量，采用目前為止性能最優(yōu)的NEH啟發(fā)式方法對(duì)種群進(jìn)行初始化，種群規(guī)模設(shè)置為微粒維度的3倍。

NEH啟發(fā)式算法假定在所有機(jī)器上的總加工時(shí)間越長的工件，比總加工時(shí)間短的工件具有更高的優(yōu)先級(jí)，具體步驟如下：

（1）按照在所有機(jī)器上總加工時(shí)間遞減的順序排列n個(gè)批。

（2）選擇前兩個(gè)批進(jìn)行排序，直到在只有兩個(gè)批的情況下獲得最小的局部Makespan的排序?yàn)橹埂?/p>

（3）對(duì)余下的k個(gè)批，k=3，4，…，n，依次插入到前面所獲排序的k個(gè)位置上，直到每次插入均獲得最小局部Makespan為止；最后可得到整個(gè)批序列的NEH排序結(jié)果。

利用NEH啟發(fā)式算法產(chǎn)生第一個(gè)微粒的初始位置：

由于NEH算法得到的是批的排序，因此必須轉(zhuǎn)化為對(duì)應(yīng)的位置矢量才能夠參與微粒群算法的進(jìn)一步進(jìn)化搜索。因此按照如下方式實(shí)現(xiàn)轉(zhuǎn)換：

其中，xNEH，j為微粒在第j維的位置值；sNEH，j為通過NEH方法得到的解得第j維序號(hào)；xmax，j和xmin，j分別為連續(xù)空間上微粒位置的上界值和下界值，這里分別設(shè)置為4.0和-4.0；r代表0到1的一個(gè)隨機(jī)數(shù)。

其余的微粒的位置矢量在一定連續(xù)區(qū)間內(nèi)隨機(jī)生成。

微粒的初始位置矢量采用如下方式隨機(jī)生成：

其中xmin=0，xmax=4.0。

初始化微粒的速度矢量采用相似的方式，如下：

其中vmin=-4.0，vmax=4.0。微粒的速度被限制在特定的范圍內(nèi)，即[-4.0，4.0]。更新微粒速度的加速常數(shù)c1和c2，均設(shè)置為2.0。

微粒群算法的慣性權(quán)系數(shù)w的設(shè)置直接影響算法的收斂性，是調(diào)整全局和局部搜索能力的重要因素。較小的慣性權(quán)系數(shù)有利于精確局部搜索，使算法易于收斂，而較大的慣性權(quán)系數(shù)則有利于搜索跳出局部極小解，改善全局搜索。為了平衡算法的局部搜索和全局搜索能力，這里提出一種自適應(yīng)慣性權(quán)系數(shù)AIWF的計(jì)算表達(dá)式，如下：

其中wmax和wmin分別為w的最大值和最小值，f為微粒當(dāng)前的目標(biāo)值函數(shù)，favg和fmin分別為微粒的平均值和最小目標(biāo)值。

對(duì)依據(jù)上述方法生成的微粒（n為微粒的維度），根據(jù)ROV規(guī)則分別確定出各自的批序列的排序，并求得相應(yīng)的目標(biāo)函數(shù)值，即Makespan值。則每個(gè)微粒計(jì)算出的Makespan值即為各個(gè)微粒的初始最佳位置（pbest）對(duì)應(yīng)的適應(yīng)度函數(shù)值，而其中最小值對(duì)應(yīng)的微粒的位置為初始的全局最佳位置（gbest）。

3.2.4 引入變鄰域搜索改進(jìn)gbest搜索機(jī)制

為了改進(jìn)微粒群算法的局部搜索能力較差，容易陷入局部極小解的問題，這里在微粒每次更新中引入變鄰域搜索算法，利用其無需設(shè)置參數(shù)，實(shí)現(xiàn)簡(jiǎn)單的特性，對(duì)微粒每次迭代更新時(shí)獲得的gbest運(yùn)用多個(gè)鄰域結(jié)構(gòu)進(jìn)行搜索以獲得新的gbest，從而提高了搜索的質(zhì)量和效率。

對(duì)于微粒群算法，可進(jìn)行的鄰域搜索分為兩種類型：一種是基于第t次迭代中第i個(gè)微粒的位置矢量的鄰域搜索，另一種則是基于第t次迭代中第i個(gè)排序πi的第j個(gè)批πij的鄰域搜索。本文將后一種鄰域搜索技術(shù)引入每次的迭代更新中，采用了如下兩種鄰域結(jié)構(gòu)：

（1）互換（interchange）

將第μ維和第η維的批互相交換位置產(chǎn)生新的批序列，圖2（a）給出了將第1維所在的批與第4維所在的批執(zhí)行interchange操作前后批的排序情況。

（2）插入（insert）

移除第μ維的批并將之插入第η維。圖2（b）給出了將第1維所在的批與原第4維所在批執(zhí)行insert操作前后的批的排序情況。

圖2 變鄰域搜索的兩種鄰域結(jié)構(gòu)圖

基于以上鄰域搜索，變鄰域搜索的算法流程如圖3所示。

圖3 VNS算法流程圖

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)設(shè)計(jì)

為了測(cè)試算法的性能，以Melouk[13]等提出的方法生成隨機(jī)測(cè)試實(shí)例。該方法考慮了問題在工件規(guī)模n、工件尺寸si和工件加工時(shí)間tj三個(gè)維度的變化。其中工件尺寸和工件加工時(shí)間均服從離散均勻分布。工件按工件數(shù)分類可得到J1，J2，J3，J4，J5，J6類問題，其工件數(shù)依次為20，50，100，200，300，500；根據(jù)工件尺寸的不同范圍，問題可分為s1，s2，s3三類，尺寸區(qū)間依次為[2，4]，[4，8]，[1，10]；根據(jù)工件加工時(shí)間所取的不同范圍，問題可分為t1和t2兩類，時(shí)間區(qū)間依次為[1，10]和[1，20]。綜合上述三個(gè)維度可將具體問題表述為Jisjtk，i=1，2，…，6,j=1，2，3,k=1，2。例如：工件規(guī)模為20，工件尺寸服從[2，4]的離散均勻分布，工件加工時(shí)間服從[1，10]的離散均勻分布的實(shí)例，可表示為J1s1t10。實(shí)驗(yàn)中一共設(shè)計(jì)了36類子問題，假設(shè)每個(gè)批的最大容量均為10。這里所選的機(jī)器容量、工件加工時(shí)間以及工件尺寸代表了電子制造服務(wù)提供商的產(chǎn)品在環(huán)境應(yīng)力篩選實(shí)驗(yàn)箱中的測(cè)試活動(dòng)。

4.2 實(shí)驗(yàn)結(jié)果與分析

設(shè)微粒群算法的種群規(guī)模為9，批處理機(jī)的數(shù)量為3臺(tái)，算法終止條件為迭代次數(shù)達(dá)到100次或者全體極值連續(xù)20次無改進(jìn)?？紤]到算例的隨機(jī)性，采用200次實(shí)驗(yàn)所獲得的結(jié)果的平均值進(jìn)行比較。實(shí)驗(yàn)中分批階段的算法均采用Palmer+BF獲得初始分批，批的排序階段測(cè)試的算法包括求解實(shí)例下界LB的算法、NEH啟發(fā)式算法、標(biāo)準(zhǔn)的PSO算法以及改進(jìn)的PSO算法（表中簡(jiǎn)稱為PSOVNS），以上算法均在JDK 6.0環(huán)境下編程實(shí)現(xiàn)。測(cè)試結(jié)果如表2。

表2 各算法的測(cè)試結(jié)果

圖4 算法性能表現(xiàn)圖

在表1中，“平均”表示各算法200個(gè)算例Cmax的算術(shù)平均值；“比率”表示該平均值與算例平均下界的比率，該值越接近1則說明算法性能越好。表1的橫軸依照不同的工件尺寸范圍分為s1，s2，s3三類；縱軸按照工件規(guī)模將問題劃為6類，即J1，J2，J3，J4，J5，J6，每一類工件規(guī)模又按照工件的加工時(shí)間分為t1和t2兩類。如J1t1，表示工件規(guī)模為20且加工時(shí)間服從[2，4]離散均勻分布的情況。為了更清楚地比較各算法在以上的各個(gè)算例下的性能，給出算法性能表現(xiàn)圖如圖4。

由圖4可知，在工件規(guī)模較小時(shí)，PSO算法與NEH算法相比沒有什么優(yōu)勢(shì)，NEH算法的Cmax值優(yōu)于標(biāo)準(zhǔn)PSO算法。但隨著工件規(guī)模進(jìn)一步增大，當(dāng)規(guī)模大于200之后，PSO算法的性能逐漸超過NEH。而本文提出的PSOVNS算法由于在微粒初始化、參數(shù)設(shè)置以及gbest更新中引入不同的優(yōu)化策略，求解結(jié)果在任何情況下均優(yōu)于NEH啟發(fā)式算法和標(biāo)準(zhǔn)PSO算法。

5 結(jié)論

流水車間批調(diào)度問題的分批以及批的排序均為NP難問題，而此類問題在現(xiàn)實(shí)中有著大量實(shí)例，對(duì)此問題的求解算法研究具有重要的現(xiàn)實(shí)意義。在該問題的分批階段設(shè)計(jì)了基于Palmer+BF的分批策略，在批排序階段提出了一種基于PSO算法的優(yōu)化分配算法。在算法編碼時(shí)，構(gòu)造了基于ROV規(guī)則的排序方案；在微粒初始化時(shí)通過引入NEH啟發(fā)式算法改進(jìn)了初始解的生成質(zhì)量，采用了一種自適應(yīng)慣性權(quán)系數(shù)，并在更新gbest時(shí)引入了變鄰域搜索來提高算法的局部搜索能力，避免了過早收斂的問題。仿真實(shí)驗(yàn)表明，本文算法對(duì)問題的求解是有效的，適于應(yīng)用到生產(chǎn)實(shí)踐中。

進(jìn)一步的研究可從兩方面進(jìn)行：一是繼續(xù)研究其他的智能優(yōu)化算法在此問題的應(yīng)用，如遺傳算法、蟻群算法等，以及通過混合優(yōu)化策略，結(jié)合不同算法的優(yōu)點(diǎn)來提高求解質(zhì)量；二是在分批階段提出更好的分批策略，改進(jìn)分批的質(zhì)量，以及探討首階段分批與后階段排序的關(guān)聯(lián)性，以提高整體優(yōu)化效果。

[1]Mirsanei H S.Flow shop scheduling with two batch processing machinesandnonidenticaljobsizes[J].IntJ AdvManuf Technol，2009，45：553-572.

[2]PurushothamanD，PraveenK.MinimizingMakespanona batch-processing machine with non-identical job sizes using genetic algorithms[J].Int J Production Economics，2006，103： 882-891.

[3]Alebachew D，Kudret D.Fuzzy scheduling of job orders in atwo-stageflowshopwithbatch-processingmachines[J]. International Journal of Approximate Reasoning，2009，50：117-137.

[4]Liao L M，Huang C J.Tabu search heuristic for two-machine flowshop with batch processing machines[J].Computers and Industrial Engineering，2011，60：426-432.

[5]Ali H.An improved mixed integer linear formulation and lower bounds for minimizing Makespan on a flow shop with batch processing machines[J].Int J Adv Manuf Technol，2009，40：582-594.

[6]梁艷春，吳春國.群智能優(yōu)化算法理論與應(yīng)用[M].北京：科學(xué)出版社，2009.

[7]王凌，劉波.微粒群優(yōu)化與調(diào)度算法[M].北京：清華大學(xué)出版社，2008.

[8]Mladenovic N，Hansen P.Variable neighborhood search[J].Computer Ops Res，1997，24（11）：1097-1100.

[9]Nawaz M，Enscore E，Ham I.A heuristic algorithm for the m-machine n-job flow shop sequencing problem[J].Omega，1983，11：11-95.

[10]Uzsoy R.Scheduling a single batch processing machine with nonidentical job sizes[J].International Journal of Production Research，1994，32（7）：1615-1635.

[11]Palmer D.Sequencing jobs through a multi-stage process in the minimum total time-a quick method of obtaining a near optimum[J].Operation Research Quarterly，1965，16：101-107.

[12]Hall L A.Approximability of flow shop scheduling[C]// Proceedings of the 41st Annual Symposium on Foundations of Computer Science，Milwaukee，Wisconsin，2005：82-91.

[13]Melouk S，Damodaran P，Chang P Y.Minimizing Makespan for single machine batch processing with non-identical job sizes using simulated annealing[J].International Journal of Production Economics，2004，87（2）：141-147.

ZHU Qi,CHEN Chengdong,CHEN Huaping

School of Management,University of Science and Technology of China,Hefei 230026,China

An approach based on swarm intelligence is presented to solve the problem of scheduling tasks on flow-shop with batch processing machines.According to the characteristics of the problem under study,a method based on Palmer and Best Fit heuristic algorithm is developed to form batches.Moreover,an improved Particle Swarm Optimization（PSO）algorithm is presented to sequence the obtained batches.In PSO,the NEH heuristic is employed to improve the quality of the initial population. In order to enhance the search capabilities of the proposed algorithm,a variable neighborhood searching is performed for each iteration before the global best position is updated.The experimental results show that the proposed algorithm has a better effectiveness than the standard PSO algorithm and the NEH heuristic.

flow-shop;batch processing machines;Particle Swarm Optimization（PSO）;variable neighborhood search

針對(duì)流水車間批調(diào)度問題，提出一種基于群智能算法的求解思路。結(jié)合問題具體特點(diǎn)，給出工件集合的分批策略，設(shè)計(jì)了將Palmer和Best Fit（BF）分批規(guī)則相結(jié)合的分批方法；在批排序階段，提出了一種改進(jìn)的微粒群算法；在粒子初始生成階段，通過引入NEH啟發(fā)式算法改進(jìn)了粒子的初始化質(zhì)量；在全局最佳位置更新前，通過變鄰域搜索優(yōu)化了算法的局部搜索能力，避免了算法陷入局部最優(yōu)。仿真實(shí)驗(yàn)表明，改進(jìn)后的算法優(yōu)于傳統(tǒng)的微粒群算法和NEH啟發(fā)式算法。

流水車間；批處理機(jī)；微粒群算法；變鄰域搜索

A

TP301

10.3778/j.issn.1002-8331.1111-0048

ZHU Qi,CHEN Chengdong,CHEN Huaping.Scheduling flow-shop problem with batch processing machines and non-identical job size.Computer Engineering and Applications,2013,49（13）：221-227.

國家自然科學(xué)基金（No.70821001，No.71171184）。

朱頎（1983—），男，碩士研究生，研究領(lǐng)域：生產(chǎn)調(diào)度與智能算法；陳成棟（1985—），男，碩士研究生，研究領(lǐng)域：生產(chǎn)調(diào)度與智能算法；陳華平（1965—），博士生導(dǎo)師，中國科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院執(zhí)行院長，研究領(lǐng)域：網(wǎng)絡(luò)計(jì)算，高性能計(jì)算，智能計(jì)算及其應(yīng)用。

2011-11-10

2012-01-19

1002-8331（2013）13-0221-07

CNKI出版日期：2012-04-25http://www.cnki.net/kcms/detail/11.2127.TP.20120425.1723.093.html