[發明專利]一種基于免疫遺傳算法求解第一類裝配線平衡問題的方法

在審

• 申請號: 201810803005.6
• 申請日: 2018-07-20
• 公開（公告）號: CN109146136A
• 公開（公告）日: 2019-01-04
• 發明（設計）人: 張含葉;梁偉杰
• 申請（專利權）人: 九江學院
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/12;G06Q50/04
• 代理公司: 南昌新天下專利商標代理有限公司 36115
• 代理人: 謝德珍

一種基于免疫遺傳算法求解第一類裝配線平衡問題的方法，該方法定義了一個函數ψ(?)使種群中的個體滿足裝配優先關系約束，并給出了第一類裝配線平衡問題的約束條件和目標函數，最后構建了免疫遺傳算法求解第一類裝配線平衡問題，該方法包括函數ψ(?)的定義，約束條件，目標函數，免疫遺傳算法；其中免疫遺傳算法包括：設定參數、初始化、更新種群、更新記憶庫、終止條件驗證和結果輸出。本發明將人工免疫算法和遺傳算法結合起來，建立一種綜合性能更好的混合算法，可用于解決第一類裝配線平衡問題，例如用于求解APXV9R20B天線裝配線平衡問題。

技術領域

本發明涉及一種基于免疫遺傳算法求解第一類裝配線平衡問題的方法。

背景技術

裝配線作為一種重要的制造系統，它是高效生產的開始。在裝配線的設計中，最重要、最關鍵的是裝配線平衡問題。為了解決產品第一類裝配線平衡問題，尤其是APXV9R20B天線裝配線平衡問題，本專利設計了一種免疫遺傳算法。

自從福特于1913年建立第一條汽車裝配線開始，生產平衡問題就隨之產生，但是直到1954年這一問題才由Bryton在其碩士論文《Balancing of a continuous productionline》中正式提出。迄今為止，解決此問題的方法主要有：最優化方法（精確方法）、啟發式方法和人工智能方法。

Bowman采用兩個獨立的線性規劃模型求解裝配線平衡問題，其運算量很大，與實際情況相差甚遠。Calleja等提出一種MILP模型求解AWALBP。其中，以最小化裝配節拍為目標函數。結果表明，工件的長度越長，求解將越困難；對于大規模的問題而言，只能獲得工件長度在25個單位之內的最優解；對于小/中等規模而言，可以獲得工件長度在25～40個單位之內的最優解。Ozcan提出一種機會約束的線性分段的混合整數規劃求解雙邊隨機裝配線平衡問題。實例結果顯示，該算法是有效的，且是雙邊隨機裝配線平衡問題研究方面的第一篇文章。Bautista等提出一種基于啟發式規則的動態規劃算法求解第I類裝配線平衡問題。從公開發表的文獻中選取269個實例，利用本文所提出的算法進行求解。結果表明，有267個實例可以獲得更好的解，另外一個實例也獲得了最優解，僅對一個實例無法求解。吳爾飛等提出一種分支定界算法求解雙邊裝配線平衡問題。該算法采用基于任務、單步、深度優先的方法進行搜索，采用一系列啟發式規則來控制分支節點搜索順序，運用節點支配規則、下界規則、最大緩沖時間規則等對分支節點進行定界，以便迅速找到最優解。算例結果表明該算法具有較好的性能。

盡管最優化方法可以獲得待求問題的最優解，但是由于其大量的數學計算以及實際生產線問題的復雜性而降低了其實用性，它只能適用于較小計算規模的問題。

Jackson首次采用枚舉法求解第一類裝配線平衡問題。他從理論上證明，該方法一定可以獲得最優解，且優于完全枚舉法。但是，隨著求解問題規模的增大，該方法的求解時間耗時巨大。Amen提出兩種新的啟發式方法求解面向成本的裝配線平衡問題。一種優先規則叫做“閑置成本最佳變化”；另一種更復雜的方法叫做“滑動問題窗”，該方法不僅可以用于裝配線平衡問題的求解，而且也可以用于其它一些具有優先關系問題的求解。Chen等采用啟發式方法對具有并行工作站的U型裝配線平衡問題進行了研究。結果表明該算法執行速度很快，同時也預測：如果利用該算法對不具有并行工作站的U型裝配線平衡問題進行求解，則有大約50%的概率獲得最優解。Fazlollahtabar等提出一種基于RPW算法的啟發式方法對隨機裝配線平衡問題進行研究，同時，也開發了正態分布法和蒙特卡羅模擬法。實例結果表明，與正態分布法相比，本文所提出的算法和和蒙特卡羅模擬法更有效。Su等采用基于Petri網的兩階段啟發式算法求解第E類混流裝配線平衡問題。實例表明，針對大規模問題，無論是在求解的精度方面，還是求解的效率方面，該算法都可以實現較好的效果。