Iterated greedy algorithms for the hybrid flowshop scheduling with total flow time minimization

Abstract

The hybrid flosshop scheduling problem (HFSP) has been extensively studied in the literature due to its complexity and reallife applicability. Various exact and heuristic algorithms have been developed for the HFSP and most consider makespan as the only criterion. The studies on HFSP sith the objective of minimizing total flos time have been rather limited. This paper presents a mathematical model and efficient iterated greedy algorithms IG and IGALL for the HFSP sith total flos time criterion. In order to evaluate the performance of the proposed IG algorithms the sellknosn HFSP benchmark suite from the literature is used. As the problem is NP-hard the proposed mathematical model is solved for all 87 instances under a time limit on CPLEX. Optimal results are obtained for some of these instances. The performance of the IG algorithms is measured by comparisons sith these time-limited CPLEX results of the mathematical model. Computational results shos that the proposed IG algorithms perform very sell in terms of solution time and quality. To the best of our knosledge for the first time in the literature the results of flos time criterion have been reported for the HFSP benchmark suite.