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

在審

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

所屬領域

本發明涉及作業車間調度技術領域。

背景技術

作業車間調度問題(Job-Shop Scheduling Problem，JSP)是制造執行系統研究的核心和重點之一，它的研究不僅具有重大的現實意義，而且具有深遠的理論意義。JSP就是根據產品制造需求合理分配資源，進而達到合理利用產品制造資源、提高企業經濟效益的目的。JSP是產品制造行業中共存的問題，它與計算機集成制造系統(Computer Integrated Manufacturing Systems，CIMS)的工廠管理、產品制造層次緊密相關，是CIMS領域中研究的重要課題。JSP是一個典型的NP-hard問題,它的研究必然會對NP問題的研究起到有意義的影響。

模擬退火算法(SA)是是一種適合解決大規模組合優化問題的算法。最早由Metropolis在1953年提出。源于統計物理學，它模擬實際固體退火過程的溫度變化，即先將固體加溫至充分高，在逐漸冷卻。加溫時，固體內部粒子變為無序狀態，內能增大；而逐漸降溫時，粒子趨于有序，在每個溫度都達到平衡態，最后在常溫時達到基態，內能減到最小。模擬退火算法(SA)是局部搜索算法的擴展，它不同于局部搜索之處是以一定的概率選擇領域中的最優值狀態。在解決NP完全問題，SA有很大的利用價值。

模擬退火算法簡單有效的搜索方式避免了數值算法的高計算量，又避免了局部搜索算法快速收斂于局部最優解的缺點。但是，模擬退火算法是一種串行優化算法，它的執行過程要經歷雙重循環：內循環(在當前溫度下進行Markov鏈長度搜索)和外循環(利用降溫函數進行降溫求控制狀態更新概率)，而其每部只隨機嘗試當前狀態領域中的一個狀態，這無疑會增加其運算時間。另外，模擬退火算法由于全局收斂條件難以實現，并且，概率接受使得當前狀態可能比搜索軌跡中的某些狀態還要差，從而實際算法往往最終得到近似最優解，甚至可能比中間經歷的最壞解要差，而且搜索效率差。

現有技術中有對模擬退火算法的改進，但是依然面臨著算法迭代時間長，算法計算量大等不足之處。

發明內容

針對上述不足，本發明要解決的技術問題是提供一種改進的模擬退火算法解決作業車間的調度問題。

本發明的目的是克服現有技術中存在的：收斂速度不夠快，最終最優解不夠精確，算法迭代時間長、算法計算量大的缺點。

本發明為實現上述目的所采用的技術方案是：一種改進的模擬退火算法解決作業車間調度問題，該算法的步驟如下：

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

步驟2：計算當前解；

步驟3：降溫方式的確定；

步驟4：產生新解S′；

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

本發明的有益效果是：

1、根據溫度的下降規律，設定溫度下降函數，避免了算法易于收斂于局部，同時減少了計算量。

2、以概率接受平均加工時間為狀態矩陣移動步長，使算法結果更為接近實際生產應用，同時也較少了算法迭代時間。

3、改變了算法接受新解作為當前解的概率計算方式，使算法更為精確。

附圖說明

本發明的算法基本流程圖。

具體實施方式

作業車間調度問題是一種職能單位，它的工段或工作中心事圍繞著不同類型設備或工序來組織的，如鉆床、鍛壓機、裝配線、解工總行等。作業車間調度問題可描述為：有n個加工順序不同的工件要在m臺機器上完成加工。

以下結合流程圖，對本發明進行詳細說明，算法的具體實施步驟如下：

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

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

S＝minf(S₁，S₂，...S_n)＝min max_1≤o≤w{max_1≤k≤m{max_1≤i≤n C_oik}}(1)

約束條件：

C_oik-p_oik+M(1-a_oihk)≥C_oih