A Q-learning-based hyper-heuristic evolutionary algorithm for the distributed flexible job-shop scheduling problem with crane transportation

With the globalization and sustainable development of the modern manufacturing industry, distributed manufacturing and scheduling systems that consider environmental effects have attracted increasing attention. This article addresses the distributed flexible job-shop scheduling problem with crane transportation (DFJSPC) for minimizing the weighted sum of makespan and total energy consumption. In this study, we present a mixed integer linear programming model for DFJSPC and make a first attempt to propose a Q-learning-based hyper-heuristic evolutionary algorithm (QHHEA) for solving such a strongly NP-hard problem. The QHHEA has the following features: (i) a hybrid population initialization method is designed to produce high-quality individuals with certain diversity; (ii) a novel left-shift decoding scheme is added to the decoding scheme to improve the utilization of machine processing and crane transportation resource; (iii) a Q-learning-based high-level strategy is developed to determine the most suitable low-level heuristic (LLH) from a pre-designed set based on valuable information fed by the efficacy of LLHs; (iv) a new state definition and a dynamic adaptive mechanism are used to balance population convergence and diversity; (v) an improved move acceptance method is adopted to avoid falling into local optima and to drive the search behavior toward promising regions. To evaluate the efficiency and effectiveness of the proposed algorithm, extensive experiments and comprehensive comparisons are conducted on a benchmark with 36 instances. The statistical results show that QHHEA outperforms several state-of-the-art algorithms in solving DFJSPC.