Scheduling one and two-processor tasks on two parallel processors

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