[發明專利]一種基于天牛須搜索的粒子群算法求解柔性作業車間調度的方法

有效

• 申請號: 202010068722.6
• 申請日: 2020-01-21
• 公開（公告）號: CN111311077B
• 公開（公告）日: 2022-02-18
• 發明（設計）人: 唐浩;黎向鋒;張立果;左敦穩;張麗萍;陸開勝;王建明;葉磊;王子旋;劉安旭;劉晉川
• 申請（專利權）人: 南京航空航天大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06N3/00
• 代理公司: 南京天華專利代理有限責任公司 32218
• 代理人: 瞿網蘭

一種基于天牛須搜索的粒子群算法求解柔性作業車間調度的方法，它利用天牛須搜索對粒子群算法進行改進，并混合變鄰域搜索算法，實現柔性作業車間調度。本發明有效地解決在求解柔性作業車間調度問題中的深度性與穩定性不足等難題。為平衡全局搜索和局部搜索能力，本發明將變鄰域算法巧妙融合進混合粒子群算法中，增強算法的局部搜索能力。該混合算法首次被運用在柔性作業車間調度領域，可以有效提高調度方案的質量。考慮到柔性作業車間染色體的編碼方式，需對混合粒子群算法進行適當編碼改進，以免產生不可行解，同時引進遺傳操作，增強其全局搜索能力，從而提高算法的魯棒性。

技術領域

本發明涉及一種生產調度技術，尤其是一種基于天牛須搜索的改進粒子群算法求解柔性作業車間調度的方法，天牛須搜索自首次被提出來為止仍然沒有被運用到柔性作業車間調度領域，運用在此領域可以獲得良好的調度方案。

背景技術

制造業是國民經濟的主體，是立國之本、興國之器、強國之基。為了加快實現到2025 年我國邁入制造強國的戰略目標，制造行業對于車間的調度方案優化、效率優化等研究有著迫切的需求。柔性作業車間調度問題(Flexible Job Shop Scheduling Problem，簡稱FJSP) 是傳統作業車間調度問題的擴展，是實際生產中迫切需要解決的一類問題。相對傳統作業車間調度問題(Job Shop Scheduling Problem，簡稱JSP)，FJSP更為復雜，因為首先要為每個工序分配合理的機器，然后才是工序調度問題。FJSP是對JSP的擴展，由于已經證明JSP是 NP—hard問，所以FJSP也是NP—hard問題。FJSP包括兩個子問題：(1)機器分配，為每道工序分配合理的機器；(2)工序排列，即在選定的機器集上安排工序的起止加工時間。

FJSP由Brucker和Schlie于1990年提出，到目前為止，已經有各種不同的優化算法被用于這類問題的求解，如Willian等融合帝國競爭算法和禁忌搜索算法，以最小化生產周期為目標求解FJSP。姜天華使用混合灰狼優化算法求解FJSP，以灰狼算法為基礎，加入遺傳算子提升算法的全局搜索能力，加入變鄰域搜索算法以加強算法的局部搜索能力。但是諸多優化方法都是基于傳統智能優化算法來進行優化的，其他新型智能優化算法在作業車間調度領域也可以有很好的效果，把新型算法糅合進傳統算法也是未來求解組合優化問題的一種趨勢。

發明內容

本發明的目的是針對現有的柔性車間調度使用的BAS算法僅針對個體，不考慮群體之間的連接關系，PSO側重于群體對于單個粒子的影響，忽略了粒子在搜索過程中自己對環境周圍的判斷，導致了深度性與穩定性不足。本發明提出的算法將BAS和PSO模型結合在一起，PSO的每一個粒子被描述為天牛并行搜索，在迭代過程中，更新天牛位置的方式，不再僅僅依賴全局最佳調度方案和天牛個體的當前最優調度方案，而是添加了天牛天線搜索思想，可以在每次迭代過程中對環境空間判斷。除此之外，本發明還在迭代過程中糅合變鄰域算法，對優秀個體進行局部搜索，以防止該算法陷入局部最優，以較高的概率收斂到全局最優。

本發明的技術方案是：

一種基于天牛須搜索的粒子群算法的求解柔性作業車間調度的方法，它把天牛須搜索和變鄰域搜索同時糅合進粒子群算法，實現柔性作業車間調度，其特征在于它包括以下步驟：

步驟1：初始化算法參數，設置PSO種群的大小為N，最大迭代次數MAX，學習因子為c1、c2、c3，以及每個甲殼蟲天線感知長度為d₀，天牛進化步長δ，在柔性作業車間調度中以求解最大完工時間最小為單目標，在本發明中定義適應度值為最大完工時間的倒數；

步驟2：初始化調度解種群，該種群分兩段編碼，即機器序列編碼和工序序列編碼；機器編碼和工序編碼長度相等；初始化粒子的速度向量v和慣性權重w；種群初始化對于算法求解的速度與質量有很大影響；

步驟3：利用活動解碼計算每個個體的適應度，進行適應度排序，通過逐一比較得到當前的全局最優解；