李知聰，顧幸生（華東理工大學(xué)化工過程先進控制與優(yōu)化技術(shù)教育部重點實驗室，上海 200237）

?

改進的生物地理學(xué)優(yōu)化算法在混合流水車間調(diào)度中的應(yīng)用

李知聰，顧幸生
（華東理工大學(xué)化工過程先進控制與優(yōu)化技術(shù)教育部重點實驗室，上海 200237）

摘要：調(diào)度問題是將有限的資源分配給各項不同任務(wù)的決策過程，其目的是優(yōu)化一個或多個目標，它廣泛存在于當今大多數(shù)的制造和生產(chǎn)系統(tǒng)中?；旌狭魉囬g調(diào)度問題是一般流水車間調(diào)度問題的推廣，更接近實際的生產(chǎn)過程。采用一種新型的算法——生物地理學(xué)優(yōu)化算法求解混合流水車間調(diào)度問題，通過引入改進策略，增強了算法的全局搜索能力和局部搜索能力，并提高了算法的收斂速度。通過10個標準調(diào)度算例的仿真研究，并與遺傳算法進行對比，驗證了改進后的生物地理學(xué)優(yōu)化算法在求解混合流水車間調(diào)度問題方面的優(yōu)越性。

關(guān)鍵詞：生產(chǎn)調(diào)度；混合流水車間；生物地理學(xué)優(yōu)化算法；向量編碼；深度搜索

2015-12-11收到初稿，2015-12-18收到修改稿。

聯(lián)系人：顧幸生。第一作者：李知聰（1992—），男，碩士研究生。

引 言

混合流水車間調(diào)度問題(hybrid flow-shop scheduling problem, HFSP)是流水線調(diào)度與并行機調(diào)度的結(jié)合，又被稱為多處理單元調(diào)度問題或者柔性流水車間調(diào)度問題(flexible flow-shopschedulingproblem, FFSP)[1]，最早由Salvador[2]在1973年基于石油工業(yè)背景提出。HFSP具有很強的工業(yè)背景，廣泛存在于石油、化工、紡織、造紙、機械、物流等領(lǐng)域。

在HFSP問題中，每一個工件都必須以相同的順序依次通過各個階段進行加工，每一個階段都存在一臺或多臺機器，并且至少有一個階段存在一臺以上的并行機[3]。已經(jīng)證明，即便是只有兩道工序的混合flow-shop調(diào)度問題也是NP-難問題，一般采用啟發(fā)式算法對解空間尋優(yōu)以得到最優(yōu)調(diào)度方案[4]。Simon[5]在2008年提出了生物地理學(xué)優(yōu)化算法(biogeography-based optimization, BBO)。Bhattacharya 等[6]采用差分進化算法改進BBO算法，并用于求解負荷經(jīng)濟調(diào)度問題。Rarick等[7]利用BBO算法求解潮流優(yōu)化問題，并與遺傳算法比較，驗證了BBO算法的優(yōu)越性。

基本BBO算法存在局部搜索能力較差、收斂速度緩慢、在規(guī)定迭代次數(shù)中難以得到最優(yōu)解等缺點[8]。針對以上問題，本文設(shè)計了3種改進策略，分別是使用NEH規(guī)則初始化棲息地、改進BBO算法的遷入率和變異率以及融入鄰域搜索算法。仿真結(jié)果驗證了改進的BBO算法求解混合流水車間調(diào)度問題的有效性。

1 混合flow-shop調(diào)度問題

1.1 問題的描述

混合flow-shop調(diào)度問題的描述如下[9]：有n個工件J={1,2,…,i, …,n-1,n}在s道串行工序上進行加工。在第j道工序中，有mj臺并行機，如圖1所示。這些并行機完全相同，可以一直使用，不會損壞。根據(jù)混合flow-shop定義可知，每道工序存在一臺或一臺以上的加工機器，至少有一道工序存在一臺以上的加工機器，即至少有一個mj滿足mj＞1。每個工件按照給定的加工順序進行加工，每道工序上只需在任意一臺并行機上進行加工。在任何時刻，每臺機器最多只能加工一個工件，每個工件最多只能在一臺機器上加工。工件i在工序j上的加工時間設(shè)為pi,j。任意兩道工序之間中間儲存無限，不需要等待。加工任務(wù)不存在優(yōu)先級。加工過程中不允許中斷。調(diào)度的目標是確定各個工件在各道工序上的加工順序，并確定各工件在哪一臺并行機上進行加工，該問題的一般優(yōu)化目標是使得最大完成時間makespan最小。

圖1 HFSP調(diào)度問題示意圖Fig 1 Hybrid flow shop scheduling problem

1.2 問題的數(shù)學(xué)模型

求解混合flow-shop調(diào)度問題的過程中，需要考慮一個關(guān)鍵的問題，那就是如何定義一個解的結(jié)構(gòu)，從而保證算法在迭代過程中產(chǎn)生的新解都是可行的調(diào)度解[10]。本文采用向量編碼方式，這種編碼方式只考慮整個加工過程中第一道工序的工件排列順序，即只用一個工件排列代表整個加工過程。雖然它只考慮了工件在第一道工序的排列順序，但是卻有很好的效果，而且做到了算法解和問題解之間的一一對應(yīng)。更為重要的是，向量編碼方式非常簡單，易于操作變換。

本文采用向量編碼方式，通過表調(diào)度（list scheduling，LS）算法實現(xiàn)由向量解到完整的可行調(diào)度解的轉(zhuǎn)化[11-12]。此算法依據(jù)先到先得（firstcome-first-service）的原則，即在前一道工序先完工的工件，在下一道工序中優(yōu)先加工。最小化最大完成時間的數(shù)學(xué)模型如下所示

Subject to

其中，πj表示第j道工序的工件排序； πk(i)表示工件排序πk的第i個工件；Cπk(i),j表示工件πk(i)在第j道工序的完成時間；IMi,j表示第j道工序中機器i的空閑時間；NMj表示第j道工序中最早可用的機器號；argmkin{IMk}表示k個IM中最小個體的編號；函數(shù)sj(i)=g(sj?1(i))(i=1,2,…,n)定義為在第j道工序中i(i=1,2,…,n)的一個排序，i的排序根據(jù)第j-1道工序中的sj?1(i)值按升序排列。

2 基本BBO算法

2.1 BBO算法的設(shè)計原理

生物物種生活在不同的棲息地，每個棲息地的適宜度指數(shù)（habitat suitability index, HSI）是不同的，與HSI相關(guān)的特征包括棲息地的降雨量、植被的多樣性、地質(zhì)的多樣性和氣候等因素，這些特征變量構(gòu)成了一個描述棲息地適宜度的向量SIV(suitable index vector, SIV)[13]。BBO算法用于求解優(yōu)化問題時，將問題的可行解看作一塊棲息地的SIV，通過計算該棲息地的HSI評價解的優(yōu)劣。通過不同棲息地之間物種的遷移和棲息地內(nèi)物種的變異，使較差棲息地獲得更多較好棲息地的信息，實現(xiàn)棲息地的不斷進化[14]。

2.2 BBO的遷移操作

BBO算法通過遷移算子實現(xiàn)棲息地之間的信息交互，從而實現(xiàn)對整個解空間的搜索。適宜度較高的棲息地擁有較多的物種，適宜度較低的棲息地擁有較少的物種。這就需要建立一個表征物種數(shù)量與棲息地適宜度關(guān)系的映射函數(shù)[15]。BBO算法先根據(jù)各棲息地適宜度高低對棲息地由高到低進行排序，設(shè)棲息地數(shù)量為h，最大物種數(shù)Qmax，則棲息地u的物種數(shù)量Q(u)=Qmax?u，u=1,2,…,h (u是各棲息地經(jīng)過排序后的標號)。各棲息地遷入率和遷出率的計算公式如式(7)、式(8)所示。從式中可以看出棲息地的遷入率與其物種數(shù)量呈反比，而遷出率與其物種數(shù)量呈正比[16]。

其中，λ(u)表示棲息地u的遷入率，μ(u)表示棲息地u的遷出率，I表示最大遷入概率，E表示最大遷出概率。

2.3 BBO算法變異操作

災(zāi)難性事件，如自然災(zāi)害和瘟疫等能夠徹底摧毀一個棲息地的生態(tài)環(huán)境，打破該棲息地物種之間的平衡。一個棲息地的適宜度值會因為這種隨機事件發(fā)生劇烈的變化。BBO算法通過變異操作模擬這一變化，用PEv表示棲息地含有v個物種的概率，根據(jù)棲息地物種概率PEv可以計算出棲息地的變異率，從而對棲息地的特征分量執(zhí)行變異操作，以增加棲息地的物種多樣性[17]。

上一時刻、當前時刻和下一時刻棲息地的物種數(shù)量概率有如下關(guān)系

其中，λv表示棲息地的物種數(shù)量為v時的遷入概率，uv表示棲息地的物種數(shù)量為v時的遷出概率。

其中，vmax=Qmax。

這里定義PE=[PE0PE1PE2…PEh]T，式(10)可以轉(zhuǎn)化為

其中，

棲息地物種數(shù)量的概率可以由式(11)這個矩陣方程求出。既然要進行變異操作，那就存在如何選擇發(fā)生變異的棲息地的問題，在BBO算法中，一個棲息地發(fā)生變異的概率與其物種數(shù)量的概率呈反比關(guān)系。棲息地u的變異率δ(u)和物種數(shù)量的概率PEv關(guān)系如式(13)所示。從該公式可以看出，在BBO算法中，HSI較高的棲息地和HSI較低的棲息地均對應(yīng)較高的變異概率，而HSI居中的棲息地對應(yīng)較低的變異概率。

其中，PEmax為BBO算法設(shè)定的最大物種數(shù)量的概率，δmax為設(shè)定的最大變異概率。

3 改進的BBO算法用于求解混合流水車間調(diào)度問題

3.1 算法的編碼與初始化

將BBO算法用于求解混合流水車間調(diào)度問題，使用2.2節(jié)中的向量編碼方式，每一組向量解對應(yīng)BBO算法中一塊棲息地的SIV，向量解對應(yīng)的調(diào)度解（在本文中即makespan）與BBO算法中的HSI值呈反比，即一個向量解經(jīng)過解碼后的makespan越小，其對應(yīng)的棲息地的適宜度值越高。

基本BBO算法的初始解是隨機產(chǎn)生的，不能保證初始解的質(zhì)量。改進的BBO算法采用NEH規(guī)則（圖2）和隨機方式共同生成初始解，使得算法在第一代至少存在一個較優(yōu)解，這樣既保證了算法的收斂速度，又不失初始解的多樣性[18]。

圖2 使用NEH規(guī)則初始化棲息地的偽代碼Fig. 2 Pseudo-code of using NEH algorithm to initialize habitats

NEH啟發(fā)式算法是由Nawaz等[19]提出的啟發(fā)式算法，該算法的核心思想是賦予總的加工時間越長的工件在排列中的插入優(yōu)先權(quán)越高，算法通過每一步插入一個新工件，得到最好的局部解，最后得到局部最優(yōu)的工件加工順序。

3.2 對棲息地按照適宜度值排序

在對棲息地執(zhí)行遷入遷出操作、變異操作和精英保留策略之前，需要對棲息地按適宜度值由高到低進行降序排列。

3.3 精英保留策略

BBO算法在迭代過程中產(chǎn)生較優(yōu)解，如果不對較優(yōu)解采取保護措施，仍對其進行遷移和突變操作，很可能造成優(yōu)良解的流失，削弱算法的搜索能力。因此設(shè)計了精英保留策略，即每次在執(zhí)行遷移和變異操作前，保留兩個當前最優(yōu)解，不參與以上操作。

3.4 改進的遷入率

在BBO算法中，通過遷移操作使低HSI的棲息地獲得更多高HSI棲息地的信息，實現(xiàn)棲息地的不斷進化。在基本BBO算法中，棲息地的遷入率僅與棲息地的物種數(shù)量相關(guān)。但從整體進化的角度來看，每個棲息地的遷入率應(yīng)該隨著進化過程逐漸變小，以避免對算法后期的穩(wěn)定性造成影響而導(dǎo)致算法迭代終止時不能收斂，或加長收斂過程。基于以上考慮，本文設(shè)計了一種與迭代次數(shù)和棲息地物種數(shù)量相關(guān)的遷入率計算公式

其中，TGen為預(yù)設(shè)的最大迭代次數(shù)；Q(u)表示棲息地u的物種數(shù)量；Qmax表示最大物種數(shù)量。

3.5 改進的變異概率

在BBO算法中，變異算子主要起保證解的多樣性的作用，產(chǎn)生新的解以抑制早熟現(xiàn)象。在基本BBO算法中，棲息地的變異概率僅與棲息地的物種數(shù)量概率相關(guān)。但從整體進化的角度來看，變異概率應(yīng)該隨著迭代次數(shù)的增加而逐漸減小，以保證算法的收斂性。基于以上考慮，本文設(shè)計了一種與迭代次數(shù)和棲息地HSI值相關(guān)的變異概率計算公式

其中，δ(u)表示棲息地u對應(yīng)的變異概率，HSImax表示當前最優(yōu)棲息地所對應(yīng)的HSI值，HSI(u)表示棲息地u對應(yīng)的HSI值，δmax、δmin分別為算法的最大變異概率和最小變異概率。

3.6 鄰域搜索算子

在BBO算法中加入鄰域搜索策略，可以很好地改善解的質(zhì)量，提高算法的局部搜索能力。

考慮到BBO算法的效率問題，在迭代過程中，只有當最優(yōu)棲息地的HSI值發(fā)生變化時，才執(zhí)行基于插入的鄰域搜索策略。

3.7 改進的BBO算法用于混合流水車間調(diào)度流程

改進后的BBO算法求解混合流水車間調(diào)度問題流程見圖3。

3.8 算法的復(fù)雜度分析

假設(shè)算法的迭代次數(shù)為TGen，計算各棲息地的HSI值的時間復(fù)雜度為O(hsnlogn)，對各棲息地適宜度值排序的時間復(fù)雜度為O(h2)，遷移變異算子的時間復(fù)雜度為O(hn)，鄰域搜索算子的時間復(fù)雜度為O(sn3logn)，因此算法的時間復(fù)雜度為O(TGen× (snlogn(h+n2)+h(h+n)))，可以看出算法的計算量主要與問題規(guī)模（加工階段數(shù)s，工件數(shù)n），算法設(shè)定的棲息地數(shù)量h和迭代次數(shù)TGen有關(guān)。以上提出的改進策略，NEH規(guī)則和改進遷移突變模型并沒有提高算法的復(fù)雜度，僅僅增加了計算量。鄰域搜索算子是概率性發(fā)生，對時間復(fù)雜度的增加影響不大。

圖3 改進后的BBO算法求解混合流水車間調(diào)度問題流程Fig 3 Improved BBO algorithm for solving hybrid flow shop scheduling problem

4 仿真研究

4.1 實驗參數(shù)設(shè)置

針對10個Liao算例[20]，分別采用遺傳算法(GA)，原始的BBO算法(BBO)，加入NEH規(guī)則的BBO算法(BBO-NEH)，加入NEH規(guī)則并改進遷入率和變異率的BBO算法(BBO-NEH-QT)，加入NEH規(guī)則、改進遷入率和變異率并加入鄰域搜索算子的BBO算法(IBBO)對以上算例進行優(yōu)化，每種算法獨立運行10次。

BBO算法參數(shù)設(shè)定：棲息地數(shù)量h設(shè)為20，最大物種數(shù)量Qmax設(shè)為20，最大物種數(shù)量的概率PEmax設(shè)為1/20，迭代次數(shù)TGen為300代，全局遷移概率Pmod設(shè)為1，最大遷入概率I設(shè)為1，最大遷出概率E設(shè)為1，最大變異概率δmax設(shè)為0.1，最小變異概率δmin設(shè)為0.05，精英保留個數(shù)為2，每種算法獨立運行10次得到最優(yōu)最小Makespan(Min)，平均最小Makespan(Ave)和算法運行時間(Time)。

4.2 仿真結(jié)果分析

從表1中可以看出，原始的BBO算法與GA算法性能較為接近；加入NEH啟發(fā)式規(guī)則后，算法的初始解得到了優(yōu)化，最優(yōu)解的質(zhì)量得到改善；使用改進的遷移概率和變異概率，即在算法的迭代初期使用較高的遷入概率和變異概率，保證了算法初期在解空間的勘測性能(exploration)，在算法的迭代后期使用較低的遷入概率和變異概率，保證了算法后期的收斂性，從表中可以看出以上改進策略明顯提高了最優(yōu)解的質(zhì)量；加入基于插入的鄰域搜索策略后增強了算法的開采能力(exploitation)，即提高了算法的局部搜索能力，在之前策略的基礎(chǔ)上，進一步優(yōu)化了解的質(zhì)量。

對于一個Liao算例，分別采用BBO、BBONEH、BBO-NEH-QT、IBBO算法，以機器運行時間(s)為橫坐標，迭代過程中產(chǎn)生的最優(yōu)解為縱坐標，繪制仿真結(jié)果圖，從算法的效率角度進行分析。

從圖4可以看出，BBO-NEH算法相比于BBO算法，加入了NEH規(guī)則，改善了BBO算法最優(yōu)解的質(zhì)量。但可以看出，算法容易陷入局部最優(yōu)，全局搜索能力有待提升。

表1 IBBO算法與其變種及GA之間的比較Table 1 Comparison between IBBO algorithm, its variants and GA

從圖5可以看出，BBO-NEH-QT算法相比于BBO-NEH算法，使用了改進的遷入率和變異概率，提高了算法的全局搜索能力，改善了最優(yōu)解的質(zhì)量。

圖4 BBO算法和BBO-NEH算法收斂曲線Fig 4 Comparison between BBO and BBO-NEH

圖5 BBO-NEH算法和BBO-NEH-QT算法收斂曲線Fig 5 Comparison between BBO-NEH and BBO-NEH-QT

從圖6可以看出，IBBO算法相比于BBO-NEHQT算法，加入了基于插入的鄰域搜索策略，增強了算法的局部搜索能力，加快了算法的收斂速度，改善了最優(yōu)解的質(zhì)量。

圖6 BBO-NE-QT算法和IBBO算法收斂曲線Fig 6 Comparison between BBO-NEH-QT and IBBO

5 結(jié) 語

本文介紹了一種新型的生物地理學(xué)優(yōu)化算法的原理及其用于求解混合流水車間調(diào)度的問題的步驟。針對BBO算法的不足，提出了3種改進策略：使用NEH規(guī)則初始化棲息地，改進遷移率和變異率，加入基于插入的鄰域搜索策略。以上3種改進策略提高了算法的收斂速度，增強了算法的尋優(yōu)能力。通過10個Liao算例的仿真實驗，并與遺傳算法進行比較，驗證改進策略的有效性。

本文針對混合流水車間調(diào)度問題，采用改進的BBO算法進行求解，取得了較好的優(yōu)化效果。接下來可以從以下幾個方面做進一步的研究。

（1）本文提出的BBO算法不僅可以解決混合流水車間調(diào)度問題，還可以考慮用于存在多目標、零等待、故障、中斷、存在優(yōu)先約束等情況，作為BBO算法求解其他調(diào)度問題的研究基礎(chǔ)。

（2）研究基于BBO算法的混合算法?；旌纤惴ㄌ攸c在于吸收各種算法的優(yōu)點，新算法的搜索能力要明顯高于原算法。例如有些學(xué)者提出的基于差分進化的BBO算法，就是由BBO算法結(jié)合差分進化算法構(gòu)成的混合算法。

References

[1] RUBEN R, JOSE A V R. The hybrid flow shop scheduling problem [J]. European Journal of Operational Research, 2010, 205(1): 1-18.

[2] SALVADOR M S. A solution of a special class of flow shop scheduling problems[C] // Symposium on the Theory of Scheduling and Its Applications. Berlin, 1973: 83-91．

[3] MARICHELVAM M K, PRABAHARAN T, YANG X S. Improved cuckoo search algorithm for hybrid flow shop scheduling problems to minimize makespan [J]. Applied Soft Computing, 2014, 19: 93-101.

[4] 吳云高, 王萬良. 基于遺傳算法的混合flowshop調(diào)度 [J]. 計算機工程與應(yīng)用, 2002, 38(12): 82-84.

WU Y G, WANG W L. Hybrid flowshop scheduling method based on genetic algorithm [J]. Computer Engineering and Applications, 2002, 38(12): 82-84.

[5] SIMON D. Biogeography-based optimization [J]. IEEE Trans. Evolutionary Computation, 2008, 12(6): 702-713.

[6] BHATTACHARYA A, CHATTOPADHYAY P K. Hybrid differential evolution with biogeography-based optimization for solution of economic load dispatch [J]. Power Systems, IEEE Transactions on, 2010, 25(4): 1955-1964.

[7] RARICK R, SIMON D, VILLASECA F E, et al. Biogeography-based optimization and the solution of the power flow problem[C]//Systems, Man and Cybernetics, 2009: 1003-1008.

[8] LIN J. A hybrid biogeography-based optimization for the fuzzy flexible job-shop scheduling problem [J]. Knowledge-Based Systems, 2015, 78: 59-74.

[9] 湯洪濤, 丁彬楚, 李修琳, 等. 基于改進免疫遺傳算法的混合車間調(diào)度研究 [J]. 中國機械工程, 2014, (9): 1189-1194, 1201.

TANG H T, DING B C, LI X L, et al. Improved immune genetic algorithm for mixed-model scheduling problem [J].China Mechanical Engineering, 2014, (9): 1189-1194, 1201.

[10] ONWUBOLU G DAVENDRA D. Scheduling flow shops using differential evolution algorithm [J]. European Journal of Operational Research，2006, 171(2): 674-692.

[11] O?UZ C, ZINDER Y, JANIAK A, et al. Hybrid flow-shop scheduling problems with multiprocessor task systems [J]. European Journal of Operational Research, 2004, 152(1): 115-131.

[12] OGUZ C, ERCAN M F. A genetic algorithm for hybrid flow shop scheduling with multiprocessor tasks [J]. Journal of Scheduling, 2005, 8(4): 323-351.

[13] WANG X H, DUAN H B. A hybrid biogeography-based optimization algorithm for job shop scheduling problem [J]. Computers & Industrial Engineering, 2014, 73: 96-114.

[14] WANG Z C, WU X B. Hybrid biogeography-based optimization for integer programming [J]. The Scientific World Journal, 2014, 12 (6) : 1-7.

[15] SIMON D. A probabilistic analysis of a simplified biogeographybased optimization algorithm [J]. Evolutionary Computation, 2011, 19(2): 167-188.

[16] BOUSSA?D I, CHATTERJEE A, SIARRY P, et al. Biogeographybased optimization for constrained optimization problems [J]. Computers & Operations Research, 2012, 39(12): 3293-3304.

[17] 王存睿, 王楠楠, 段曉東, 等. 生物地理學(xué)優(yōu)化算法綜述 [J]. 計算機科學(xué), 2010, 37(7): 34-38.

WANG C R, WANG N N, DUAN X D, et al. Survey of biogeography-based optimization [J]. Computer Science, 2010, 37(7): 34-38.

[18] 耿佳燦, 顧幸生. 不確定條件下中間存儲時間有限多產(chǎn)品間歇生產(chǎn)過程調(diào)度 [J]. 化工學(xué)報, 2015, 66(1): 357-365.

GEN J C, GU X S. Time-constrained intermediate storage multiproduct batch process scheduling with uncertainty [J]. CIESC Journal, 2015, 66(1) : 357-365.

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

[20] LIAO C J, TJANDRADJAJA E, CHUNG T P. An approach using particle swarm optimization and bottleneck heuristic to solve hybrid flow shop scheduling problem [J]. Applied Soft Computing, 2012, 12(6): 1755-1764.

研究論文

Received date: 2015-12-11.

Foundation item: supported by the National Natural Science Foundation of China (61174040,61573144) and Key Foundation Research Project of Science and Technology Bureau of Shanghai (12JC1403400).

Improved biogeography-based optimization algorithm used in solving hybrid flow shop scheduling problem

LI Zhicong, GU Xingsheng
(Key Laboratory of Advanced Control and Optimization for Chemical Processes, Ministry of Education, East China University of Science and Technology, Shanghai 200237, China)

Abstract:Scheduling problems is a form of decision-making that allocates limited resources to tasks and its goal is to optimize one or more objectives. It exists widely in most of the modern manufacturing and production industries. As a expansion of classic flow shop scheduling problem, hybrid flow shop scheduling problem is closer to the practical production process. This paper presents an improved biogeography optimization algorithm(IBBO) to solve hybrid flow shop scheduling problem. By introducing improved strategy, enhance the ability of global and local search and improve the convergence speed. Simulation experiments based on ten standard scheduling instances and comparison with genetic algorithm verify the excellence of the improved biogeography-based optimization algorithm in solving hybrid flow shop scheduling problem.

Key words:production scheduling; hybrid flow shop scheduling problem; biogeography optimization algorithm; vector encoding; depth search

DOI：10.11949/j.issn.0438-1157.20151879

中圖分類號：TP 278

文獻標志碼：A

文章編號：0438—1157（2016）03—0751—07

基金項目：國家自然科學(xué)基金項目(61174040，61573144)；上海市科委基礎(chǔ)研究重點項目(12JC1403400)。

Corresponding author:Prof. GU Xingsheng, xsgu@ecust.edu.cn