Minimizing the number of tardy jobs for m parallel machines

The importance of the criterion of number of the tardy jobs has been well recognized in the literature, but there is no efficient heuristic to minimize this objective in the parallel machine case. This paper proposes two fundamental approaches, job-focused and machine-focused, to minimize the number of tardy jobs in the parallel processors. The machine-focused approach heuristic is an important extension of Moore's (also called Hodgson's) algorithm to solve the number of tardy jobs problem for the one-machine case. An extensive simulation experiment is conducted to test the effectiveness of the heuristics, and shows that three of the proposed heuristics (two heuristics from the job-focused approach and the machine-focused heuristic) perform very well. We also compare the heuristic solutions with the optimal solution for 800 small problems so as to access the average deviation above the optimum. The simulation results show that the best heuristic is about 1.2% of the optimum.