Article ID: | iaor2008727 |
Country: | United Kingdom |
Volume: | 8 |
Issue: | 5 |
Start Page Number: | 453 |
End Page Number: | 460 |
Publication Date: | Oct 2005 |
Journal: | Journal of Scheduling |
Authors: | Vlach Milan, Sung Shao Chin |
We are concerned with problems of scheduling jobs non-preemptively with the objective to maximize the weighted number of jobs that are completed exactly at their due dates. It has been shown that the problems for single machine and identical parallel machines are polynomial time solvable. The purpose of this paper is to establish the complexity status of the problem for unrelated parallel machine, which was left open. First, we present a polynomial time algorithm for solving the problem when the number of machine is fixed. Second, we show that when the number of machine is a part of input, the problem becomes NP-hard in the strong sense.