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: | Lee Chae Y., Cai X.Q. |
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.