Hybrid meta-heuristic solving no-wait flow shop scheduling minimizing maximum tardiness
摘要
The non-waiting constraint is a crucial factor in industries with continuous production flows. Recognizing the significance of this constraint in the manufacturing process, we propose several approaches to minimize the maximum tardiness in the no-wait manufacturing flow shop scheduling problem. This research presents two main approaches: an exact method that utilizes mixed integer linear programming and an approximate method based on constructive heuristics and hybrid meta-heuristics. To tackle the problem, we introduce multiple heuristics and hybrid improved meta-heuristics based Nawaz Enscore Ham, greedy randomized adaptive search procedure and genetic algorithm. Furthermore, we propose three hybrid meta-heuristics based on the simulated annealing approach. To validate the effectiveness and robustness of our methods, we conducted experiments on multiple instances of the flow shop problem proposed by Taillard. The results demonstrate that the hybrid algorithm, which combines a greedy randomized adaptive search procedure with the insertion procedure and simulated annealing, exhibits strong performance. In fact, this algorithm achieved a success rate of