[發明專利]基于操作權限回溯的雙工作站實現雙席互斥的方法

在審

• 申請號: 202111110134.5
• 申請日: 2021-09-18
• 公開（公告）號: CN113806100A
• 公開（公告）日: 2021-12-17
• 發明（設計）人: 萬云瑩;黃振茂;高慧
• 申請（專利權）人: 南京恒星自動化設備有限公司
• 主分類號: G06F9/52
• 分類號: G06F9/52;G06F8/36;G06F8/75
• 代理公司: 南京禾易知識產權代理有限公司 32320
• 代理人: 詹慶銣

1.一種基于操作權限回溯的雙工作站實現雙席互斥的方法，其特征在于：包括以下步驟：

第一步，獲取調度系統工作站的資源數據，建立針對所述資源數據的解空間；

第二步，將包含資源數據的解空間轉化為解空間樹結構；

第三步，基于深度優先搜索算法對解空間樹結構進行遍歷，得到所述資源數據的可行解或最優解

S3-1，以所述解空間樹結構的根節點為基點向解空間樹結構區域內與此基點相鄰的任一結點作試探性連接；

S3-2，判斷所述結點是否包含所述資源數據的解，其中，

若結點不包含資源數據的解，則跳過以該結點為根節點的子樹的搜索，逐層向其祖先結點回溯；

S3-3，順序執行S3-1以及S3-2，直至找到所述資源數據的可行解或最優解。

2.根據權利要求1所述的一種基于操作權限回溯的雙工作站實現雙席互斥的方法，其特征在于：在第三步中，基于深度優先搜索算法對解空間樹結構進行遍歷時，需要基于約束函數對擴展結點處進行優化，用于剪去不滿足約束條件的路徑；

同時，當解空間樹結構中某一結點處上界函數值小于當前最優解時，需剪去以該結點為根節點的子樹，以剪去不能得到最優解的路徑，節省搜索范圍。

3.根據權利要求1所述的一種基于操作權限回溯的雙工作站實現雙席互斥的方法，其特征在于：在S3-3中，當資源數據的解為至少一個解時，需要回溯到解空間樹結構的根節點進行遍歷搜索，直至此解空間樹結構的根節點的所有子樹均被搜索遍后結束；

當資源數據的解有且只有一個解時，只要在回溯到解空間樹結構的根節點進行遍歷搜索的過程中或以所述解空間樹結構的根節點為基點向解空間樹結構區域內與此基點相鄰的任一結點作試探性連接的過程中，搜索并判斷出此結點或此根節點包含一個資源數據的解時，結束；

輸出。

4.根據權利要求1所述的一種基于操作權限回溯的雙工作站實現雙席互斥的方法，其特征在于：基于遞歸實現和遞推實現所述雙工作站的操作權限回溯。