帶時(shí)間懲罰的有向串并聯(lián)圖任務(wù)分配問題

胡淑珂　龐留勇　周向前

摘 要：隨著經(jīng)濟(jì)的快速增長(zhǎng)，很多產(chǎn)品的運(yùn)作生產(chǎn)，往往需要不同的工藝流程。文章考慮了帶有時(shí)間懲罰的有向串并聯(lián)圖最小任務(wù)分配問題和帶有時(shí)間懲罰的有向串并聯(lián)圖最小跨度任務(wù)分配問題，根據(jù)有向串并聯(lián)任務(wù)優(yōu)先圖結(jié)構(gòu)構(gòu)建有向串并聯(lián)分配圖。在此基礎(chǔ)上，文章應(yīng)用時(shí)間復(fù)雜性更小的特殊結(jié)構(gòu)最短路算法以及收縮方法，分別設(shè)計(jì)了兩個(gè)時(shí)間復(fù)雜性為O（nm2k2）的多項(xiàng)式算法來(lái)解決帶時(shí)間懲罰的有向串并聯(lián)圖任務(wù)分配問題，其中n為任務(wù)數(shù)量，m為處理器數(shù)量，k是時(shí)間段限制數(shù)量。

關(guān)鍵詞：有向串并聯(lián)圖；任務(wù)分配；多項(xiàng)式算法；時(shí)間限制懲罰；最小成本；最小跨度

中圖分類號(hào)：O224? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：1673-260X（2023）02-0014-06

3.2 模型構(gòu)建

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

證明：Min-MS-PSA算法區(qū)別于Min-PSA算法的是當(dāng)分支收縮合并為兩層有向結(jié)構(gòu)時(shí)，目標(biāo)是在異構(gòu)多核處理器系統(tǒng)下使得整個(gè)過(guò)程跨度最小，算法將局部收縮的兩層有向結(jié)構(gòu)對(duì)應(yīng)頂點(diǎn)之間的弧權(quán)重置為并行最短路中權(quán)重最大值，最后能夠得到帶有時(shí)間懲罰的有向串并聯(lián)圖最小跨度分配問題的全局最優(yōu)分配解。時(shí)間復(fù)雜性同定理1證明。

4 結(jié)論

本文提出的帶有時(shí)間懲罰的有向串并聯(lián)圖任務(wù)分配問題靜態(tài)Min-PSA算法和Min-MS-PSA算法是通過(guò)逐步獲得局部最優(yōu)解，并收縮合并最后獲得問題的全局最優(yōu)解。Min-PSA算法和Min-MS-PSA算法都是基于并行SHORT算法來(lái)解決帶有時(shí)間懲罰的有向串并聯(lián)圖最小成本分配問題和帶有時(shí)間懲罰的有向串并聯(lián)圖最小跨度分配問題，其時(shí)間復(fù)雜度均為O（nm2k2）。

本文是基于帶有時(shí)間懲罰的有向串并聯(lián)圖結(jié)構(gòu)的基礎(chǔ)上對(duì)任務(wù)分配問題進(jìn)行分配，大大提高任務(wù)執(zhí)行的效率，從而提高生產(chǎn)生活中的效益。同樣適用于無(wú)時(shí)間懲罰的有向串并聯(lián)圖的任務(wù)分配問題，更多特殊結(jié)構(gòu)的任務(wù)分配以及調(diào)度問題值得進(jìn)一步探討。

——————————

參考文獻(xiàn)：

〔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〕劉軼，張昕，李鶴，錢德沛.多核處理器大規(guī)模并行系統(tǒng)中的任務(wù)分配問題及算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2008，29（05）：972-975.

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

〔10〕趙國(guó)亮，李云飛，王川.異構(gòu)多核系統(tǒng)任務(wù)調(diào)度算法研究[J].計(jì)算機(jī)工程與設(shè)計(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

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目（12171193）；河南省高等學(xué)校重點(diǎn)科研項(xiàng)目（23B110012；23B110009；22B110006；21A110015；20B110008）；河南省科技攻關(guān)項(xiàng)目（212102310464）