黃 明，郝 倩，張春蕾，張志鵬

(大連交通大學(xué) 軟件學(xué)院，遼寧 大連 116028)＊

0 引言

混合流水車(chē)間調(diào)度問(wèn)題(Hybrid Flow-shop Scheduling Problem，HFSP)［1］，是由普通流水車(chē)間調(diào)度問(wèn)題拓展而來(lái)的，具有多并行的flow shop問(wèn)題，增加了求解問(wèn)題的難度，是NP問(wèn)題［2］.目前，針對(duì)混合流水車(chē)間調(diào)度問(wèn)題已經(jīng)提出了啟發(fā)式方法［3］和分支定界法等，但這些算法通常只適用于求解小規(guī)模問(wèn)題，并且很難保證解的質(zhì)量.

免疫算法(Immune Algorithm，IA)是受生物免疫系統(tǒng)啟發(fā)，在免疫學(xué)理論基礎(chǔ)上發(fā)展起來(lái)的一種新興的智能算法.它具有特有的自我調(diào)節(jié)機(jī)構(gòu)，已經(jīng)運(yùn)用到多個(gè)研究領(lǐng)域，其中包括車(chē)間調(diào)度問(wèn)題.文獻(xiàn)［4］中提出了一種模糊免疫調(diào)度算法，該文獻(xiàn)主要是對(duì)不確定條件下的流水車(chē)間調(diào)度問(wèn)題的模型補(bǔ)進(jìn)行分析，并用算法對(duì)該問(wèn)題進(jìn)行了求解，并未對(duì)算法進(jìn)行太多的改進(jìn);文獻(xiàn)［5］提出了一種雙種群雙倍體自適應(yīng)免疫算法，并將算法應(yīng)用到了多目標(biāo)柔性作業(yè)車(chē)間調(diào)度問(wèn)題中，雖然算法能夠求得滿意的結(jié)果，但是算法的結(jié)構(gòu)設(shè)計(jì)復(fù)雜，運(yùn)行效率不高;文獻(xiàn)［6］將改進(jìn)的免疫算法應(yīng)用到了flow shop中，雖然算法提高了一定的自適應(yīng)性，但是參數(shù)的設(shè)計(jì)比較復(fù)雜.文獻(xiàn)［7］提出了一種混合免疫進(jìn)化算法，但是種群規(guī)模的微小變化對(duì)算法的性能影響較大，也沒(méi)有將該算法應(yīng)用到車(chē)間調(diào)度中.雖然諸多的研究者對(duì)免疫算法進(jìn)行了改進(jìn)和優(yōu)化，但是算法本身的基本問(wèn)題并沒(méi)有得到解決.免疫算法屬于一種概率隨機(jī)搜索算法，與其他進(jìn)化算法一樣，容易陷入局部最優(yōu)，在算法后期，優(yōu)秀的抗體產(chǎn)生新抗體時(shí)，優(yōu)勢(shì)不明顯，從而使種群進(jìn)化不明顯.本文在免疫算法的基礎(chǔ)之上，提出了一種改進(jìn)的混合免疫算法，針對(duì)單一的算法往往表現(xiàn)出優(yōu)化效果不佳的狀況，借鑒免疫算法的自適應(yīng)及群體多樣性特點(diǎn)和模擬退火的局部搜索理論，將兩者進(jìn)行取長(zhǎng)短，應(yīng)用到混合流水車(chē)間調(diào)度問(wèn)題的求解中.

1 混合流水車(chē)間調(diào)度問(wèn)題描述

1.1 問(wèn)題描述

典型的具有批處理功能的HFSP，至少有一個(gè)階段的設(shè)備集大于1，HFSP的輸入是待加工的工件，每個(gè)工件的加工路徑相同，但是不同工件在不同設(shè)備上所需加工時(shí)間不同.

為保證模型的正確建立，HFSP通常要作如下假設(shè):

(1)同一工件必須按其工藝順序進(jìn)行加工;

(2)一臺(tái)設(shè)備同一時(shí)刻只能操作一個(gè)工件;

(3)工件在加工過(guò)程中不可被中斷;

(4)工件可在每階段的任意設(shè)備上加工.

1.2 建立數(shù)學(xué)模型

(1)約束條件:

1)順序約束

ci，j≤ si，j+1，i?{1，2，…，n}，j?{1，2，…，m}

表示同一工件的前后工序需要滿足的條件，只有前一工序加工完成后，才能進(jìn)行下一工序的加工.

2)資源約束

ci，j=ck，j時(shí)，ci，j≤ sk，j或 ck，j≤ si，j，

其 中， i，k?{1，2，…，n}，j?{1，2，…，m}，ci，j?Mj.

表示第i和第k個(gè)工件的j工序安排在同一設(shè)備ci，j上，必須先完成前個(gè)工件的工序才能加工下件工件，即任一時(shí)刻該設(shè)備不能同時(shí)處理兩個(gè)不同的工件.

3)時(shí)間約束

si，j≥ 0，i?{1，2，…，n}，j∈ {1，2，…，m}表示工件可以從零時(shí)刻開(kāi)始加工.

ci，j=si，j+pi，j，i?{1，2，…，n}，j?{1，2，…，m}

同一階段上，工序的開(kāi)始時(shí)間與結(jié)束時(shí)間的關(guān)系，工序一旦開(kāi)始加工就不會(huì)被中斷.

(2)目標(biāo)函數(shù):

F=min max{cim，i?{1，2，…，n}}本文采用最大最小完工時(shí)間，即盡量使最后完工的工序完成時(shí)間最早作為調(diào)度目標(biāo).

模型中涉及到的具體參數(shù):n為待加工工件數(shù);m為加工工件所需的工序數(shù)，即階段總數(shù);Mj為第j道工序可供選擇的并行設(shè)備數(shù)，j∈{1，2，…，m};pi，j為工件 i的第 j道工序的處理時(shí)間;si，j為工件i的第j道工序的開(kāi)始處理時(shí)刻;ci，j為工件i的第j道工序的結(jié)束處理時(shí)刻;ci，j為工件i的第j道工序安排的設(shè)備.

2 改進(jìn)的混合免疫算法

在免疫算法的早期，由于初始種群是隨機(jī)產(chǎn)生的，所以其離最優(yōu)解相差甚遠(yuǎn)，而在算法的后期已經(jīng)接近最優(yōu)解，如果在算法的早期和后期使用相同的變異方法會(huì)使得算法早期的收斂速度過(guò)慢且算法后期產(chǎn)生過(guò)多冗余的信息計(jì)算.免疫算法在進(jìn)化過(guò)程中，會(huì)逐步積累具有優(yōu)良性能的抗體，但是由于初始種群、進(jìn)化環(huán)境、免疫算子和參數(shù)設(shè)定等因素的影響，經(jīng)過(guò)一定代數(shù)的進(jìn)化后，算法有可能進(jìn)入一個(gè)局部平衡的狀態(tài)，種群的抗體不會(huì)再有大的變化，導(dǎo)致算法不能求得全局最優(yōu)解.

為加快算法的收斂速度，在算法的早期，采用反轉(zhuǎn)法［8］對(duì)抗體進(jìn)行變異，增大隨機(jī)搜索的范圍，較快獲得接近最優(yōu)解的可行解;而在算法后期，已經(jīng)接近最優(yōu)解時(shí)，采用小步成熟機(jī)制的換位法［9-11］對(duì)抗體進(jìn)行變異.同時(shí)在算法的后期，以平均適應(yīng)度值作為標(biāo)準(zhǔn)，把部分仍然未達(dá)到標(biāo)準(zhǔn)的個(gè)體從種群中分割出來(lái)，進(jìn)行模擬退火選擇，引導(dǎo)算法跳出局部最優(yōu).并且，改進(jìn)算法在對(duì)高濃度抗體進(jìn)行抑制時(shí)，為避免丟失已求得的最優(yōu)解，采用精英保留策略.即在每次更新記憶庫(kù)時(shí)，先將與抗原親和度最高的若干個(gè)體存入記憶庫(kù)，再進(jìn)行后續(xù)操作.算法的整體流程可見(jiàn)圖1.

圖1 改進(jìn)的混合免疫算法流程圖

2.1 編碼及解碼設(shè)計(jì)

對(duì)抗體采用雙層的整數(shù)編碼方式，每個(gè)抗體表示全部工件的加工順序.如果待加工的工件數(shù)為4，工序個(gè)數(shù)為2，則抗體為長(zhǎng)度16的整數(shù)串.其中，抗體的前半部分編碼表示所有工件在設(shè)備上的加工順序，后半部分表示工件每道工序?qū)?yīng)的加工設(shè)備號(hào).

例如，對(duì)于分別有2個(gè)和3個(gè)并行設(shè)備的兩級(jí) HFSP，設(shè)備集M1={1，2}，設(shè)備集M2={3，4，5}，其中的一個(gè)抗體的編碼為(2 3 4 1 1 2 3 4 1 2 2 1 3 2 1 1)

第一層編碼:2 3 4 1 1 2 3 4

第二層編碼:1 2 2 1 3 2 1 1

其中，第一層編碼為前8位，表示工件的加工順序?yàn)楣ぜ?→工件3→工件4→工件1→工件2→工件3→工件4;第二層編碼為9～16位，表示工件各階段對(duì)應(yīng)的加工設(shè)備為設(shè)備1→設(shè)備2→設(shè)備2→設(shè)備1→設(shè)備5→設(shè)備4→設(shè)備3→設(shè)備3.

在免疫算法中，目標(biāo)函數(shù)的取值不僅與可能解的數(shù)值有關(guān)，還與其在字符串中的編碼位置相關(guān).有效的編碼方式可以表達(dá)更多的特征，增加抗體與抗原的匹配程度.本文的算法對(duì)抗體采用雙層編碼，每層編碼均表示不同的含義，兩層編碼共同完整的表達(dá)了問(wèn)題的解，提供了更多的解的信息，從而使每一個(gè)抗體都可以更準(zhǔn)確的表達(dá)調(diào)度問(wèn)題的解.

2.2 抗體評(píng)價(jià)標(biāo)準(zhǔn)的制定

在本算法中對(duì)個(gè)體的評(píng)價(jià)是以抗體的期望繁殖率為標(biāo)準(zhǔn)的.

算法中的期望繁殖概率設(shè)計(jì)由抗體的濃度和該抗體對(duì)應(yīng)的適應(yīng)度共同決定，抗體的期望繁殖概率決定了算法的選擇機(jī)制.在進(jìn)行選擇時(shí)既鼓勵(lì)了適應(yīng)度高的抗體，又抑制了濃度高的抗體，從而有效了保證了種群的多樣性.

一般的免疫算法在對(duì)抗體間的親和力進(jìn)行定義時(shí)，大多采用信息熵的方式.但是，基于信息熵的親和力計(jì)算過(guò)程往往比較復(fù)雜，比較適合求解采用二進(jìn)制編碼的抗體，將此方法應(yīng)用到整數(shù)編碼的抗體上會(huì)有較大的誤差.改進(jìn)的算法采用的R位連續(xù)計(jì)算方式，該計(jì)算方式簡(jiǎn)單易行，加快了算法執(zhí)行的效率，能夠在一定程度上反應(yīng)抗體之間的相似度.

2.3 精英保留策略

根據(jù)期望繁殖概率可以有效控制抗體的濃度，但是與抗原親和度較高的個(gè)體也可能因?yàn)樗臐舛冗^(guò)高而受到抑制，容易丟失最優(yōu)解，所以采用精英保留策略，每次更新記憶庫(kù)時(shí)先將與抗原親和度特別高的若干個(gè)體存入記憶庫(kù)中，然后再按照期望繁殖概率的大小從群體中選擇抗體存入記憶庫(kù).

2.4 變異算子及模擬退火操作

在算法的早期迭代的過(guò)程中，為加快算法向最優(yōu)解進(jìn)化的速度，采用反轉(zhuǎn)變異的方法.反轉(zhuǎn)變異能夠在解空間內(nèi)進(jìn)行大范圍的成熟查找，提高算法在早期的查找效率.

在算法進(jìn)行一定代數(shù)的反轉(zhuǎn)變異以后，種群中的抗體基本已經(jīng)接近最優(yōu)解，成熟的反轉(zhuǎn)變異法已經(jīng)對(duì)算法不再適用，采用小步成熟機(jī)制的換位變異法，使得算法有效的避免盲目的搜索，提高了算法的執(zhí)行效率.

免疫算法進(jìn)化到一定程度之后可能達(dá)到某個(gè)局部的平衡狀態(tài)，為避免此現(xiàn)象的產(chǎn)生，在算法后期加入模擬退火操作.模擬退火操作雖然能夠增強(qiáng)算法的局部尋優(yōu)能力，但是算法的執(zhí)行效率也隨之降低.為使種群質(zhì)量更優(yōu)，同時(shí)算法的效率更高，本算法對(duì)控制溫度下降的函數(shù)參考文獻(xiàn)［12］提到的一種自適應(yīng)變溫方法.當(dāng)前溫度可設(shè)為

T=ceil{T0［1-N/(M+1)］}

式中，N為當(dāng)前迭代代數(shù);ceil(*)表示對(duì)括號(hào)內(nèi)的內(nèi)容向下取整.

3 仿真測(cè)試和比較

為便于算法比較，選取文獻(xiàn)［13］中使用的流水車(chē)間調(diào)度問(wèn)題作為本文測(cè)試的對(duì)象.可以假設(shè)該調(diào)度問(wèn)題加工工件數(shù)n=12，加工階段m=3，各階段對(duì)應(yīng)的設(shè)備數(shù)為M1={1，2，3}、M2={4，5，6}、M3={7，8，9}.以文獻(xiàn)［14］的最優(yōu)子種群遺傳算法，文獻(xiàn)［15］遺傳算法，以及文獻(xiàn)［16］的免疫克隆選擇算法作為比較對(duì)象，對(duì)算法進(jìn)行性能分析.

本文所述的IASA算法，迭代次數(shù)M設(shè)為100，反轉(zhuǎn)變異代數(shù)M1為30，種群規(guī)模sizepop為40，記憶庫(kù)容量overbest為10，設(shè)置算法初始溫度T0為1000，結(jié)束溫度Tend為0.1，多樣性評(píng)價(jià)參數(shù)Pm為0.6，交叉概率Pc為0.7，變異概率Pm為0.4，進(jìn)行10次的仿真.文獻(xiàn)［16］僅給出了ICSA一次實(shí)驗(yàn)的仿真結(jié)果，文獻(xiàn)［14］、文獻(xiàn)［15］給出了10次獨(dú)立運(yùn)行仿真結(jié)果，與本文算法相對(duì)比，結(jié)果如表1所示.

表1 統(tǒng)計(jì)結(jié)果比較

圖2 免疫模擬退火算法收斂曲線

圖3 工件加工甘特圖

由表1可見(jiàn)，本文改進(jìn)的混合免疫算法能得到的最優(yōu)解為24，對(duì)應(yīng)解的進(jìn)化曲線和最優(yōu)解的甘特圖如圖2和圖3所示.從整體性能來(lái)看，改進(jìn)的混合免疫算法能在10次獨(dú)立運(yùn)行中6次達(dá)到最小值，并且平均性能也優(yōu)于其他三種算法.通過(guò)圖2可以看出，本文算法在早期能夠快速的進(jìn)行收斂，提高了算法效率，同時(shí)又避免了早熟的現(xiàn)象，在搜索最優(yōu)解方面也有較明顯的優(yōu)勢(shì).

4 結(jié)論

本文在對(duì)混合流水車(chē)間調(diào)度問(wèn)題進(jìn)行研究的基礎(chǔ)上，針對(duì)有多臺(tái)并行處理機(jī)的flow shop調(diào)度問(wèn)題，建立了相應(yīng)的調(diào)度模型，結(jié)合免疫算法和模擬退火算法的特點(diǎn)，提出了解決該問(wèn)題的混合免疫算法，并對(duì)改進(jìn)的算法進(jìn)行了詳細(xì)的分析.最后通過(guò)對(duì)典型的混合流水車(chē)間調(diào)度實(shí)例進(jìn)行仿真實(shí)驗(yàn)，表明了算法可行性和有效性.進(jìn)一步的研究工作是將免疫算法應(yīng)用到多目標(biāo)調(diào)度車(chē)間問(wèn)題上.

［1］王凌.車(chē)間調(diào)度及其遺傳算法［M］.北京:清華大學(xué)出版社，2003:138-145.

［2］唐立新，吳亞萍.混合流水車(chē)間調(diào)度的遺傳下降算法［J］.自動(dòng)化學(xué)報(bào)，2002，28(4):637-641.

［3］RIANE F，ARTIBA A，ELMAGHRABY S E.Sequencing a hybrid two-stage flow shop with dedicated machines［J］.International Journal of Production Research，2002，40(17):4353-4380.

［4］徐震浩，顧幸生.不確定條件下具有零等待的流水車(chē)間免疫調(diào)度算法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2004，10(10):1247-1251.

［5］余建軍，孫樹(shù)棟，郝京輝.免疫算法求解多目標(biāo)柔性作業(yè)車(chē)間調(diào)度研究［J］.計(jì)算機(jī)集成制造系統(tǒng)，2006，12(10):1643-1651.

［6］周安陽(yáng)，戴青云，王美林，等.一種改進(jìn)的免疫算法在車(chē)間調(diào)度中的研究［J］.中國(guó)制造業(yè)信息化，2012，41(19):16-18.

［7］劉星寶，蔡自興，王勇，等.用于全局優(yōu)化問(wèn)題的混合免疫進(jìn)化算法［J］.西安電子科技大學(xué)學(xué)報(bào)，2010，37(5):971-980.

［8］黃雨田，于彩燕，段富.免疫算法解決車(chē)間生產(chǎn)調(diào)度問(wèn)題方法綜述［J］.計(jì)算機(jī)工程與科學(xué)，2010，32(6):135-137.

［9］劉曉冰，呂強(qiáng).免疫克隆選擇算法求解柔性生產(chǎn)調(diào)度問(wèn)題［J］.控制與決策，2008，23(7):781-785.

［10］常桂娟，張紀(jì)會(huì).基于正交試驗(yàn)的免疫遺傳算法在調(diào)度問(wèn)題中的應(yīng)用［J］.信息與控制，2008，37(1):46-51.

［11］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.

［12］李修琳，魯建廈，柴國(guó)鐘，等.基于混合遺傳算法的混流混合車(chē)間協(xié)同調(diào)度問(wèn)題［J］.中國(guó)機(jī)械工程，2012，23(8):937-938.

［13］王萬(wàn)良，姚明海，吳云高，等.基于遺傳算法的混合Flow-shop調(diào)度方法［J］.系統(tǒng)仿真學(xué)報(bào)，2002，14(7):863-865.

［14］王金鵬，朱洪俊，周 俊.最優(yōu)子種群遺傳算法求解柔性流水車(chē)間調(diào)度問(wèn)題［J］.計(jì)算機(jī)應(yīng)用研究，2012，29(2):444-445.

［15］周輝仁，唐萬(wàn)生，魏穎輝.柔性Flow-Shop調(diào)度的遺傳算法優(yōu)化［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45(30):225-226.

［16］許愛(ài)軍.基于免疫克隆選擇算法的混合流水車(chē)間調(diào)度方法［J］.計(jì)算機(jī)應(yīng)用于軟件，2013，30(3):76-77.