求解混合流水線調(diào)度問(wèn)題的離散人工蜂群算法

李俊青 ， 潘全科 ， 王法濤

(1.聊城大學(xué) 計(jì)算機(jī)學(xué)院,山東 聊城 252059; 2.東北大學(xué) 流程工業(yè)綜合自動(dòng)化國(guó)家重點(diǎn)實(shí)驗(yàn)室,遼寧 沈陽(yáng) 110819； 3.北京郵電大學(xué) 經(jīng)濟(jì)管理學(xué)院,北京 100876)

?

求解混合流水線調(diào)度問(wèn)題的離散人工蜂群算法

李俊青1,2， 潘全科1,2， 王法濤1,3

(1.聊城大學(xué) 計(jì)算機(jī)學(xué)院,山東 聊城 252059; 2.東北大學(xué) 流程工業(yè)綜合自動(dòng)化國(guó)家重點(diǎn)實(shí)驗(yàn)室,遼寧 沈陽(yáng) 110819； 3.北京郵電大學(xué) 經(jīng)濟(jì)管理學(xué)院,北京 100876)

本文給出了一種離散的人工蜂群算法(HDABC)用于求解混合流水車間調(diào)度(HFS)問(wèn)題。采用工件排序的編碼方式，并設(shè)計(jì)了四種鄰域結(jié)構(gòu)。雇傭蜂依次分派到解集中每個(gè)解，采用結(jié)合問(wèn)題特征的局部搜索策略完成挖掘搜索工作。跟隨蜂隨機(jī)選擇兩個(gè)解并挑選較優(yōu)者作為當(dāng)前解，完成進(jìn)一步的探優(yōu)過(guò)程。偵察蜂采用三種策略跳出局部極小。通過(guò)34個(gè)同構(gòu)并行機(jī)HFS問(wèn)題和2個(gè)異構(gòu)并行機(jī)HFS實(shí)際調(diào)度問(wèn)題的實(shí)驗(yàn)，并與當(dāng)前文獻(xiàn)中的典型算法對(duì)比，驗(yàn)證了本文提出的算法無(wú)論在算法時(shí)間還是在求解質(zhì)量上，都具備良好的性能。

混合流水車間調(diào)度；人工蜂群；局部搜索；鄰域結(jié)構(gòu)

0 引言

調(diào)度問(wèn)題是工業(yè)工程領(lǐng)域中關(guān)鍵技術(shù)問(wèn)題，混合流水線 (Hybrid Flow Shop, HFS)調(diào)度問(wèn)題屬于NP-難問(wèn)題，是調(diào)度問(wèn)題的一個(gè)特例，由于其廣泛存在于生產(chǎn)流程中，已成為近年來(lái)的研究熱點(diǎn)[1]。 在HFS中，加工流程劃分為幾個(gè)階段，每個(gè)加工階段由若干同型或異構(gòu)機(jī)床組成，任何一個(gè)工件需要嚴(yán)格按照相同的加工順序依次流經(jīng)每個(gè)加工階段，到達(dá)任意階段時(shí)，可以從多個(gè)并行機(jī)床中選擇一個(gè)進(jìn)行加工。文獻(xiàn)[2]是最早采用分支-定界法求解HFS問(wèn)題的文獻(xiàn)，之后出現(xiàn)了許多不同的算法。按照加工階段的不同，HFS一般分為三種類型：2-階段HFS、3-階段HFS和m-階段HFS。當(dāng)前，m-階段HFS由于更貼近生產(chǎn)實(shí)際而成為研究熱點(diǎn)。研究m-階段HFS的主要文獻(xiàn)有：1998年，Portman設(shè)計(jì)了一種遺傳算法和分支-定界相結(jié)合的方法[3]；Neron給出了在5-階段下求解HFS問(wèn)題的優(yōu)化算法[4]；Oguz則設(shè)計(jì)了一種基于遺傳算法的混合方法[5]；Ruiz等針對(duì)順序決定的準(zhǔn)備時(shí)間的HFS開(kāi)發(fā)了一種基于遺傳算法的方法[1]；Janiak則采用基于禁忌搜索和模擬退火的啟發(fā)式方法[7]；此外，Niu等設(shè)計(jì)了量子啟發(fā)式免疫算法[8]；Kahrama設(shè)計(jì)了一種并行貪婪優(yōu)化算法[9]；Liao等提出了一種結(jié)合瓶頸機(jī)床的粒子群優(yōu)化算法[10]。

上述優(yōu)化算法用于求解HFS問(wèn)題，有些收斂能力不足，有些則易于陷入局部極小。人工蜂群(Artificial Bee Colony, ABC)算法是一種新的群體智能優(yōu)化方法，由Karaboga等于2005年首次提出，主要應(yīng)用于求解連續(xù)函數(shù)優(yōu)化問(wèn)題[11,12]。文獻(xiàn)[13,14]針對(duì)ABC方法應(yīng)用到離散問(wèn)題領(lǐng)域，提出了離散人工蜂群算法，并應(yīng)用求解流水線調(diào)度。文獻(xiàn)[15]則把離散ABC方法應(yīng)用到求解柔性作業(yè)車間調(diào)度(Flexible Job Shop scheduling Problem, FJSP)問(wèn)題中。上述文獻(xiàn)表明，ABC算法由于有效平衡了全局搜索和局部搜索能力，可以有效應(yīng)用于求解復(fù)雜調(diào)度問(wèn)題。本文結(jié)合ABC算法的特點(diǎn)，提出了一種求解HFS問(wèn)題的離散ABC方法。

1 問(wèn)題描述與定義

HFS問(wèn)題如下：假設(shè)有M個(gè)機(jī)床m={Mk}1≤k≤m，n個(gè)工件J={Ji}1≤i≤n，和s個(gè)加工階段。每個(gè)加工階段si包含mi個(gè)同型或異構(gòu)的并行機(jī)床，每個(gè)工件Ji通過(guò)加工階段si時(shí)，可任選其中一個(gè)機(jī)床進(jìn)行加工。為構(gòu)建HFS問(wèn)題模型，定義如下符號(hào)：Mi為加工階段i中的并行機(jī)床集合；pijk為工件j在加工階段i選擇機(jī)床k的加工時(shí)間 (pijk≥0)；sij為工件j在加工階段i的開(kāi)工時(shí)間；cij為工件j在加工階段i的完工時(shí)間；L為極大數(shù)。

有了上述符號(hào)，HFS問(wèn)題的模型如下：

圖1HFS問(wèn)題定義

其中，不等式約束(2)描述同一工件的工序間的先后約束關(guān)系，不等式約束(3)限制同一個(gè)機(jī)床上有緊前關(guān)系的工件間不允許出現(xiàn)加工時(shí)間重疊，等式約束(4)定義每個(gè)工件的每個(gè)加工階段只能選擇一個(gè)機(jī)床加工。

2 基本人工蜂群算法

人工蜂群算法是由Karaboga等[11,12]于2005年提出的一種新的群體智能優(yōu)化算法，是模擬蜜蜂尋找食物的過(guò)程而演化的仿生過(guò)程。在基本ABC中，食物源(food source)和人工蜜蜂(artificial bees)是基本構(gòu)成要素。人工蜜蜂又被分為三種，即雇傭蜂(Employed bees)、跟隨蜂(Onlooker bees)和偵察蜂(Scout bees)。雇傭蜂的任務(wù)是在隨機(jī)食物源周圍進(jìn)一步挖掘，以便找到更好的食物源；在雇傭蜂把挖掘后的信息帶回后，守在蜂巢中的跟隨蜂按照一定概率選擇較好的食物，進(jìn)一步搜索挖掘；當(dāng)某些食物在經(jīng)過(guò)一定周期后，未曾發(fā)生改變，則派出偵察蜂隨機(jī)搜索新的食物源。ABC算法中基本控制參數(shù)包括：解集大小SN，解無(wú)更新而被丟棄的周期大小Ls，雇傭蜂數(shù)目Es，跟隨蜂數(shù)目Os，偵察蜂數(shù)目Ss和終止條件。

3 混合算法框架

基本ABC用于求解連續(xù)優(yōu)化問(wèn)題，因而，應(yīng)用于求解離散調(diào)度問(wèn)題需要進(jìn)行離散化。結(jié)合問(wèn)題特征，本文對(duì)基本ABC算法進(jìn)行離散化設(shè)計(jì)。

表1 HFS示例

3.1 問(wèn)題編碼

圖2 HFS問(wèn)題甘特圖

本文采用簡(jiǎn)單工序排列編碼方式[1]。假設(shè)問(wèn)題加工時(shí)間和各個(gè)加工階段機(jī)床分配情況如表1所示。給定一個(gè)解{4,1,2,5,3}，其含義如下：在第一個(gè)加工階段，按照各工件在解中的位置次序先后調(diào)度，首先調(diào)度工件J4，之后J1，最后調(diào)度工件J3。由于解中沒(méi)有包含機(jī)床選擇策略，各個(gè)工件按照最早完工機(jī)床原則選擇相應(yīng)機(jī)床加工：如果有多個(gè)機(jī)床空閑可用于加工，則選擇加工時(shí)間最短的；如果只有一個(gè)空閑機(jī)床，則直接開(kāi)始在該機(jī)床上加工。經(jīng)過(guò)后面各個(gè)加工階段時(shí)，各個(gè)工件按照在上一個(gè)加工階段完工時(shí)間的先后次序，選擇相應(yīng)機(jī)床進(jìn)行加工。對(duì)應(yīng)表1的HFS例子，其最優(yōu)的調(diào)度甘特圖如圖2所示。圖中，每個(gè)工件由一對(duì)數(shù)字表示，第一個(gè)數(shù)字對(duì)應(yīng)工件編號(hào)，第二個(gè)對(duì)應(yīng)加工階段序號(hào)。例如，在機(jī)床M1上，第一個(gè)加工的是(4,1)，對(duì)應(yīng)工件J4在第一個(gè)加工階段選擇機(jī)床M1。圖中，最后一個(gè)完工的工件J5，其完工時(shí)間是30，表示該解對(duì)應(yīng)的最優(yōu)目標(biāo)值是30。

3.2 初始解集的建立

為了提高初始解集的多樣性，避免解集的趨同性，本文采用如下隨機(jī)解集產(chǎn)生策略：

步驟1Cnt=1；

步驟2 如果Cnt=SN，終止初始過(guò)程，否則，隨機(jī)產(chǎn)生一個(gè)解；

步驟3 如果產(chǎn)生的新解不同于當(dāng)前解集中的任何解，則插入到當(dāng)前解集，并設(shè)置Cnt=Cnt+1；否則，忽略該解；

步驟4 跳轉(zhuǎn)到步驟2。

3.3 鄰域結(jié)構(gòu)

結(jié)合問(wèn)題結(jié)構(gòu)特點(diǎn)，本文設(shè)計(jì)了4種鄰域結(jié)構(gòu)，定義如下：

交換鄰域，記為N1。產(chǎn)生策略為：在解的長(zhǎng)度范圍內(nèi)隨機(jī)生成兩個(gè)位置，記為r1和r2，交換r1和r2對(duì)應(yīng)的工件編號(hào)；

前插鄰域，記為N2。產(chǎn)生策略為：在解的長(zhǎng)度范圍內(nèi)隨機(jī)生成兩個(gè)位置，記為r1和r2(r1

翻轉(zhuǎn)鄰域，記為N3。產(chǎn)生策略為：在解的長(zhǎng)度范圍內(nèi)隨機(jī)生成兩個(gè)位置，記為r1和r2(r1

序?qū)粨Q鄰域，記為N4。產(chǎn)生策略為：(1)在解的長(zhǎng)度范圍內(nèi)隨機(jī)生成兩個(gè)位置，記為r1和r2，令i=r1,j=r2；(2)交換位置i和j對(duì)應(yīng)的工件編號(hào)，令i=i+1,j=j-1，如果i>=j，則停止，否則，循環(huán)執(zhí)行步驟(2)。

3.4 局部搜索策略

本文給出了一種局部搜索策略，用于在給定解周圍挖掘可能的較優(yōu)解。該局部搜索策略用于雇傭蜂、跟隨蜂以及偵察蜂搜索食物的過(guò)程，具體描述如圖3所示。

圖3 局部搜索過(guò)程

3.5 雇傭蜂階段

雇傭蜂的主要任務(wù)是在分配的食物上開(kāi)展挖掘工作，搜索更好的食物源?；続BC中雇傭蜂的操作算子不適合于調(diào)度問(wèn)題。本文給出的離散ABC算法中，雇傭蜂的策略如下：

步驟1 為當(dāng)前解集中每個(gè)食物源分配一個(gè)雇傭蜂；

步驟2 以指定解為當(dāng)前解Sc，在3.3節(jié)中給定的四種鄰域結(jié)構(gòu)中隨機(jī)選擇鄰域結(jié)構(gòu)Nc，執(zhí)行3.4節(jié)的局部搜索策略，得到更新后的解Sc′；

步驟3 用Sc′替換給定的解。

3.6 跟隨蜂階段

在雇傭蜂挖掘工作結(jié)束后，守候著蜂巢的跟隨蜂在更新后的解集中以概率選擇的方式挑選較優(yōu)解進(jìn)一步挖掘搜索。采用輪盤賭注選擇方式，需要比較解集中每個(gè)解的目標(biāo)值的大小，因而時(shí)間復(fù)雜度較高。為了提高算法效率，本文給出了一種簡(jiǎn)單的跟隨蜂的選擇策略，具體描述如下：

步驟1 在當(dāng)前解集中隨機(jī)選擇兩個(gè)解S1和S2；

步驟2 在選中的解中挑選較優(yōu)解作為當(dāng)前解Sc；

步驟3 隨機(jī)選擇鄰域結(jié)構(gòu)Nc；

步驟4 執(zhí)行3.4節(jié)中的局部搜索策略，找到更新后的解Sc′，并替換當(dāng)前選中的解。

3.7 偵查蜂階段

結(jié)合HFS問(wèn)題特征，本文給出了三種偵察蜂策略，具體描述如下：

策略一，隨機(jī)解策略。若解集中某個(gè)解在指定時(shí)間間隔內(nèi)沒(méi)有更新，生成一個(gè)隨機(jī)解替換該解，并派出偵察蜂進(jìn)一步挖掘。

策略二，丟棄解策略。在某個(gè)解在指定時(shí)間間隔內(nèi)沒(méi)有更新時(shí)，對(duì)該丟棄解進(jìn)行10次鄰域擾動(dòng)，然后派出偵察蜂在擾動(dòng)后的解上進(jìn)一步挖掘搜索。

策略三，最好解策略。對(duì)最好解進(jìn)行10次鄰域擾動(dòng)，用擾動(dòng)后的最好解替換該解，然后派出偵察蜂進(jìn)一步挖掘搜索。

偵察蜂挖掘搜素的過(guò)程如下：

步驟1 隨機(jī)選擇鄰域結(jié)構(gòu)Nc；

步驟2 執(zhí)行3.4節(jié)中的局部搜索策略，找到更新后的解Sc′，并替換當(dāng)前選中的解。

3.8HDABC框架流程

本文給出的HDABC算法流程如下：

步驟1 初始化實(shí)驗(yàn)參數(shù)，生產(chǎn)初始解集；

步驟2 若終止條件滿足，則結(jié)束算法，否則，執(zhí)行步驟3～6；

步驟3 給當(dāng)前解集中每個(gè)解分派雇傭蜂，執(zhí)行挖掘搜索工作；

步驟4 分派跟隨蜂，進(jìn)一步挖掘更新后的解集；

步驟5 ：如果滿足派出偵察蜂的條件，則隨機(jī)選擇一種偵察蜂策略，開(kāi)展進(jìn)一步強(qiáng)化搜索。

步驟6 ：返回步驟2。

4 實(shí)驗(yàn)分析

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

以VC++6.0為開(kāi)發(fā)環(huán)境，采用Intel Core i5 3.3 GHZ、4GB RAM的PC機(jī)，針對(duì)34個(gè)同構(gòu)HFS經(jīng)典算例和2個(gè)異構(gòu)并行機(jī)煉鋼連鑄現(xiàn)實(shí)生產(chǎn)的HFS問(wèn)題，驗(yàn)證所得算法的性能，問(wèn)題規(guī)模從10個(gè)工件5個(gè)加工階段到30個(gè)工件5個(gè)加工階段。算法參數(shù)設(shè)置如下：

初始解集大小=10；

雇傭蜂數(shù)量=10；

跟隨蜂數(shù)量=10；

偵查蜂數(shù)量=1；

偵察蜂派出時(shí)機(jī)：某個(gè)解超過(guò)10秒沒(méi)有更新；

局部搜索策略相關(guān)參數(shù)：雇傭蜂、跟隨蜂循環(huán)次數(shù)Ti=10，偵察蜂循環(huán)次數(shù)Ti=50，鄰域解集大小Tn=10；

結(jié)束條件：運(yùn)行時(shí)間超過(guò)150秒。

4.2 同型并行機(jī)實(shí)驗(yàn)結(jié)果分析

本節(jié)我們從77個(gè)Carlier和Neron的經(jīng)典算例[10,16]中選取了24個(gè)較難的算例，并與四種典型算法做了對(duì)比，比較結(jié)果如表2所示。表中第一列給出了算例問(wèn)題，包括12個(gè)10工件問(wèn)題和12個(gè)15工件問(wèn)題，每個(gè)算例由三個(gè)字符和三個(gè)整數(shù)表示，這三個(gè)字符含義如下：“j”表示工件，“c”表示加工階段，第三個(gè)字符表示并行機(jī)的布局方式，其含義如下為：(1)“c” 表示中間加工階段有兩臺(tái)機(jī)床，其余階段有三臺(tái)機(jī)床；(2)“d” 表示每個(gè)加工階段有三臺(tái)并行機(jī)床。例如，“ j10c5c1”表示該問(wèn)題有10個(gè)工件和5個(gè)加工階段，其并行機(jī)布局方式是中間階段有兩臺(tái)機(jī)床，其余階段有三臺(tái)機(jī)床并行。

表2 24個(gè)Carlier和Neron算例對(duì)比

表2給出了求解上述24個(gè)經(jīng)典算例的結(jié)果，比較算法包括PSO[10]，AIS[17]，ACO[18]和B&B[4]四種算法。表中第二列給出了每個(gè)算例的下界值。每個(gè)算法的結(jié)果包括兩列：第一列給出了該算法經(jīng)過(guò)20次獨(dú)立運(yùn)行找到的最好目標(biāo)值，即makespan值；第二列給出了算法平均計(jì)算時(shí)間，單位為秒。最后五列則給出了每種算法所找到的目標(biāo)值相對(duì)于最優(yōu)值的偏差。由表2可見(jiàn)：(1)HDABC算法具備最好的求解速度，其平均運(yùn)行時(shí)間僅為2.8秒，而其余比較算法花費(fèi)的時(shí)間大大超過(guò)HDABC算法，即使考慮機(jī)器性能的差異性，比較結(jié)果也足以證明HDABC算法的效率；(2)從求解質(zhì)量來(lái)看，PSO算法在求解24個(gè)算例中表現(xiàn)了良好的性能，其偏差為2.85，HDABC算法在求解”j10c5c3”和”j10c5d2”兩個(gè)算例稍差于PSO算法，但整體性能強(qiáng)于其他三種算法；(3)綜合考慮算法耗費(fèi)時(shí)間和求解質(zhì)量，HDABC在求解中等規(guī)模HFS問(wèn)題中表現(xiàn)了良好的性能。

為進(jìn)一步驗(yàn)證算法在求解較大規(guī)模HFS問(wèn)題的性能，本文選取文獻(xiàn)[10]中列出的10個(gè)較大規(guī)模算例進(jìn)行對(duì)比分析，比較算法包括PSO和AIS兩種算法。表3給出了比較結(jié)果。表中給出了每個(gè)算法求解問(wèn)題的最好值(Min)、最差值(Max)、平均值(Avg)和平均耗費(fèi)時(shí)間(CPU)。算法求解的最好值與最優(yōu)值間的偏差也在表中給出。表中最后一列給出了每個(gè)算例的最優(yōu)值，該最優(yōu)值是三種對(duì)比算法所找到的最好解。

表3 10個(gè)大規(guī)模HFS問(wèn)題比較

表3可見(jiàn)：(1)從最好解來(lái)看，在求解10個(gè)較大規(guī)模算例中，HDABC能找到所有10個(gè)算例的最好值，而其他兩種算法的最好值明顯次于HDABC。例如，對(duì)于”j30c5e10”問(wèn)題，HDABC找到最優(yōu)解是580，而PSO找到594，AIS的最好值是604；(2)從最差值的比較可見(jiàn)，HDABC對(duì)于所有10個(gè)大規(guī)模算例的最差解均優(yōu)于其他兩種比較算法，且有些最差解好于對(duì)比算法的最好解，進(jìn)一步驗(yàn)證了算法的性能；(3)平均值的對(duì)比可見(jiàn)，HDABC平均性能明顯優(yōu)于兩種對(duì)比算法。例如，對(duì)于”j30c5e1”問(wèn)題，HDABC的平均值優(yōu)于其他兩種算法的最好值，驗(yàn)證了算法的魯棒性；(4)平均耗費(fèi)時(shí)間的比較可見(jiàn)，HDABC略優(yōu)于PSO，而明顯好于AIS算法；(5)結(jié)合算法耗費(fèi)時(shí)間和最好值、最差值以及平均值的對(duì)比可見(jiàn)，HDABC算法在求解較大規(guī)模HFS問(wèn)題中表現(xiàn)了明顯的優(yōu)勢(shì)。

圖4 求解j30c5e10問(wèn)題收斂曲線

為了比較不同算法參數(shù)對(duì)算法性能的影響，本文選取三組實(shí)驗(yàn)參數(shù)進(jìn)行比較分析：(1) ABC-I算法，參數(shù)設(shè)置同4.1節(jié)；(2) ABC-II算法，與ABC-I不同之處是：初始解集大小=5；雇傭蜂數(shù)量=5；跟隨蜂數(shù)量=5；(3) ABC-III算法，與ABC-II不同之處是：Tn=5。圖4給出了上述三種算法求解最大規(guī)?！眏30c5e10”問(wèn)題的收斂曲線，由圖4可見(jiàn)，三種算法均具備良好的收斂能力，而ABC-I算法優(yōu)于其他兩種算法。上述比較結(jié)果證明：種群的大小設(shè)置應(yīng)該適中，太小的種群搜索能力不足；局部搜索策略中，鄰域解集不能太小，否則影響算法尋優(yōu)能力。

4.3 異構(gòu)并行機(jī)實(shí)驗(yàn)結(jié)果分析

異構(gòu)并行機(jī)HFS相對(duì)于同構(gòu)并行機(jī)HFS問(wèn)題更貼近生產(chǎn)實(shí)際，因而更具備現(xiàn)實(shí)意義。為驗(yàn)證算法求解不相關(guān)并行機(jī)HFS問(wèn)題的性能，本文選取兩個(gè)實(shí)際生產(chǎn)調(diào)度問(wèn)題實(shí)例，具體描述可參見(jiàn)文獻(xiàn)[19]，比較算法包括AIS、SFLA和EDA三種算法[19]。由表4比較結(jié)果可見(jiàn)：

(1)求解兩個(gè)現(xiàn)實(shí)生產(chǎn)調(diào)度問(wèn)題，HDABC和EDA均取得了最好值，且明顯優(yōu)于其他兩種算法；(2)在平均值方面，HDABC算法明顯優(yōu)于其他三種比較算法，驗(yàn)證了算法的平均性能；(3)算法求解兩種調(diào)度算例，均可在1秒左右內(nèi)完成，驗(yàn)證了算法的高效性。

表4 異構(gòu)并行機(jī)HFS問(wèn)題比較結(jié)果

5 結(jié)論

本文給出了一種混合離散人工蜂群算法用于求解混合流水車間調(diào)度問(wèn)題，主要貢獻(xiàn)包括：設(shè)計(jì)了性能良好的鄰域結(jié)構(gòu)；構(gòu)建了新的雇傭蜂、跟隨蜂和偵察蜂策略；設(shè)計(jì)的算法可有效用于求解同型并行機(jī)和異構(gòu)并行機(jī)HFS問(wèn)題。通過(guò)經(jīng)典算例實(shí)驗(yàn)，并與當(dāng)前文獻(xiàn)典型算法做對(duì)比分析，驗(yàn)證了算法的有效性和穩(wěn)定性。下一步的工作時(shí)繼續(xù)優(yōu)化提出的混合算法，并應(yīng)用算法求解其他生產(chǎn)調(diào)度問(wèn)題。

[1] Ruiz R, Vázquez Rodríguez J A. The hybrid flow shop scheduling problem[J]. European Journal of Operational Research, 2010, 205: 1-18.

[2] Gupta J N D. Two-stage, hybrid flow shop scheduling problem[J]. Journal of the Operational Research Society, 1988, 39: 359-364.

[3] Portmann M C, Vignier A, Dardilhac D, Dezalay D. Branch and bound crossed with GA to solve hybrid flowshops[J]. European Journal of Operational Research, 1998, 107: 389- 400.

[4] Neron E, Baptiste P, Gupta J N D. Solving hybrid flow shop problem using energetic reasoning and global operations[J]. Omega-International Journal of Management Science, 2001, 29: 501-511.

[5] Oguz C, Ercan M. A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks[J]. Journal of Scheduling,2005, 8: 323-351.

[6] Ribas I, Leisten R, Framinan J M. Review and classification of hybrid flow shop scheduling problems from a production systems and a soluntions procedure perspective[J]. Computers & Operations Research, 2010, 37: 1439-1454.

[7] Janiak A, Kozan E, Lichtenstein M, Oguz C. Metaheuristic approaches to the hybrid flow shop scheduling problem with a cost-related criterion[J]. International Journal of Production Economics, 2007, 105: 407- 424.

[8] Niu Q, Zhou T, Ma S. A quantum-inspired immune algorithm for hybrid flow shop with makespan criterion[J]. Journal of Universal Computer Science, 2009, 15: 765-785.

[9] Kahraman C, Enginb O, Kaya I，?ztürk R E. Multiprocessor task scheduling in multistage hybrid flow-shops: a parallel greedy algorithm approach[J]. Applied Soft Computing, 2010, 10: 1293-1300.

[10] 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: 1755-1764.

[11] Karaboga D. An idea based on honey bee swarm for numerical optimization[R]. Technical Report TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.

[12] Karaboga D, Basturk B. On the performance of artificial bee colony(ABC)algorithm[J]. Applied Soft Computing, 2008, 8 (1):687- 697.

[13] Pan Q K, Tasgetiren M F, Suganthan P N, Chua T J. A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem[J]. Information Sciences, 2010, 181(12): 2455-2468.

[14] Pan Q K, Wang L, Mao K, Zhao J H, Zhang M. An effective artificial bee colony algorithm for a real-world hybrid flowshop problem in steelmaking process[J]. IEEE Transactions on automation science and engineering, doi: 10.1109/TASE.2012.2204874.

[15] Li J Q, Pan Q K, Gao K Z. Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems[J]. International Journal of Advanced Manufacturing Technology, 2011, 55(9-12): 1159-1169.

[16] Carlier J, Neron E. An exact method for solving the multi-processor flowshop[J]. RAIRO Operations Research, 2000, 34: 1-25.

[17] Engin O, Doyen A. A new approach to solve hybrid flow shop scheduling problems by artificial immune system[J]. Future Generation Computer Systems, 2004, 20(6): 1083-1095.

[18] Alaykyran K, Engin O, Doyen A. Using ant colony optimization to solve hybrid flow shop scheduling problems[J]. International Journal of Advanced Manufacturing Technology, 2007, 35(5-6): 541-550.

[19] 王圣堯，王凌，許燁，周剛.求解混合流水車間調(diào)度問(wèn)題的分布估計(jì)算法[J].自動(dòng)化學(xué)報(bào)，2012，38(3):437- 443.

Solving Hybrid Flow-shop Scheduling Problems by a Hybrid Discrete Artificial Bee Colony Algorithm

LI Jun-qing1,2, PAN Quan-ke1,2, WANG Fa-tao1,3

(1.SchoolofComputerScience,LiaochengUniversity，Liaocheng252059，China; 2.StateKeyLaboratoryofSyntheticalAutomationforProcessIndustries,NortheasternUniversity,Shenyang110819,China; 3.SchoolofEconomicsandManagement,BeijingUniversityofPostsandTelecommunications,Beijing100876,China)

In this paper, we propose a hybrid discrete artificial bee colony(HDABC)algorithm for solving the hybrid flow-shop scheduling(HFS)problems. In the hybrid algorithm, each solution is coded by a job-permutation mechanism. Four neighborhood structures are designed. The employed bees are assigned to each solution in the population set, to complete the local search task with a detailed designed local search approach. Onlooker bees randomly fetch two updated solutions and select the better one as the current solution, and then complete a further exploitation process. The scouts help the algorithm jump out of the local best by applying three different approaches. Then, the proposed algorithm is tested on the 34 identical parallel machines HFS and two un-related parallel machines HFS problems. The performance comparisons with other efficient algorithms are provided. It is concluded that the proposed algorithm is competitive to the compared existing algorithms for the problem considered, in terms of searching quality, diversity, robustness and convergence ability.

hybrid flow shop scheduling; artificial bee colony algorithm; local search; neighborhood structure

2013- 05- 09

國(guó)家自然科學(xué)基金項(xiàng)目(61104179，61174187,61374187)

李俊青(1976-)，男，山東冠縣人，博士研究生，副教授，主要從事計(jì)算智能、優(yōu)化算法的研究；潘全科(1971-)，男，山東陽(yáng)谷人，博士，教授，博士生導(dǎo)師，主要從事優(yōu)化調(diào)度研究；王法濤(1980-)，男，山東德州人，講師；北京郵電大學(xué)經(jīng)濟(jì)管理學(xué)院管理科學(xué)與工程專業(yè)博士研究生，研究方向：電子商務(wù)與供應(yīng)鏈管理。

TP18

A

1007-3221(2015)01- 0157- 07