[發明專利]基于改進禁忌搜索算法的生產運輸協同調度方法及系統

有效

• 申請號: 201710813169.2
• 申請日: 2017-09-11
• 公開（公告）號: CN107392402B
• 公開（公告）日: 2018-08-31
• 發明（設計）人: 裴軍;宋慶儒;劉心報;陸少軍;張強;范雯娟;孔敏
• 申請（專利權）人: 合肥工業大學
• 主分類號: G06F17/00
• 分類號: G06F17/00;G06Q10/04;G06Q10/06;G06Q50/04
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 王瑩;余罡

本發明實施例涉及一種基于改進禁忌搜索算法的生產與運輸協同調度方法及系統，該方法包括：1工件組批；2初始化算法參數；3產生初始解4產生鄰域解集；5個體進行變異、交叉和選擇；6確定候選解集；7計算個體適應度值；8更新候選解集；9更新禁忌表；10判斷算法終止條件是否滿足，若滿足則輸出全局最優解，否則返回步驟4；本發明主要是針對多制造商情形下的生產與運輸協同批調度問題，求得該問題的近似最優解，即獲得一個科學有效的生產與運輸協同調度方案，從而可以提高企業在生產與運輸兩個階段中實現整體效益最大化，并為企業的客戶提供優質服務，提升企業的核心競爭力。

技術領域

本發明實施例涉及軟件技術領域，具體涉及一種基于改進禁忌搜索算法的生產運輸協同調度方法及系統。

背景技術

批調度問題作為一類典型的組合優化問題，廣泛存在于現代的生產活動中，如交通運輸，生產運輸以及船閘調度等領域。而在同類平行機批調度問題中，各機器的處理能力相同但處理速度不同，批處理機在能力范圍內可以同時加工處理多個工件。在當今的云制造主流模式背景下，為充分利用現有的生產資源從而為客戶提供優質的服務，針對客戶同一個訂單，企業間以合作形式共同完成該訂單生產任務。設計科學合理的分布式同類機生產調度方案不僅可以使得社會的生產資源得以充分利用，還可以促進企業生產能力的提高。因此，針對分布式同類平行機批調度問題，如何確定一個合理有效的生產調度方案成為企業亟待解決的問題，對該類問題的研究具有重要的實際意義。

在以往的研究中，智能算法和啟發式算法被廣泛應用于解決復雜情形下的生產運輸協同調度問題。一種研究是針對差異工件相同平行機批調度問題進行研究，工件具有不同的尺寸和加工時間，并設計了混合模擬退火和遺傳算法解決該問題；另一種研究是考慮工件含不同加工時間，到達時間，截止時間和尺寸，并設計了群算法解決該問題；還有一種研究是考慮了分布式環境下工件動態到達各批處理機，且加工前后都有運輸時間，針對該問題提出了若干個啟發式算法。本文針對分布式制造商的同類平行機生產與運輸協同批調度問題，設計了改進的禁忌搜索算法，通過該算法確定各工件批在機器上的分配方案，從而獲得一個使得生產與運輸兩階段整體效益最大化的生產與運輸協同調度方案。禁忌搜索算法的一般步驟包括：(1)生成初始解；(2)產生鄰域解；(3)確定候選解；(4)選出候選解集中滿足禁忌規則的最優個體；(5)更新候選集；(6)更新禁忌表；(7)更新全局最優解。通過重復以上步驟在整個解空間搜索并獲取最優解，即最優的生產與運輸協同調度方案。

然而，在進行發明創造的過程中發明人發現，現有技術存在以下缺陷：(1)在研究問題上，以往研究的關注點主要集中在相同平行機上，而對同類機上批調度問題的研究相對較少，并且在同類機情形下同時考慮生產與運輸的研究成果較少。在實際生產活動中，存在著同一個訂單生產任務由多個企業共同完成，由于各企業的生產條件不同，所以企業的加工機器處理速度并不完全相同。在解決此類調度問題時，不僅需要考慮工件的差異性，同時還需要考慮機器的差異對問題所優化制造時間跨度的影響。(2)在研究方法上，候選解的確定，禁忌規則，禁忌表長度等，這些因素都影響著禁忌搜索算法的性能。

發明內容

本發明實施例提供了一種基于改進禁忌搜索算法的生產運輸協同調度方法及系統，用以解決上述至少一個技術問題。

第一方面，本發明實施例提供一種基于改進禁忌搜索算法的生產運輸協同調度方法，包括：

S1、將工件集合J＝{J₁,...,J_i,...,J_n}中所有工件按基本加工時間非遞增進行排序，得到經過排序后的工件集合J'＝{J'₁,...,J'_i,...,J'_n}；

S2、根據工件集合J'，在現存的批中選出能容納第一個未分配的工件的所有批，從已選出的批中獲取剩余空間最小的批，將J'中第一個未分配的工件放置于最終選出的批中，并將該工件從工件列表中刪除；