A Q-learning based hyper-heuristic scheduling algorithm with multi-rule selection for sub-assembly in shipbuilding

Sub-assembly is the basic stage of ship hull construction. It is necessary to optimize the scheduling of subassembly to shorten its assembly cycle and ensure the normal execution of subsequent processes. The scheduling problem of sub-assembly is an NP-hard problem that should take into consideration both spatial layout and temporal schedule. In this work, a mathematical model for scheduling the sub-assembly is established, and a Qlearning based hyper-heuristic with multi-spatial layout rule selection is proposed. Specifically, a spatial layout method based on multi-rule selection is proposed first. In various scenarios, distinct spatial layout rules are chosen to derive an appropriate spatial arrangement. Subsequently, a hyper-heuristic algorithm based on Qlearning is crafted to optimize the scheduling sequence and the selection of spatial layout rules. As a verification, numerical experiments are carried out in cases of different scales collected from a large shipyard. The effectiveness of the proposed algorithm is verified by comparing it with different spatial layout algorithms, various heuristic operators, existing well-known hyper-heuristic methods, and other Q-learning based scheduling methods. The results suggest that the proposed algorithm outperforms other comparison algorithms in most testing cases.