[發明專利]一種批量流混合流水車間調度問題的改進候鳥優化方法

有效

• 申請號: 202110021878.3
• 申請日: 2021-01-07
• 公開（公告）號: CN112731888B
• 公開（公告）日: 2022-07-01
• 發明（設計）人: 湯洪濤;王丹南;陳貴芳;任森麗;鄭之恒;周嘉豪
• 申請（專利權）人: 浙江工業大學
• 主分類號: G05B19/418
• 分類號: G05B19/418
• 代理公司: 杭州杭誠專利事務所有限公司 33109
• 代理人: 尉偉敏

本發明公開了一種批量流混合流水車間調度問題的改進候鳥優化方法，包括如下步驟：S1：初始化種群：初始化AMBO算法的六個控制參數；S2：領導解改進；S3：跟隨解改進；S4：領導解替換；S5：更新領導解的算子權重；S6：通過擾動機制對領導鳥進行順序部分擾動，重新計算最優解，當滿足終止條件時輸出計算結果。本發明針對MBO算法各算子在算法運行不同階段改進概率具有差異的特點，提出了一種基于自適應鄰域搜索算法的候鳥遷徙算法（AMBO），通過初始化種群、領導解改進、跟隨解改進、領導解替換、更新領導解的算子權重和擾動機制幾個步驟解決現有用于不相等批量流混合流水車間調度問題的優化方法容易陷入局部最優的技術問題。

技術領域

本發明涉及計算機集成制造技術領域，具體涉及一種批量流混合流水車間調度問題的改進候鳥優化方法。

背景技術

批量流混合流水車間調度問題(Lot Streaming Hybrid Flowshop SchedulingProblem， LS-HFSP)是批量流問題(Lot-streaming，LS)與混合流水車間調度問題(HybridFlowshop Scheduling Problem，HFSP)的結合。近年來，LS-HFSP得到了廣泛的關注，并且大量的研究表明，批量流可以顯著提高調度效率[2]。根據給定拆分子批大小是否相同，可以將批量流問題分為相等批量流問題(Equal Lot-streaming,ELS)與不相等批量流問題(Inqual Lot-streaming,ILS)。相等批量流混合流水車間調度問題(ELS-HFSP)是目前研究較多的 LS-HFSP問題，相等批量拆分是解決批量流問題的最簡單、最直接的方法，一旦確定了子批次數量，就可以確定每個子批次的大小。但相等批量拆分只能優化子批的數量，無法優化每個子批次的大小。在現實中，不相等批量流問題更符合實際生產生活，由于不相等批量流混合流水車間調度問題(Inequal Lot Streaming Hybrid Flowshop SchedulingProblem，ILS-HFSP) 在優化加工順序的同時，又要優化子批的數量與子批量的大小，大大增加了計算的復雜度。

近年來，國內外已經有學者在ILS-HFSP鄰域做了大量研究，但這些工作具有一定的局限性，現有研究以單目標優化為主。Mei Zhang等研究了柔性作業車間不相等批量拆分調度問題(BS-FJSP)的大小可變的批量拆分調度問題，并用競爭合作機制改進候鳥遷徙算法來提高算法求解RPI值。Nederai和Yazdani以最小化延遲時間為目標，研究k階段不可混流的ILS_HFSP問題以及子批的情形，并提出了一種帝國競爭算法來解決該問題。Lalitha等人以最小化最大生產時間為指標，研究了只在最后一個階段具有多臺并行機的k階段不可混流的ILS_HFSP問題。Zhang等人以最小化平均完工時間為優化目標，研究了一種特殊的不可混插子批的兩階段ILS_HFSP問題，第一階段含有多臺并行機而第二階段只包含一臺機器，分別解決加工批次的調度順序和批次分割批數量以及批量大小。文獻是關于多目標不相等批量流混合流水車間調度問題為數不多的研究，但以最小在制品數量為目標的相關研究尚處空白。Zhang等針對存在隨機擾動的相等批量流混合流水車間調度問題(ELS-HFSP)，提出了多目標候鳥遷徙算法(MMBO)，解決了最小化總加工時間與子批開工時間偏差的雙目標優化問題。Li等研究了以減少平均停滯時間、能源消耗及提前和延遲造成損失為目標，研究可變批次的批量流混合流水車間調度問題。Garey和Johonson證明了HFSP是個NP難問題，所以本文研究的不相等批量流混合流水車間調度問題(ILS-HFSP)也是個NP難問題，使用確定性算法獲得精確解是耗時困難的，故學者常采用啟發式算法來解決。候鳥遷徙算法(Migrating Birds Optimization,MBO)是一種新的啟發式算法，由Duman等在2012年首次提出。該算法模擬以V形編隊飛行的鳥類遷徙行為，每一只鳥都代表一種可行解。在該算法中，鳥的數量、鄰域解的數量、跟隨鳥共享的鄰域數量以及鄰域搜索次數是影響其性能的四個參數，它具有較強的局部搜索能力和簡單的結構，已成功應用于二次分配、流水車間調度、信用卡欺詐等不同的研究領域。