周华奇 鲁鸣鸣 朱 洪. 有不同中断时间代价的一致并行抢先调度问题[J]. 计算机研究与发展, 2005, 42(3).
 引用本文: 周华奇 鲁鸣鸣 朱 洪. 有不同中断时间代价的一致并行抢先调度问题[J]. 计算机研究与发展, 2005, 42(3).
Zhou Huaqi, Lu Mingming, and Zhu Hong. A Preemptive Scheduling Problem with Different Interrupted Time Cost on Identical Parallel Machines[J]. Journal of Computer Research and Development, 2005, 42(3).
 Citation: Zhou Huaqi, Lu Mingming, and Zhu Hong. A Preemptive Scheduling Problem with Different Interrupted Time Cost on Identical Parallel Machines[J]. Journal of Computer Research and Development, 2005, 42(3).

## A Preemptive Scheduling Problem with Different Interrupted Time Cost on Identical Parallel Machines

• 摘要: 提出了具有不同中断时间代价的抢先调度问题(P|ptmn(δ\-i)|C\-max).该问题在工程任务分配、分布式计算和网络通信等实际问题中有着广泛的应用背景.首先证明了这个问题是一个NP难优化问题.并给出了一个时间复杂度为O(nlogn)的近似算法，其近似度为5/3. 算法的特点是结合中断时间δ\-i来应用LPT思想，而不只是把它应用到任务i的执行时间p\-i上，从而避免了LPT算法在最坏情形下的近似度差的问题.在算法的关键部分，运用了均分的技巧来提高任务执行的并行性，进一步提高了近似度.

Abstract: A new preemptive scheduling problem P|ptmn(δ\-i)|C\-max is proposed in this paper, in which a preemption penalty δ\-i is introduced if a task is interrupted and resumed later. This problem has numerous applications in task scheduling, distributed computing, and network communication. Firstly, P|ptmn(δ\-i)|C\-max is proved to be an NP-hard optimization problem. Then an LPT algorithm is presented. LPT is relatively succinct and easy to implement. However, the approximation ratio of LPT is unsatisfied. In order to improve the approximation ratio, a new LPT-based algorithm is designed. In this LPT-based algorithm, the technique of LPT is applied to not only the execution time p\-i but also the interrupt time δ\-i, therefore avoiding the worst case of LPT algorithm. In the key part of the LPT-base algorithm, the averaging technique is employed to enhance the parallelism.

/

• 分享
• 用微信扫码二维码

分享至好友和朋友圈