Scheduling one and two-processor tasks on two parallel processors
作者:
CHUNG-YEE LEE,
XIAOQIANG CAI,
期刊:
IIE Transactions
(Taylor Available online 1999)
卷期:
Volume 31,
issue 5
页码: 445-455
ISSN:0740-817X
年代: 1999
DOI:10.1080/07408179908969847
出版商: Taylor & Francis Group
数据来源: Taylor
摘要:
In this paper we study a two-processor scheduling problem where some tasks need to be processed by one processor, while the others have to be processed by both processors simultaneously. The objective is to minimize the total weighted completion time. We first examine the complexity of the problem, showing that it is NP-complete in the strong sense. We then derive optimality properties, and present dynamic programming algorithms, which can find optimal solutions in pseudo-polynomial time. Heuristic methods that can find approximate solutions efficiently are also proposed, and the error bounds of the approximate solutions are established. Finally, a special case is examined and a polynomial algorithm is provided. We show in the Appendix that the problem of minimizing the maximum lateness is also strongly NP-complete and that most of our approaches can be modified to solve this problem.
点击下载:
PDF (962KB)
返 回