基于離散候鳥遷徙優化算法的置換流水車間調度問題

張素君,　顧幸生

(1.河南科技學院機電學院,河南 新鄉 453003; 2.華東理工大學化工過程先進控制和優化技術教育部重點實驗室,上海 200237)

?

基于離散候鳥遷徙優化算法的置換流水車間調度問題

張素君1,2,顧幸生2

(1.河南科技學院機電學院,河南 新鄉 453003; 2.華東理工大學化工過程先進控制和優化技術教育部重點實驗室,上海 200237)

針對置換流水車間調度問題,以最小化最大完成時間為調度目標,提出了一種離散候鳥遷徙優化(Discrete Migrating Birds Optimization,DMBO)調度算法。采用NEH產生一個調度可行解,其余個體隨機產生,保證了種群的質量和多樣性,初始化鳥群按優化目標值升序排成倒V字形。領飛鳥通過優化插入加優化交換產生的鄰域解進化,而通過混合策略獲得跟飛鳥的鄰域解。跟飛鳥通過其鄰域解和前面個體未使用的、較好的鄰域解進化,這種進化機制是獨一無二的。最后,采用局部搜索算法進一步優化種群。仿真實驗中使用正交設計方法調節算法參數,通過求解Car 和Rec標準算例,驗證了算法的有效性。

置換流水車間調度問題; 離散候鳥遷徙優化算法; 破壞重建; 優化插入加優化交換操作

流水車間調度問題已經被研究了六十多年,尤其是優化目標為最小化最大完成時間的流水車間調度問題更是吸引了很多學者的關注。該問題能吸引這么多學者關注是因為它在實際生產生活中的廣泛應用,多數的制造業加工過程都可以建模為流水車間調度問題[1],并且已經被證明是NP難問題[2]。置換流水車間調度問題(Permutation Flow Shop Scheduling Problem,PFSP)可以描述為n個工件在m臺機器上按照相同順序加工的過程。求解該問題的方法很多,采用精確算法優化大規模問題計算時間較長,甚至得不到最優解,后來學者提出一些啟發式算法[3-4],通過一步或者三步構造調度解。一步算法是直接根據經驗構造,三步操作是產生排序、調度解的構造、調度解的改進。為了提高構造解的質量還提出了混合啟發式算法[5],它混和了多種啟發式算法。啟發式算法和混合啟發式算法的共同點是能夠在有限的時間內構造出調度解,但不能保證調度解的質量。為了平衡調度解的質量和時間成本,近年來,各類智能優化算法也廣泛地應用于求解置換流水車間調度問題,它可以彌補精確算法和啟發式算法的不足。其中遺傳算法[6]、模擬退火算法[7]、粒子群算法[8-10]、差分進化算法[11]、人工蜂群算法[12]、果蠅優化算法[13]及這些算法的改進、混合等已經被成功應用于置換流水車間調度問題。

Duman[14]在2012年提出了一種智能優化算法——候鳥遷徙優化 (Migrating Birds Optimization,MBO) 算法,并應用于二次分配問題。該算法模擬候鳥遷徙時采用倒V字形編隊飛行可以節省能量的思想實現優化。該算法已成功應用在混合流水車間調度[15]和信用卡欺詐檢測[16]等優化問題中,是一種新穎的群智能算法。由于它提出的時間較短并且有較好的優化性能,相關的研究在國內還比較少,在各個領域的應用還具有較大的研究空間。本文針對置換流水車間調度問題提出了離散候鳥遷徙算法。

1　置換流水車間調度問題

把n個工件在m臺機器上按照相同的順序加工的調度問題稱為置換流水車間調度問題。n個工件中每一個工件必須在每臺機器上進行加工,即每個工件有m個加工步驟,分別在m臺機器上完成,并且不同的工件在機器上的加工順序相同。置換流水車間調度問題的求解是找到較好的工件加工順序(調度解),使某個優化指標的目標值在所有可行的調度解中最小。

式中Pπ(i),j,Cπ(i),j分別表示工件π(i)在機器j上的加工時間和加工完成時間。式(1)表示第1個工件在第1臺機器上的加工完成時間C(π(1),1)等于它的加工時間Pπ(1),1;式(2)表示某一工件π(i)在第1臺機器上的加工完成時間等于前一個工件π(i-1)在第1臺機器上的加工完成時間加上該工件在第1臺機器上的加工時間;式(3)描述了第1個工件π(1)在第j臺機器上的加工完成時間;式(4)給出工件π(i)(i∈{2,3,…,n})在機器j(j∈{2,3,…,m})上的加工完成時間,當i=n,j=m時求得C(π(n),m)即為該調度解π的最大完成時間Cmax(π)。依據上述方法求出集合Π中所有調度解的最大完成時間,找到完成時間最小的調度解π*。

2　基本候鳥遷徙優化(MBO)算法

受候鳥遷徙時排成倒V字形這一自然現象啟發Duman提出了候鳥遷徙優化 (MBO)[14]算法。經過分析,排成倒V字形的原因一是因為節省能量,二是鳥群之間的視覺關系以及避免相互碰撞。生物學家研究表明,影響節省能量程度的參數主要有兩個:鳥群中每只鳥與前一只鳥翅尖之間的橫向距離,它決定了V字形的開度;另一個參數為候鳥中鳥之間的縱向距離。算法中鳥群中的每只鳥對應優化問題的一個解,每個解都可以得益于前面個體。算法開始于倒V字形的一種隨機排列,其中第1個解對應領飛鳥,其余的排在兩邊的是跟飛鳥,進化過程中每只鳥(解)都在其鄰域內進行搜索,搜索到的鄰域解若優于當前解,則替換,同時較好的、未使用的鄰域解存到某個集合中供跟飛鳥進化時使用。每只跟飛鳥通過其自身的鄰域解以及前面個體未使用的、較好的鄰域解進化,若它們中最優的優于當前解,則替換,直到所有的個體都完成進化。這樣的過程經過幾次巡回,更新領飛鳥。MBO算法在國內外的研究還處于起步階段,文獻較少,因此如何設計算法使之適應于解決各類優化問題,以及算法中參數的設計是值得研究的問題,并且有很大的研究空間。

候鳥遷徙算法的偽代碼如下:

Generateninitial solutions and place them on an hypothetial V formation arbitrarily

ForT=1:Genmax

Forg=1:G

Fori=1:S

進化領飛鳥,通過領飛鳥的鄰域解;

進化跟飛鳥,通過跟飛鳥的鄰域解和前面個體鄰域解中未使用的較好的鄰域解;

End For

End For

更新領飛鳥;

End For

其中：T和Genmax分別為進化代數和最大進化代數；G為巡回次數；S為種群規模。

MBO算法不同于其他群智能算法表現在以下幾方面:(1) 并行搜索。并行解進化方式可以擴大搜索范圍,更容易搜索到全局最優解。(2) 個體進化機制。該算法的個體進化機制是目前群智能算法中獨一無二的。每個個體不僅在其鄰域內搜索較優的解,還可以利用前面個體產生的未使用的、較優的鄰域解來更新個體。這種進化機制使得種群中的個體不僅并行優化,個體之間還會分享較優的解,增加了算法的全局搜索能力。(3)一定的巡回次數后,更新領飛鳥,增加算法的局部搜索能力，每個個體都會在它的鄰域內充分搜索。

從MBO算法的進化過程來看,它適用于流水車間調度這種組合優化問題。

3　求解置換流水車間調度問題的離散候鳥遷徙優化(DMBO)算法

3.1編碼與種群初始化

用工件排序進行離散編碼,π={π(1),π(2),…,π(n)}。若π={2,5,3,1,4}是1個5工件的調度解,表明工件加工順序依次是2,5,3,1,4。

為了兼顧種群的質量和多樣性,初始化中利用NEH初始化領飛鳥,其余的個體隨機產生。已經證明NEH[4]是一種性能較好的啟發式算法,特別是調度目標為最大完成時間的流水車間調度問題,因此常用來初始化種群。NEH算法描述如下:

(2) 根據優化指標調度排列中的前兩個工件,得到較優的部分調度解,作為當前部分調度解;

(3) 將步驟(1)排列中的第i(i=3,4,…,n)個工件依次插入到當前部分調度解的所有可能位置,找出較優的調度解作為當前的部分調度解,直到所有的工件調度完。

將得到的種群按照優化指標(makespan)升序排列,其中最小的作為領飛鳥,其余偶數序號的個體依次放在左邊隊列Ll,奇數序號的個體依次放在右邊隊列Lr,使種群中的個體排成倒V字形。

3.2領飛鳥的進化

在流水車間調度問題中,常用的鄰域解產生方式有3種,其中插入和交換較為有效。假設有n個工件待加工。

插入操作:假設把工件排列中的第v個工件插入到位置w。

ifv

πnew={π(1),…,π(v-1),π(v+1),…,π(w),π(v),π(w+1)，…，π(n)}

ifv>w,則

πnew={π(1),…,π(w-1),π(v),π(w),…,π(v-1),π(v+1)，…，π(n)}

交換操作:交換排列中任意兩個工件的加工順序。

ifv

πnew={π(1),…,π(v-1),π(w),π(v+1),…,π(w-1),π(v),π(w+1)，…，π(n)}

ifv>w,則

πnew={π(1),…,π(w-1),π(v),π(w+1),…,π(v-1),π(w),π(v+1)，…，π(n)}

DMBO算法中領飛鳥的更新是利用本身的鄰域解,其鄰域解中未使用的較優解供跟飛鳥進化時使用,領飛鳥的鄰域解質量對算法的效果影響較大,因此,采用優化插入加優化交換操作。

優化插入操作:

(1) 從當前工件序列中隨機選擇一個工件π(v),并從原序列中刪除,得到部分序列;

(2) 把該工件插入到部分序列中的n個可能位置上,得到n個新的排列;

(3) 根據優化目標,把n個新的排列中最優的一個,作為優化插入后的序列。

優化交換操作:

(1) 隨機從工件序列中選擇一個工件π(v),并把該工件與原序列中的任一工件交換位置,可以得到n-1個新的排列;

(2) 依據優化目標,找到n-1個新的排序和原序列共n個序列中最好的排序,作為優化交換后的序列。

優化插入加優化交換操作中優化交換的對象為優化插入作用后得到的序列。領飛鳥進化采用優化插入加優化交換產生k個鄰域解。若這k個鄰域解中的最優解優于當前領飛鳥,則用這個最優解替換當前領飛鳥,并將未使用的2x個最優的鄰域解中x個填入集合PL，另外x個填入集合PR，其中PL和PR為左右兩邊存放該個體鄰域解中未使用的最優解的集合。

3.3跟飛鳥的進化

跟飛鳥通過鄰域解及前面個體鄰域解中未使用的較優鄰域解進化。為保證鄰域解的質量和多樣性,每個鄰域解采用以下混合策略之一產生。混合策略操作包括插入、交換和破壞重建操作,用Si表示。而插入和交換的次數p(擾動程度)對鄰域解的質量影響很大。破壞重建(Destruction-Construction)操作是迭代貪婪算法(Iterated Greedy,IG)[17]的核心操作,也是較為有效的產生鄰域解的方法。

S1:執行插入操作1次(p=1);

S2:執行交換操作1次(p=1);

S3:執行插入操作2次(p=2);

S4:執行交換操作2次(p=2);

S5:執行插入操作3次(p=3);

S6:執行交換操作3次(p=3);

S7:執行破壞重建操作。

破壞重建操作[17]的步驟如下:

(1) 從排序π中不重復地隨機選出d個工件,組成部分序列πd,并把這d個工件從原序列中刪除,其余工件組成的序列稱為πr;

(2) 把πd中的第1個工件插入到πr中的所有可能位置,依據優化指標找出最好的,更新πr,同時把πd中的第1個工件刪除,更新πd;

(3) 如果πd不為空,轉到步驟 (2),否則結束,πr即為經過破壞重建操作的一個完整調度解。其中d為對調度解的破壞程度,因此,d的選擇將會對算影響較大。

對于個體π∈Ll,采用混合策略操作產生k-x個鄰域解,即{π(1),π(2),…,π(k-x)},集合NZ={π(1),π(2),…,π(k-x)}∪PL中最優解如果優于π則替換,清空PL,并用NZ中未使用的x個最優解填充。

對于個體π∈Lr,采用多策略操作產生k-x個鄰域解,即{π(1),π(2),…,π(k-x)},集合NY={π(1),π(2),…,π(k-x)}∪PR中的最優解如果優于π,則替換,清空PR,并用NY中未使用的x個最優解填充。

3.4領飛鳥的更新

領飛鳥和所有跟飛鳥進化一定的巡回次數后,更新領飛鳥,用標志F0表示是用左邊隊列第1個跟飛鳥替換領飛鳥還是用右邊替換。若F0=1,則用左邊的替換領飛鳥,而原來的領飛鳥移到左邊隊列的最后一個,左邊隊列的其他鳥依次前移一個位置,并且置F0=0;若F0=0,用右邊第1個替代領飛鳥,原來的領飛鳥到右邊隊列的最后一個,右邊隊列的其他個體依次前移一個位置,并且置F0=1。

3.5種群重置

為了避免算法陷入局部最優,本文設計了一種重置機制。如果鳥群中的最優個體超過limit代沒有更新,種群將會被重置。重置個體如果隨機產生,前面的進化結果將不起作用,導致算法收斂速度下降。一般認為最優個體攜帶著較好的信息,因此對最優個體執行2次交換(SWAP)操作來產生種群中的個體,這樣,既保留了原來進化得到的較好信息,也兼顧了種群的多樣性。

3.6局部搜索

局部搜索是為了增強算法的局部搜索能力,在領飛鳥和跟飛鳥都完成進化后,對鳥群中的個體執行破壞重建，進行局部搜索,如果得到的解優于原解,則替換,否則保留原解。

3.7離散候鳥遷徙優化(DMBO)算法流程

離散候鳥遷徙優化(DMBO)算法流程見圖1。

圖1　離散候鳥遷徙算法流程圖Fig.1　Flow chart of discrete migrating birds algorithm

4　仿真實驗

4.1仿真環境和算例

仿真實驗硬件環境為Intel Core(TM) i7-4770k/3.5 GHz/8.0 GB,軟件平臺為Windows 8系統,所有算法均采用Matlab R2012b編寫。

仿真實驗通過測試國際標準算例Car[18]和Rec[19]來測試本文算法的參數以及性能,其中Car算例有8個不同規模,而Rec標準算例包含21個不同規模。

4.2參數調節

智能優化算法中的參數設置對算法的優化效果影響很大,為了保證算法在其最佳的狀態下運行,需要對參數合理設置。在DMBO算法中,鳥群規模S=51,每個個體進行鄰域搜索時產生的鄰域解數量k=3,傳遞給下一個體的鄰域解數量x=1;然而巡回次數G,破壞重建操作中的破壞程度d,最優解持續不變的最大代數limit以及混合策略中的插入和交換擾動程度p也會對算法的效果造成影響。運用正交試驗法對上述4個參數調節,4個參數設為4個因素,每個因素有3個水平,如表1所示。

表1　正交試驗因素/水平表Table 1　Factors and levels for orthogonal experiment

用正交試驗法對DMBO算法中的4個參數調節,只需測試32=9組參數值,就能得到每個參數的最佳設置值,但如果對全部參數組合進行測試,需要34=81組實驗,據此,采用正交試驗法選擇參數可以提高效率。

本文通過對中等規模的算例Rec29進行正交試驗來測試參數。表2列出正交設計表L9(34)以及得到的正交試驗結果,算法中的參數分別設置為表2中的參數組合,每組實驗獨立運行10次,共需測試9×10=90次算法。表2中的最后一列為該組參數得到的算法10次運行最大完成時間(makespan)的平均值AVG。k1,k2,k3對應各個參數在3個水平上測試結果的平均值。SD為標準差(Standard Deviation,SD),每個參數的k1到k3的標準差列于最后一行。k1,k2,k3中每一列的最小值對應的水平為該因素較好的選擇,并在表中以黑體標出。SD值較大的因素,對算法的影響也較大,SD值的排列按降序排列,序號置于對應的值后的括號內。4個參數在不同水平的變化曲線圖如圖2所示。

表2　L9(34)正交表和實驗結果Table 2　Orthogonal parameter table L9(34) and results

圖2　DMBO算法中4個參數在3個水平的變化趨勢圖Fig.2　Trend graph of 4 parameters at 3 levels in HDABC algorithm

由表2和圖2可知,由于d的SD最大，因此破壞程度d對算法性能影響最大,而limit影響最小,G如果選擇太大將會使算法復雜度大大增加,因此在不影響算法效果的前提下,兼顧算法復雜度選擇G=10,其余參數選擇p=3,d=8,limit=5時算法效果較好。

4.3測試算法性能

為測試本文算法DMBO在求解PFSP時的效果,將DMBO算法與文獻[11]和文獻[12]中解決同一問題的算法進行對比,2個算法分別是混合差分進化算法(HDE)和混合離散果蠅算法(HDFOA)。同時為了驗證加入種群重置后的效果,還列出了NDMBO算法的測試結果，如表3所示。表中BRE為最優百分偏差,ARE為平均百分偏差,計算公式如式(6)和式(7)所示。SD為10次測試結果的標準差,如式(8)所示。

(6)

(7)

(8)

式(6)和式(7)中，C*為makespan理論最優值,Cmin和CAVG分別為10次測試結果的最小值和平均值。

表3列出了針對3個相同指標4個算法的對比結果,對相同指標4個算法得到的最小目標值用黑體標出。可以看出,DMBO和NDMBO算法具有較好的優化效果,但是計算時間比HDFOA和HDE算法的計算時間略長。DMBO和NDMBO相比,加入種群重置機制可以使算法跳出局部最優,收斂到更好的目標值。圖3示出了4種算法測試Car和Rec算例中的最大規模算例Rec41的收斂曲線,從4條曲線的收斂速度以及最后達到的收斂精度可以看出,DMBO和NDMBO相比,DMBO能搜索到更好的目標值,二者收斂速度相當。而在本算例上HDFOA要比HDE差些,但對其他大部分算例,>HDFOA要優于HDE,這點從表3不難看出,但兩者都略差于本文提出的算法。

圖3　算例Rec41的4個算法收斂曲線圖Fig.3　Convergence curves of instance Rec41表3　NDMBO/DMBO/HDFOA/HDE算法對比結果Table 3　Comparison results of NDMBO,DMBO,HDFOAand HDE

問題n,mNDMBODMBOHDFOA[13]HDE[11]BRE/%ARE/%SDBRE/%ARE/%SDBRE/%ARE/%SDBRE/%ARE/%SDCar111,5000000000000Car213,4000000000000Car312,500000000000.5444.35Car414,4000000000000Car510,600000000000.5949.54Car68,900000000000.1527.41Car77,700000000000.4560.22Car88,8000000000000Rec0120,500.140.6000000.100.9800.150.45Rec0320,500000000000.151.25Rec0520,500.191.2000.051.2000.220.770.240.383.33Rec0720,1000000000000.927.59Rec0920,1000000000000.2711.60Rec1120,10000000000000Rec1320,150.100.182.2900.020.8000.191.700.260.718.57Rec1520,1500000000.121.900.051.0014.96Rec1720,1500.07000000.042.100.371.3111.87Rec1930,100.280.2900.240.280.300.290.514.060.290.919.10Rec2130,100.151.317.800.140.1500.451.395.160.201.289.17Rec2330,100.150.372.460.100.212.100.350.602.820.500.7010.63Rec2530,150.200.483.4300.203.140.401.157.940.681.4316.49Rec2730,150.130.688.360.000.264.660.341.005.350.841.204.60Rec2930,150.090.345.570.000.112.800.480.954.800.531.3013.34Rec3150,100.260.422.300.260.270.300.851.357.970.431.2013.11Rec3350,100000000.030.404.760.350.794.74Rec3550,10000000000000Rec3775,201.391.6510.931.071.4712.532.182.8512.201.702.6333.41Rec3975,200.881.054.770.690.945.701.201.8512.781.281.547.86Rec4175,201.351.7217.330.911.3316.842.462.9413.301.712.6236.39Average0.170.312.310.120.181.740.310.543.050.330.7713.79

綜上,就求解PFSP問題而言,本文提出的DMBO算法具有一定的有效性和優越性,由于候鳥遷徙算法的并行搜索以及個體之間的利益共享機制使該算法具有較強的局部和全局搜索能力。

5　結　論

針對置換流水車間調度問題(PFSP),本文提出了離散候鳥遷徙優化算法優化工件的最大完成時間。初始化采用NEH,提高初始化種群質量。進化過程分為領飛鳥進化和跟飛鳥進化兩個階段,領飛鳥進化通過其鄰域解,跟飛鳥進化通過其鄰域解以及前面個體鄰域解中未使用的、較好的鄰域解。進化過程經過一定的巡回次數后,更新領飛鳥,每個個體都在其鄰域內充分搜索,提高了算法的局部搜索能力。實驗結果驗證了DMBO算法的優化能力,利用該算法求解,大部分算例幾乎都能找到最優解,個別找不到最優解的算例,也找到了比其他算法更接近最優解的次優解。下一步的研究重點是將離散候鳥遷徙優化算法進一步改進應用在其他調度問題中,并致力于降低算法的復雜度。

[1]MOHAMMAD M.A novel hybrid genetic algorithm to solve the sequence-dependent permutation flow-shop scheduling problem[J].The International Journal of Advanced Manufacturing Technology,2014,71(1/4):429-437.

[2]GAREY M R,JOHNSON S,SETHY R.The complexity of flow shop and job-shop scheduling[J].Mathematics of Operations Research,1976,1(2):117- 129.

[3]唐聃,黃健.流水車間調度問題的啟發式算法研究[J].電子科技大學學報,2013,42(6):921-925.

[4]NAWAZ M,ENSCORE J E,HAM I.A heuristic algorithm for them-machine,n-job flow-shop sequencing problem[J].Omega,1983,11(1):91-95.

[5]ZOBOLAS G I,TARANTILIS C D,IOANNOU G.Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm[J].Computers & Operations Research,2009,36(4):1249-1267.

[6]凃雪平,施燦濤,李鐵克.求解流水車間調度問題的改進遺傳算法[J].計算機工程與應用,2009,45(36):50-53.

[7]PEMPERA J,SMUTNICKI C,ZELAZNY D.Optimizing bicriteria flow shop scheduling problem by simulated annealing algorithm[J].Procedia Computer Science,2013,18:936-945.

[8]KUO I H,HORNG S J.An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model[J].Expert Systems with Applications,2009,36(3):7027-7032.

[9]楊子江,顧幸生.基于混沌量子粒子群算法的置換流水車間調度[J].華東理工大學學報(自然科學版),2013,39(3):325-330.

[10]劉延風,劉三陽.改進微粒群優化求解置換流水車間調度問題[J].計算機集成制造系統,2009,15(10):1968-1972.

[11]QIAN Bin,WANG Ling.A hybrid differential evolution method for permutation flow-shop scheduling[J].The International Journal of Advanced Manufacturing Technology,2008,38(7):757-777.

[12]LIU Yangfeng,LIU Sanyang.A hybrid discrete artificial bee colony algorithm for permutation flow shop scheduling problem[J].Applied Soft Computing,2013,13(3):1459-1463.

[13]鄭曉龍,王陵,王圣堯.求解置換流水線調度問題的混合離散果蠅算法[J].控制理論與應用,2014,31(2):159-164.

[14]DUMAN E,UYSAL M,ALKAYA A F.Migrating birds optimization:A new metaheuristic approach and its performance on quadratic assignment problem[J].Information Sciences,2012,217:65-77.

[15]PAN Quanke,YAN Dong.An improved migrating birds optimization for a hybrid flow shop scheduling with total flow time minimization[J].Information Sciences,2014,277:643-655.

[16]DUMAN E,ELIKUCUK I.Solving credit card fraud detection problem by the new metaheuristics migrating birds optimization[C]//Proceedings of 12th International Work-Conference on Artificial Neural Networks:Advances in Computational Intelligence.Spain:Springer,2013:62-71.

[17]RUIZ R,STüTZLE T.A simple and effective iterated greedy algorithm for the permutation flow shop scheduling problem[J].European Journal of Operational Research,2007,177(3):2033-2049.

[18]CARLIER J.Ordonnancements a contraintes disjonctives[J].Rairo IRO-Operations Research-Recherche Opérationnelle,1978,12(4):333-350.

[19]REEVES C R.A genetic algorithm for flow shop sequencing[J].Computers & Operations Research,1995,22(1):5-13.

A Discrete Migrating Birds Optimization Algorithm for Permutation Flow Shop Scheduling Problem

ZHANG Su-jun1,2,GU Xing-sheng2

(1.School of Mechanical and Electrical Engineering,Henan Institute of Science and Technology,Xinxiang 453003,Henan,China; 2.Key Laboratory of Advanced Control and Optimization for Chemical Process,Ministry of Education,East China University of Science and Technology,Shanghai 200237,China)

In this work,a discrete migrating birds optimization (DMBO) scheduling algorithm is proposed for permutation flow shop scheduling problem (PFSP) with the objective of minimizing maximum completion time (i.e. makespan).In order to guarantee the quality and diversity of the flock, NEH is employed to yield a feasible solution and the others are generated randomly in DMBO algorithm.The flock are arranged in the reversed hypothetical V formation according to the ascending order of optimization value.The leader is evolved from the neighbor solutions which are generated by optimizing insertion and swap operators.Meanwhile,the other birds in the flock are evolved by their neighbor solutions generated by hybrid-strategy and the unused better neighbor solutions of the previous generated by hybrid-strategy individuals.This evolution mechanism is unique for migrating birds optimization algorithm.Furthermore,a local search procedure is performed on every individual.Finally,an orthogonal design method is employed in experiment to regulate the parameters of DMBO.By testing the Car and Rec benchmarks,it is shown that the proposed DMBO algorithm is effective in the performance.

permutation flow shop scheduling problem; discrete migrating birds algorithm; destruction and construction; optimized insertion and optimized swap operators

A

1006-3080(2016)03-0412-08

10.14135/j.cnki.1006-3080.2016.03.019

2015-09-29

國家自然科學基金(61174040,61573144)

張素君(1978-),女,河南湯陰人,講師,主要研究方向為生產調度和智能優化算法。E-mail:sujunzh111@126.com

通信聯系人：顧幸生,E-mail:xsgu@ecust.edu.cn

F273