A hybrid electromagnetism-like mechanism/tabu search procedure for the single machine scheduling problem with a maximum lateness objective

Abstract

This paper presents a hybrid meta-heuristic search procedure to solve the well-known single machine scheduling problem to minimize the maximum lateness over all jobs, where precedence relations may exist between some of the jobs. The hybridization consists of a well-designed balance between the principles borrowed from an Electromagnetism-like Mechanism algorithm and the characteristics used in a tabu search procedure. The Electromagnetism-like Mechanism (EM) algorithm follows a search pattern based on the theory of physics to simulate attraction and repulsion of solutions in order to move towards more promising solutions. The well-known tabu search enhances the performance of a local search method by using memory structures by prohibiting visited solutions during a certain time of the search process. The hybridization of both algorithms results in an important trade-off between intensification and diversification strategies. These strategies will be discussed in detail. To that purpose, a new set of data instances is used to compare different elements of the hybrid search procedure and to validate the performance of the algorithm.