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

在審

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

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

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

2)參數(shù)設(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的坐標(biāo)是連續(xù)的實數(shù)，而工作序列是離散的整數(shù)序列，用最小排序方法將連續(xù)坐標(biāo)轉(zhuǎn)化為工作序列，即將個體x_s＝(x_s1,…,x_sn)的各個維度從小到大排序，排序的序號構(gòu)成的整數(shù)序列作為初始工作序列π₁。

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

螢火蟲算法的目標(biāo)函數(shù)為序列對應(yīng)的最大完成時間C_max。本發(fā)明基于先到先得的原則，根據(jù)前一階段各工作的完成時間順序構(gòu)造下一階段的工作序列，然后根據(jù)一定規(guī)則對生成的工作序列進行適當(dāng)調(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ù)量。

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

4.3)令j＝1，根據(jù)適當(dāng)規(guī)則調(diào)整序列π_i+1中第j和j+1個工作的次序。

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

a.ST_iA>ST_iB

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

規(guī)則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的處理順序。

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

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

b.ST_iA＝ST_iB

規(guī)則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

規(guī)則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所需的處理機數(shù)量，p_iA、p_iB、p_iC分別表示工作A、B、C在階段i的處理時間，m_i表示階段i的處理機總量

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

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

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

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

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

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

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

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

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

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

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

5.3)按照鄰域結(jié)構(gòu)N_num隨機產(chǎn)生一個新解V'，比較新解V'與初始解V對應(yīng)的適應(yīng)度值，即序列對應(yīng)的C_max。

5.4)若f(V')<f(V)，則令BV＝V'，適應(yīng)度值更小的新解代替初始解，繼續(xù)在鄰域結(jié)構(gòu)N_num內(nèi)搜索；否則，num＝num+1。

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

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

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

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

7)迭代次數(shù)達(dá)到t_max輸出G_best和調(diào)度方案否則轉(zhuǎn)至步驟4)。