遺傳算法與模擬退火算法在FMS中的混合應用

王 濤，吳林彥，張如偉，王 琪，裴 翦

（1.山東建筑大學，濟南 250100；2.山推工程機械股份有限公司，濟寧 272023）

0 引言

FMS中的機器裝載問題為通過滿足技術約束（如可用機器時間和工具槽約束）來分配機器、所選作業的操作以及執行這些操作所需的工具，以確保系統不平衡性的最小化和吞吐量的最大化，同時求解目標函數，使結果更接近FMS環境的真實假設[1]。目前有許多針對FMS中的機器負載問題的研究，并提出了啟發式算法來優化系統的不平衡和吞吐量。然而到目前為止，探討的都是單一的算法而混合算法并沒有被廣泛應用于FMS問題中。因此針對柔性制造系統中的機器裝載問題，提出了一種結合GA和SA的高效混合進化啟發式算法，并進行了驗證。

1 研究背景

本文所考慮的柔性制造系統是由一些多功能的數控機床和其他能夠執行多種操作的設施組成。制造系統中的作業工序是批量可用的，同時每道子工序在加工過程中可以以隨機順序進行排列。當我們已知批次大小、操作次數、加工時間和每個作業所需的刀具槽數，假設有一套工具和一套機器可以生產我們所需的各種各樣零件。同時假設加工時間和刀具槽隨著分配給不同機器的工件變化而變化，那么就會出現有時某個工具槽工件短缺的情況。對于工件操作來說，通常分為兩種：

1）必選操作-此操作只能在特定的機器上進行。

2）可選操作-此操作可以在具有相同或相似加工時間和刀具槽的多臺機器上執行。

因此工序中的可選操作使得整個工作流程具有彈性的可能。本文所考慮的FMS具有四個多功能機器，每個機器具有480min的可用處理時間（8HRS＝1個移位）和5個工具槽。本文中符號的含義如表1所示。

表1 符號含義圖

表1（續）

本文討論的FMS問題列于表2中。機器裝載問題可以定義為：給定要生產的一組作業、給定在一組機器上處理作業所需的一組工具，用以上的資源分配簡化整個系統工作流程[1]。

表2 示例FMS問題

機器裝載問題通常被表述為二元目標問題，問題包含兩個主要目標函數，即系統不平衡性最小化和系統吞吐量最大化，并且細節如下[2]：

最小化系統不平衡性：即使得分配所有可行的作業后機器上剩余的空閑時間的總和，而系統中機的剩余時間總和必須是0（即實現系統中所有機器100%利用率）或是一個可以接受的數值。

最大化吞吐量：即使得計劃范圍內所有選定作業的批次大小的總和最大。

即：

因此組合目標函數（COF）為：

文獻[1～11]使用十個數據集來測試他們的方法的性能。而本文也使用相同的數據集來評估所提出的算法的性能。

2 混合進化啟發式算法

在其他文獻中，研究人員提出了兩種啟發式方法來選擇某一操作是否可以在幾臺機器上進行。Swarnkar和Tiwari根據機器中最高可用時間選擇機器[1]，MukopaDyayet等人實現了在可選操作的情況下根據操作所占的重要性比率選擇機器的方法[2]。本章主要描述了GASA的混合算法在解決機器裝載問題中的應用，同時討論了有關混合GASA算法實現過程中的各種設計問題。本文所提出的模型的結構如圖1所示，并在本章中討論了模型中各種模塊的實現。為了通過實例說明算法流程，本文采用的數據集如表2所示。

圖1 混合進化啟發式算法GASA流程圖

2.1 初始化

首先采用最短處理時間（SPT）規則生成初始序列，SPT規則所需的每個作業的總處理時間，已在表3中給出[12]。隨后以從最低處理時間到最高處理時間的升序排列作業。以表3給出的作業序列為例，生成的排列后的初始序列如圖2所示。而生成初始序列后，采用循環移位法生成其他n-1個序列，其中n=N。由于程序中的種群大小固定為10，而之前的操作只能產生6個種群，因此剩余的染色體是隨機產生的，而生成后每一個隨機產生的染色體用現有染色體檢查，避免染色體重復。

表3 作業所需的加工時間

2.2 適應度評價

通過目標函數作為約束條件確定染色體的適應值。目標函數的具體公式在上文已給出。

2.3 啟發式機器選擇

例如，考慮序列S=[6 1 5 2 3 4]。表4給出了每臺機器上可用的加工時間和刀具槽。

表4 四臺機器的加工時間和刀具槽

以第6號作業為例進行計算：

由表1可知，作業中的子工序為11，必要操作數為1，可選操作數為0。對于必要操作1，可用的機器編號為2，T2＝480-21×11＝249，t2＝5-3＝2。由于RTS1＝5＞0，RTS2＝2＞0，RTS3＝5＞0，RTS4＝5＞0；同時RTM1+RTM2+RTM3+RTM4＝480＋249＋480＋480＝480＝1689>=0。表示第6號作業選擇完畢。而在分配第6號作業之后可用的處理時間和工具槽在如表5所示。

表5 選擇作業6后四臺機器的加工時間和刀具槽

隨后我們對第1號作業進行計算：

作業中的子工序為15，必要操作數為0，可選操作數為1。對于可選操作1，可用機器是4和2。在可選操作的情況下，采用啟發式方法選擇可用機器，啟發式方法的工作方式在圖3中給出。根據計算選取比值最高的機器，由圖3可知選擇機器4來執行可選操作。T4＝480-10×15＝330，t4＝5-2＝3。由于RTS1＝5＞0，RTS2＝2＞0，RTS3＝5＞0，RTS4＝3＞0，并且RTM1+RTM2+RTM3+RTM4＝480＋249＋480＋330＝1539＞=0。表示第1號作業選擇完畢。而在分配第1號作業之后可用的處理時間和工具槽在如表6所示。

表6 選擇作業6后四臺機器的加工時間和刀具槽

圖3 作業1選擇示意圖

按照同樣步驟完成對所有工序的機器選擇和作業分配，最終機器上可用的加工時間和刀具槽如表7所示。此時已分配的工作序列AS=[6 1 5 2 3]，未分配的工作UAS=[4]。

表7 分配作業完畢后加工時間和刀具槽

此時目標函數值的計算過程如下：

系統不平衡性等于所有機器分配后所有機器的過度使用或未充分利用時間的總和。從表7中，機器1和機器3被過度利用，機器2和機器4未被充分利用。因此，SU＝（240 +249302＋330）＝37。

吞吐量等于產生的工作單位。分配的作業AS＝[6 1 5 2 3]。因此，TH＝11＋15＋16＋10＋12＝64。

目標函數等于適應度值為（TH/所有作業的總和）+（1-(SU/工廠中所有機器的可用時間總和））=（64/73）+（1-（37/1920））=0.8767+0.9807=1.8574。

2.4 模擬退火算法

模擬退火算法的本質為接受劣解以清除局部最優通道并接近全局最優，模擬退火算法在本流程中的主要功能為：將染色體群體中提取的最優和最差序列通過模擬退火算法選擇出來[13]。模擬退火算法中，初始溫度T在過程開始時設定為10。溫度T是一個參數，其作用類似于迭代每次減少0.9。溫度T每獲得一個新值，進行一次迭代。對于每次迭代，染色體S將會生成一個鄰域（S'）。將解S'與當前最優解S進行比較，如果S'的目標函數值優于S，則自動替換S'為當前最優解。否則，按照接受概率來接受S'。因此，當溫度T較高時，較低的解決方案被接受的可能性較高。通常凍結溫度可以根據程序所需的迭代次數來確定，本實驗設直到溫度低于0.7時迭代中止。一旦溫度降到凍結溫度以下，將染色體S作為當前最佳染色體返回到種群。這個過程同時作用于效果最優的和效果最差的染色體上，采用循環移位攝動法生成鄰域，且其接受概率為e(delta/T)。

2.5 選擇、交叉與變異

選擇操作將決定進化過程的流程，為遺傳算法提供了驅動力。在過去的二十年中，研究者們已經提出了許多選擇方法。經過驗證和比較之后本文提出的GASA采用簡單的輪盤賭選擇方法。本研究根據文獻[12]采用了四個不同的交叉算子：循環交叉，部分映射交叉，線性順序交叉和邊緣重組交叉，交叉概率為0.7。GASA從這四個交叉算子中隨機選擇。此外文獻[14]也提供了三個變異算子：相互交換突變、插入突變和反轉突變，突變概率為0.3。GASA從這三個變異算子中隨機選擇。

3 結果與討論

經過實驗和比較，GASA的最優控制參數如表8所示。同時本文采用文獻[1～11]中的數據集對所提出的GASA性能進行評價，并與文獻中采用的啟發式算法進行比較，結果如表9所示。

從表9可以看出，本文提出的GASA對于對于被測試的10個數據集中的7個能夠達到最佳解，表9最后一行中的平均COF（1.7401）表示本文提出的其優于考慮用于評估的其他啟發式的性能。

表8 GASA中各項參數

表9 GASA算法與文獻中算法的比較

表9（續）