In this paper the authors consider the problem of scheduling n independent jobs on m parallel and identical machines with preemptions. The objective is to minimize the maximum job completion time (or makespan) while meeting all job due-dates. The authors present an algorithm which is able to generate a due-date schedule, if one exists, and to find the minimum makespan. They also discuss the relevance of the number of job preemptions as a performance measure for the class of parallel-machine scheduling problems. Finally, the authors identify some potential areas worthy of further research.
