[發明專利]一種求解多處理器過載調度問題最優解的確定性方法

有效

• 申請號: 202010141625.5
• 申請日: 2020-03-03
• 公開（公告）號: CN111459655B
• 公開（公告）日: 2022-02-25
• 發明（設計）人: 廖曉鵑;張輝;黃榮
• 申請（專利權）人: 成都理工大學
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 成都眾恒智合專利代理事務所(普通合伙) 51239
• 代理人: 劉華平

本發明公開了一種求解多處理器過載調度問題最優解的確定性方法，該算法包括步驟(S1)確定調度問題，將調度問題的規則屬性編碼為MaxSAT硬子句；(S2)將調度目標編碼為MaxSAT軟子句；(S3)將步驟(S1)中得到的硬子句和步驟(S2)中得到的軟子句通過合取運算符進行連接，從而得到MaxSAT問題；(S4)通過MaxSAT解算器計算出MaxSAT問題的最優解。通過上述方案，本發明達到了可以求得多處理器調度系統的最優調度方案的目的，具有很強的可擴展性、實用價值和推廣價值。

技術領域

本發明屬于計算機應用技術領域，具體地講，是涉及一種求解多處理器過載調度問題最優解的確定性算法。

背景技術

多處理器上的調度問題長久以來被廣泛研究。自1979年Graham等人將調度問題用α|β|γ的形式來表示處理器屬性、任務屬性、調度目標以來，眾多研究致力于調度問題的復雜度分析，即通過調整調度問題的α、β、γ屬性來分析該問題的復雜度。例如：P|pmtn|∑U_j(并行處理器上的可搶占調度，所有任務同時就緒，目標為最大化截止日期前完成的任務數量)在1983年被證明為NP困難問題。如果任務具有不同的就緒時刻，該問題表示為P|pmtn，r_j|∑U_j，Du等人證明當處理器個數為2時，該問題就已經是NP困難問題。給每個任務賦予不同的權重會進一步加大問題的困難程度，例如：P|pmtn，p_j＝p|∑U_j(并行處理器上的可搶占調度，所有任務同時就緒且任務處理時長相等，目標為最大化截止日期前完成的任務數量)是多項式可解問題，而P|pmtn，p_j＝p|∑w_jU_j(并行處理器上的可搶占調度，所有任務同時就緒且任務處理時長相等，目標為最大化截止日期前完成的任務權重之和)是NP困難問題。由于多處理器調度問題的困難性，目前眾多針對P|pmtn，r_j|∑w_jU_j(并行處理器上的可搶占調度，所有任務就緒時間不同，目標為最大化截止日期前完成的任務權重之和)問題，求解算法僅致力于求出問題的近似解，它們雖然能給出比經典調度算法更有效的調度方案，卻無法確保輸出的近似解能夠穩定接近于最優解。

發明內容

為了克服現有技術中的上述不足，本發明提供一種求解多處理器過載調度問題最優解的確定性算法，根據任務就緒時刻不同，以可搶占的方式進行調度，目標為最大化截止日期前完成的任務權重之和，從而確定調度問題最優解。

為了實現上述目的，本發明采用的技術方案如下：

一種求解多處理器過載調度問題最優解的確定性算法，包括如下步驟：

(S1)確定調度問題，將調度問題的規則屬性編碼為MaxSAT硬子句；

(S2)將調度目標編碼為MaxSAT軟子句；

(S3)將步驟(S1)中得到的硬子句和步驟(S2)中得到的軟子句通過合取運算符進行連接，從而得到MaxSAT問題；

(S4)通過MaxSAT解算器計算出MaxSAT問題的最優解。

進一步地，所述步驟(S1)中規則屬性編碼成與之對應的MaxSAT硬子句應同時滿足以下規則；

規則一：

任何任務分片必須由某個單處理機執行，將這種規則屬性編碼為式(1)所示的硬子句：

其中，是布爾變量，表示任務j的第i個分片f_i^j被安排在處理器M_u上執行；

規則二：