基于改進(jìn)模擬退火－遺傳算法的FMS生產(chǎn)排程優(yōu)化分析

陳應(yīng)飛，彭正超，胡曉兵，李彥儒

基于改進(jìn)模擬退火－遺傳算法的FMS生產(chǎn)排程優(yōu)化分析

陳應(yīng)飛1，彭正超1，胡曉兵1，李彥儒2

（1.四川大學(xué) 機(jī)械工程學(xué)院，四川 成都 610065；2.中國(guó)核動(dòng)力研究設(shè)計(jì)院，四川 成都 610200）

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

柔性制造系統(tǒng)；生產(chǎn)排程；模擬退火遺傳算法；Matlab優(yōu)化

現(xiàn)代制造型企業(yè)競(jìng)爭(zhēng)越來(lái)越激烈，任何一個(gè)小的失誤都可能導(dǎo)致整個(gè)市場(chǎng)的丟失，從而使得企業(yè)的經(jīng)濟(jì)受到較大的打擊，甚至可能有破產(chǎn)的風(fēng)險(xiǎn)。在制造企業(yè)中，如何進(jìn)一步提高零部件產(chǎn)品的生產(chǎn)效率始終是一個(gè)值得探索的問(wèn)題。建立FMS（Flexible Manufacture System，柔性制造系統(tǒng)）是提高零部件產(chǎn)品生產(chǎn)效率的一項(xiàng)重要措施，但是如何在此基礎(chǔ)上更進(jìn)一步提高零部件產(chǎn)品的生產(chǎn)效率，經(jīng)過(guò)研究人員大量的實(shí)驗(yàn)和分析研究發(fā)現(xiàn)，生產(chǎn)調(diào)度問(wèn)題（又稱生產(chǎn)排程）也是影響零部件產(chǎn)品生產(chǎn)效率的另一個(gè)重要因素。

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

1 機(jī)床關(guān)鍵箱體類零件生產(chǎn)計(jì)劃問(wèn)題

1.1 生產(chǎn)計(jì)劃的概念和層次

生產(chǎn)計(jì)劃是指企業(yè)對(duì)自身生產(chǎn)的產(chǎn)品形式和種類、產(chǎn)品數(shù)量、產(chǎn)品質(zhì)量和生產(chǎn)進(jìn)度進(jìn)行統(tǒng)籌安排的過(guò)程。對(duì)于大型制造型企業(yè)來(lái)講，生產(chǎn)計(jì)劃可以分為兩大類，一個(gè)是廠級(jí)生產(chǎn)計(jì)劃，另一個(gè)是車間級(jí)生產(chǎn)計(jì)劃。生產(chǎn)排程問(wèn)題就屬于車間級(jí)生產(chǎn)計(jì)劃問(wèn)題，其主要對(duì)產(chǎn)品加工過(guò)程中的工序進(jìn)行合理安排。生產(chǎn)計(jì)劃的具體層次和相應(yīng)特征如表1所示。

表1 生產(chǎn)計(jì)劃的層次和特征

1.2 生產(chǎn)計(jì)劃約束條件

企業(yè)在制定生產(chǎn)計(jì)劃的同時(shí)，也需要對(duì)產(chǎn)品的生產(chǎn)指標(biāo)進(jìn)行確定，如產(chǎn)品數(shù)量、產(chǎn)品質(zhì)量等級(jí)、產(chǎn)值以及交貨日期等。在完成指標(biāo)的過(guò)程中，可能會(huì)受到某些方面的生產(chǎn)約束導(dǎo)致企業(yè)不能順利完成生產(chǎn)指標(biāo)。生產(chǎn)約束對(duì)企業(yè)生產(chǎn)所產(chǎn)生的效應(yīng)類似于木桶效應(yīng)，約束條件中的最低值將決定企業(yè)的最大生產(chǎn)能力。產(chǎn)生生產(chǎn)約束的原因是多方面的，有物料供應(yīng)、企業(yè)生產(chǎn)能力、市場(chǎng)環(huán)境和資金等，其中物料供應(yīng)、企業(yè)生產(chǎn)能力和市場(chǎng)環(huán)境是最主要的影響因素，其中企業(yè)生產(chǎn)能力是由企業(yè)自身?xiàng)l件決定的，企業(yè)可以通過(guò)不斷的優(yōu)化和改進(jìn)提高自身的生產(chǎn)能力。

（1）企業(yè)生產(chǎn)能力，是指企業(yè)在一定的時(shí)間范圍內(nèi)，企業(yè)員工利用相關(guān)設(shè)備進(jìn)行有效生產(chǎn)的產(chǎn)品的最大產(chǎn)量。企業(yè)生產(chǎn)能力的約束主要來(lái)自于生產(chǎn)設(shè)備、員工素質(zhì)和生產(chǎn)流程等。

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

（3）市場(chǎng)環(huán)境，也是影響企業(yè)生產(chǎn)計(jì)劃的重要因素。決策者正確地判斷市場(chǎng)發(fā)展趨勢(shì)能夠加大產(chǎn)品銷售量，減少產(chǎn)品庫(kù)存量，增加現(xiàn)金流，順利開展下一項(xiàng)生產(chǎn)任務(wù)。

1.3 機(jī)床廠制定生產(chǎn)計(jì)劃的基本流程

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

圖1 某機(jī)床廠制定生產(chǎn)計(jì)劃的基本流程

2 改良模擬退火遺傳算法的設(shè)計(jì)

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

（1）粒子群優(yōu)化算法

粒子群優(yōu)化算法，又稱為微粒群優(yōu)化算法，是科學(xué)家通過(guò)觀察鳥類的覓食行為而逐步發(fā)展的一種隨機(jī)搜索算法。粒子群算法進(jìn)行優(yōu)化計(jì)算的基本思路是將所求問(wèn)題的解轉(zhuǎn)換為三維空間中具有一定初速度和初始位置的微小粒子，并使這些微小粒子在解空間中不斷地去尋找最優(yōu)粒子，并且在尋找過(guò)程中粒子的速度和位置都會(huì)不斷的調(diào)整。

粒子在解空間中的運(yùn)動(dòng)方程為：

式中：為慣性權(quán)重；為粒子速度，為粒子下一個(gè)位置的速度；1、2為常數(shù)；1、2為隨機(jī)數(shù)；b為當(dāng)前個(gè)體的最佳位置；p為個(gè)體的當(dāng)前位置；g為粒子種群的當(dāng)前位置；p'為個(gè)體在p位置的后一個(gè)位置。

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

圖2 粒子群優(yōu)化算法基本流程圖

（2）模擬退火算法

模擬退火算法以其簡(jiǎn)便、靈活等特點(diǎn)在車間調(diào)度和組合優(yōu)化問(wèn)題中得到了比較廣泛的使用。模擬退火算法最早由Metropolis等提出，其中心思想本質(zhì)上就是不斷迭代、不斷改進(jìn)的一個(gè)過(guò)程，并且有強(qiáng)的有限區(qū)域搜索能力。

模擬退火算法的數(shù)學(xué)公式為：

式中：P為新解取代舊解的概率；E表示目標(biāo)函數(shù)的函數(shù)值為；E表示經(jīng)過(guò)模擬退火算法迭代后的目標(biāo)函數(shù)的函數(shù)值為；為算法中的溫度控制參數(shù)。

可以看出，當(dāng)參數(shù)的值較大時(shí)，舊解被新解取代的概率很高，但隨著迭代的不斷進(jìn)行，參數(shù)的值越來(lái)越小、并最終趨近于0，此時(shí)舊解被取代的概率極低，并以此作為全局的最優(yōu)解。

模擬退火算法的基本流程如圖3所示：①設(shè)定初始狀態(tài)值，確定溫度參數(shù)，產(chǎn)生隨機(jī)初始解E；②擾動(dòng)產(chǎn)生新解E；③由Metropolis準(zhǔn)則判斷是否接受新的解，若接受新解則輸出新解，若不接受新解則輸出舊解；④判斷由Metropolis準(zhǔn)則輸出的解是否滿足停止條件，若滿足則跳出計(jì)算、獲得最優(yōu)解，若不滿足則改變控制參數(shù)的值、返回第2步，依次循環(huán)，直至獲得最優(yōu)解。

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

（3）遺傳算法

遺傳算法是一種借鑒生物界“優(yōu)勝劣汰”機(jī)制演化過(guò)來(lái)的并行搜索方法[6]，具有操作簡(jiǎn)單、通用性強(qiáng)、受約束條件少和全局搜索能力強(qiáng)等特點(diǎn)，在解決組合優(yōu)化問(wèn)題中得到了比較廣泛的應(yīng)用，也是未來(lái)智能制造領(lǐng)域的關(guān)鍵性技術(shù)之一。

運(yùn)用遺傳算法解決組合優(yōu)化問(wèn)題類似于求一個(gè)函數(shù)的最大值（或最小值）的優(yōu)化問(wèn)題，其數(shù)學(xué)規(guī)劃模型為：

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

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

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

圖4 遺傳算法基本流程圖

2.2 改良模擬退火遺傳算法的設(shè)計(jì)

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

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

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

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

（3）評(píng)價(jià)種群中個(gè)體適應(yīng)度，然后選擇優(yōu)秀個(gè)體生成種群，在選擇優(yōu)秀個(gè)體時(shí)采用輪盤賭法和最大保留法相結(jié)合的方式進(jìn)行；

（4）進(jìn)行個(gè)體交叉操作。以交叉概率為指標(biāo)進(jìn)行個(gè)體交叉，將產(chǎn)生的子代個(gè)體適應(yīng)度值與父代個(gè)體適應(yīng)度值進(jìn)行比較，若子代個(gè)體適應(yīng)度值大于父代個(gè)體適應(yīng)度值則接受子代個(gè)體為當(dāng)前個(gè)體；若子代個(gè)體適應(yīng)度值小于或等于父代個(gè)體則按接受概率判斷，若＞random則接受子代個(gè)體為當(dāng)前個(gè)體，否則保留父代個(gè)體為當(dāng)前個(gè)體；

（5）進(jìn)行個(gè)體變異操作。接受原則與個(gè)體交叉類似，以變異概率P作為判斷指標(biāo)；

（6）全局退火操作。全局退火觀念即對(duì)全局范圍內(nèi)個(gè)體適應(yīng)度值進(jìn)行適當(dāng)拉伸操作，避免個(gè)別特別優(yōu)秀的個(gè)體充斥整個(gè)種群，影響搜索效率。在溫度較高時(shí)使性能相似的個(gè)體在適應(yīng)度值方面差異較小，在溫度較低時(shí)擴(kuò)大個(gè)體的適應(yīng)度值，便于顯示優(yōu)秀個(gè)體的優(yōu)勢(shì)。

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

其算法為：

式中：f為第個(gè)個(gè)體的適應(yīng)度值，f'為第個(gè)個(gè)體迭代過(guò)后新的適應(yīng)度值；為當(dāng)前溫度；為種群規(guī)模；為迭代次數(shù)；0為模擬退火算法中的初始溫度。

3 基于改良模擬退火遺傳算法優(yōu)化箱體類零件生產(chǎn)排程問(wèn)題

3.1 約束條件

在應(yīng)用FMS對(duì)機(jī)床箱體類零件進(jìn)行生產(chǎn)加工時(shí)，以最大完工時(shí)間最小化作為優(yōu)化目標(biāo)，其數(shù)學(xué)模型為：

式中：為機(jī)器序號(hào)；為機(jī)器數(shù)量；為工件序號(hào)；為工件數(shù)量；C為工件完工時(shí)間。

還需要遵守如下規(guī)則：

（1）所有零件在初始時(shí)刻都可進(jìn)行加工；

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

（3）任何工序在同一時(shí)間都只能在一臺(tái)設(shè)備上加工；

（4）一臺(tái)設(shè)備在同一時(shí)間只能加工一個(gè)零件；

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

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

3.2 染色體編碼

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

比如，第一層機(jī)器編碼為：

[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]

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

[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 適應(yīng)度

適應(yīng)度是評(píng)價(jià)個(gè)體適應(yīng)環(huán)境能力的指標(biāo)，適應(yīng)度值越大則表示個(gè)體適應(yīng)環(huán)境的能力越強(qiáng)，反之則表示個(gè)體適應(yīng)環(huán)境的能力越弱。所以在進(jìn)行子代生成時(shí)，應(yīng)該盡量使適應(yīng)度值大的個(gè)體作為父代，將父代優(yōu)良基因遺傳到子代。本實(shí)例以零件最大完工時(shí)間最小化作為優(yōu)化目標(biāo)，所以采用零件完工時(shí)間取倒數(shù)的方法作為適應(yīng)度值的計(jì)算公式，即：

式中：F為適應(yīng)度值；()為零件完工時(shí)間。

3.4 交叉與變異操作

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

（1）交叉

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

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

（2）變異

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

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

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

圖7 工序編碼層的改進(jìn)POX交叉法示意圖

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

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

4 機(jī)床箱體類零件生產(chǎn)排程實(shí)例仿真

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

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

表3為本實(shí)例中各個(gè)零件的各個(gè)工序的加工機(jī)器，如第一行第一列的[1 3]表示工件1的第1道工序可以在機(jī)器1或機(jī)器3上進(jìn)行加工。

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

表2 機(jī)床各箱體類零件機(jī)床安排時(shí)間表

表3 零件各工序所需的加工機(jī)器

表4 零件各工序所需的加工時(shí)間

經(jīng)過(guò)MATLAB2019仿真后得到改良模擬退火遺傳算法的進(jìn)化曲線如圖10所示。

傳統(tǒng)模擬退火遺傳算法優(yōu)化后的染色體編碼為[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所示，其最小化最大完工時(shí)間為648 s。

改良模擬退火遺傳算法優(yōu)化后的染色體編碼為[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所示，其最小化最大完工時(shí)間為592 s，加工效率比傳統(tǒng)模擬退火遺傳算法提高了約11%。

圖10 改良模擬退火遺傳算法進(jìn)化曲線圖

圖11 傳統(tǒng)模擬退火遺傳算法方案甘特圖

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

5 小結(jié)

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

改良模擬退火遺傳算法依托于遺傳算法、模擬退火算法和粒子群優(yōu)化算法，區(qū)別于傳統(tǒng)的模擬退火遺傳算法，在初始種群中融入粒子群優(yōu)化算法加強(qiáng)了初始種群的篩選，在遺傳算法的交叉、變異操作融入了模擬退火算法加強(qiáng)了局部搜索能力，再在得到的新個(gè)體中融入全局退火操作，對(duì)新個(gè)體的適應(yīng)度值進(jìn)行拉伸，有助于擴(kuò)大個(gè)體間的適應(yīng)度差異，便于尋優(yōu)。關(guān)于車間調(diào)度排程問(wèn)題的研究發(fā)展至今，將生產(chǎn)排程計(jì)劃與人工智能、專家系統(tǒng)等相結(jié)合是未來(lái)研究的主要方向，更加能夠解決各種復(fù)雜的生產(chǎn)排程問(wèn)題，提升企業(yè)的生產(chǎn)效率。

[1]覃炳發(fā)，蔣緣，潘玉雯. 汽配件制造業(yè)鐘的生產(chǎn)排程模型研究[J].計(jì)算機(jī)產(chǎn)品與流通，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]潘怡穎，徐嘉杰. 基于遺傳算法的汽車零配件生產(chǎn)排程問(wèn)題[J]. 海峽科技與產(chǎn)業(yè)，2019（3）：116-122.

[4]李飛. 船體車間的分段生產(chǎn)排程優(yōu)化研究[D]. 鎮(zhèn)江：江蘇科技大學(xué)，2019.

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

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

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

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

[9]韓文民，范吉文. 基于改進(jìn)遺傳算法的柔性作業(yè)車間調(diào)度問(wèn)題研究[J]. 科學(xué)技術(shù)與工程，2008，8（22）：6135-6137.

[10]鄧炎澤. 關(guān)于典型箱體類零件加工工藝的思考與探討[J]. 科技與創(chuàng)新，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]吳樹景，游有鵬，羅福源. 變鄰域保優(yōu)遺傳算法求解柔性車間調(diào)度問(wèn)題[J]. 計(jì)算機(jī)工程與應(yīng)用，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

國(guó)家科技重大專項(xiàng)（2018ZX04032001）

陳應(yīng)飛（1994－），男，四川成都人，碩士研究生，主要研究方向?yàn)橹悄苤圃?、?shù)字化生產(chǎn)，E-mail：1564647444@qq.com；胡曉兵（1970－），男，湖北武漢人，博士，教授，主要研究方向?yàn)槠髽I(yè)信息化、機(jī)器視覺(jué)、數(shù)字化車間，E-mail：huxb@ scu.edu.cn。