[發明專利]一種基于改進果蠅算法的作業車間調度方法

在審

• 申請號: 201611042598.6
• 申請日: 2016-11-24
• 公開（公告）號: CN108108829A
• 公開（公告）日: 2018-06-01
• 發明（設計）人: 戴佐俊;張月霞;殷生旺
• 申請（專利權）人: 江蘇創源電子有限公司;北京信息科技大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G05B19/418
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明提出了一種基于改進果蠅算法的作業車間調度方法，所述方法包括：根據作業車間的特點，建立作業車間的數學模型，構建出每個工件不同工序的加工順序的約束條件，以及每臺機器上不同工件的工序加工順序的約束條件。然后建立基于最大完工時間最小的作業車間調度目標函數，通過基于工序的編碼方式形成果蠅個體，采用了自適應步長的分類嗅覺隨機搜索方法，使果蠅種群快速找到味道濃度判定函數的最小值，得出作業車間調度的最優解，即作業車間調度的最優方案。該算法實現簡單，只需要設置兩個參數，并且全局尋優能力較強，能夠有效地解決作業車間調度問題。

技術領域

本發明涉及作業車間調度問題，具體涉及一種基于改進果蠅算法的作業車間調度方法。

背景技術

作業車間調度問題實際上是生產調度問題的簡化，其具有廣泛的應用背景，譬如生產制造、交通規劃、郵電通信、大規模集成電路設計等問題。作為一類滿足任務配置和順序約束要求的資源分配問題，作業車間調度已被證明是一個典型的NP-hard問題，它的求解難度遠大于流水線調度問題，針對其算法的研究一直是學術界和工程界共同關注的重要課題。

如今，制造業的競爭日益激烈，制造企業正朝著有不同完工時間和產品要求的多類型、小批量的生產模式發展。如何利用現有資源，滿足加工任務所需各種約束，使所有任務能盡量按時完成，即如何有效地解決作業車間調度問題，成為一個十分現實和迫切的問題。高效調度算法，可以大大提高生產效益和資源利用率，從而增強企業的競爭能力，因此對作業車間調度問題的研究有非常重要的理論和實用價值。

目前，求解作業車間調度問題的主要方法是群智能優化算法，如遺傳算法、模擬退火算法、禁忌搜索算法、蟻群算法、粒子群算法、蛙跳算法以及各種混合調度算法等。遺傳算法是根據自然進化論得出的一種并行優化搜索算法，該算法能夠以較大概率找到全局優化解。蟻群算法是模擬螞蟻尋路的過程而設計出的一種大量個體相互協作的啟發式搜索算法，也能夠很快搜索到比較好的解。但是，這些算法的參數設置較多、計算復雜度較大，并不能夠有效的解決車間調度的問題。

發明內容

本發明的目的在于提供一種基于改進果蠅算法的作業車間調度方法。該方法可以有效地解決車間調度問題、提高作業車間調度效率。

本發明提出了一種基于改進果蠅算法的作業車間調度方法，所述方法包括：根據作業車間的特點，建立作業車間的數學模型，構建出每個工件不同工序的加工順序的約束條件，以及每臺機器上不同工件的工序加工順序的約束條件。然后建立基于最大完工時間最小的作業車間調度目標函數，通過基于工序的編碼方式形成果蠅個體，采用了自適應步長的分類嗅覺隨機搜索方法，使果蠅種群快速找到味道濃度判定函數的最小值，得出作業車間調度的最優解，即作業車間調度的最優方案。該算法實現簡單，只需要設置兩個參數，并且全局尋優能力較強，能夠有效地解決作業車間調度問題。其具體步驟如下：

1)根據作業車間的特點，建立作業車間的數學模型；

2)構建出每個工件不同工序的加工順序的約束條件；

3)構建每臺機器上不同工件的工序加工順序的約束條件；

4)建立基于最大完工時間最小的作業車間調度目標函數；

5)通過基于工序的編碼方式，并形成果蠅個體即果蠅種群初始化；

6)采用自適應步長的分類嗅覺隨機搜索方法，使果蠅種群快速找到味道濃度判定函數的最小值，確定出新的果蠅種群；

7)對得到新的果蠅種群進行評價，并依此進行迭代尋優；

8)進行終止條件判定，若條件不滿足，則跳轉至步驟6并依次進行余下步驟。否則，算法結束，輸出結果。

上述步驟1中，建立作業車間調度數學模型：