A heuristic for scheduling on nonidentical machines to minimize tardy jobs

This paper considers the nonidentical parallel machine scheduling problem in which n jobs having different due dates are to be scheduled on m nonidentical parallel machines. Each job consists of a single operation with different processing times depending on the capability of machines. The objective is to schedule the jobs in such a way that the number of tardy jobs is as small as possible. Among several scheduling objectives, minimizing tardy jobs considered in this paper is more important in a make-to-order manufacturing environment because the penalty cost of a job depends on whether the job is late or not, rather than how late the job is. The proposed algorithm makes use of the concept of assignment problem based on the suitability measure between jobs and machines. A real life industrial application shows that the proposed algorithm is superior to the existing ones for the number of tardy jobs.