Scheduling on Parallel Machines to Minimize Two Criteria Related to Job Tardiness

This paper deals with the scheduling of independent, nonpreemptible jobs with due dates on parallel machines. The machines are allowed to have different rates of operation, though a special algorithm is developed for the case in which they are all identical. The principal objective treated is minimizing the number of processors required to meet all due date constraints; in addition, it is shown that the solution methods for this first problem may be used to minimize maximum tardiness on a fixed number of machines. A lower bound on the number of machines required is developed, and several approximation algorithms are presented. Two enumerative optimization algorithms are developed. Computational results are presented for the case of identical machines.