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

Abstract

Abstract 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.