[發(fā)明專利]基于ST的啟發(fā)式算法的三階段柔性流水車間調(diào)度方法

在審

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

1.基于ST的啟發(fā)式算法的三階段柔性流水車間調(diào)度方法，包括如下步驟：

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

；

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

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

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

步驟2：根據(jù)分配規(guī)則分別安排工件在三個加工單元的機器上加工；

因此，本發(fā)明提出一種基于TS算法的啟發(fā)式算法TSM，求解問題；

步驟四：設計仿真實驗，對ST啟發(fā)式算法進行了仿真調(diào)度。

2.如權利要求1所述的基于ST的啟發(fā)式算法的三階段柔性流水車間調(diào)度方法，其特征在于，所示TSM算法包括如下步驟：

步驟一：運用R-S算法(R-S算法的求解輔助問題，得到工件加工列表；

步驟二：根據(jù)FAM規(guī)則，依次安排的工件在第一個加工單元的機器上加工；

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

步驟四：根據(jù)FAM規(guī)則，依次安排的工件和與其協(xié)同加工A類工件在第二個加工單元的機器上加工；

步驟五：根據(jù)LBM規(guī)則，安排的工件在第三個加工單元的機器上加工。

3.如權利要求1所述的基于ST的啟發(fā)式算法的三階段柔性流水車間調(diào)度方法，其特征在于，所述問題的數(shù)學模型如下：

（1）

約束條件為:

???(2)

???(3)

??(4)

??(5)

???(6)

???(7)

???(8)

???(9)

?(10)

??(11)

以下是數(shù)學模型用到的變量：

：第i個A類工件，i=1,2，…，n；

：第j個B類工件，j=1,2，…，q；

：加工單元d的機器數(shù)量，d=1,2,3;

：工件l在加工單元d的到達時間，l=1,2，…，(n+q)；

：加工單元d中第k臺機器，k=1,2，…，m_d；

：B類工件在第二道序加工時需要A類工件協(xié)同加工的第i個工件；

：工件l在加工單元d第k臺機器上的加工時間；

：工件l在加工單元d加工的開始加工時間

：工件l在加工單元d加工的完工時間；

：工件在第二道工序需要A類工件協(xié)同加工的工件集；

：工件集的數(shù)量；

??二進制變量：

;

上述的表達式中：式(1)表示問題的目標函數(shù)，最小化工件最大完工時間；式(2)表示目標函數(shù)值等于最后一個完工的工件完工時間；式(3)表示每個工件必須在每個加工單元中的一臺機器上加工；式(4)計算每個工件在每個加工單元加工的完工時間；式(5)表示工件在每個加工單元的開始加工時間不能早于其在該加工單元的到達時間；式(6)表示工件在下一個加工單元的到達時間等于該工件在上一個加工單元的完工時間；式(7)表示在第一和第三個加工單元的機器同一時間只能加工一個工件；式(8)?表示A類工件在第二道序需要成組加工的工件集；式(9)表示第二加工單元的機器同一時間只能加工一個B類工件；式(10)表示B類工件需要與其對應的A類工件在第二個加工單元中具有成組加工，并且A類工件具有并行加工特點；式(11)表示A類工件成組后的工件總數(shù)等于成組前的工件總數(shù)。