Heuristic algorithms for scheduling hybrid flow shops with machine blocking and setup times

Abstract

We investigate a new variant of the hybrid flow shop problem (HFSP) considering machine blocking and both sequence-independent and sequence-dependent setup times. Since the HFSP is NP-hard, we propose heuristic algorithms along with priority rules based on the traditional SPT and LPT rules. We carried out computational experiments on simulated problem instances to test the performance of the priority rules. The objective function adopted was makespan minimization, and we used the rate of success and the relative deviation as erformance criteria. The results indicate superiority of LPT-based rules. On instances with sequence-independent setup times, the LP rule, which is based on the non-increasing sorting of total processing times, outperformed other rules in most tested instances. In instances with sequence-dependent setup times, the LPS rule, which is based on the non-increasing sum of processing time and average setup times, outperformed other rules in most tested instances.