Scheduling one- and two-processor tasks on two parallel processors

Scheduling one- and two-processor tasks on two parallel processors

0.00 Avg rating0 Votes
Article ID: iaor20021167
Country: United States
Volume: 31
Issue: 5
Start Page Number: 445
End Page Number: 455
Publication Date: May 1999
Journal: IIE Transactions
Authors: ,
Abstract:

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-poly-nomial 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.

Reviews

Required fields are marked *. Your email address will not be published.