差異工件流水車間批調度問題的求解

朱頎，陳成棟，陳華平

中國科學技術大學 管理學院，合肥 230026

差異工件流水車間批調度問題的求解

朱頎，陳成棟，陳華平

中國科學技術大學 管理學院，合肥 230026

1 引言

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

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

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

2 問題描述

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

（1）流水車間的每個階段均是一臺批處理機，可同時將多個工件作為一批同時進行加工；

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

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

（4）批的加工時間為批中加工時間最長的工件的加工時間；

（5）批在加工時不允許中斷；

（6）假定每個批之間存在一個無限大的緩沖區。

根據調度問題的三參數表示法，該問題可表示為Fm|B，sj| Cmax，數學模型如下：

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

3 流水車間批調度問題的求解

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

由于成批后不能加入新工件或者將批內工件移除出批，則每個批可看做一個獨立的工件，因此后續的加工問題等價于置換流水車間調度問題，即批的排序問題。當流水車間的機器數量為2臺時，可在多項式時間內得到解答，而機器數量大于2臺的情況已被證明為NP難題[12]。近年來PSO算法在求解大規模優化問題上獲得了廣泛應用和認同，本文對傳統的PSO算法進行了改進，來對批的排序進行求解。

3.1 差異工件的分批

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

Palmer算法是基于斜度指標（Slope Index）排序工件的啟發式算法。根據流水車間工件的加工順序，加工時間趨于增加的工件被賦予較大的優先權數。工件i的斜度指標（Slope Index）Si定義為：

其中，m為機器數目，pij為第i個工件在第j臺機器上的加工時間。按照Si遞減的順序對工件進行初始排序。

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

3.2 基于改進的PSO算法的批排序方法

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

圖1 算法總體結構圖

3.2.1 微粒編碼

流水車間批調度問題的編碼方式類似置換流水車間，這里采用最常用的編碼方式，即直接采用批的排序。對于批的個數為n的問題，微粒采用n維向量表示，每個批對應微粒的某一維度。由于微粒群算法的微粒的位置為連續值矢量，標準微粒群算法是無法實現批的排序更新的。因此這里構造從微粒的位置矢量到批的排序的映射機制，利用微粒的位置值的大小關系，結合隨機鍵編碼，將微粒的連續位置Xi=[xi，1，xi，2，…，xi，n]轉換為離散的加工順序π=[πi，1，πi，2，…，πi，n]，即每個批在機器上的加工順序。

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

例假設微粒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 微粒位置矢量對應的ROV值

對于每個微粒，根據其位置矢量對應的ROV值確定每個批的加工順序，在m臺機器的情況下，加工順序遵循j1，j2，…，jn的流水車間批調度問題，可由如下遞歸方程得到問題的Makespan：

其中，Ci，j1表示在機器i上第j1個批的完成時間；pi，jk表示第i臺機器上第jk個批的加工時間。

3.2.2 微粒的位置更新公式

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

其中w為慣性權系數，r1和r2為0到1的隨機數，c1和c2為正的加速常數。

3.2.3 微粒的初始化和參數設置

標準的微粒群算法通常采用隨機生成微粒的方式進行初始化。但是為了使初始種群具備一定的分散度和質量，采用目前為止性能最優的NEH啟發式方法對種群進行初始化，種群規模設置為微粒維度的3倍。

NEH啟發式算法假定在所有機器上的總加工時間越長的工件，比總加工時間短的工件具有更高的優先級，具體步驟如下：

（1）按照在所有機器上總加工時間遞減的順序排列n個批。

（2）選擇前兩個批進行排序，直到在只有兩個批的情況下獲得最小的局部Makespan的排序為止。

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

利用NEH啟發式算法產生第一個微粒的初始位置：

由于NEH算法得到的是批的排序，因此必須轉化為對應的位置矢量才能夠參與微粒群算法的進一步進化搜索。因此按照如下方式實現轉換：

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

其余的微粒的位置矢量在一定連續區間內隨機生成。

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

其中xmin=0，xmax=4.0。

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

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

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

其中wmax和wmin分別為w的最大值和最小值，f為微粒當前的目標值函數，favg和fmin分別為微粒的平均值和最小目標值。

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

3.2.4 引入變鄰域搜索改進gbest搜索機制

為了改進微粒群算法的局部搜索能力較差，容易陷入局部極小解的問題，這里在微粒每次更新中引入變鄰域搜索算法，利用其無需設置參數，實現簡單的特性，對微粒每次迭代更新時獲得的gbest運用多個鄰域結構進行搜索以獲得新的gbest，從而提高了搜索的質量和效率。

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

（1）互換（interchange）

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

（2）插入（insert）

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

圖2 變鄰域搜索的兩種鄰域結構圖

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

圖3 VNS算法流程圖

4 仿真實驗

4.1 實驗設計

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

4.2 實驗結果與分析

設微粒群算法的種群規模為9，批處理機的數量為3臺，算法終止條件為迭代次數達到100次或者全體極值連續20次無改進。考慮到算例的隨機性，采用200次實驗所獲得的結果的平均值進行比較。實驗中分批階段的算法均采用Palmer+BF獲得初始分批，批的排序階段測試的算法包括求解實例下界LB的算法、NEH啟發式算法、標準的PSO算法以及改進的PSO算法（表中簡稱為PSOVNS），以上算法均在JDK 6.0環境下編程實現。測試結果如表2。

表2 各算法的測試結果

圖4 算法性能表現圖

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

由圖4可知，在工件規模較小時，PSO算法與NEH算法相比沒有什么優勢，NEH算法的Cmax值優于標準PSO算法。但隨著工件規模進一步增大，當規模大于200之后，PSO算法的性能逐漸超過NEH。而本文提出的PSOVNS算法由于在微粒初始化、參數設置以及gbest更新中引入不同的優化策略，求解結果在任何情況下均優于NEH啟發式算法和標準PSO算法。

5 結論

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

進一步的研究可從兩方面進行：一是繼續研究其他的智能優化算法在此問題的應用，如遺傳算法、蟻群算法等，以及通過混合優化策略，結合不同算法的優點來提高求解質量；二是在分批階段提出更好的分批策略，改進分批的質量，以及探討首階段分批與后階段排序的關聯性，以提高整體優化效果。

[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]梁艷春，吳春國.群智能優化算法理論與應用[M].北京：科學出版社，2009.

[7]王凌，劉波.微粒群優化與調度算法[M].北京：清華大學出版社，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

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

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

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.

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

朱頎（1983—），男，碩士研究生，研究領域：生產調度與智能算法；陳成棟（1985—），男，碩士研究生，研究領域：生產調度與智能算法；陳華平（1965—），博士生導師，中國科學技術大學計算機科學與技術學院執行院長，研究領域：網絡計算，高性能計算，智能計算及其應用。

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