[發明專利]一種基于遺傳變鄰域算法的飛機裝配線作業調度方法

有效

• 申請號: 201911247383.1
• 申請日: 2019-12-09
• 公開（公告）號: CN110991056B
• 公開（公告）日: 2021-08-06
• 發明（設計）人: 張劍;蔡瑋;陳浩杰;袁銘暉;江海凡;付建林
• 申請（專利權）人: 西南交通大學
• 主分類號: G06F30/20
• 分類號: G06F30/20;G06Q10/06;G06Q50/04;G06N3/12;G06F111/04;G06F111/10
• 代理公司: 北京盛詢知識產權代理有限公司 11901
• 代理人: 劉靜

1.一種基于遺傳變鄰域算法的飛機裝配線作業調度方法，其特征在于，步驟如下：

步驟1：設定飛機裝配線作業調度的相關參數；

設飛機裝配作業項目由活動集合J；J＝{0，1，2，…，n+1}組成，其中活動0和n+1為虛活動，僅代表項目的開始和結束，不占用時間和資源；活動j的緊前作業集合用P_j，j∈J表示，j的緊后作業集合用S_j表示；t_j表示活動j的持續時間，st_j表示活動j的作業開始時間；定義M為部段集合，M＝{1，2，…，z}，m∈M為部段號，z為正整數，C_m表示在部段m中的活動集合，e_j表示作業活動j的空間占用量，各部段的最大空間容量為N_m；用r_jq表示活動j對第q種資源單位時間的需求量，其中，q＝1，2，…，k，k為整數；b_q為資源q單位時間的最大供應量；對時間進行離散化處理，d＝{1，2，…，T}為離散的時間節點，T表示裝配作業總工期，A_d＝{j|st_j＜d≤st_j+t_j}為d時刻正在執行的作業活動集合；

步驟2：建立飛機裝配線作業調度目標優化的數學模型，目標函數為：

minT＝st_n+1 (1)

即求解最小化裝配作業總工期，其約束為：

t₀＝t_n+1＝0 (5)

r0_q＝r(n+1)_q＝0，q＝1，2，...，k (6)

其中，式(2)為決策變量；式(3)表示每項作業活動必須在其規定持續時間完成；式(4)表示活動j一旦開始則在完成之前不能中斷；式(5)和(6)表示虛活動0和n+1的持續時間和資源需求量都為0；式(7)為活動緊前緊后約束，活動j必須在其全部緊前活動完成后才能開始；式(8)為資源約束，d時刻正在執行的所有活動對某種資源的需求量不大于該資源單位時間的最大供應量；式(9)為各部段的空間約束，d時刻在部段m中正在執行的所有活動對空間的需求量不大于部段m的最大空間容量；

步驟3：遺傳變鄰域算法優化求解，其步驟如下：

3.1參數設置：設最大代次數為maxGen；種群規模為popSize；交叉概率為P_c；變異概率為P_m；

3.2種群初始化：采用整數編碼的方式產生popSize個染色體，由于考慮到求解目標為最小化項目工期，先采用優先級規則初始化部分個體，其余個體采用隨機初始化以提高初始種群的多樣性；

步驟3.2中采用的優先級規則為EDDF或者MINLFT，進而提高了初始解的質量，從而縮小求解空間；

3.3計算個體適應度值，選用目標函數的倒數1/T乘以系數C作為適應度函數，即Fitness＝C/T，并判斷當前迭代次數gen是否達到最大迭代次數maxGen，若達到最大迭代次數則輸出最優解；否則轉步驟3.4；

3.4選擇：采用錦標賽選擇策略對個體進行選擇，每次從種群中隨機選擇一定數量的個體，根據其適應度函數值選擇其中最優的個體進入新種群，并重復此操作直至選擇出的新種群規模達到初始種群的90％；

3.5交叉：按照交叉概率p_c進行交叉操作，在單點交叉的基礎上進行了改進，形成考慮緊前緊后關系的交叉策略；從父代取兩個個體進行交叉，分別為M₁和M₂，取隨機整數m'作為斷點，1≤m'n，n為整數，則得到兩個子代C₁和C₂；子代C₁的活動序列中，i＝1,…,m'的部分來自于父代M₁，而i＝m'+1,…,n，n為整數，的部分來自于父代M₂，但在這部分序列中，已經從父代M₁中選擇的活動將不再被考慮，這樣的操作保證了父代中的活動優先順序得以被保留且每個活動只出現一次，所產生的子代個體不會出現非法個體，子代C₂的產生同理可得，便得兩個新的子代個體；

3.6變異：按變異概率p_m對遺傳算子的基因型做變動，采用了一種右移變異的策略，考慮某一個體的活動序列λ＝{1,2,..,i,…,n}，n為整數，i為隨機選擇的活動，現將i所在位點右移某一位置產生新一代個體，為了使新個體的活動序列仍然符合活動的優先級循序而不產生非法解，在右移之前需要判斷該活動最小的可右移位置，即不破壞原有的緊后關系，而由于是將活動右移，所以其緊前活動仍然有效，從而得到新的個體

λ’＝{1,…,i-1,i+1,…,h-1,i,h,…,n}，n為整數，h所在位置即為i最小的可右移位置；變異操作后產生新的種群newPop；

3.7變鄰域操作：從newPop中選擇適應度值前20％的個體作為變鄰域操作的初始解集S，變鄰域操作后生成局部最優解集；

步驟3.7中設計了3種不會產生非法解的鄰域結構，具體如下：

隨機選擇個體基因中的某一位點，根據活動的緊前緊后關系，記錄該位點上對應活動的所有緊前活動在該項目列表中最大的下標位置，及該活動的所有緊后活動在該項目列表中最小的下標位置；將該基因右移插入到緊后活動最小下標位置前一位，構成第一種鄰域結構；將該基因左移插入到緊前活動最大下標位置后一位，構成第二種鄰域結構；將該基因隨機插入到最小下標位置與最大下標位置之間，構成第三種鄰域結構；

步驟3.7中還提出一種接受閾值的計算方法，即在接受閾值內考慮是否接受變鄰域搜索得到的最優解，設變鄰域搜索的初始解為s，目標函數值為f(s)，經過鄰域搜索后得到的新解為s’，目標函數值為f(s’)；當得到的新解優于初始解，即f(s’)-f(s)0時，以概率p＝1接受新解，令s＝s’進入下一步迭代；當得到的新解劣與初始解時，即f(s’)-f(s)0時，以概率p＝exp{-[f(s’)-f(s)]/f(s)}接受劣解，令s＝s’進入下一步迭代；

3.8將局部最優解集重插入到原種群中，轉步驟3.3。