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

有效

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

本發明公開了一種基于遺傳變鄰域算法的飛機裝配線作業調度方法，該方法首先建立資源受限的飛機裝配線作業調度模型，將實際生產中的作業調度問題轉化為優化求解的數學模型問題；其次以最小化裝配作業總工期為優化目標，同時考慮緊前緊后約束、資源約束和空間約束，構建飛機裝配線分部段作業調度模型；最后采用改進遺傳變鄰域算法進行求解。本發明設計了一種結合優先級規則的種群初始化方法以縮減解空間，采用一種結合接受閾值的變鄰域局部搜索方式，構建三種考慮緊前緊后關系的鄰域結構來確保搜索過程中產生合法解，以提高搜索能力，避免傳統遺傳算法陷入局部最優；通過本方法所得的飛機裝配線作業調度方案可有效縮短裝配作業總工期。

技術領域

本發明屬于飛機裝配線作業車間在資源、空間受限情況下的作業調度領域，具體涉及一種基于遺傳變鄰域算法的飛機裝配線作業調度方法。

背景技術

飛機裝配具有作業數量大、裝配關系復雜等特點，且駕駛艙等部段區域可容納資源的空間有限，所以飛機裝配線作業調度問題可看作是一類具有特殊空間約束的資源受限項目調度問題(Resource Constrained Project Scheduling Problem,RCPSP)，該類問題已被證明為一類復雜的強NP-hard問題。

從求解角度來看，解決RCPSP及其擴展問題的算法可分為三大類：精確算法、啟發式算法和元啟發式算法(智能算法)，其中精確算法雖然能得到理論最優解，但僅適用于小規模求解，由此近似算法開始被應用于求解大規模RCPSP問題。自1963年調度生成方案后被提出后，各種啟發式算法也相繼被應用到該問題，但其不具備優化能力，往往受到問題本身的影響而得不到滿意解。元啟發式算法和智能算法的應用使問題的求解得到了新的發展，如引入局部搜索中的模擬退火算法(Simulated Annealing，SA)來求解RCPSP，進化算法(如遺傳算法，Genetic Algorithm，GA)和群體智能算法(如蟻群優化算法，Ant ColonyOptimization，ACO)都在求解RCPSP問題上得到了廣泛的應用。

飛機裝配線調度問題屬于傳統RCPSP的擴展問題，其中作業活動除了受到緊前緊后約束和資源的約束外，在飛機的某些部段，眾多滿足資源的并行活動，常因空間的限制而無法同時進行，從而增加了問題空間和計算求解的復雜度。針對問題的復雜性，將元啟發式算法進行混合以彌補各自算法缺點成為解決這類問題的新方法，通過算法混合既提高了問題求解的效率，同時能夠在全局范圍內得到更精確的解。

發明內容

為克服現有技術在解決飛機裝配作業線調度問題中存在的不足，本發明提供一種基于遺傳變鄰域算法的飛機裝配線作業調度方法。

本發明的一種基于遺傳變鄰域算法的飛機裝配線作業調度方法，具體步驟如下：

步驟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＝{r₁,r₂,…,r_q,…,r_k}表示裝配過程中的k種資源集合，用r_jq表示活動j對第q種資源單位時間的需求量，b_q為資源q單位時間的最大供應量；對時間進行離散化處理，d＝{1,2,…,T}為離散的時間節點，T表示裝配作業總工期，A_d＝{j|st_jd≤st_j+t_j}為d時刻正在執行的作業活動集合。