基于改進模擬退火－遺傳算法的FMS生產排程優化分析

陳應飛，彭正超，胡曉兵，李彥儒

基于改進模擬退火－遺傳算法的FMS生產排程優化分析

陳應飛1，彭正超1，胡曉兵1，李彥儒2

（1.四川大學 機械工程學院，四川 成都 610065；2.中國核動力研究設計院，四川 成都 610200）

制造型企業在采用柔性制造系統進行產品多品種生產加工時，車間生產調度問題（即生產排程）也是影響產品生產效率的一大重要因素。生產排程問題實際上是一個NP-C問題，它沒有一個確定的解，只能是結果趨于最優，所以許多科研人員采用遺傳算法來解決柔性制造系統的生產排程問題。本文以某機床廠的機床關鍵箱體類零件為研究對象，在遺傳算法的基礎上融入粒子群優化算法和模擬退火算法，對遺傳算法的初始種群、交叉和變異操作等進行處理，期望能夠使算法的收斂速度更快、結果更優。以該機床廠的需求為例，以成組布局的方式進行生產設備的布局，運用Matlab軟件對其生產排程方案進行優化分析，結果表示針對該生產對象提出的生產排程優化算法有效可行，可以在實際生產中加以運用。

柔性制造系統；生產排程；模擬退火遺傳算法；Matlab優化

現代制造型企業競爭越來越激烈，任何一個小的失誤都可能導致整個市場的丟失，從而使得企業的經濟受到較大的打擊，甚至可能有破產的風險。在制造企業中，如何進一步提高零部件產品的生產效率始終是一個值得探索的問題。建立FMS（Flexible Manufacture System，柔性制造系統）是提高零部件產品生產效率的一項重要措施，但是如何在此基礎上更進一步提高零部件產品的生產效率，經過研究人員大量的實驗和分析研究發現，生產調度問題（又稱生產排程）也是影響零部件產品生產效率的另一個重要因素。

為此，許多研究人員在生產排程問題上進行了大量的實驗和數據分析，希望能得到最優的排程方式，使產品的生產效率能夠提高到最大化。覃炳發等[1]對汽車零配件間的生產順序進行研究并建出模型，在模型建立過程中對模型建立的關鍵點和困難點進行了匯總，對模型的最終實施效果進行了評定，最后建立了汽車零配件生產排程的線性整數規劃模型；Gonzalo Mejía等[2]通過使用Petri網框架解決一般多目標調度問題，最后在大量的計算實驗中驗證了該通用框架在獲得高質量解方便的適用性；潘怡穎等[3]研究了一種基于零件顏色和零件種類相融合的染色體編碼方法，并且還構建了一種基于最大化零件生產量和最小化換色次數的多目標生產排程模型，通過使用遺傳算法解決生產調度問題，最后通過實例驗證了該方法的有效性和穩定性；李飛等[4]對生產排程優化中的遺傳算法和模擬退火算法進行了詳細介紹，并對兩種優化算法進行了綜合運用得到模擬退火遺傳算法，對該算法的總體流程進行設計與改進，最后把該方法運用到分段車間實驗中進行驗證并與標準的遺傳算法進行比較分析；鐘志慶等[5]將綠色制造理念與零部件最短完工時間相結合，建立多目標生產排程優化問題，并通過遺傳算法對該問題進行優化分析，最后通過合理設計出適應函數，選擇、交叉和變異算子從而成功求解出模型。

1 機床關鍵箱體類零件生產計劃問題

1.1 生產計劃的概念和層次

生產計劃是指企業對自身生產的產品形式和種類、產品數量、產品質量和生產進度進行統籌安排的過程。對于大型制造型企業來講，生產計劃可以分為兩大類，一個是廠級生產計劃，另一個是車間級生產計劃。生產排程問題就屬于車間級生產計劃問題，其主要對產品加工過程中的工序進行合理安排。生產計劃的具體層次和相應特征如表1所示。

表1 生產計劃的層次和特征

1.2 生產計劃約束條件

企業在制定生產計劃的同時，也需要對產品的生產指標進行確定，如產品數量、產品質量等級、產值以及交貨日期等。在完成指標的過程中，可能會受到某些方面的生產約束導致企業不能順利完成生產指標。生產約束對企業生產所產生的效應類似于木桶效應，約束條件中的最低值將決定企業的最大生產能力。產生生產約束的原因是多方面的，有物料供應、企業生產能力、市場環境和資金等，其中物料供應、企業生產能力和市場環境是最主要的影響因素，其中企業生產能力是由企業自身條件決定的，企業可以通過不斷的優化和改進提高自身的生產能力。

（1）企業生產能力，是指企業在一定的時間范圍內，企業員工利用相關設備進行有效生產的產品的最大產量。企業生產能力的約束主要來自于生產設備、員工素質和生產流程等。

（2）物料供應，包括原材料、毛坯件、半成品件和成品件等。及時的物料供應能夠最大程度地提高加工設備的利用率，從而能夠提高產品產量、縮短生產周期。

（3）市場環境，也是影響企業生產計劃的重要因素。決策者正確地判斷市場發展趨勢能夠加大產品銷售量，減少產品庫存量，增加現金流，順利開展下一項生產任務。

1.3 機床廠制定生產計劃的基本流程

某機床廠在制定生產計劃過程中的基本流程如圖1所示。首先由營銷部門根據銷售訂單類型和數量、單產品銷售計劃（非訂單產品的銷售計劃）、企業自身的生產能力、生產成本和原料供應情況等制定月度銷售計劃，并下發至運行部。運行部門根據月度銷售計劃進行分解處理，制定出總生產計劃，其中包括日生產計劃、周生產計劃和月生產計劃，并下發至生產部。生產部門根據總生產計劃要求進行產品的生產加工，產品加工完成后又返回營銷部進行產品的銷售。同時，生產部門也會根據生產車間的實際情況，實時地將生產情況反饋到營銷部和運行部，確保能夠及時地對銷售計劃和生產計劃進行準確的調整，以免影響產品的生產和銷售。

圖1 某機床廠制定生產計劃的基本流程

2 改良模擬退火遺傳算法的設計

2.1 改良模擬退火遺傳算法中的各種算法

（1）粒子群優化算法

粒子群優化算法，又稱為微粒群優化算法，是科學家通過觀察鳥類的覓食行為而逐步發展的一種隨機搜索算法。粒子群算法進行優化計算的基本思路是將所求問題的解轉換為三維空間中具有一定初速度和初始位置的微小粒子，并使這些微小粒子在解空間中不斷地去尋找最優粒子，并且在尋找過程中粒子的速度和位置都會不斷的調整。

粒子在解空間中的運動方程為：

式中：為慣性權重；為粒子速度，為粒子下一個位置的速度；1、2為常數；1、2為隨機數；b為當前個體的最佳位置；p為個體的當前位置；g為粒子種群的當前位置；p'為個體在p位置的后一個位置。

粒子群優化算法的基本流程如圖2所示：①初始化粒子的相關參數，隨機生成粒子的速度和位置信息；②通過目標函數計算粒子的適應度值；③通過公式更新各粒子和種群的速度與位置信息；④判斷是否滿足停止條件，如最大迭代數或是否收斂等，若滿足停止條件則結束該算法，若不滿足停止條件則返回第2步，依次循環。

圖2 粒子群優化算法基本流程圖

（2）模擬退火算法

模擬退火算法以其簡便、靈活等特點在車間調度和組合優化問題中得到了比較廣泛的使用。模擬退火算法最早由Metropolis等提出，其中心思想本質上就是不斷迭代、不斷改進的一個過程，并且有強的有限區域搜索能力。

模擬退火算法的數學公式為：

式中：P為新解取代舊解的概率；E表示目標函數的函數值為；E表示經過模擬退火算法迭代后的目標函數的函數值為；為算法中的溫度控制參數。

可以看出，當參數的值較大時，舊解被新解取代的概率很高，但隨著迭代的不斷進行，參數的值越來越小、并最終趨近于0，此時舊解被取代的概率極低，并以此作為全局的最優解。

模擬退火算法的基本流程如圖3所示：①設定初始狀態值，確定溫度參數，產生隨機初始解E；②擾動產生新解E；③由Metropolis準則判斷是否接受新的解，若接受新解則輸出新解，若不接受新解則輸出舊解；④判斷由Metropolis準則輸出的解是否滿足停止條件，若滿足則跳出計算、獲得最優解，若不滿足則改變控制參數的值、返回第2步，依次循環，直至獲得最優解。

圖3 模擬退火算法基本流程圖

（3）遺傳算法

遺傳算法是一種借鑒生物界“優勝劣汰”機制演化過來的并行搜索方法[6]，具有操作簡單、通用性強、受約束條件少和全局搜索能力強等特點，在解決組合優化問題中得到了比較廣泛的應用，也是未來智能制造領域的關鍵性技術之一。

運用遺傳算法解決組合優化問題類似于求一個函數的最大值（或最小值）的優化問題，其數學規劃模型為：

式中：max()為目標函數；為決策變量；∈、∈為約束條件；為基本空間；為的子集。

滿足約束條件的解稱作可行解，集合表示所有滿足約束條件的解所組成的集合，稱作可行解集合。

遺傳算法基本流程如圖4所示：①針對預解決問題的優化變量進行某種形式的編碼；②確定問題的適應度函數并計算個體適應度值；③若滿足優化精度或達到最大迭代次數則輸出最有問題解，否則進入下一步；④選擇、交叉、變異操作產生新個體，返回第二步，依次循環。

圖4 遺傳算法基本流程圖

2.2 改良模擬退火遺傳算法的設計

模擬退火算法幾乎不具備全局空間搜索的能力，但其局部空間搜索能力較強，而遺傳算法在局部尋優能力方面則較差，所以將模擬退火算法與遺傳算法相結合，能夠取長補短。再在遺傳算法的種群初始化中融入粒子群優化算法，能夠先一步優化種群個體，使得算法的優化效率更高，優化效果更好。改良模擬退火遺傳算法流程圖如圖5所示。整個算法以遺傳算法為主體，在初始化種群中融入粒子群優化算法，在交叉算子、變異算子和新個體適應度調整方面融入模擬退火算法。

改良模擬退火遺傳算法基本流程如圖5所示，具體步驟如下：

（1）設定算法相關固定參數，個體交叉概率P、個體變異概率P，模擬退火算法的初始溫度0、種群規模、最大迭代數等；

（2）通過粒子群算法獲得初始種群；

（3）評價種群中個體適應度，然后選擇優秀個體生成種群，在選擇優秀個體時采用輪盤賭法和最大保留法相結合的方式進行；

（4）進行個體交叉操作。以交叉概率為指標進行個體交叉，將產生的子代個體適應度值與父代個體適應度值進行比較，若子代個體適應度值大于父代個體適應度值則接受子代個體為當前個體；若子代個體適應度值小于或等于父代個體則按接受概率判斷，若＞random則接受子代個體為當前個體，否則保留父代個體為當前個體；

（5）進行個體變異操作。接受原則與個體交叉類似，以變異概率P作為判斷指標；

（6）全局退火操作。全局退火觀念即對全局范圍內個體適應度值進行適當拉伸操作，避免個別特別優秀的個體充斥整個種群，影響搜索效率。在溫度較高時使性能相似的個體在適應度值方面差異較小，在溫度較低時擴大個體的適應度值，便于顯示優秀個體的優勢。

圖5 改良模擬退火遺傳算法基本流程圖

其算法為：

式中：f為第個個體的適應度值，f'為第個個體迭代過后新的適應度值；為當前溫度；為種群規模；為迭代次數；0為模擬退火算法中的初始溫度。

3 基于改良模擬退火遺傳算法優化箱體類零件生產排程問題

3.1 約束條件

在應用FMS對機床箱體類零件進行生產加工時，以最大完工時間最小化作為優化目標，其數學模型為：

式中：為機器序號；為機器數量；為工件序號；為工件數量；C為工件完工時間。

還需要遵守如下規則：

（1）所有零件在初始時刻都可進行加工；

（2）零件的加工順序沒有具體要求，可隨意變換；

（3）任何工序在同一時間都只能在一臺設備上加工；

（4）一臺設備在同一時間只能加工一個零件；

（5）每個零件都需具備合理的加工工藝；

（6）所有的零件都必須加工完成。

3.2 染色體編碼

染色體編碼是遺傳算法的開端也是關鍵，優異的編碼方式能夠提高算法效率，避免陷入局部最優解。本案例屬于柔性車間生產調度問題，其相對于一般的車間生產調度問題更加復雜。通過對類似案例的參考與分析，本案例采用雙層編碼方式進行染色體編碼，第一層是基于機器的編碼，依次按照工件工序所需加工機器的編號組成，第二層是基于工序的編碼，由工件的工序號組成[7]。

比如，第一層機器編碼為：

[1 2 1 5 7 2 5 2 1 2 1 7 1 2 6 2 1 7 1 2 6 1 2 7]

第二層工序編碼為：

[1 2 4 4 3 1 2 1 3 4 1 2 4 3 1 2 3 1 4 3 4 1 1 3]

將第一層機器編碼和第二層工序編碼合并后得到染色體編碼為：

[1 2 1 5 7 2 5 2 1 2 1 7 1 2 6 2 1 7 1 2 6 1 2 7 1 2 4 4 3 1 2 1 3 4 1 2 4 3 1 2 3 1 4 3 4 1 1 3]

3.3 適應度

適應度是評價個體適應環境能力的指標，適應度值越大則表示個體適應環境的能力越強，反之則表示個體適應環境的能力越弱。所以在進行子代生成時，應該盡量使適應度值大的個體作為父代，將父代優良基因遺傳到子代。本實例以零件最大完工時間最小化作為優化目標，所以采用零件完工時間取倒數的方法作為適應度值的計算公式，即：

式中：F為適應度值；()為零件完工時間。

3.4 交叉與變異操作

在生物學中基因重組和變異是生物進化的原材料，在遺傳算法中交叉和變異操作同樣也是促進個體進化的原動力。在進行染色體基因交叉和變異操作時，由于本文把個體基因編碼分為了機器編碼和工序編碼兩層，所以針對不同的編碼層采用不同的交叉和變異方式，以減少非法解出現的概率。

（1）交叉

在機器編碼層采用等位基因隨機交叉法，并結合模擬退火算法對新個體做出取舍判斷。圖6所示為機器編碼層采用的等位基因隨機交叉法的示例。交叉操作完成后，計算新個體1和2的適應度值，若適應度值大于舊個體（1、2）的適應度值則保留新個體，若適應度值小于舊個體的適應度值則以概率＝exp(-Δ/T)進行判斷新個體是保留還是舍棄。

在工序編碼層則采用改進的POX交叉法，同樣結合模擬退火算法對新個體進行取舍判斷。圖7所示為工序編碼層采用的改進POX交叉法示例。交叉操作完成后，計算新個體1的適應度值，若適應度值大于交叉所用兩個舊個體（1、2）的適應度值則保留新個體，若適應度值小于其中一個舊個體的適應度值則以概率＝exp(-Δ/T)進行判斷新個體是保留還是舍棄。

（2）變異

在機器編碼層采用變異位隨機分配可選機器法。在機器編碼層中隨機選擇個變異位（一般變異位數不高于總位數的1/4），并在該位置隨機分配可替換的機器序號，如圖8所示。變異操作完成后，需要計算新個體1的適應度值，若適應度值大于舊個體（1）的適應度值則保留新個體，若適應度值小于舊個體的適應度值則以概率＝exp(-Δ/T)進行判斷新個體是保留還是舍棄。

在工序編碼層采用末位隨機插入法。將工序編碼層中的最后一位隨機的插入工序編碼層中的某一位中，如圖9所示。變異操作完成后，依然需要計算新個體1的適應度值，若適應度值大于舊個體（1）的適應度值則保留新個體，若適應度值小于舊個體的適應度值則以概率＝exp(-Δ/T)進行判斷新個體是保留還是舍棄。

圖6 機器編碼層的等位基因隨機交叉法示意圖

圖7 工序編碼層的改進POX交叉法示意圖

圖8 機器編碼層的變異位隨機分配法示意圖

圖9 工序編碼層的末尾隨機插入法示意圖

4 機床箱體類零件生產排程實例仿真

改良模擬退火算法是在MATLAB R2019a平臺上編程實現。計算機硬件和軟件采用處理器Intel CORE i7第7代、主頻2.80 GHz、內存8.0 GB、64位Windows10操作系統。該算法的固定參數設置為：種群大小＝50，交叉概率P＝0.8，變異概率P＝0.03，最大迭代數＝50，初始溫度0＝3000。

機床中4種典型箱體類零件在加工時所用設備的加工順序及單機加工時間如表2所示。

表3為本實例中各個零件的各個工序的加工機器，如第一行第一列的[1 3]表示工件1的第1道工序可以在機器1或機器3上進行加工。

表4為本實例中各個零件的各個工序加工完成所需要的加工時間，如第一行第一列的36表示工件1的第1道工序所需加工時間為36 s。

表2 機床各箱體類零件機床安排時間表

表3 零件各工序所需的加工機器

表4 零件各工序所需的加工時間

經過MATLAB2019仿真后得到改良模擬退火遺傳算法的進化曲線如圖10所示。

傳統模擬退火遺傳算法優化后的染色體編碼為[1 2 3 9 8 4 9 2 2 2 3 7 1 2 6 4 3 7 1 4 6 3 4 7 1 2 4 1 2 1 4 3 4 1 2 1 4 2 3 1 4 1 3 1 3 4 3 3]，方案甘特圖如圖11所示，其最小化最大完工時間為648 s。

改良模擬退火遺傳算法優化后的染色體編碼為[3 2 1 5 8 2 5 2 3 2 3 8 1 2 6 2 1 7 3 2 6 3 2 7 3 1 2 1 4 2 3 1 3 2 4 1 4 3 2 4 3 1 4 3 1 4 1 1]，方案甘特圖如圖12所示，其最小化最大完工時間為592 s，加工效率比傳統模擬退火遺傳算法提高了約11%。

圖10 改良模擬退火遺傳算法進化曲線圖

圖11 傳統模擬退火遺傳算法方案甘特圖

圖12 改良模擬退火遺傳算法方案甘特圖

5 小結

本文對柔性車間生產排程的相關概念和評價方法等做了簡要總結，同時結合課題項目對某機床廠機床關鍵箱體零件的生產計劃問題進行了簡單的分析，并且運用改良后的模擬退火遺傳算法對本項目中柔性車間的生產排程問題進行了優化分析，優化結果顯示：以最小化最大完工時間為目標、運用改良算法優化后的排程計劃時間比原計劃時間節省了約11%。經過科研人員的不斷創新和改進，如今生產排程優化的方法有很多，但無論是采用哪一種方式方法，其最終目的都是使企業能夠達到經濟效益最大化，那么對于生產排程結果的評價就顯得十分重要。目前，對生產排程結果的評價基準主要有完工時間最短、設備利用率最大、工件半成品數量最小和交貨時間最短等方面，大多數的優化算法也是根據以上幾方面為目標進行優化改進的。

改良模擬退火遺傳算法依托于遺傳算法、模擬退火算法和粒子群優化算法，區別于傳統的模擬退火遺傳算法，在初始種群中融入粒子群優化算法加強了初始種群的篩選，在遺傳算法的交叉、變異操作融入了模擬退火算法加強了局部搜索能力，再在得到的新個體中融入全局退火操作，對新個體的適應度值進行拉伸，有助于擴大個體間的適應度差異，便于尋優。關于車間調度排程問題的研究發展至今，將生產排程計劃與人工智能、專家系統等相結合是未來研究的主要方向，更加能夠解決各種復雜的生產排程問題，提升企業的生產效率。

[1]覃炳發，蔣緣，潘玉雯. 汽配件制造業鐘的生產排程模型研究[J].計算機產品與流通，2019（10）：266.

[2]Gonzalo Mejia，Jordi Pereira. Multiobjective scheduling algorithm for flexible manufacturing systems with Petri nets[J]. Journal of Manufacturing Systems，2020（54）：272-284.

[3]潘怡穎，徐嘉杰. 基于遺傳算法的汽車零配件生產排程問題[J]. 海峽科技與產業，2019（3）：116-122.

[4]李飛. 船體車間的分段生產排程優化研究[D]. 鎮江：江蘇科技大學，2019.

[5]鐘志慶. 面向FMS的低碳生產排程方法研究[J]. 制造技術與機床，2019，1（7）：23-27.

[6]楊智超，鄧斌. 基于遺傳算法對液壓閥用磁流變液阻尼器的優化設計[J]. 機械，2019，46（11）：52-57.

[7]張炳根，龍偉. 基于遺傳算法的制造單元繼承性生成方法[J].機械，2018，45（1）：18-23.

[8]宗玉杰，崔建偉. 模擬退火遺傳算法在機械臂路徑規劃中的應用[J]. 測控技術，2018，37（3）：1-5.

[9]韓文民，范吉文. 基于改進遺傳算法的柔性作業車間調度問題研究[J]. 科學技術與工程，2008，8（22）：6135-6137.

[10]鄧炎澤. 關于典型箱體類零件加工工藝的思考與探討[J]. 科技與創新，2016（21）：25-25.

[11]Leilei Meng，Chaoyong Zhang，Yaping Ren，et al. Mixed-integer linear programming and constraint programming formulations for solving distributed flexible job shop scheduling problem[J]. Computers & Industrial Engineering，2020（142）：45-52.

[12]吳樹景，游有鵬，羅福源. 變鄰域保優遺傳算法求解柔性車間調度問題[J]. 計算機工程與應用，2010，4（5）：242-249.

Analysis of FMS Scheduling Optimization Based on Improved Simulated Genetic Annealing Algorithm

CHEN Yingfei1，PENG Zhengchao1，HU Xiaobing1，LI Yanru2

(1.School of Mechanical Engineering, Sichuan University,Chengdu 610065, China; 2.Nuclear Power Institute of China, Chengdu 610200, China)

Job scheduling problem (production scheduling) is an important factor affecting the production efficiency when using FMS in production and processing. Production scheduling is actually a problem of NP-C. There is no definite solution for the problem, but the results can be optimized. Many researchers use genetic algorithm to solve FJSP. This paper studies the key box parts of machine tools in a machine tool factory. We incorporate GA with PSO and SA to deal with the initial population, crossover and mutation operations of GA, hoping to make the algorithm converge faster and get better results. The equipment was laid out in groups. The production scheduling scheme was optimized and analyzed by MATLAB. The results show that the production scheduling optimization algorithm proposed for this factory is effective and feasible. It can be applied in actual production.

flexible manufacturing system；production scheduling；improved simulated annealing genetic algorithm；Matlab optimization

TH164；TP315

A

10.3969/j.issn.1006-0316.2021.02.002

1006－0316 (2021) 02－0007－10

2020－06－01

國家科技重大專項（2018ZX04032001）

陳應飛（1994－），男，四川成都人，碩士研究生，主要研究方向為智能制造、數字化生產，E-mail：1564647444@qq.com；胡曉兵（1970－），男，湖北武漢人，博士，教授，主要研究方向為企業信息化、機器視覺、數字化車間，E-mail：huxb@ scu.edu.cn。