Integrating sequence-dependent setup times and blocking in hybrid flow shop scheduling to minimize total tardiness

This study addresses the minimization of total tardiness in a hybrid flow shop scheduling problem with sequence-dependent setup times and blocking constraints. Each production stage includes multiple machines, and there are no buffers between the stages. The setup time required to process a job depends on the previously processed job. Two mixed-integer linear programming models are developed to formulate the problem. Moreover, an iterative local search algorithm and hybrid genetic algorithms are proposed to have quality solutions with minimal computational efforts. Several computational tests are conducted to tune the heuristic parameters for better performance. Computational experiments are carried out to evaluate the performance of solution methodologies in terms of quality and time. The results indicate that while mixed-integer programming models can solve small-size problem instances, they are not capable of solving large-sized instances. However, the proposed heuristic algorithms find quality solutions for all instances in a very short time.