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

?

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

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

摘要：調(diào)度問題是將有限的資源分配給各項(xiàng)不同任務(wù)的決策過程，其目的是優(yōu)化一個(gè)或多個(gè)目標(biāo)，它廣泛存在于當(dāng)今大多數(shù)的制造和生產(chǎn)系統(tǒng)中?；旌狭魉囬g調(diào)度問題是一般流水車間調(diào)度問題的推廣，更接近實(shí)際的生產(chǎn)過程。采用一種新型的算法——生物地理學(xué)優(yōu)化算法求解混合流水車間調(diào)度問題，通過引入改進(jìn)策略，增強(qiáng)了算法的全局搜索能力和局部搜索能力，并提高了算法的收斂速度。通過10個(gè)標(biāo)準(zhǔn)調(diào)度算例的仿真研究，并與遺傳算法進(jìn)行對(duì)比，驗(yàn)證了改進(jìn)后的生物地理學(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)度與并行機(jī)調(diào)度的結(jié)合，又被稱為多處理單元調(diào)度問題或者柔性流水車間調(diào)度問題(flexible flow-shopschedulingproblem, FFSP)[1]，最早由Salvador[2]在1973年基于石油工業(yè)背景提出。HFSP具有很強(qiáng)的工業(yè)背景，廣泛存在于石油、化工、紡織、造紙、機(jī)械、物流等領(lǐng)域。

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

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

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

1.1 問題的描述

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

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

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

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

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

Subject to

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

2 基本BBO算法

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

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

2.2 BBO的遷移操作

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

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

2.3 BBO算法變異操作

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

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

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

其中，vmax=Qmax。

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

其中，

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

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

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

3.1 算法的編碼與初始化

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

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

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

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

3.2 對(duì)棲息地按照適宜度值排序

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

3.3 精英保留策略

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

3.4 改進(jìn)的遷入率

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

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

3.5 改進(jìn)的變異概率

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

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

3.6 鄰域搜索算子

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

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

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

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

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

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

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

4 仿真研究

4.1 實(shí)驗(yàn)參數(shù)設(shè)置

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

BBO算法參數(shù)設(shè)定：棲息地?cái)?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，精英保留個(gè)數(shù)為2，每種算法獨(dú)立運(yùn)行10次得到最優(yōu)最小Makespan(Min)，平均最小Makespan(Ave)和算法運(yùn)行時(shí)間(Time)。

4.2 仿真結(jié)果分析

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

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

從圖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算法，使用了改進(jìn)的遷入率和變異概率，提高了算法的全局搜索能力，改善了最優(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算法，加入了基于插入的鄰域搜索策略，增強(qiáng)了算法的局部搜索能力，加快了算法的收斂速度，改善了最優(yōu)解的質(zhì)量。

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

5 結(jié) 語

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

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

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

（2）研究基于BBO算法的混合算法。混合算法特點(diǎn)在于吸收各種算法的優(yōu)點(diǎn)，新算法的搜索能力要明顯高于原算法。例如有些學(xué)者提出的基于差分進(jìn)化的BBO算法，就是由BBO算法結(jié)合差分進(jìn)化算法構(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]. 計(jì)算機(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] 湯洪濤, 丁彬楚, 李修琳, 等. 基于改進(jìn)免疫遺傳算法的混合車間調(diào)度研究 [J]. 中國機(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]. 計(jì)算機(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ǔ)時(shí)間有限多產(chǎn)品間歇生產(chǎn)過程調(diào)度 [J]. 化工學(xué)報(bào), 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

中圖分類號(hào)：TP 278

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：0438—1157（2016）03—0751—07

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

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