带时间惩罚的有向串并联图任务分配问题

胡淑珂　庞留勇　周向前

摘 要：随着经济的快速增长，很多产品的运作生产，往往需要不同的工艺流程。文章考虑了带有时间惩罚的有向串并联图最小任务分配问题和带有时间惩罚的有向串并联图最小跨度任务分配问题，根据有向串并联任务优先图结构构建有向串并联分配图。在此基础上，文章应用时间复杂性更小的特殊结构最短路算法以及收缩方法，分别设计了两个时间复杂性为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）