[發明專利]一種高效的優化調度方法

在審

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

1.一種高效的優化調度方法。其特征是：應用基于變鄰域搜索的螢火蟲算法和新的解碼算法，能有效求解多處理機任務混合流水車間調度問題，生成最優調度方案。具體過程包括以下幾個步驟：

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

2)參數設置，種群個體數N、最大迭代次數t_max、隨機參數α、個體吸引力β₀、介質吸收率γ；其中令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之間的實數，s∈{1,2,…,N}，j∈{1,2,…,n}。由于個體x_s的坐標是連續的實數，而工作序列是離散的整數序列，用最小排序方法將連續坐標轉化為工作序列，即將個體x_s＝(x_s1,…,x_sn)的各個維度從小到大排序，排序的序號構成的整數序列作為初始工作序列π₁。

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

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

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

4.2)將第i階段的各工作加工完成時間進行非遞減順序排序，得到第i+1個階段的調度序列π_i+1。對于任意的π_i(h)和π_i(l)，h,l∈J，當且h<l時，進行π_i+1排序時假定

4.3)令j＝1，根據適當規則調整序列π_i+1中第j和j+1個工作的次序。

對于階段i中相鄰的三個工作A,B,C，即A＝π_i,p，B＝π_i,p+1，C＝π_i,p+2。根據ST_iA與ST_iB的關系，可分別提出以下規則來得到更優的處理序列。

a.ST_iA>ST_iB

規則1-i，若size_iB+size_iC>m_i，size_iA+size_iC>m_i，則交換A與B的處理順序。

規則1-ii，若size_iB+size_iC≤m_i，size_iA+size_iC>m_i，size_iA+size_iB>m_i，且max{{ST_iB+p_iB,ST_iA}+p_iA,ST_iC}<max{ST_iA+p_iA+p_iB,ST_iC+p_iC}，則交換A與B的處理順序。

規則1-iii，若size_iB+size_iC>m_i，size_iA+size_iC≤m_i，則交換A與B的處理順序。

規則1-iv，若size_iB+size_iC≤m_i，size_iA+size_iC≤m_i，則交換A與B的處理順序。

b.ST_iA＝ST_iB

規則2，若size_iA+size_iB>m_i，size_iB+size_iC>m_i，size_iA+size_iC≤m_i，則交換A與B的處理順序。

c.ST_iA<ST_iB

規則3，若ST_iA+p_iA>ST_iB，size_iA+size_iB>m_i，size_iB+size_iC>m_i，size_iA+size_iC≤m_i，則交換A與B的處理順序。

其中，ST_iA、ST_iB、ST_iC分別表示工作A、B、C在階段i的最早開始時間，size_iA、size_iB、size_iC分別表示工作A、B、C在階段i所需的處理機數量，p_iA、p_iB、p_iC分別表示工作A、B、C在階段i的處理時間，m_i表示階段i的處理機總量

4.4)若j＝n-2計算π_i+1中各工作的完成時間，繼續；否則j＝j+1，轉至步驟4.3)。

4.5)若i＝k-1，π_i+1各工作的完成時間中最大值即為目標函數最大完成時間C_max，繼續；否則i＝i+1，轉步驟4.2)。

4.6)將該個體i完工時間C_max,i與全局最優值G_best進行比較，其中G_best＝max(C_max,i),i＝1,2,…,N，若C_max,i<G_best，則令G_best＝C_max,i，同時用記錄該個體在階段i的調度序列π_i。

5)對個體進行變鄰域搜索。設計了5種產生最優解鄰域的方法，大大提升了種群多樣性。在求解大規模問題時，可以用較短的時間獲得全局最優解。

5.1)確定五種鄰域結構N_num，num＝1,2,3,4,5，初始化參數P＝20，計數值count＝0，令V＝π₁，BV＝V。五種鄰域結構如下：

a.兩點交換。隨機產生兩個交換位置，交換兩個位置上的元素。例如，對于個體“231476589”，隨機產生兩個交換位置2和8，交換兩個位置上的元素得到序列“281476539”。

b.插入。隨機產生兩個元素位置，將大位置處的元素插入小位置處的元素前面，小位置及其之后的元素按順序向后順延。例如，對于個體“231476589”，隨機產生兩個元素位置3和7，執行插入操作后可以得到新序列為“235147689”。

c.反轉逆序。隨機產生兩個元素位置，將兩點之間的元素逆序排列。例如，對于個體“231476589”，隨機產生兩個元素位置3和7，執行反轉逆序操作后可以得到新序列為“235674189”。

d.打亂互換。隨機產生一些元素位置，打亂這些元素的順序。例如，對于個體“231476589”，隨機產生四個元素位置1、5、7、8，元素順序為“2758”，隨機打亂元素順序得到“5872”，最終新序列為“531486729”。

e.NEH插入，隨機產生一個元素位置，在原有序列中將該元素刪去。針對每一個可插入位置，假設將該元素插入后，計算目前整個排序的完成時間，選擇能使完成時間最小的位置。

5.2)如果count<P，則令num＝1；否則，結束變鄰域搜索，并將BV對應的C_max與全局最優值G_best進行比較，若C_max<G_best，則令G_best＝C_max，同時用記錄該個體在階段i的調度序列π_i。

5.3)按照鄰域結構N_num隨機產生一個新解V'，比較新解V'與初始解V對應的適應度值，即序列對應的C_max。

5.4)若f(V')<f(V)，則令BV＝V'，適應度值更小的新解代替初始解，繼續在鄰域結構N_num內搜索；否則，num＝num+1。

5.5)若num>5，則count＝count+1，返回步驟5.2)；否則，返回步驟5.3)，進入下一個鄰域結構搜索。

6)對于每個個體，如在種群中有C_max更小的個體，則按照下式向該個體移動：

xs=xs+β0e-γrsb2(xb-xs)+α(R-12)]]>

其中，x_s與x_b為兩個體的位置，r_sb為兩個體之間的歐幾里德距離。β₀為距離為0時的吸引力，常數γ為介質的吸收率，α為[0,1]間的值，R為[0,1]間的隨機數，使個體在向更亮個體移動的同時存在一定的隨機移動。

7)迭代次數達到t_max輸出G_best和調度方案否則轉至步驟4)。