A fast local search for the identical parallel machine scheduling problem with the position-based deteriorating effect and maintenance

In this paper, we develop a fast local search for the identical parallel machine scheduling problem with maintenance activities and the position-based deteriorating under the maximum lateness minimization. Our approach allows us to calculate criterion values in a constant time per solution in a neighbourhood. The application is given on the basis of the Nawaz-Ensore-Ham method, iterative local search, tabu search, and a family of memetic search algorithms, where their efficiency equipped with our method is compared with their classical versions. The computational experiments confirm the theoretical analysis that our approach essentially overwhelms the typical implementation and speeds up the related algorithms over 200 times for reasonable problem sizes. Thereby it allows us to search for significantly larger solution space at the same time and, therefore, radically improve the criterion values of the obtained solutions.