Article ID Journal Published Year Pages File Type
1134265 Computers & Industrial Engineering 2014 12 Pages PDF
Abstract

•A hybrid meta-heuristic search procedure to solve the single machine scheduling problem.•A well-designed balance between two different meta-heuristic procedures are used.•A new set of data instances is used to hybridize and validate the search procedures.

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.

Related Topics
Physical Sciences and Engineering Engineering Industrial and Manufacturing Engineering
Authors
, ,