帶時間懲罰的有向串并聯圖任務分配問題

胡淑珂　龐留勇　周向前

摘 要：隨著經濟的快速增長，很多產品的運作生產，往往需要不同的工藝流程。文章考慮了帶有時間懲罰的有向串并聯圖最小任務分配問題和帶有時間懲罰的有向串并聯圖最小跨度任務分配問題，根據有向串并聯任務優先圖結構構建有向串并聯分配圖。在此基礎上，文章應用時間復雜性更小的特殊結構最短路算法以及收縮方法，分別設計了兩個時間復雜性為O（nm2k2）的多項式算法來解決帶時間懲罰的有向串并聯圖任務分配問題，其中n為任務數量，m為處理器數量，k是時間段限制數量。

關鍵詞：有向串并聯圖；任務分配；多項式算法；時間限制懲罰；最小成本；最小跨度

中圖分類號：O224? 文獻標識碼：A? 文章編號：1673-260X（2023）02-0014-06

3.2 模型構建

定理2：Min-MS-PSA算法是帶有時間懲罰的有向串并聯圖最小跨度分配問題的一個精確算法，其時間復雜性為O（nm2k2），n為任務數量，m為處理器數量，k為時間段限制數量。

證明：Min-MS-PSA算法區別于Min-PSA算法的是當分支收縮合并為兩層有向結構時，目標是在異構多核處理器系統下使得整個過程跨度最小，算法將局部收縮的兩層有向結構對應頂點之間的弧權重置為并行最短路中權重最大值，最后能夠得到帶有時間懲罰的有向串并聯圖最小跨度分配問題的全局最優分配解。時間復雜性同定理1證明。

4 結論

本文提出的帶有時間懲罰的有向串并聯圖任務分配問題靜態Min-PSA算法和Min-MS-PSA算法是通過逐步獲得局部最優解，并收縮合并最后獲得問題的全局最優解。Min-PSA算法和Min-MS-PSA算法都是基于并行SHORT算法來解決帶有時間懲罰的有向串并聯圖最小成本分配問題和帶有時間懲罰的有向串并聯圖最小跨度分配問題，其時間復雜度均為O（nm2k2）。

本文是基于帶有時間懲罰的有向串并聯圖結構的基礎上對任務分配問題進行分配，大大提高任務執行的效率，從而提高生產生活中的效益。同樣適用于無時間懲罰的有向串并聯圖的任務分配問題，更多特殊結構的任務分配以及調度問題值得進一步探討。

——————————

參考文獻：

〔1〕H.S. Stone. Multiprocessor scheduling with the aid of network flow algorithms[J]. IEEE Transactions on Software Engineering， 1977， 3（01）： 85-93.

〔2〕V. M. Lo. Heuristic algorithms for task assignment in distributed systems[J]. IEEE Transactions on Computers， 1988，37（11）： 1384-1397.

〔3〕S.H. Bokhari. On the mapping problem[J]. IEEE Transactions on Computers，1981， 30（03）：207-214.

〔4〕D. Fernandez-Baca. Allocating modules to processors in a distributed system[J]. IEEE Transactions on Software Engineering， 1989， 15（11）： 1427-1436.

〔5〕S.H. Bokhari. A shortest tree algorithm for optimal assignments across space and time in a distributed processor system[J]. IEEE Transactions on Software Engineering， 1981， 7（06）： 583-589.

〔6〕Alain Billionnet. Allocating Tree Structured Programs in a Distributed System with Uniform Communication Costs.[J]. IEEE Trans. Parallel Distrib. Syst.，1994，5（04）： 445-448.

〔7〕D. Towsley. Allocating programs containing branches and loops within a multiple processor system[J]. IEEE Transactions on Software Engineering， 1986， 12（10）： 1018-1024.

〔8〕劉軼，張昕，李鶴，錢德沛.多核處理器大規模并行系統中的任務分配問題及算法[J].小型微型計算機系統，2008，29（05）：972-975.

〔9〕S.H. Bokhari. Assignment Problems in Parallel and Distributed Computing[M]. Boston： Kluwer Academic Publishers， 1987.

〔10〕趙國亮，李云飛，王川.異構多核系統任務調度算法研究[J].計算機工程與設計，2014，35（09）：3099-3106.

〔11〕Q. Zhuge， C. Xue， E.H.M. Sha. Efficient assignment and scheduling for heterogeneous DSP systems[J]. IEEE Transactions on Parallel and Distributed Systems： A Publication of the IEEE Computer Society， 2005， 16（06）： 516-525.

〔12〕Jacobo Valdes，Robert E. Tarjan，Eugene L. Lawler. The Recognition of Series Parallel Digraphs[J]. SIAM Journal on Computing，1982，11（02）： 298-313.

收稿日期：2022-09-15

基金項目：國家自然科學基金項目（12171193）；河南省高等學校重點科研項目（23B110012；23B110009；22B110006；21A110015；20B110008）；河南省科技攻關項目（212102310464）