[發明專利]用于將排程問題切分成子問題的方法和系統

有效

• 申請號: 201280053934.0
• 申請日: 2012-10-30
• 公開（公告）號: CN104662566B
• 公開（公告）日: 2018-09-11
• 發明（設計）人: 大衛·埃弗頓·諾曼
• 申請（專利權）人: 應用材料公司
• 主分類號: G06Q10/06
• 分類號: G06Q10/06
• 代理公司: 北京律誠同業知識產權代理有限公司 11006
• 代理人: 徐金國;趙靜

1.一種方法，所述方法包含以下步驟：

接收用戶輸入的排程問題數據，所述排程問題數據涉及排程問題，且所述排程問題數據包含多個站、多個任務以及一定數量的任務與站的多個組合，其中排程系統不能處理所述數量的任務與站的多個組合；

使用所述排程問題數據建構圖形問題，所述圖形問題包含圖形和所述圖形中表示所述多個站的多個節點；

使用切分算法將所述圖形切分成子圖形以產生滿足一閾值的切分結果；

從所述排程問題數據和所述子圖形確定至少一個任務，所述至少一個任務符合被不同子圖形中的節點所表示的站處理的條件；

對于每一子圖形，通過計算系統將子圖形中的站子集與相應任務子集進行分組；

通過所述計算系統按照與所述排程系統相容的格式產生所述排程問題的新表示，所述新表示根據所述分組減少任務和站的組合的數量，其中減少數量的任務和站的組合可由所述排程系統處理；和

通過所述計算系統經由網絡為所述排程系統提供所述排程問題的所述新表示，其中所述新表示表示了具有一個或多個子問題的減少數量的任務和站的組合以及至少一個確定的任務，所述至少一個確定的任務符合被不同子圖形中的站處理的條件，并且所述新表示使所述排程系統能夠使用減少數量的組合處理所述排程問題。

2.如權利要求1所述的方法，其中所述切分結果具有最少數量的符合被不同子圖形中的節點所表示的站處理的條件的任務、或最少數量的任務類型。

3.如權利要求1所述的方法，其中所述圖形包含一條或多條線，所述一條或多條線連接所述多個節點中的一對或多對以表示與對應于所述連接的節點的所述站相關的任務。

4.如權利要求1所述的方法，其中建構所述圖形的步驟包含以下步驟：

將權重分配至在所述圖形中表示站的節點或者在所述圖形中連接一對節點的線中的至少一個，其中所述線表示與對應于所述連接的節點對的所述站相關的至少一個任務，且所述權重指示下述中的至少一個：(i)與對應于所述節點對的所述站相關的任務數量、(ii)與對應于所述節點對的所述站相關的任務百分比、和(iii)與對應于所述節點對的所述站相關的任務優先級。

5.如權利要求1所述的方法，其中按照規定的流程順序處理所述多個任務。

6.如權利要求1所述的方法，其中所述多個任務涉及制造半導體。

7.一種使用處理裝置切分排程問題的設備，所述設備包含：

接收用戶輸入的排程問題數據的裝置，所述排程問題數據涉及排程問題，且所述排程問題數據包含多個站、多個任務以及一定數量的任務和站的多個組合，其中排程系統不能處理所述數量的任務和站的多個組合；

使用所述排程問題數據建構圖形問題的裝置，所述圖形問題包含圖形和所述圖形中表示所述多個站的多個節點；

使用切分算法將所述圖形切分成子圖形以產生滿足一閾值的切分結果的裝置；

從所述排程問題數據和所述子圖形確定至少一個任務的裝置，所述至少一個任務符合被不同子圖形中的節點所表示的站處理的條件；

對于每一子圖形，通過所述處理裝置將子圖形中的站子集與相應任務子集進行分組的裝置；

通過所述處理裝置按照與所述排程系統相容的格式產生所述排程問題的新表示的裝置，所述新表示根據所述分組減少任務和站的組合的數量，其中減少數量的任務和站的組合可由所述排程系統處理；和

通過所述處理裝置經由網絡為所述排程系統提供所述排程問題的所述新表示的裝置，其中所述新表示表示了具有一個或多個子問題的減少數量的任務和站的組合以及至少一個確定的任務，所述至少一個確定的任務符合被不同子圖形中的站處理的條件，并且所述新表示使所述排程系統能夠使用減少數量的組合處理所述排程問題。

8.如權利要求7所述的設備，其中所述切分結果具有最少數量的符合被不同子圖形中的節點所表示的站處理的條件的任務、或最少數量的任務類型。