A fast neighborhood search scheme for identical parallel machine scheduling problems under general learning curves

There is a limited number of results concerning fast and efficient solution algorithms for scheduling problems with general learning models. Therefore, we develop a fast insert neighborhood search (FINS) for a group of identical parallel machine scheduling problems with general learning curves under the following minimization objectives: the maximum completion time (makespan) and the maximum lateness. Our fast search scheme allows to calculate criterion values in a constant time per solution in a neighborhood. The application is presented on the basis of Nawaz-Enscore-Ham's method (NEH), iterative local search, tabu search, particle swarm optimization and hybrid simulated annealing - tabu search algorithms, where the efficiency of their standard implementations are compared to their versions enhanced by our fast insert neighborhood search. The computational experiments confirm the theoretical analysis that our method essentially overwhelms the well known approaches. The metaheuristics augmented by our FINS are about 120 times faster than their standard versions and improve the criterion values by up to 25% for analyzed instances with 100-800 jobs and 5-80 machines. (C) 2021 Elsevier B.V. All rights reserved.

Automated summary

This study introduces a fast insert neighborhood search (FINS) for scheduling problems with general learning curves, which significantly outperforms traditional methods. Comparing to other algorithms, the FINS method is 120 times faster and improves criterion values by up to 25% for instances with 100-800 jobs and 5-80 machines.