基于蟻獅算法求解柔性作業(yè)車間調(diào)度問題的研究

王彥杰，向鳳紅

（昆明理工大學 信息工程與自動化學院，云南 昆明 650000）

0 引 言

生產(chǎn)調(diào)度的出現(xiàn)，使人們脫離了原始的生產(chǎn)模式，解放了勞動力。但隨著社會的發(fā)展，單一的生產(chǎn)調(diào)度模式已經(jīng)不符合人們?nèi)找嬖鲩L的需求，需尋求更加符合實際生產(chǎn)模式，可以有效解決此類問題的方法[1]。柔性作業(yè)車間調(diào)度問題（Flexible Job Shop Scheduling Problem，F(xiàn)JSP）[2]符合現(xiàn)代多變、復雜的生產(chǎn)環(huán)境，解決此類問題變得困難。因此眾多學者對其的關(guān)注度越來越高。

伴隨著智能時代的來臨，對于柔性作業(yè)車間調(diào)度問題的研究過渡到運用智能算法解決該問題。算法的出現(xiàn)可以極大程度地解決復雜性強、問題規(guī)模大的FJSP問題，為解決這一問題提供了工具。SINGH[3]等在傳統(tǒng)粒子群算法中引入量子行為策略，根據(jù)該策略的特點，提出了混合量子行為粒子群算法求解FJSP問題；喬兵[4]等在遺傳算法中設(shè)計了新的基因編碼方式，對不合法以及不合理基因進行重新設(shè)計，極大程度地增加優(yōu)秀基因的出現(xiàn)，在此基礎(chǔ)上解決FJSP所出現(xiàn)的問題，使收斂速度加快；賀仁杰[5]等利用不同種群之間的進化方式以及調(diào)整參數(shù)設(shè)置來推演優(yōu)秀種群的演進過程，并且根據(jù)種群之間的不同方式的演進過程和資源競爭，達到種群之間的信息共享，來推動算法整體的進化，提出用知識型協(xié)同進化算法求解FJSP問題；MASTROLOLLI[6]等利用禁忌搜索算法與新領(lǐng)域結(jié)構(gòu)相結(jié)合的方式，增加了求解FJSP問題時算法搜索的效率與范圍，避免了算法過早陷入局部最優(yōu)。

對于柔性作業(yè)車間調(diào)度問題的研究方法，主要是利用智能算法模擬實際生產(chǎn)，找尋最好的調(diào)度方案。但這些算法已被廣泛地使用，無法達到研究課題的創(chuàng)新性。目前，國內(nèi)外尚無人證明蟻獅算法求解FJSP問題的可行性?；谙仾{算法具有種群多樣、尋優(yōu)與適應(yīng)性強、調(diào)節(jié)參數(shù)少、求解與收斂精度高以及不受研究對象約束等各方面的優(yōu)點，本文使用蟻獅算法（Ant Lion Optimization，ALO），嘗試解決以最小最大完工時間為目標的FJSP問題，對實驗結(jié)果進行分析。

1 柔性作業(yè)車間調(diào)度

1.1 問題描述

FJSP包括兩個子問題，一是對加工工序進行合理的機器分配，二是對在所選加工機器上進行不同加工工件的加工工序進行緊前緊后安排。具體描述如下：柔性作業(yè)車間調(diào)度問題是n個工件 (j1,j2,j3,…,jn)可以在m臺機器(m1,m2,m3,…,mn)上加工，工件i(i=1,2,3,…,n)有qi道工序，每道工序所用的加工時間為t，允許工序可以在多個機器上進行加工操作，根據(jù)所選擇的加工機器的不同，加工時間也不同。調(diào)度問題研究的實質(zhì)就是解決工件工序是否可以在某幾臺機器上加工，根據(jù)選擇加工機器的不同，所產(chǎn)生的加工時間也不同。為實現(xiàn)最理想化的生產(chǎn)，為工件的工序進行安排以及選擇合適的加工機器，是整個調(diào)度方案的重點。Oij表示工件i的第j道工序；Mij表示工件i的第j道工序的可選工序集，Ri為每個工件的釋放周期，Di為每個工件的交貨期；Tijk表示工序Oij在機器k上的加工時間；Pij表示工序Oij的加工結(jié)束時間。在建立問題模型之前，需要對加工過程進行條件約束，具體如下：

（1）機器在某時刻有且只有一個工件可以進行加工操作；

（2）工件工序加工在某時刻只能選擇一臺機器進行加工操作；

（3）工件工序加工開始就不會停止，直到該工件工序完成加工；

（4）所待加工的工件，在選擇加工時無主次之分，僅根據(jù)調(diào)度方案安排工件的加工；

（5）相同工件的不同工序需考慮加工先后順序。

為了幫助讀者更好地理解，本文對文中所用符號進行定義，具體如表1所示。

表1 本文所用符號定義

1.2 模型建立

為證明蟻獅算法求解柔性作業(yè)車間調(diào)度問題的可行性，本文建立以最小最大完工時間Cm為優(yōu)化目標的單目標柔性作業(yè)車間調(diào)度模型。數(shù)學模型表示為：

具體約束條件如下。

（1）對于加工過程的約束，每個工件的每道工序一旦加工開始就不能中斷，如式（2）所示：

（2）確認是否可以在機器k上進行加工。式（3）為0-1決策變量，若工件i的第j道工序可以在機器k上加工，則，否則。

（3）工件的不同工序之間在加工時有著緊前緊后關(guān)系，如式（4）所示：

（4）Cij表示工件i的第j道工序開始加工時間，與在機器k上的加工時間Tijk之和不得超過工序Oij的結(jié)束加工時間Pij，如式（5）所示：

（5）工序Oij的加工結(jié)束時間要小于等于Oi(j+1)道工序的起始加工時間Ci(j+1)，如式（6）所示：

（6）工件的結(jié)束加工的時間Pj要小于調(diào)度方案最大完工時間Cm，如式（7）所示：

（7）某工件的所有工序可以在相同的機器上進行加工操作，如式（8）所示：

式中：Yijk表示工件i的第j道工序在機器k上的加工操作在機器k+1之前，Xijk表示工件i的第j道工序是否可以在機器k上加工。Yijk與Xijk都是0-1決策變量。

2 基于蟻獅算法求解單目標柔性作業(yè)車間調(diào)度問題

2.1 蟻獅算法

蟻獅優(yōu)化算法（ALO）[7]是通過模擬自然界中一種生物——蟻獅狩獵螞蟻的行為，來實現(xiàn)對目標函數(shù)優(yōu)化問題的求解。借助于蟻獅周邊螞蟻的隨機游走，保證該算法的全局搜索能力。與粒子群等算法不同，ALO算法有蟻獅和螞蟻兩個種群，通過蟻獅對螞蟻的捕獲，實現(xiàn)種群的進化。ALO算法具有求解精度高、調(diào)參少等優(yōu)點，得到了廣泛的應(yīng)用[8-9]。蟻獅算法具有螞蟻的隨機游走機制、陷阱對螞蟻隨機游走的影響、蟻獅的捕獲方式、捕獲螞蟻后重筑陷阱以及精英更新等機制，故ALO算法在多個領(lǐng)域得到應(yīng)用[10-12]。但無人證明其求解FJSP問題的可行性，故本文首次嘗試使用蟻獅算法求解柔性作業(yè)車間調(diào)度問題，證明其可行性，并分析問題，為下一步改進做準備。

2.2 編碼解碼

2.2.1 編碼

由于傳統(tǒng)的FJSP問題只考慮工件工序的加工順序，故一般只是對工件工序進行設(shè)計編碼，但是FJSP調(diào)度問題不僅要設(shè)計工序的加工方案，使其合理安排加工，不會出現(xiàn)因加工順序安排出錯導致加工沖突的事件發(fā)生，還要根據(jù)約束以及調(diào)度方案為每道工序設(shè)計合理的可加工機器，避免機器利用率不高以及加工工序在機器上加工時出現(xiàn)沖突的情況發(fā)生，因此僅對工序進行編碼設(shè)計無法達到合理安排以及解決問題的目的。因此，本文使用基于工序和機器的雙層實數(shù)編碼方法。該編碼針對工序以及加工機器兩部分進行編碼設(shè)計，合理解決加工工序間和機器間的沖突以及機器利用率不夠的問題，且最終得到正確可行的調(diào)度解。

例如，圖1顯示了擴展的基于工序和機器的雙層整數(shù)編碼方式所產(chǎn)生的染色體。為便于讀者理解，提出一個3×5的MOFJSP例子?，F(xiàn)有工序集為O1={O11,O12,O13}，O2={O21,O22}，O3={O31,O32,O33}；機器集為M={M1,M2,M3,M4,M5}。該編碼表示工件2的第1道工序可以在機器4上加工，工件1的第1道工序可以在機器3上加工，其表示的序列為：(O21,M4)，(O11,M3)，(O31,M1)，(O12,M1)，(O32,M2)，(O13,M5)，(O22,M2)，(O33,M5)。其中，基于工序編碼方案基因是確定具體合理的工件工序的加工安排；基于機器編碼方案是根據(jù)約束與調(diào)度方案安排合理的可加工機器，且機器與工序基因長度相呼應(yīng)。

圖1 擴展的基于工序和機器雙層編碼方式

2.2.2 解 碼

解碼是對設(shè)計的編碼信息以及編碼規(guī)則所形成的調(diào)度方案，利用甘特圖的形式，清晰地看出是否合理地安排加工過程，根據(jù)甘特圖所表示出來的問題進行進一步修改，直到找尋到最佳的調(diào)度方案，且不同的解碼設(shè)計方案會產(chǎn)生不同的調(diào)度解，影響著最終調(diào)度結(jié)果的優(yōu)越性。因此本文利用插入式貪婪算法，根據(jù)編碼信息以及編碼規(guī)則進行解碼操作。具體過程為：找尋到加工機器的空閑時間，判斷在該機器加工空閑時間里是否可以加工其他工件的工序。利用插入式貪婪算法對圖2編碼方式進行解碼，可得到可行解的甘特圖，其中圖2編碼方式的加工時間為[4，3，7，2，6，8，3，5]。如圖2所示，機器5上共可以加工兩道工序即O13與O33，判斷工序O13后是否有空閑時間可將工序O33前插進行加工操作；機器2可加工兩道工序O32與O22，判斷O32之后有無大面積的空閑時間將工序O32后插進行加工操作，這種操作可以使機器之間利用均衡，達到理想的加工效果。

圖2 基于插入式貪婪算法解碼得到的甘特圖

3 仿真實驗分析

本文使用Matlab 2014b進行編程，操作系統(tǒng)為64位 Windows10，處 理 器 為Intel（R） Core（TM） i5-6200U CPU 2.40 GHz，內(nèi)存4 GB。算法參數(shù)設(shè)置種群大小為100，迭代次數(shù)為200次。以Brandimarte基準算例中的MK01算例進行實驗驗證和分析。Brandimarte基準算例由MK01-MK10共計10個測試算例組成，算例均是在給定取值范圍中均勻且隨機分布生成，所需要加工的工件數(shù)根據(jù)算例的不同有10到20個不等，機器數(shù)也不同，有4到15個不等。初步使用MK01算例求解該問題。收斂迭代圖如圖3所示，實驗結(jié)果甘特圖如圖4所示。

圖3 收斂迭代圖

圖4 甘特圖

從圖3迭代收斂圖可以看出，蟻獅算法可以求解柔性作業(yè)車間調(diào)度問題，但第一次迭代時，得出的最優(yōu)解為65，說明蟻獅算法隨機生成的初始種群在解決單目標柔性作業(yè)車間調(diào)度問題時的質(zhì)量不好。從全局看，該算法迭代160次左右時才求得最優(yōu)值，算法的收斂速度較慢。算法在40代到135代之間共有100代左右，最優(yōu)值長時間處于55，逃離局部最優(yōu)的能力較弱，減緩了算法的收斂速度。從加工時長來看，蟻獅算法在MK01算例的加工環(huán)境中，完成加工所花費的最小最大完工時間較長，為55。從圖4柔性作業(yè)車間調(diào)度甘特圖來看，5號機器利用率極低，只有工件5的第1道工序和工件3的第5道工序這兩道工序在該機器上進行加工操作；而4號機器的加工空閑時間較多，沒有充分利用。

4 結(jié) 語

本文嘗試使用蟻獅算法求解單目標柔性作業(yè)車間調(diào)度問題，通過實驗驗證發(fā)現(xiàn)，蟻獅算法可以求解柔性作業(yè)車間調(diào)度問題。在實驗分析中，盡管蟻獅算法可以應(yīng)用在解決此問題上，但根據(jù)實驗分析發(fā)現(xiàn)，還是會出現(xiàn)隨機生成的初始種群質(zhì)量不好、算法的收斂速度較慢、逃避局部最優(yōu)能力較弱、完成加工所花費的最小最大完工時間較長、加工機器利用率低以及加工空閑時間較多等問題。下一步的工作是嘗試改進蟻獅算法，設(shè)計一種混合策略以優(yōu)化初始化種群，使初始種群的質(zhì)量變佳；引入遺傳算法中的交叉變異策略，提高迭代過程中的收斂與擇優(yōu)能力，降低局部最優(yōu)的發(fā)生。