[發明專利]一種基于矩陣的作業車間調度死鎖檢測與修復方法

在審

• 申請號: 201611206622.5
• 申請日: 2016-12-23
• 公開（公告）號: CN106776053A
• 公開（公告）日: 2017-05-31
• 發明（設計）人: 石飛;趙詩奎
• 申請（專利權）人: 濟南大學
• 主分類號: G06F9/52
• 分類號: G06F9/52
• 代理公司: 濟南譽豐專利代理事務所(普通合伙企業)37240
• 代理人: 李茜

技術領域

本發明涉及生產調度技術領域，具體涉及一種基于矩陣的作業車間調度死鎖檢測與修復方法。

背景技術

作業車間調度問題（Job Shop Scheduling Problem，JSP）是制造執行系統研究的核心和重點之一，其研究具有重要的理論意義和應用價值。目前，以遺傳算法、差分進化算法、禁忌搜索算法、人工蜂群算法等為代表的智能算法在求解JSP問題中得到了成功應用。研究發現，各種高效智能算法的一個共同點是總會融入基于鄰域結構的鄰域搜索技術，因為鄰域結構能夠體現問題本身的特征領域知識，結合問題本身的特點，可以有效的指導搜索方向。但是，在基于鄰域結構的關鍵工序移動過程中，可能會導致已有可行解不可行，即死鎖狀態。死鎖是相互競爭資源的事務間相互等待、各事物的資源請求在現行的并發控制機制下永遠得不到滿足的一種停滯狀態。反映在JSP問題上，是工件工序的加工順序約束關系得不到滿足。進而使得加工進程不能順利進行，甚至造成新的加工進程不能開始，因此，有必要研究死鎖問題。

目前，解決JSP死鎖問題有三種策略：死鎖預防，死鎖避免，死鎖檢測與修復。其中，針對死鎖檢測與修復，大多數的研究都是基于圖模型理論，尤其涉及一種析取圖模型，即構造能描述問題特征的析取圖模型，如果發現該模型中存在有向回路，則發生死鎖。死鎖修復的關鍵在于拆斷有向回路，使各工件工序的加工順序約束關系得到滿足。目前文獻中的各種修復策略，只是將其修復為一個可行解，本發明擬實現一種更為先進的修復策略，在得到可行解的前提下，盡可能修復為目標函數值更為優良的可行解。

發明內容

本發明的目的是將數學中的鄰接矩陣和可達矩陣引入作業車間調度問題的研究中，進而從數學矩陣運算和性質的角度進行相關的理論研究，提出一種基于矩陣的作業車間調度死鎖檢測與修復方法，以期通過數學邏輯運算能快速檢測出由工序移動引發的死鎖，并給出死鎖時，導致死鎖的信息。然后結合JSP問題的領域知識，根據工序類型信息，拆斷導致死鎖的有向回路，實現更為先進的修復，不但修復為可行解，而且盡可能修復為目標函數值更好的可行解，進而使得各種基于鄰域結構搜索的高效智能算法在求解JSP問題時更加高效可行。

本發明的目的采用如下技術方案實現。

一種基于矩陣的作業車間調度死鎖檢測與修復方法，其特征在于包括如下步驟：

步驟1：根據調度結果對應的析取圖模型G構建鄰接矩陣A；

步驟2：根據鄰接矩陣A，計算可達矩陣M；

步驟3：死鎖檢測，如果發現死鎖則尋找導致死鎖的矩陣元素，并標記，否則，結束；

步驟4：根據死鎖信息，結合JSP問題的領域知識，拆斷導致死鎖的有向回路，打破死鎖；

步驟5：根據步驟4中修改的結果修正析取圖模型G，返回步驟1。

步驟1中所述析取圖模型G=<V，E>，其中：V是節點集合，V={v₁，v₂，…，v_n}，包括一個虛擬的開始節點S和一個虛擬的結束節點F；E是有向邊的集合；V中除節點S和節點F以外的節點均表示工序；E包括連接弧和析取弧，連接弧表示工件工序的二元關系，析取弧表示機器工序的二元關系。

步驟1中所述鄰接矩陣A是n階方陣，A=(a_ij)_n×n，a_ij的值通過下式確定：

矩陣最左邊和最上邊的元素代表工序號，當i等于j時，x_i和y_j表示相同工序。

步驟2中所述可達矩陣M是根據所構建的鄰接矩陣A計算得到，M也是n階0-1方陣，且符合布爾代數運算法則，其計算公式為 ： ，其中I為與A同階次的單位矩陣，反映元素自身到達，最大傳遞次數（路長）r根據下式確定：

。