基于蟻群算法的柔性作業車間問題求解

何奔洋

（福州大學 經濟與管理學院，福建 福州 350111）

0 引言

隨著科技的不斷發展，社會環境也逐漸變得復雜多變，隨之而來的是產品的差異化與顧客需求的個性化逐漸地增強。對生產企業來說，制造的產品也從單一品種大批量向多品種小批量逐漸演變。對于這種變化，傳統的生產調度方式已難以適應，故柔性作業車間調度已逐漸成為生產企業提升經濟效益的重要手段之一。柔性作業的調度方式通過對資源的合理分配及利用，從而達到目標最優值，能夠減少資源浪費，更好地適應如今的社會需求環境，故此，對于柔性作業車間調度問題的研究也顯得十分必要。趙詩奎等對作業車間調度問題的模型及求解算法進行了總結，并對作業車間調度問題的發展前景進行了展望[1]，王凌等則對分布式車間調度問題的優化算法進行了分析與總結[2]，張亞明對柔性制造生產方式進行了深入的討論[3]，李愛平等則針對零件族為對象對柔性生產線進行了設計與優化[4]，余璇等提出了混合遺傳禁忌搜索算法對多目標柔性作業車間調度問題進行了求解[5]，何東東搭建了柔性作業車間調度問題模型并以改進遺傳退火算法求解[6]，李濤等以卷煙制絲的生產為例對柔性制造技術進行實際應用[7]。

蟻群算法是通過模擬螞蟻覓食的一種優化算法，最早應用于TSP問題的解決，后被應用于各項優化問題的求解中。因此，基于以上研究，本文引入了蟻群算法對柔性作業車間的調度問題進行求解，以柔性作業車間調度問題中最大完工時間的最小化為目標，搭建了優化模型，并引入了實例，驗證了模型的適用性及蟻群算法在求解柔性作業車間調度問題的可行性。

1 模型建立

1.1 問題描述

柔性作業車間調度問題可以描述為：有m個進行加工的器械，共n個零件待加工。第i個零件的工序數為qi且qi＞1，對于相同零件的工序加工順序有要求；每道工序至少可由一個機器進行生產，并且同一道工序經不同的機器加工時間也不同；不同的零件之間的工序可以不同。通過靈活地調度資源，以進行對各道工序的加工順序、加工機器的合理分配，從而實現工序最大加工時間最小的目標，以提升效率減少成本。

1.2 模型分析

在對工序的時間和資源進行分配及安排時，常常會遇到許多現實問題，因此，為了令模型更加地貼近實際，模型需滿足以下約束條件：

（1）任一工序可用的加工機器數大于一；

（2）同一時刻每個加工器械僅可加工一道工序；

（3）每個零件的任一工序僅可加工一次，且同一時刻僅可由一個機器加工；

（4）每道工序開始加工后必須加工完成，不可中斷；

（5）每個零件的不同工序間存在順序要求，不同零件的工序間不存在順序要求。

模型主要參數包括：

Fij：工序Oij加工完成的時間

Fijk：工序Oij在機器Mk上結束加工的時間

Bijk：工序Oij在機器Mk上開始加工的時間

pijk：工序Oij在機器Mk上的加工時間

1.3 模型建立

根據上述分析，建立工序最大完工時間的最小值優化函數為：

由上即為優化模型，其中：公式（1）為目標函數，表示求所有的零件中最大的工序加工時間的最小值；公（2）表示的是工藝約束，即每個零件的各個工序必須按照順序進行加工；式（3）表示每道工序由一臺機器加工且僅可加工一次，且開始加工后必須加工直至完成不可中斷；式（4）為同一加工機器在同一時間僅可加工一道工序。

2 算法設計

本文使用蟻群算法對問題進行求解。蟻群算法是通過模擬螞蟻覓食的生物行為，根據螞蟻走過的每條支路的長短等因素來計算支路上信息素的濃度，并根據信息素濃度的大小來計算選擇該支路的概率，并以輪盤賭的方式決定是否接受此解，從而在全局范圍內搜索滿意解。本文算法流程如圖1所示。

圖1 算法流程圖

蟻群算法首先進行各參數的初始化，隨后螞蟻隨機選擇覓食路徑，并在路徑上留下分泌的信息素，信息素濃度與路徑的長短成反比，同時信息素會揮發。后續螞蟻進行搜索時會根據信息素的濃度選擇路徑，信息素濃度更高的路徑會有更大的概率被選中。隨著搜尋螞蟻數量的不斷增多，信息素的濃度會逐漸增高，最終搜索出最優的方案。

3 實驗計算

3.1 算例數據

為驗證優化模型及算法的實用性，引入了算例對模型及算法進行仿真比較。表1中給出了6個零件以及10個加工機器的實例。其中包括了每個零件的各道工序的可加工的機器及不同機器上的加工時間。每列工序下左列為該道工序可進行加工的機器設備，右列為不同機器上的加工時間，每道工序均有至少一個機器進行加工，每個零件具有6道不同的工藝。

表1 零件加工實例

3.2 算法參數設置

對于本文所使用的蟻群算法，需要事先設置算法初始參數，參數設置如表2所示。

表2 算法參數設置

3.3 實驗結果

本文采用MATLAB編程求解。通過求解得到最優解為47min，可得到最小工時為47min的甘特圖，最優解甘特圖如圖2所示。根據甘特圖進行結果分析可得到，機器平均利用率為44.1%，其中機器1與機器10利用率最低，僅為6.4%，利用率遠低于平均利用率，而利用率最高的機器4與機器5則高達80.9%，最高機器利用率和最低機器利用率之間相差較大。所以在日常生產加工過程中，企業可針對利用率低的機器1和機器10進行改善，解決其利用率過低的問題，提高資源利用率。同時對于利用率較高的機器4和機器5需要做好日常維護，防止其因為使用過度而出現損壞等現象。

圖2 最優解甘特圖

由圖3，給出了蟻群算法求解結果的目標函數優化曲線。由圖可見，目標函數迭代至第10代即可得到最優值，從最初的54min下降至最優解47min，顯示了良好的收斂效果。通過優化模型優化后，加工總耗時相較優化前降低了13.0%，顯示了良好的優化效果，由此可見本文模型可以大幅度減少生產作業中柔性調度的完工時間，對柔性作業車間調度問題有良好的優化效果。并從實例中可看出，蟻群算法在計算中表現良好，能夠有效地求解出最優解，并可適用于柔性作業車間調度問題的模型求解中，在解決柔性作業車間調度問題中具有較強的實用性。

圖3 算法迭代圖

生產力不斷發展，社會也不斷地進步，單品種大批量制造中常用的調度方式已出現靈活度差、難以適應強個性化需求等種種問題，柔性作業車間調度的方式逐漸成為主流。本文基于此根據實際情況設立了約束條件，以完工實際最小化為優化目標搭建了整數規劃模型。采用了蟻群算法對模型進行求解，并為驗證模型和算法的實用性和應用價值引入實例進行仿真對比。從結果中可以看出，本文所設計的算法及搭建的模型具有較好的優化效果及收斂性，可作為生產柔性調度作業問題中的優化求解工具。在今后的生產作業優化中也具有較大的實用性，可根據具體情況靈活求解不同問題，具有較高的使用價值。