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

V. Sels () and Mario Vanhoucke

Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium from Ghent University, Faculty of Economics and Business Administration

Abstract: 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.

Pages: 2 pages
Date: 2011-04
New Economics Papers: this item is included in nep-cmp
References: Add references at CitEc
Citations:

Downloads: (external link)
http://wps-feb.ugent.be/Papers/wp_11_716.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:rug:rugwps:11/716

Access Statistics for this paper

More papers in Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium from Ghent University, Faculty of Economics and Business Administration Contact information at EDIRC.
Bibliographic data for series maintained by Nathalie Verhaeghe ().