改進的免疫模擬退火算法求解混合流水車間調(diào)度問題

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

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

0 引言

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

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

1 混合流水車間調(diào)度問題描述

1.1 問題描述

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

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

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

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

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

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

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

(1)約束條件:

1)順序約束

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

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

2)資源約束

ci，j=ck，j時，ci，j≤ sk，j或 ck，j≤ si，j，

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

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

3)時間約束

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

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

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

(2)目標函數(shù):

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

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

2 改進的混合免疫算法

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

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

圖1 改進的混合免疫算法流程圖

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

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

例如，對于分別有2個和3個并行設(shè)備的兩級 HFSP，設(shè)備集M1={1，2}，設(shè)備集M2={3，4，5}，其中的一個抗體的編碼為(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位，表示工件的加工順序為工件2→工件3→工件4→工件1→工件2→工件3→工件4;第二層編碼為9～16位，表示工件各階段對應(yīng)的加工設(shè)備為設(shè)備1→設(shè)備2→設(shè)備2→設(shè)備1→設(shè)備5→設(shè)備4→設(shè)備3→設(shè)備3.

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

2.2 抗體評價標準的制定

在本算法中對個體的評價是以抗體的期望繁殖率為標準的.

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

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

2.3 精英保留策略

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

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

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

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

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

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

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

3 仿真測試和比較

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

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

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

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

圖3 工件加工甘特圖

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

4 結(jié)論

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

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

［2］唐立新，吳亞萍.混合流水車間調(diào)度的遺傳下降算法［J］.自動化學(xué)報，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］徐震浩，顧幸生.不確定條件下具有零等待的流水車間免疫調(diào)度算法［J］.計算機集成制造系統(tǒng)，2004，10(10):1247-1251.

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

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

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

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

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

［10］常桂娟，張紀會.基于正交試驗的免疫遺傳算法在調(diào)度問題中的應(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］李修琳，魯建廈，柴國鐘，等.基于混合遺傳算法的混流混合車間協(xié)同調(diào)度問題［J］.中國機械工程，2012，23(8):937-938.

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

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

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

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