A Hybrid NSGA-II and VNS for Solving a Bi-objective No-wait Flexible Flowshop Scheduling Problem


We address the no-wait k-stage flexible flowshop scheduling problem where there are m identical machines at each stage. The objectives are to schedule the available n jobs so that makespan and mean tardiness of n jobs are minimized. Sequence-dependent setup times are treated in this problem as one of the prominent practical assumptions. This problem is NP-hard, and therefore we present a new multiobjective approach for solving the mentioned problem. The proposed meta-heuristic is evaluated based on randomly generated data in comparison with two well-known multiobjective algorithm including NSGA-II and SPEA-II. Due to sensitivity of our proposed algorithm to parameter values, a new approach for tackling of this issue was designed. Our proposed method includes Taguchi method (TM) and multiobjective decision making (MODM). We have chosen six measures into two groups. Qualitative metrics including number of Pareto solutions (NPS), diversity metric (DM) as well as the spread of non-dominance solution (SNS) and quantitative metrics including the rate of achievement to two objectives simultaneously (RAS), mean ideal distance (MID) and quality metric (QM) to evaluate the performance of our proposed algorithms. Computational experiments and comparisons show that the proposed NSGA-II + VNS algorithm generates better or competitive results than the existing NSGA-II and SPEA-II for the no-wait flexible flow shop scheduling problem with sequence-dependent setup times to simultaneous minimizing the makespan and mean tardiness criterion.