[發明專利]一種具有充分必要條件鄰域結構的作業車間調度優化方法

在審

• 申請號: 202011373398.5
• 申請日: 2020-11-30
• 公開（公告）號: CN112330221A
• 公開（公告）日: 2021-02-05
• 發明（設計）人: 李新宇;桂林;高亮
• 申請（專利權）人: 華中科技大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 孔娜;李智

1.一種具有充分必要條件鄰域結構的作業車間調度優化方法，其特征在于，該方法包括下列步驟：

對于作業車間的當前調度順序，采用充分必要條件鄰域結構對調度的關鍵路徑上路徑塊中的加工順序進行調整，以此獲得多種不同的加工順序，計算每個加工順序對應的總加工時間，將總加工時間最短的加工順序作為當前調度順序，多次迭代調整后獲得總加工時間最短的調度順序，以此實現車間調度的優化，其中，所述充分必要條件鄰域結構包括以下兩個：

(1)u移動到v之后加工產生可行加工順序的充分必要條件：若不存在js(u)到v的路徑時，將u移動到v之后加工可行，若存在js(u)到v的路徑時，將u移動到v之后加工不可行；

(2)v移動到u之前加工產生可行加工順序的充分必要條件：若不存在u到jp(v)的路徑時，則將v移動到u之前加工可行，若存在u到jp(v)的路徑時，則將v移動到u之前加工不可行；

其中，u和v同一臺機器上的不同工序，且u在v前面加工，js(u)是加工同一個工件時工序u后面的一道工序，jp(v)是加工同一個工件時工序v前面的一道工序。

2.如權利要求1所述的一種具有充分必要條件鄰域結構的作業車間調度優化方法，其特征在于，當u為首工序時，且不存在js(u)到v的路徑時，將u移動至v后加工所產生的中間解集比其它方式獲得的中間解集對當前調度順序改進的概率更大。

3.如權利要求1所述的一種具有充分必要條件鄰域結構的作業車間調度優化方法，其特征在于，當u為首工序時，且不存在u指向jp(v)的路徑時，將v移動至u之前加工產生所產生的中間解集比其它方式獲得的中間解集對當前調度順序改進的概率更大。

4.如權利要求1所述的一種具有充分必要條件鄰域結構的作業車間調度優化方法，其特征在于，當v為尾工序時，且不存在js(u)指向v的路徑時，將u移動至v后加工產生所產生的中間解集比其它方式獲得的中間解集對當前調度順序改進的概率更大。

5.如權利要求1所述的一種具有充分必要條件鄰域結構的作業車間調度優化方法，其特征在于，當v為尾工序時，且不存在u指向jp(v)的路徑時，將v移動至u之前加工產生所所產生的中間解集比其它方式獲得的中間解集對當前調度順序改進的概率更大。

6.如權利要求1所述的一種具有充分必要條件鄰域結構的作業車間調度優化方法，其特征在于，所述根據獲得可行解的充分必要條件對關鍵路徑上路徑塊中的加工順序進行調整，其中調整的是關鍵路徑塊上的關鍵路徑塊中的加工工序的順序。

7.如權利要求1所述的一種具有充分必要條件鄰域結構的作業車間調度優化方法，其特征在于，判斷是否存在js(u)到v的路徑，或者是否存在u到jp(v)的路徑時，是通過從析取圖中進行判斷。