A Novel General Variable Neighborhood Search through Q-Learning for No-Idle Flowshop Scheduling

Abstract

In this study a novel general variable neighborhood search through Q-learning (GVNS-QL) algorithm is proposed to solve the no-idle flowshop scheduling problem with the makespan objective. In the outer loop of the GVNS-QL insertion and exchange operators are used to shaking the permutation. On the other hand in the inner loop of variable neighborhood descent procedure variable iterated greedy and variable block insertion heuristic algorithms are employed with two effective insertion local search procedures. The proposed GVNS-QL defines the parameters of the algorithm using a Q-learning mechanism. The developed GVNS-QL algorithm is compared with the traditional iterated greedy (IG) algorithm using the well-known benchmark set. The comprehensive computational experiments show that the GVNS-QL outperforms the traditional IG algorithm. The results of the IG and GVNS-QL algorithms are also compared with the current best-known solutions reported in the literature. The computational results show that the proposed GVNS-QL algorithm improves the current best-known solutions for 104 out of 250 instances.