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

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

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

0 引言

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

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

1 混合流水車間調度問題描述

1.1 問題描述

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

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

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

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

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

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

1.2 建立數學模型

(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工序安排在同一設備ci，j上，必須先完成前個工件的工序才能加工下件工件，即任一時刻該設備不能同時處理兩個不同的工件.

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}

同一階段上，工序的開始時間與結束時間的關系，工序一旦開始加工就不會被中斷.

(2)目標函數:

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

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

2 改進的混合免疫算法

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

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

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

2.1 編碼及解碼設計

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

例如，對于分別有2個和3個并行設備的兩級 HFSP，設備集M1={1，2}，設備集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位，表示工件各階段對應的加工設備為設備1→設備2→設備2→設備1→設備5→設備4→設備3→設備3.

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

2.2 抗體評價標準的制定

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

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

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

2.3 精英保留策略

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

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

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

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

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

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

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

3 仿真測試和比較

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

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

表1 統計結果比較

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

圖3 工件加工甘特圖

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

4 結論

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

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

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

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

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

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

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

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

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

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

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

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

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