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

在審

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

本發明屬于車間調度相關技術鄰域，其公開一種具有充分必要條件鄰域結構的作業車間調度優化方法。該方法包括下列步驟：由作業車間調度問題的當前解獲取調度的關鍵路徑，根據充分必要條件對關鍵路徑塊中工序的加工順序進行調整，獲得多種不同加工順序。計算每個加工順序的總加工時間，將總加工時間最短的加工順序作為當前調度順序。充分必要條件為：(1)不存在js(u)到v的路徑是u移動到v之后加工生成的鄰域解為可行解的充分必要條件；(2)不存在u到jp(v)的路徑是v移動到u之前加工生成的鄰域解為可行解的充分必要條件。通過本發明，實現在求解作業車間調度問題時，有效的提高求解質量，縮短求解時間。

技術鄰域

本發明屬于車間調度相關技術領域，更具體地，涉及一種具有充分必要條件鄰域結構的作業車間調度優化方法。

背景技術

車間調度問題是指將生產資源進行合理地配置，以此提高生產效率，降低生產成本等。作業車間調度問題(job-shop scheduling problem,JSP)是一種經典的車間調度問題，其描述為有n個工件，每個工件有m道工序需要在m臺不同機器上進行加工，不同的工件在加工過程中流經的機器順序不同，需要對每一臺機器上工件的加工順序和加工時間進行安排，使得某些指標達到最優。

JSP是NP難問題，對于小規模問題使用可以使用精確解法，但對于大規模問題，很難使用精確算法在有限時間里獲得滿意解。因此，為了提高問題的求解效率和求解質量，學者們通常使用智能優化算法，其中具有高效局部搜索的智能優化算法能夠極大的提高求解質量和求解效率，而鄰域結構是局部搜索的關鍵之一。

在現有研究中，鄰域結構通常分為兩種類型：基于編碼的鄰域結構和基于關鍵路徑的鄰域結構。針對JSP，大多使用基于關鍵路徑的鄰域結構，關鍵路徑是指從剛開始加工到所有工件加工結束時的最長路徑，現在常用的基于關鍵路徑的鄰域結構有三種，其被命名為N5，N6，N7，Nowicki等人(Nowicki,E.,Smutnicki,C.(1996).A fast taboo searchalgorithm for the job shop problem.Management Science,42(6),797-813.)提出N5鄰域結構，Balas等人(Balas E,Vazacopoulos A.Guided local search with shiftingbottleneck for job shop scheduling[J].Management science,1998,44(2):262-275.)提出N6鄰域結構，Zhang等人(Zhang C Y,Li P G,Guan Z L,et al.A tabu searchalgorithm with a new neighborhood structure for the job shop schedulingproblem[J].ComputersOperations Research,2007,34(11):3229-3242.)提出了一種N7鄰域結構，上述方法中存在的問題在于：獲得的鄰域解數量有限，搜索的時間長且精度低。

發明內容

針對現有技術的以上缺陷或改進需求，本發明提供了一種具有充分必要條件鄰域結構的作業車間調度優化方法，提出一種新型的鄰域鄰域結構，并通過該新型的鄰域結構對關鍵路徑塊上的關鍵路徑塊的順序進行調整，能獲得所有可行的調度順序，并且能從所有可行的調度順序中快速準確的搜索獲得總加工時間最短的調度順序。

為實現上述目的，按照本發明，提供了一種具有充分必要條件鄰域結構的作業車間調度優化方法，該方法包括下列步驟：

由作業車間調度問題的當前解獲取調度的關鍵路徑，根據獲得可行解的充分必要條件對關鍵路徑上的徑塊中工序的加工順序進行調整，以此獲得多種不同加工順序的可行鄰域解，計算每個可行鄰域解的加工時間，將總加工時間最短的鄰域解作為當前解，多次迭代后獲得所需的最優鄰域解，其中，所述充分必要條件包括以下兩個：