Scheduling with two job classes and setup times to minimize the number of tardy jobs

This paper considers the problem of minimizing the number of tardy jobs to be processed on a single machine with two job classes where a job’s setup time depends on its job classes. This is an increasingly important problem due to the growing popularity of group technology manufacturing techniques, where jobs are divided into job classes (families). Using the optimal properties of Moore’s algorithm, two approximate algorithms are developed and illustrated with an example. A simulation study conducted to examine the effectiveness of the proposed algorithms shows that the proposed algorithms perform significantly better than Moore’s algorithm and its extension.