吳靈媛 曹家賡 曹言

摘要：基于CNC在加工過程中可能發(fā)生故障的情況，構建了刀具出現(xiàn)問題的情況下新的動態(tài)約束模型，利用模擬退火算法，采用MATLAB軟件編程求解，得出了在最大成本與加入新的約束條件下的最大成本新解之間的差值為-650，正好滿足新退火解的要求。

關鍵詞：模擬退火算法;動態(tài)調(diào)度;RGV智能車

0 引言

1.問題背景

RGV是一種無人駕駛、能在固定軌道上自由運行的智能車。目前已經(jīng)廣泛運用到柔性生產(chǎn)制造流程中，其調(diào)度規(guī)劃問題成為生產(chǎn)決策的重點。研究的智能加工系統(tǒng)由8臺計算機數(shù)控機床（CNC）、1輛軌道式自動引導車（RGV）、1條RGV直線軌道、1條上料傳送帶、1條下料傳送帶等附屬設備組成。

CNC在加工過程中可能發(fā)生故障的情況，每次故障排除時間介于10～20分鐘之間，故障排除后即刻加入作業(yè)序列，建立動態(tài)調(diào)度模型并提供相應的求解算法，以解決整個車床加工零件變化情況。

1.算法引用

模擬退火遺傳算法在尋找全局優(yōu)化解方面融合了模擬退火算法和遺傳算法的特點，能夠使優(yōu)化過程的搜索行為更加完善，在發(fā)生意外情況時全局的搜索能力和效率都得到加強，而且能有效控制遺傳算法避開所有最大值導致的效率分配問題，理論上能較好解決車間故障下的車輛合理調(diào)度問題。

2.算法原理

模擬退火算法來源于固體退火原理，用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當前解重復“產(chǎn)生新解→計算目標函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時的當前解即為所得近似最優(yōu)解，這是一種啟發(fā)式隨機搜索過程，包括影響的參數(shù)有初值t及其衰減因子Δt、每個t值時的迭代次數(shù)L和停止條件S。

3.算法在本問題中的擴展

將每一次物料加工的過程看做一個完整的退火過程，而RGV運輸過程中CNC出現(xiàn)的故障是調(diào)度優(yōu)化的干擾項。對于單個的工件加工時間Tj一定有隨機干擾項θj影響遺傳算法調(diào)度RGV，其中θj是為第j個工件加工的CNC出現(xiàn)故障而浪費的時間，它的出現(xiàn)與CNC故障的概率pj有正相關的關系，pj越大，CNC出現(xiàn)故障的時間越長。則文中物料等待時間模型

中必須要加入隨機概率下的故障時間θj。那么重新建立約束的模型如下：

（9）

其中θj= f （ pj），則根據(jù)模擬退火算法的思想，Wj在不斷產(chǎn)生由于 f （ pj）的新解過程中，需要得到一個Cj*，使ε=（Cj-Cj*）中的ε得到一個比較大的值，那么這個Cj*就是融合了CNC故障之后RGV運輸工件的等待時間模型的合理數(shù)值。

4.運行步驟

模擬退火算法新解的產(chǎn)生和接受可以用四個步驟求解：

（1）在最大成本最小化的目標函數(shù)規(guī)劃下，可以得到如下動態(tài)規(guī)劃模型：

（10）

（11）

此時Wj*為目標函數(shù)一個新的約束條件，且其對目標函數(shù)會產(chǎn)生新的影響，用matlab模擬出隨著pj變化Cj*變化的值。（代碼詳見附件）

（2）在新解的情況下計算與新解所對應的目標函數(shù)差，即ε=（Cj-Cj*），這里記為ΔC。設定一個概率：

（2）

當在新的約束條件下有最優(yōu)解，即ΔC≤0時，φ=0，能夠

取得這個Cj*新解;而若ΔC >0，則，這個概率非常小，即Cj*=Cj。

（3）在進行新解的迭代過程中，設置迭代次數(shù)的記錄與最終的停止條件。對于題目的問題可以設置的停止條件為，則整體的求解優(yōu)化模型建立如下：

5.仿真模擬分析

基于以上方法，采用任務二的第一組數(shù)據(jù)為例，針對CNC對上下料時間影響的特殊性，對所提出的動態(tài)調(diào)度優(yōu)化模型進行仿真驗證。

由對比可知，模擬退火算法調(diào)節(jié)干擾項的遺傳算法是有效果的。在只有6臺機器工作的情況下，模型在考慮到局部時間可能增加的情況下，利用pj存在的區(qū)間（0，1）上隨機分布對ΔC的變動影響，合理估計了φ出現(xiàn)的情況，從而跳過局部最優(yōu)解，得到了和無故障情況下時間相差較少的新解，CNC故障下最優(yōu)的調(diào)度路徑為：CNC1↑CNC2↑CNC3↑CNC4↑CNC5↑CNC6↑ CNC7↑CNC8。在最大成本與加入新的約束條件下的最大成本新解之間的差值為-650，正好滿足新退火解的要求。

參考文獻：

[1]喬彥平，張駿.基于一種改進遺傳模擬退火算法的TSP求解[J].計算機仿真，2009，26 （05）：205-208.

[2]吳焱明，劉永強，張棟，趙韓.基于遺傳算法的RGV動態(tài)調(diào)度研究[J].起重運輸機械，2012 （06）：20-23.