[發明專利]一種求解零等待流水車間調度問題的改進粒子群優化方法

有效

• 申請號: 201711350306.X
• 申請日: 2017-12-15
• 公開（公告）號: CN108053119B
• 公開（公告）日: 2021-07-30
• 發明（設計）人: 趙付青;楊國強;宋厚彬;何繼愛;唐建新;姚毓凱;張建林
• 申請（專利權）人: 蘭州理工大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06N3/00
• 代理公司: 北京科家知識產權代理事務所(普通合伙) 11427
• 代理人: 陳娟

本發明公開了一種求解零等待流水車間調度問題的改進粒子群優化方法，首先參數初始化和種群初始化，生成初始工件序列，然后使用階乘編碼方法，將所有排列映射至整數構成初始種群，最后，隨機生成可行的初始速度集；移動粒子；通過原始PSO種群更新策略更新種群，將新的種群映射到相應的工件序列，并評估每個新工件序列的完工時間。使用改進的變鄰域搜索算法進行局部搜索，并將搜索得到的結果替換；使用種群自適應算子PA增加種群的多樣性；檢查終止條件，如果終止條件滿足，停止，返回變量的值和相應的序列作為最終的解，否則繼續更新粒子速度。本發明的有益效果是改進了粒子群優化算法，提升了全局搜索能力，避免了過早收斂。

技術領域

本發明屬于流水車間調度算法技術領域，具體涉及用算法求解零等待流水車間調度問題。

背景技術

調度問題通常是指在規定的時間內，怎樣利用現有的資源進行合理地安排生產，從而實現生產效益的最大化。車間調度問題是調度問題的一個子集，是企業進行生產計劃與控制的一個重要組成部分，是幫助企業提高自己競爭力的關鍵因素。隨著科學技術的不斷發展，元啟發式方法被提出，該方法的成功取決于他們提供探索(多樣化)和開發(強化)之間的平衡的能力。根據他們的搜索策略，元啟發式方法可以分為兩類：一種是基于單一解的局部搜索算法，包括模擬退火算法，禁忌搜索。另一種是基于種群的有學習部分的搜索算法，包括克隆優化算法、粒子群優化算法、遺傳算法、免疫算法。一般而言，基于單一解的啟發式算法表現更多的局部搜索能力，而基于種群的啟發式算法擁有更多的全局搜索能力。

Eberhart和Kennedy在1995年提出的粒子群優化算法(PSO，Particle SwarmOptimization)是一種群體智能算法，它模擬群體行為，如鳥類群落和魚群。PSO最初被用來優化各種連續的非線性函數。由于其結構簡單且搜索效率高，PSO作為一種被廣泛采用的優化技術，已經被成功應用于許多現實問題，包括NWFSP等組合優化問題。一些學者修改了PSO的主要算子以適應工件序列。另一些則使用新的表示方式來代替工件排列表示，通常引入編碼方法來將離散解映射到連續域。常見的編碼規則包括RK(random-key)，LOV(largest-order-value)，SOV(smallest-order-value)，LRV(largest-ranked-value)和SPV(smallest-position-value)等。雖然這些編碼規則表現出了良好的性能，但編碼效率是通常較低。另外，這些編碼規則下的搜索空間并不能完全適應原本應用于連續空間的演化算法，例如PSO。

本發明要解決的技術問題是：針對傳統粒子群算法初期收斂速度快，而在后期容易陷入早熟、局部最優，且PSO適用于連續解空間；以及階乘碼表示方法能將零等待流水車間調度問題(No-wait Flow Shop SchedulingProblem，NWFSP)中的離散解映射至連續整數空間的能力。提出在階乘碼表示的NWFSP下對原始的PSO算法進行改進，優化PSO求解NWFSP的性能。

發明內容

本發明的目的在于提供一種求解零等待流水車間調度問題的改進粒子群優化方法，解決了針對傳統粒子群算法初期收斂速度快，而在后期容易陷入早熟、局部最優的問題。

本發明技術方案包括以下步驟：

步驟1：參數初始化；

設置控制參數的值：MRT為最大運行時間限制，c₁和c₂為速度常數，W_min和w_max影響慣性重量的參數，c＝0是種群距離未變化次數，g＝1為當前的迭代次數；

步驟2：種群初始化；

使用NN+NEH生成初始工件序列，NN和NEH是兩種流行的啟發式算法。評估其適應度值得到當前最優解pbest，歷史最優解gbest＝pbest，種群之間的歐氏距離D₀，然后使用階乘編碼方法，將所有排列映射至整數構成初始種群，最后，隨機生成可行的初始速度集；