[發明專利]基于ST的啟發式算法的三階段柔性流水車間調度方法

在審

• 申請號: 201410656544.3
• 申請日: 2014-11-18
• 公開（公告）號: CN104392124A
• 公開（公告）日: 2015-03-04
• 發明（設計）人: 楊海東;黎展濤;劉國勝;張沙清;郭建華
• 申請（專利權）人: 廣東工業大學
• 主分類號: G06F19/00
• 分類號: G06F19/00;G05B19/418;G06Q50/04
• 代理公司: 北京精金石專利代理事務所(普通合伙) 11470
• 代理人: 劉曄

技術領域

本發明涉及柔性流水車間調度領域，尤其涉及一種基于ST的啟發式算法的三階段柔性流水車間調度方法。

背景技術

柔性流水車間(Flexible?flow?shop,?FFS)調度問題在離線制造系統中普遍存在，對其進行研究具有重要理論意義和工程實用價值。經典的柔性流水車間調度可描述為：有s類處理機，第j類有sj個同等并行機每個工件有s道工序，每道工序需要在每類同等并行機中的一個處理機上加工，且每個工件的加工順序相同。對于經典的柔性流水車間調度問題已經有不少的研究成果。然而，經典柔性流水車間調度問題對實際調度環境做了較大的簡化，例如，所有工件在零時刻到達；機器都是同等并行機等。在實際生產環境中調度環境要復雜多，出于理論研究和工程實際的需要，研究者提出了各種FFS調度問題模型并研究了其相應的算法，如考慮工件帶到達時間、考慮工件加工時間不確定、考慮機器為非同等并行機等FFS調度問題。目前針對帶成組約束的FFS調度問題的研究成果并不多，有的考慮了混雜的二階段流水作業問題，其中第一階段由m臺并行機組成，第二階段由一臺批處理機組成，并以最少化最大完工時間為研究目標；有的以模具電極加工作為研究背景，考慮了具有數控加工CNC(Computer?Numerical?Control，CNC)和電火花EDM(Electrical?Discharge?Machining，EDM)兩道工序且后工序帶有成組特征的柔性流水車間調度問題進行了研究，以最少化電極總拖期量為目標，提出了一種啟發式算法。事實上，帶成組約束的柔性流水車間調度問題普遍存在于離散制造行業，例如工件的熱處理、模具行業中的電火花等，本發明根據出現成組約束的位置不同把該類問題分為三種子類問題：前成組約束、后成組約束和中成組約束柔性流水車間。

通過對上面的分析，發現對于FFS問題的研究，大多數只是局限在兩階段的柔性流水車間調度問題，對三階段或者多階段的柔性流水車間調度問題的研究相對來說較少，更沒有發現對于具有中成組約束的三階段柔性流水車間調度問題的研究。?

發明內容

本發明的目的在于提供一種基于ST的啟發式算法的三階段柔性流水車間調度方法，為求解帶成組約束的柔性流水車間調度問題提供一套完整的求解算法，解決了中成組約束的三階段柔性流水車間調度問題。

為實現上述目的，本發明提供如下技術方案：

基于ST的啟發式算法的三階段柔性流水車間調度方法，包括如下步驟：

步驟一：提出一類考慮中成組約束的、工件批量到達的三階段柔性流水車間調度問題，并且每階段都是由非同等并行機構成，且用Graham的三元組來描述這樣一類問題：

；

步驟二：在對中成組約束進行了定義和數學描述的基礎上，進一步建三階段柔性流水車間調度問題的優化模型；

步驟三：通過對該類調度問題的分析，得到問題的下界和一個定理，提出一種基于ST思想的啟發式算法，其中ST算法的核心思想如下：

步驟1：應用啟發式算法對輔助問題進行求解，得到原問題的一個初始加工隊列;

步驟2：根據分配規則分別安排工件在三個加工單元的機器上加工;

因此，本發明提出一種基于TS算法的啟發式算法TSM，求解問題;

步驟四：設計仿真實驗，對ST啟發式算法進行了仿真調度。

進一步，所示TSM算法包括如下步驟：

步驟一：運用R-S算法(R-S算法的詳細步驟可以參考文獻[26])求解輔助問題，得到工件加工列表;

步驟二：根據FAM規則，依次安排的工件在第一個加工單元的機器上加工;

步驟三：依據B類工件在第一個加工單元的完工時間不減排序，得到B類工件在第二個加工單元加工的隊列;

步驟四：根據FAM規則，依次安排的工件和與其協同加工A類工件在第二個加工單元的機器上加工;

步驟五：根據LBM規則，安排的工件在第三個加工單元的機器上加工；

進一步/，上述問題的數學模型如下：

????（1）

約束條件為:

????(2)

??????????????????????????(3)

?????????(4)

????????????????????????????????(5)

????????????????????????????(6)

????????(7)