基于混合果蠅-遺傳算法求解柔性作業車間調度問題

劉晶晶,劉業峰,黎 虹

(1.沈陽工學院 基礎課部，遼寧 撫順 113122;2.遼寧省數控機床信息物理融合與智能制造重點實驗室, 遼寧 撫順 113122;3.沈陽工學院 機械工程與自動化學院，遼寧 撫順 113122)

0 引言

近年來，智能制造技術迅速發展，柔性作業車間的調度問題具有重要的現實意義。 科學地調度其生產過程可提高企業生產效率，在一定程度上保障交貨時間，降低生產能耗。大量學者用不同的方法研究了自動化車間的生產調度問題。采用的方法主要有傳統運籌學方法(拉格朗日松弛方法[1]、分支定界法[2])等)和智能算法(群智能算法、人工智能算法、啟發式算法等)。 上述算法中，非智能算法的求解時間復雜度較高，并不適應大規模生產調度問題，而智能優化算法的計算效率較高，有時容易陷入局部極小，需要依據問題的不同特征予以改進。

遺傳算法(GA)是求解并行調度問題的有效算法，目前已有大量研究。文獻[3]根據機床的加工匹配特性，列出3個不同維度的優化目標，使用多層編碼技術提出了基于遺傳算法的生產調度方法；文獻[4]提出了求解生產調度問題的變鄰域改進遺傳算法；文獻[5]基于排列編碼技術提出了一種具有并行批處理和能力約束的混合車間調度遺傳算法;遺傳算法和其他智能優化算法相結合也是研究調度問題的熱點方法[6]；文獻[7]提出多維矩陣編碼技術，使用遺傳算法解決了混合流水作業調度問題；文獻[8]將傳統方法與遺傳算法相結合提出了基于單純形格設計的多目標遺傳算法求解車間調度問題。

其他啟發式算法或群智能算法也在解決生產調度問題中發揮著重要作用。文獻[9]提出了一種混合變鄰域搜索算法(HVNS)來求解混合流車間調度問題，給出了八種鄰域結構并提出了動態鄰域更新方法提取全局信息；文獻[10]基于生產車間調度，提出了兩階段啟發式算法，第一階段進行作業排序，第二階段基于禁忌搜索和貪心算法的列生產算法進行搶占式調度以最小化完工時間；除此之外，粒子群優化算法[11]、人工蜂群算法[12-14]等也被廣泛應用于生產調度問題中；部分調度問題將目標轉向生產排產[15-20]，仍圍繞生產效率最大化的主題提出了一系列啟發式算法[21-22]。

2012年，由臺灣學者潘文濤提出了果蠅優化算法(FOA)[23]，很快在優化領域受到關注。果蠅優化算法目前的研究進展[24], 包括維持種群多樣性、知識驅動策略與協同機制的設計等方面的改進工作。該文獻也介紹了果蠅優化算法在離散優化、多目標優化、不確定優化等方面的擴展性研究工作；求解并行調度問題時，多數學者對果蠅算法作了相應改進，包括編碼方式和鄰域結構生成方式的改進[25]、如何提高群體多樣性以及搜索方式的改進等[26-30]。2014年，文獻[31]將果蠅優化算法應用到煉鋼連鑄的離散生產調度問題中，取得了有效的結果；2018年，文獻[32]提出了一種多目標果蠅優化算法(MOFOA)來解決測試點的選擇問題； 2019年，文獻[33-34]也成功將果蠅優化算法應用到混合流水車間調度問題中。

綜上，柔性車間調度問題取得了一定的研究成果，但該調度問題屬于NP-Hard問題，現有的優化算法還存在不足，目前將遺傳算法和其它群智能優化算法結合使用或改進果蠅優化算法解決柔性作業車間調度問題的情況較多，將遺傳算法和果蠅優化算法結合在一起使用較少，本文結合果蠅優化算法和遺傳算法的特點，將二者結合使用，選取表達方式直接且解碼方便的多維矩陣編碼技術，引入尋優變異算子和自適應動態轉移策略，在兩階段種群進化的基礎上，以最小化完工時間為優化目標，建立了生產調度模型，得到了優化調度方案[35]。

1 問題描述

柔性車間生產調度問題是指多個工件在有限臺設備上加工。在不同時刻，一臺設備可以用于多個工件多道工序的加工，同時設備具有可選性和靈活性。因此，可以將不同設備的按序組合作為一個工件的加工路徑，以達到加工用時最小化的目標。

具體描述為：加工m個工件，每個工件各有n道工序，每道工序可以在任一臺機器上加工，連續兩道工序之間考慮運輸和工序切換等待時間，各工件各道工序的加工時間均不相同。現共有s套設備，每套設備的工作效率不同，目標為使得所有工件的總加工時間最短，如圖1所示。

圖1 柔性車間生產線運行圖

2 數學建模

2.1 符號表示

tcij：第i個工件第j道工序的加工完成時間；

tpij:第i個工件第j道工序的加工時間；

tranj,j+1：AGV小車將工件物料由第j道工序到第j+1道工序之間的運輸時間；

xijs[1]：0-1變量，當且僅當工件i的第j道工

序在機器號為s的機器上加工時為1，否則為0(i=1,2,,m)，(j=1,2,,n)，(s=1,2,3)；

yikj[1]：0-1變量，當且僅當工件i先于工件在第j道工序被加工時為1，否則為0(i,k=1,2,,m)，(j=1,2,,n)。

2.2 數學模型

將生產過程分解為“加工時間”和“工序間的運輸時間”，通過優化總加工時間來實現生產線的高效生產，現有m個工件在n道工序上加工。

2.2.1 目標函數

(1)

2.2.2 約束條件

根據自動化生產的實際調度需求，設定如下約束條件：

1)加工順序約束，即同一工件在前一道工序加工完畢送至下一道工序后開始加工。

tci,j+1-tci,j-tpi,j+1=tranj,j+1

(i=1,2,,mj=1,2,,n-1)

(2)

2)機器能力約束[1]，即同一臺機器不能同時加工多個工件。

tck,j-tci,j-tpk,j+(3-xijs-xkjs-yikj)U≥0

(k≠i,U為較大正數)

(3)

3)連續加工，即一個工件加工結束后立刻加工下一個工件。

tci+1,n-tci,n-tpi+1,n=0,i=1,，m-1

(4)

4)各道工序加工機器唯一性約束。

(5)

5)工序之間的順序關系約束。

yijs+ykjs=1(k≠i)

(6)

6)變量約束。

xijs∈{0,1},yikj∈{0,1}

(i,k=1,2,,m;j=1,2,,n;s=1,2,3)

(7)

3 基于FOA-GA算法的求解策略

FOA算法是基于果蠅覓食行為的生物學原理提出的一種智能優化算法。該算法分為兩個階段：嗅覺階段和視覺階段。通過兩個階段的不斷迭代實現覓食的優化，得到問題的滿意解。 FOA算法具有易于實現、控制參數少、便于進入問題特定的搜索環節等優點。但是，該算法強調對個體鄰域的搜索，缺少種群多樣性的變更，因此全局搜索能力較弱，容易陷入局部極小。

GA算法是利用生物進化中的自然選擇原理，依據適者生存的原則構建的計算模型，通過染色體的選擇、交叉、變異方式，進行種群的不斷迭代更新，從而找到最優解或滿意解。 GA算法操作稍復雜，但具有極大的靈活性，對于各類特殊問題都可以按照特定方式進行求解，可以較大程度地避免解集陷入局部極小。

本文結合柔性自動化生產線的加工調度問題，對FOA算法和GA算法進行改進，提出混合FOA-GA啟發式算法，以工件最短加工時間為目標函數，建立了局部搜索與全局搜索相結合的搜索方式，具體算法如下。

3.1 編碼方式

采用矩陣式編碼結構[7]矩陣的行號代表工件編號，矩陣的列號代表工件的加工工序，矩陣中的元素值代表加工的機器號。對于加工工件的任意給定排序，預先為各工件的各道工序隨機分配加工機器。

macij表示第i個工件的第j道工序在macij號設備上加工。另已知各工件在各道工序上的加工時間表為矩陣ProT，其中元素可各不相同。

3.2 適應度函數以及解碼方式

適應度為工件加工總時間的倒數(即第一個工件開始加工至最后一個工件結束加工所用時間的倒數)。在矩陣編碼機制下，采用啟發式算法解碼并計算適應度：

1)按工序搜索。將第k道工序中需要在機器m上加工的所有工件編號進行提取:

W={w1,w2,,wn}

(8)

式(8)中，w1,w2,,wn表示在第k(k=2,3,,n)道工序中第m號機器上加工的所有工件，取出上一道工序的完工時間集合:

(9)

2)排序選出在(8)中結束最早的工件，將其結束時間與第k道工序中第m號機器上正在加工工件的結束時刻作比較，二者取較大值，將其與運輸時間之和記為第k道工序中下一個工件的開始加工時間，即:

(10)

3)適應度為最后一個工件的加工完成時間與第一個工件開始加工時間之差的倒數。

(11)

3.3 算法流程

3.3.1 種群初始化

隨機產生初始種群，并計算當前最佳適應度值，記錄初步全局最優解fcur。

3.3.2 嗅覺階段

考慮到問題結構和解的離散性，采用多重交換(multi-swap)技術[31]產生每個個體的局部信息結構進行果蠅嗅覺階段的搜索，即在合適的范圍內進行工件加工機器安排的多重交換，在矩陣編碼方式下，其實際意義為工件加工路徑的局部尋優。如圖2所示(假設每道工序有5臺機器)，若交換第1、2行基因段，則工件1每道工序對應機器的加工路徑由1,5,2,3,3交換成2,4,3,2,5，這對于具有不同加工時長的各個工件尋找局部最佳加工路徑具有重要作用。若當前適應度優于交換前的適應度，則進行局部較優解以及種群個體的替換，更新種群。

圖2 嗅覺階段通過多重交換技術進行局部路徑搜索示意圖

3.3.3 交叉機制

為了豐富種群的多樣性，引入遺傳算法中的交叉機制。很多已有文獻中采用單點交叉或兩點交叉方式，本文采用單點交叉方式，父代兩兩交叉產生子代，采用精英策略保留優勢個體，在父代和子代中采用錦標賽的方式進行優勝劣汰。矩陣編碼形式下的交叉方式如圖3所示。

圖3 交叉操作示意圖

3.3.4 變異機制

1)基于實際生產情況(在每道工序3臺機器的情況下，1號、2號和3號機器生產效率依次降低)，選取一定比例的個體(本文選取80%)，設置尋優變異算法：計算當前個體中各工序中使用1號設備和3號設備的數量s1和s3，若s1>s3，變異時以β(本文β=0.8)為概率，將安排到3號機器生產的工件向效能較高的1號和2號機器調整，以提高生產效率，如圖4所示。

圖4 尋優變異算法操作示意圖

2)為避免陷入局部最優，選取20%比例的個體，按給定概率進行變異(由于選取的個體較少，本文設定變異概率為0.3)。 計算新的適應度并記錄當前最佳適應度和最佳個體。

3.3.5 視覺階段

二是相關課程的任課教師可以聯合團委、學生會等，精心設計暑期“三下鄉”社會實踐主題，引導學生在社會實踐中認識閩東、服務地方、提升能力，使學生對閩東特色文化的認識從感性上升到理性，進而增強實踐育人的實效性。比如：多渠道了解閩東革命老區的實際需求，結合學科專業特長，組織學生開展志愿服務，幫助老區人民解決實際困難，鍛煉和提高學生們的綜合素質能力；結合大學生創新創業教育，讓高校教師的科研成果、學生的創新思維在社會實踐中落地生根，實現成果轉換，惠及群眾。通過創新創業實踐，使學生逐步提高整合資源的能力、溝通協調的能力、統籌領導的能力等，從而為今后就業創業奠定良好的基礎。

整個種群向當前最優解的方向搜索。由于問題的解具有離散型，因此常規果蠅搜索方式并不適用于此。為了不改變種群的多樣性并使種群整體向好，采用如下方法：設置動態自適應轉移比例α(i)(i=1,2,,itermax)。

(12)

其中:N為種群規模。為了保持種群多樣性，在初始階段，α(i)取值較小，隨著迭代次數的增加，α(i)呈現增大趨勢(但有隨機擾動)，以加快收斂速度，將適應度較差的個體以α(i)為比例向最優個體調整，以加快種群的收斂速度。

具體流程如圖5所示。

圖5 FOA-GA算法流程圖

4 數值實驗

以某實驗室智能制造車間為原型：某生產線自動化加工單元主要由三臺智能加工設備組成。做出如下假設：車間具有三套自動化生產線，編號為1、2、3，按生產效率等級分別為高、中、低。2號設備比對應的1號設備加工時間多5個單位，3號設備比對應的2號設備加工時間多5個單位。需解決的問題是：m(一般為8的整數倍)個工件在生產線上按順序進行n個工序的加工，工件可以由AGV小車運輸調度，在對應工序的任一臺設備上加工，不考慮第一道工序開始前的物料運輸時間，如何使得總加工時間最短。

以16個工件、3道工序為例，設定各工件在各道工序加工所需時間如表1所示， AGV小車在各道工序之間的運輸時間如表2～3所示。

例如，表2中4.4387表示工件由第一道工序的1號機器運輸到第二道工序的1號機器所需時間。

表1 工件在各道工序的加工時間表(以1號機器為標準)

實驗參數設置如表4所示。

表4 參數設置表

為了排除實驗結果的隨機性因素，現給出10次實驗結果的平均值和最優值，在相同參數設置下分別對比FOA-GA、GA和FOA算法的實驗結果。使用MATLAB R2019a編寫程序，在8 G內存、1.6 GHz的CPU上運行，實驗結果如表5所示。

表5 三種算法最優加工時間平均值對比表(16個工件)

由表5可知，在加工16個工件時，FOA-GA算法、GA算法和FOA算法的最優解(即最短加工時間)分別為398.995 3、410.817 5和412.007 9比較其平均值，FOA-GA算法得到的工件加工時間比GA算法平均節約10.302 4個單位，比FOA算法平均節約12.100 4個單位，證明了算法的有效性。

現給出在FOA-GA算法下取得最優解時的調度方案。

圖6中，“1-1”代表第1個工件的第1道工序，機器編號1、4、7分別對應第1道工序的1-3號機器，機器編號2、5、8分別對應第2道工序的1-3號機器，機器編號3、6、9分別對應第3道工序的1-3號機器。當3套設備之間的生產效率差距較大時，尋優算子的作用更加明顯，機器分配的合理性更加顯著。FOA-GA算法的收斂曲線如圖7～8所示。

圖6 加工16個工件的生產任務甘特圖(FOA-GA算法)

如圖7所示，使用FOA-GAG算法，經過27次迭代后，曲線收斂，工件加工時間的最優解為398.9953個時間單位。為了體現視覺階段動態自適應轉移算子的效果，圖8給出了在近乎相同最優解下引入動態自適應轉移算子前后的實驗結果對比，可見引入動態自適應算子后，最優解曲線的收斂時間由第118次迭代步數加速至第27次迭代步數，效果顯著。

圖7 引入動態自適應轉移算子后的最優解收斂曲線圖

圖8 未引入動態自適應轉移算子時的最優解收斂曲線圖

采用GA算法和FOA算法取得最優解時的收斂曲線如圖9～10所示。

圖9 最優解收斂曲線圖(GA)

圖10 最優解收斂曲線圖(FOA)

由圖9可知，GA算法在經過74次迭代后取得最優解為410.817 5，比FOA-GA算法多耗時11.822 2個時間單位。從圖10可以看出，FOA算法在迭代140次后取得最優解412.007 9，比FOA-GA算法多耗時13.012 6個時間單位，且FOA算法收斂較慢。以上對比證明了FOA-GA算法的優越性和有效性。

實際生產中，工件數量較大，現分別考慮加工40、80、120、200個工件時的情況，并將加工16個工件時的實驗結果也記錄于表6中。在每次實驗中，工件在各道工序的加工時間隨機生成在[36,50]之間，工序間的轉移運輸時間隨機生成在[3,10]之間，比較10次實驗的平均值。

表6 3種算法的加工時間對比表(3道工序、不同工件數)

由表6可以看出，分別加工16、40、80、120、200個工件時，FOA-GA算法均表現出優勢所在。 例如，當加工80個工件時，FOA-GA算法所得的最優解為1 584.3，工件的加工用時比GA算法平均節約37.5個單位，比FOA算法平均節約50.4個單位；當加工200個工件時，FOA-GA算法的最優解平均值為3 809.3，加工用時比GA算法平均節約28.7個單位，比FOA算法平均節約117.7個單位。

實際加工中，往往不只3道工序，現給出在加工16個工件、工序個數分別為3、4和5時3種算法在10次實驗中平均值對比結果，如表7所示。

表7 3種算法的加工時間對比表(16個工件、不同工序數)

表7給出了在工件數相同、工序數不同的情況下，3種算法的結果對比，可以看出FOA算法均占有優勢，再一次驗證了算法的有效性。

5 結束語

本文在結合果蠅優化算法(FOA)和遺傳算法(GA)的基礎上，通過矩陣編碼機制，引入局部加工路徑搜索技術和以提高生產效率為原則的尋優變異算子，解決了工件自動化生產調度問題，再通過自適應動態轉移算子，加快了算法的收斂性。通過數值實驗，橫向對比GA算法和FOA算法，證明了FOA-GA算法的優越性和有效性。將上述算法依據企業的智能車間進行改進，便可進行實際應用。