A hybrid heuristic approach to minimize number of tardy jobs in group technology systems

We consider the problem of scheduling jobs on a single machine in a group technology (GT) system with the objective of minimizing the number of tardy jobs without preemption. In this system, we group jobs into families such that jobs within a family have similar processing requirements. Hence, no scheduled setup exists between any two jobs of the same family. However, a sequence-independent setup time occurs between families. The problem is of practical interest for industries such as plastic manufacturing and metal drawing operations, which often employ a GT setup. This problem has been discussed in the academic literature and shown to be NP-hard. However, no solution methods have been proposed in the literature. To solve this NP-hard problem, we develop a hybrid heuristic based on greedy randomized adaptive search procedure (GRASP) and particle swarm optimization (PSO) meta-heuristics. We conduct extensive experiments with respect to problem size and parameter settings. We benchmark the performance of the hybrid heuristic with a simple GRASP application as well as with optimal solutions. Overall, results show the hybrid heuristic performs very well, finding optimal solutions for 63% of the problem instances.