A hybrid algorithm to minimize total tardiness in cyclic flexible job shop scheduling with assembly stage and sequence-dependent setup time
Volume 13, Issue 1, July 2026, Pages 97-108
https://doi.org/10.22116/jiems.2026.392651.1512
N. Bagheri Rad, Javad Behnamian
Abstract This paper studies a cyclic flexible job shop scheduling problem with assembly operations and sequence-dependent setup time, with the objective of minimizing total tardiness. In this production system, in the first stage, parts are produced in a flexible job shop system, and in the second stage, they are assembled into finished products. In this problem, products must be delivered in predetermined batch sizes within a definite time window. To solve the problem, a mixed-integer linear model is developed. Since the problem is NP-hard, a hybrid genetic algorithm and a parallel variable neighborhood search algorithm are proposed to solve medium- and large-sized instances. The hybrid approach leverages the global search capabilities of the genetic algorithm and the robust local refinement of the parallel variable neighborhood search, ensuring better escape from local optima and improved convergence rates. After fine-tuning the hybrid algorithm using the Taguchi method, the obtained results are compared with those obtained from GAMS and a conventional genetic algorithm on various instances. The computational results show that the proposed hybrid algorithm not only reduces total tardiness more effectively but also offers significant computational efficiency improvements, thereby demonstrating its practical applicability in complex manufacturing scenarios characterized by stringent delivery requirements.
