[發(fā)明專利]一種高效的優(yōu)化調(diào)度方法

在審

• 申請?zhí)枺?/td>: 201711116302.5
• 申請日: 2017-11-13
• 公開（公告）號: CN107703900A
• 公開（公告）日: 2018-02-16
• 發(fā)明（設計）人: 劉興高;應炅;王雅琳;陽春華;桂衛(wèi)華
• 申請（專利權(quán)）人: 浙江大學
• 主分類號: G05B19/418
• 分類號: G05B19/418
• 代理公司: 杭州求是專利事務所有限公司33200
• 代理人: 邱啟旺

技術領域

本發(fā)明涉及生產(chǎn)調(diào)度領域，具體地，涉及一種高效的優(yōu)化調(diào)度方法。

背景技術

混合流水車間問題(hybrid flow-shop scheduling problem，HFSP)最早由Salvador于1973年基于石油工業(yè)背景提出。HFSP具有很強的工程背景，大量生產(chǎn)、制造、裝配、運輸、合成過程中的調(diào)度問題以及互聯(lián)網(wǎng)服務、集裝箱搬運等問題均可歸結(jié)為HFSP。隨著現(xiàn)代生產(chǎn)技術和并行計算機系統(tǒng)的快速發(fā)展，許多實際多階段調(diào)度問題要求在每個階段工件由幾臺處理器同時加工。因此，多處理機任務混合流水車間調(diào)度問題(hybrid flow-shop scheduling problem with multiprocessor tasks，HFSPMT)在實際生產(chǎn)過程中有著更為廣泛的應用。

HFSPMT的求解算法可分為精確求解算法、啟發(fā)式方法與智能算法三個大類。由于HFSPMT屬于復雜的NP-hard問題，精確求解算法和啟發(fā)式方法在實際求解過程中無法取得令人滿意的表現(xiàn)。隨著智能算法研究的不斷深入，目前有多種智能算法用于求解HFSPMT。然而，不少算法在求解過程中容易陷入局部最優(yōu)，同時在求解復雜的大規(guī)模問題時存在著算法收斂速度較慢、求解結(jié)果非最優(yōu)的缺陷。

發(fā)明內(nèi)容

為了克服目前HFSPMT求解算法易陷入局部最優(yōu)，以及算法求解速度慢、調(diào)度方案非最優(yōu)的不足，本發(fā)明目的在于提供一種能夠高效求解HFSPMT，具有很強全局搜索能力的優(yōu)化調(diào)度方法。

本發(fā)明解決其技術問題所采用的技術方案是：一種高效的優(yōu)化調(diào)度方法，應用基于變鄰域搜索的螢火蟲算法和新的解碼算法。螢火蟲算法作為一種新的群智能方法，可以提高問題的求解速度與精度。變鄰域搜索可以改變算法的鄰域結(jié)構(gòu)，拓展算法的搜索范圍。新的解碼算法則能使算法生成最優(yōu)的調(diào)度方案。具體過程包括以下幾個步驟：

1)已知一個包含n個工作的集合J＝{1,2,…,n}，在有k個階段的流水線上被處理，每個階段i有m_i個平行處理機，i＝1,2,…,k，將每個工作視作k個任務的一個序列，每個階段的任務必須在前一階段的任務完成后才能夠被處理。一件工作中的每個任務都需要對應階段的一個或多個處理機同時連續(xù)地處理一段時間。用size_ij與p_ij表示工作j在階段i所需的處理機數(shù)量與花費的時間；i＝1,2,…,k，j∈J。將求解問題需要的size和p矩陣輸入系統(tǒng)。

2)參數(shù)設置，種群個體數(shù)N、最大迭代次數(shù)t_max、隨機參數(shù)α、個體吸引力β₀、介質(zhì)吸收率γ；其中令N＝20，t_max＝500，α＝0.5，β₀＝0.2，γ＝1。

3)種群個體初始化。

生成種群X＝(x₁,x₂,…,x_N)，種群中的第s個個體x_s＝(x_s1,…,x_sn)，x_sj為0～n之間的實數(shù)，s∈{1,2,…,N}，j∈{1,2,…,n}。由于個體x_s的坐標是連續(xù)的實數(shù)，而工作序列是離散的整數(shù)序列，用最小排序方法將連續(xù)坐標轉(zhuǎn)化為工作序列，即將個體x_s＝(x_s1,…,x_sn)的各個維度從小到大排序，排序的序號構(gòu)成的整數(shù)序列作為初始工作序列π₁。

4)計算每個個體對應的最大完成時間C_max。

螢火蟲算法的目標函數(shù)為序列對應的最大完成時間C_max。本發(fā)明基于先到先得的原則，根據(jù)前一階段各工作的完成時間順序構(gòu)造下一階段的工作序列，然后根據(jù)一定規(guī)則對生成的工作序列進行適當調(diào)整，靈活地進行工作排序，減少加工過程的空閑時間，最終得到最優(yōu)的調(diào)度方案及最大完成時間C_max。

4.1)i＝1時，根據(jù)構(gòu)造出第1個階段的調(diào)度方案。其中h∈J，π₁(h)表示序列π₁中第h個元素的值，表示工作π₁(h)在第1個階段所需的處理機數(shù)量。