[發明專利]一種高效的航空發動機裝配車間調度系統

在審

• 申請號: 201711117181.6
• 申請日: 2017-11-13
• 公開（公告）號: CN107831746A
• 公開（公告）日: 2018-03-23
• 發明（設計）人: 劉興高;應炅
• 申請（專利權）人: 浙江大學
• 主分類號: 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)將該個體C_max與全局最優值G_best進行比較，若C_max<G_best，則令G_best＝C_max，同時用記錄該個體在第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)對于每個個體，如在種群中有總裝配完成時間更小的個體，則按照下式向該個體移動：

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)。