[發明專利]一種改進的模擬退火算法解決作業車間調度問題

在審

• 申請號: 201610364350.5
• 申請日: 2016-05-26
• 公開（公告）號: CN106611279A
• 公開（公告）日: 2017-05-03
• 發明（設計）人: 姜艾佳;胡成華
• 申請（專利權）人: 四川用聯信息技術有限公司
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q50/04
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種改進的模擬退火算法解決作業車間調度問題，該算法涉及作業車間調度技術領域，其特征是：該算法根據溫度的下降規律，設定溫度下降函數，避免了算法易于收斂于局部，同時減少了計算量；、以概率接受平均加工時間為狀態矩陣移動步長，使算法結果更為接近實際生產應用，同時也較少了算法迭代時間；改變了算法接受新解作為當前解的概率計算方式，使算法更為精確；算法的具體實施步驟如下：

步驟1：初始化算法參數：初始溫度T0（保證充分大），初始解狀態矩陣C(是算法迭代的起點)，工序時間矩陣P，迭代次數L；

步驟2：計算當前解：用數學模型描述如下：

目標函數：

； （1）

約束條件：

（2）

（3）

（4）

（5）

（6）

其中，式（1）表示目標函數，即完成時間（Makespan）；式（2）表示工藝約束條件決定的每個工件的操作的先后順序；式（3）表示加工每個工件的每臺機器的先后順序；式（4）表示完工時間變量約束條件；式（5）表示變量可能的取值大??；

上述公式中所涉及的符號定義含義如下： 分別為第o個訂單（或階數）中的第i個工件在機器k上的完成時間點和加工時間長度；M是一個足夠大的整數；式（6）表示第o個訂單的所有工件最大完成時間小于訂單周期的時間約束；分別為指示系數和指示變量，其含義為：

步驟3：降溫方式的確定：由于存在溫度傳遞，故溫度過高和過低的粒子溫度都會向平均溫度靠近，而能量的遞減會越來越緩慢，故采用如下方式計算溫度：，其中，k為迭代次數,k=1,2,…n；

步驟4：產生新解：

新解的產生機制：

狀態矩陣C的變化函數：狀態矩陣以概率接受平均工件加工時間為移動步長，即：，其中平均 ， 滿足Metropolis接受準則：，其中： 為的極差， ，為的方差：

迭代次數L=L-1；

將更新后的數據代入按照步驟2所列的方程，計算新的臨時解；

計算新的臨時解與當前解的目標函數差：；

接受新解準則： 如果滿足，則，否則以概率接受S(k)作為新的當前解；

步驟5：如果滿足終止條件輸出當前解作為最優解，輸出對應的狀態矩陣C，工序時間矩陣P，結束程序，否則轉步驟2，終止條件為：

滿足，，其中和是溫度下降閾值和精確度，是正實數。