摘  要： 對柔性流水車間調度問題（FFSP）進行了分析闡述，在此基礎上對某飼料廠的飼料生產過程建立了具有機器靈活性的柔性流水車間調度模型，該模型中存在多臺制粒機，既能加工大顆粒飼料，又能加工小顆粒飼料，但是必須在開始加工之前確定各臺機器的用途，增加了柔性流水車間調度的難度。利用新型的粒子群算法以最小化最大完工時間為目標對該模型求解，為了克服粒子群算法易陷入局部極值的缺點，提出基于位置相似度的鄰域結構，并對鄰域內的較優粒子采用基于最大完工時間排序的學習方式進行局部搜索。實驗結果表明，該方法有利于克服粒子群算法的早熟缺陷，有效地解決了飼料生產調度問題，有一定的應用價值。

　　關鍵詞： 柔性流水車間；機器靈活性；飼料；局部搜索；粒子群

0 引言

　　柔性流水車間調度問題（Flexible Flowshop Scheduling Problem，FFSP）是一種更加復雜也更貼近實際的流水線調度問題，屬于典型的NP難問題。由于該問題具有重要的學術價值和應用價值，在將近半個世紀的研究中已取得較大的進展。早期對柔性流水車間調度問題的求解主要是利用精確算法[1]和啟發式方法[2]。精確算法在理論上可以得到調度問題的最優解，但是在求解時間上無法讓人接受，一般只用來解決小規模問題。而啟發式方法能夠在較短時間內給出解決方案，但是解的質量無法保證。近年來智能算法[3-6]得到廣泛青睞，如模擬退火算法、禁忌搜索算法、免疫算法、遺傳算法、蟻群算法、蜂群算法、粒子群算法等。

　　本文對某飼料廠的飼料生產過程進行調研以后，發現目前的飼料行業普遍還采用人工調度，調度計劃的優劣完全取決于調度人員的經驗。而飼料生產過程可抽象為柔性流水線，于是本文建立了一種帶機器靈活性的柔性流水車間調度模型，利用智能算法——粒子群優化（Partical Swarm Optimization，PSO）算法對其進行求解。設計了一種有效的編碼及解碼方式，因為粒子群算法存在其固有的早熟缺陷，在柔性流水車間調度問題上的應用效果還有待提高，因此本文提出基于位置相似度的鄰域結構，并對鄰域較優粒子采用基于最大完成時間排序的學習方式進行鄰域搜索，改善解的質量，實驗結果表明本文提出的方法是有效的，有一定的應用前景。

1 具有機器靈活性的柔性流水車間調度問題描述

　　具有機器靈活性是指：以柔性流水車間調度問題[2]為基礎，在某道或多道加工工序中存在多用途的機器，但是該機器具體用于哪種用途需要在加工開始前確定，一旦加工開始，其用途就不可再改變。下面以某飼料廠生產過程為例介紹。

　　對某飼料廠一個生產車間的生產狀況進行調研以后，將飼料生產的兩個主要流程抽取出來建立一個調度模型。飼料在類型上主要分為顆粒飼料和膨化飼料，其中顆粒飼料分為大顆粒飼料和小顆粒飼料。所有的飼料在生產過程中首先要經過配料過程，該生產車間共有配料線5條。配料完成后顆粒飼料需要經過制粒機制成顆粒，而膨化飼料則需要用膨化機進行膨化。該車間共有制粒機5臺，膨化機3臺，其中有1臺制粒機只用于制大顆粒，1臺制粒機只用于制小顆粒，其余3臺制粒機既可以制大顆粒也可以制小顆粒。但是為了保證產品質量，生產過大顆粒的制粒機不能改制小顆粒，同樣生產過小顆粒以后也不能再用于生產大顆粒。

　　該車間的調度任務主要有三點：

　?。?）決定3臺可以制大顆粒飼料也能制小顆粒飼料的制粒機具體用于哪種用途；

　?。?）制粒機的用途確定以后即要確定所有產品的加工順序；

　　（3）決定每種產品在每道工序具體使用哪臺機器。

　　該問題為具有機器靈活性的調度問題，相比基本的柔性流水車間調度來說多了一個選擇機器用途的步驟，所以難度上有所增加。

2 粒子群算法介紹

　　粒子群優化算法自誕生以來，在無約束連續優化領域體現了其巨大的優化潛能，該算法結構簡單，易于實現，算法收斂速度快，魯棒性好。

　　因為粒子群算法的提出是為了解決連續優化問題，因此并不能直接用于組合優化問題的求解。對此，本文采用離散粒子群優化算法，根據粒子群算法的優化機理，離散粒子群算法中粒子采用整數編碼，并利用下式來更新粒子：

　　其中vi（k）和xi（k）表示粒子在第k次迭代時的速度向量和位置向量；pbest和gbest分別是粒子的歷史最優位置和種群的歷史最優位置；表示交叉操作，具體的交叉方式采用參考文獻[5]中的方法，對交叉的兩個個體pop1和pop2隨機選擇交叉區域，將pop2中的交叉區域加到pop1中對應的位置，刪除pop1中已在pop2的交叉區域出現過的工件，并進行相應的映射替換。

3 問題求解

　　3.1 粒子的編碼及解碼

　　利用粒子群算法對調度問題求解首先要考慮的是粒子的編碼及解碼方式，本文采用基于工序的編碼方式，即用整數序列來表示產品的加工順序，如一個加工任務需要加工5個產品，則隨機產生一個粒子：[2 3 1 4 5]，該編碼表示先加工2號產品，再加工3號產品、1號產品、4號產品，最后是5號產品。

　　粒子的編碼方式確定以后，就需要有解碼方式，本文采用最先空閑機器規則，參考文獻[7]中有定義：在確定的加工優先級的約束下，機器無閑置工件分配規則是一種最優分配模式。因此得到工件加工順序（從第二個階段開始工件的加工順序由前一加工階段的完成順序決定）后，需要對工件在各道工序上的加工順序和加工機器作出選擇，最先空閑機器規則具體描述見參考文獻[4]。

　　為了解決機器靈活性問題，本文在原有解碼規則的基礎上進行改進：在調度前，將多用途的機器放入一個集合中，例如common={2，3，4}，表示2、3、4號機器屬于多用途機器，在最先空閑機器規則的第二步中，如果產品可用common集合中的機器加工，則分別計算產品在集合中各機器上加工的理論時間，若結果顯示要選擇common集合中的機器來加工，則將該機器從common集合中移除，并固定用于加工該類產品，依照此思想，當common集合為空時，所有機器的用途就確定了，接下來的產品生產安排可以按照最先空閑機器規則來分配加工機器。

　　3.2 局部搜索策略

　　單純的粒子群算法容易陷入局部極值，為使算法能有效地擺脫局部極值的束縛，進行有效的局部搜索是很有必要的。定義粒子相似度：對兩個D維的粒子，其相似度為D′/D，其中D′表示兩個粒子有D′維相同。例如對粒子P1：[3 1 5 4 2]和粒子P2：[3 1 4 2 5]，其相似度為2/5。

　　有了粒子相似度的概念，規定粒子的鄰域范圍為與該粒子相似度高于某一閾值的所有粒子，在此本文采用一種基于最大完成時間排序的學習方式（Makespan Rank Based Learning，MRBL）進行局部搜索，局部搜索的時機為種群每更新一次之后，對每個粒子都進行一次局部搜索，具體的搜索方法如下：

　　（1）計算當前粒子與種群其他粒子的相似度，找出依據相似度閾值確定的鄰域中適應值最優的粒子。

　?。?）計算鄰域最優粒子對應的調度結果，找出完工時間較大的y個待加工的產品，例如完工時間如表1所示，若取y=2，則將產品2和產品7從加工序列中移除，然后依次將產品2和產品7試探性地插入到剩余加工序列的所有可能位置，最后將產品2和產品7放到能最小化最大完工時間的位置，得到一個新的加工序列。

　?。?）將新得到的序列的適應值與原粒子的適應值比較，若優于原粒子，則用新位置更新原粒子位置，否則原粒子不變。

　?。?）若所有粒子都已進行局部搜索，則局部搜索結束，否則繼續對下一粒子進行局部搜索。

　　步驟（2）中的y值實際上表示了局部搜索的深度，當y值過大時，局部搜索的時間將會過長，甚至讓人無法接受，而y值過小，會導致局部搜索深度不夠，找到局部更優的幾率減小，因此y的取值在一定程度上會影響算法效率。參考文獻[8]中采用實驗的方法確定在粒子為50維時y取6能得到較好的效果，然而現實問題的維數是不確定的，對每種情況都采用實驗的方法去尋找恰當的y值顯然很不實際，參考文獻[9]中提到，考慮到歐式空間多點極限布局，哈密爾頓回路排列外形近似正方形，因此為平衡局部搜索深度和搜索效率，本文對y值進行隨機選取，其范圍為2~D/4之間，D為問題的維數。

　　3.3 算法流程

　　利用本文算法求解帶機器靈活性的柔性流水車間調度問題的步驟如下：

　?。?）初始化：設定粒子群的種群大小和最大迭代次數，隨機產生粒子的初始位置、初始速度和多用途機器集合common，以及粒子相似度閾值；

　?。?）求出每個粒子的適應值，并初始化所有粒子的個體極值和全局極值；

　　（3）根據式（1）和式（2）更新粒子位置和粒子速度；

　?。?）求出每個粒子的適應值并更新所有粒子的個體極值和全局極值；

　?。?）對每個粒子找出其鄰域最優粒子，執行一次局部搜索，并更新粒子個體極值及全局極值。如果達到最大迭代次數，則轉步驟（6），否則轉步驟（3）；

　?。?）結束算法尋優過程，輸出最好解。

　　3.4 實例求解與分析

　　現假設要同時生產10種飼料，其中3種為大顆粒飼料，2種為小顆粒飼料，其余5種為膨化飼料，各飼料在各工序（機臺）上的加工時間如表2所示。

　　其中飼料1~飼料3為大顆粒飼料，飼料4~飼料5為小顆粒飼料，飼料6~飼料10為膨化飼料，加工時間為“-”表示該機臺不可用。

　　為了驗證算法的性能，分別利用帶局部搜索的粒子群算法和不帶局部搜索的粒子群算法對問題求解，種群大小均為40，迭代次數均為100次，局部搜索中的相似度閾值取0.85，兩種算法的迭代曲線圖如圖1所示。

　　從輸出的調度結果得到，common集合為空，且2臺通用制粒機用于制大顆粒飼料，1臺通用制粒機用于制小顆粒飼料，最終的完工時間為144個時間單位。圖1的迭代曲線顯示，帶局部搜索的粒子群算法在大約第4次迭代以后就找到了最優值，而不帶局部搜索的粒子群算法在大約13次迭代以后才達到最優值，說明本文的算法收斂速度快，尋優精度高。本例中本文算法和不帶局部搜索的粒子群算法在最后的求解精度上沒有區別，原因是本例規模較小，復雜度較低，最優值很容易找到。但是相對于飼料行業如今普遍使用的手工調度而言，本文提出的調度方法無論在求解速度上還是求解精度上都有十分出色的表現。

4 結論

　　本文針對某飼料廠生產過程的特點建立了帶機器靈活性的柔性流水車間調度模型，模型中存在加工機器靈活性也可稱為不確定性，在傳統的柔性流水車間調度基礎上要考慮某些機器的具體用途，機器用途的選擇不同，調度模型也不同，因此相比基本的柔性流水車間調度問題更有難度。本文利用有效的編碼及解碼方式，通過帶局部搜索的粒子群算法對模型進行了有效求解，求解結果較好，對飼料生產調度有一定指導意義。然而本文所做的研究有限，今后還可從編碼及解碼方式以及算法上做更多研究。

　　參考文獻

　　[1] 王圣堯，王凌，許燁，等.求解混合流水車間調度問題的分布估計算法[J].自動化學報，2012，38（3）：437-443.

　　[2] 黎展滔.具有成組約束的柔性流水車間作業計劃制定的啟發式算法[D].廣州：廣東工業大學，2012.

　　[3] 周輝仁，唐萬生，魏穎輝.柔性Flow-shop調度的遺傳算法優化[J].計算機工程與應用，2009，45（30）：224-226.

　　[4] 王凌，周剛，許燁，等.求解不相關并行機混合流水線調度問題的人工蜂群算法[J].控制理論與應用，2012，29（12）：1551-1557.

　　[5] 張其亮，陳永生.基于混合粒子群-NEH算法求解無等待柔性流水車間調度問題[J].系統工程理論與實踐，2014，34（3）：802-809.

　　[6] 張其亮，陳永生.解決具有混合約束柔性流水車間調度問題的粒子群優化算法[J].計算機應用研究，2013，30（11）：3253-3256.

　　[7] 唐立新，吳亞萍.混合流水車間調度的遺傳下降算法[J].自動化學報，2002，28（4）：637-641.

　　[8] 王大志，劉士新，郭希旺.求解總拖期時間最小化流水車間調度問題的多智能體進化算法[J].自動化學報，2014，40（3）：548-555.

　　[9] 熊偉，張江維，張火林.求解TSP問題的增強型自探索粒子群算法[J].華北電力大學學報，2009，36（6）：69-85.