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

This paper presents a hybrid meta-heuristic search procedure to solve the well-known single machine scheduling problem to minimize the maximum late- ness over all jobs. Precedence relations may exist between some of the jobs. The hybridization consists of a well-designed balance between the principles borrowed from a electromagnetism-like algorithm and the characteristics used in a tabu search procedure. The electromagnetism-like (EM) algorithm follows a search pattern based on theory of physics to simulate attraction and repulsion of solutions in order to move towards more promising solutions and has been originally proposed by Birbil and Fang (2003). 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 (Glover and Laguna, 1997). 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 set of standard instances is used to compare different elements of the hybrid search procedure and to validate and obtain results that are comparable or even outperform the best known results in literature.