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

有效

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

1.一種求解多處理器過載調度問題最優(yōu)解的確定性方法，其特征在于，包括如下步驟：

(S1)確定調度問題，將調度問題的規(guī)則屬性編碼為MaxSAT硬子句；其中，規(guī)則屬性編碼成與之對應的MaxSAT硬子句應同時滿足以下規(guī)則；

規(guī)則一：

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

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

規(guī)則二：

當任務i的第k個分片和任務j的第l個分片f_l^j存在占用同一臺處理機，且它們的執(zhí)行時間段重疊時，存在先于f_l^j執(zhí)行，或者f_l^j先于執(zhí)行，將這種規(guī)則屬性編碼為式(2)所示的硬子句：

其中，是布爾變量，表示任務i的第k個分片被安排在處理器M_u上執(zhí)行，是布爾變量，表示任務i的第k個分片先于任務j的第l個分片f_l^j執(zhí)行，是布爾變量，表示任務j的第l個分片先于任務i的第k個分片執(zhí)行；

規(guī)則三：

任務j的第i個分片的開始時刻不早于在它之前的所有任務分片的完成時刻，將這種規(guī)則屬性編碼為式(3)所示的硬子句：

其中，是布爾變量，表示任務j的第i個分片在t或t時刻之后開始執(zhí)行，p_j是任務j的執(zhí)行時長，由于任務在執(zhí)行過程中的任意單位時間間隙都可以被搶占，因此p_j也表示了任務j的分片數量及該任務最后一個分片的序號，r_j是任務j的就緒時刻，n是系統(tǒng)任務總數；

規(guī)則四：

任務j的第i個分片先于任務j的第i+1個分片執(zhí)行，將這種規(guī)則屬性編碼為式(4)所示的硬子句：

其中，是布爾變量，表示任務j的第i個分片先于任務j的第i+1個分片執(zhí)行；

規(guī)則五：

當任務分片f_i^j開始于時刻t或t之后，則它一定開始于t-1或t-1之后，將這種規(guī)則屬性編碼為式(5)所示的硬子句：

其中，是布爾變量，表示任務j的第i個分片在t或t時刻之后開始執(zhí)行，是布爾變量，表示任務j的第i個分片在t-1或t-1時刻之后開始執(zhí)行；

規(guī)則六：

當一個任務結束于t，則它的最后一個分片一定開始于時刻t-1或之前，將這種規(guī)則屬性編碼為式(6)所示的硬子句：

其中，eb_j是布爾變量，表示任務j在它的截止時刻之前完成，是布爾變量，表示任務j的第p_j個分片在t或t時刻之后開始執(zhí)行；

規(guī)則七：

對于所述規(guī)則二和規(guī)則四中出現(xiàn)過的布爾變量將其生成式(7)所示的硬子句：

其中，t和t′分別應當滿足，r_i+k(k-1)/2≤t≤d_i-(k+p_i)(p_i-k+1)/2+1，

其中，r_j是任務j的就緒時刻，d_j是任務j的截止時刻；

(S2)將調度目標編碼為MaxSAT軟子句；其中，調度目標最大化在截止時刻前完成的任務權重之和，將該調度目標編碼為式(8)所示的MaxSAT帶權軟子句：

(eb_j，W_j)(1≤j≤n) (8)

其中，W_j表示完成任務j所獲得的收益；

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

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