Citation
A Dynamic Model of Tabu Search for the Job-Shop Scheduling Problem. In Selected papers from the 1st Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA), pages 247-266, Springer, 2005.
Selected
Abstract
Although tabu search is one of the most effective meta-heuristics for solving the job-shop scheduling problem (JSP), very little is known about why this approach works so well and under what conditions it excels. Our goal is to develop models of tabu search algorithms for the JSP that answer these and other related research questions. We have previously demonstrated that the mean distance between random local optima and the nearest optimal solution, denoted [`(d)]lopt - optdlopt?opt, is highly correlated with problem difficulty for a well-known tabu search algorithm for the JSP introduced by Taillard. In this paper, we discuss various shortcomings of the [`(d)]lopt - optdlopt?optmodel and develop new models of problem difficulty that correct these deficiencies. We show that Taillard's algorithm can be modelled with exceptionally high fidelity using a surprisingly simple Markov chain. The Markov model also enables us to characterise the exact conditions under which different initialisation methods can be expected to improve performance. Finally, we analyse the relationship between the Markov and [`(d)]lopt - optdlopt?opt> models.
There is no pdf available for this paper. You might like to try to obtain the original source (see the doi, for example)
doi
The doi for this publication is 10.1007/0-387-27744-7_12 You can link directly to the original paper, via the doi, from here
What is a doi?: A doi (Document Object Identifier) is a unique identifier for sicientific papers (and occasionally other material). This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi). See http://dx.doi.org/ for more information
URL
This pubication does not have a URL associated with it.
The URL is only provided if there is additional information that might be useful. For example, where the entry is a book chapter, the URL might link to the book itself.
Bibtex
@INBOOK{2005-247-266-SI, chapter = {Selected papers from the 1st Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA)},
pages = {247--266},
title = {A Dynamic Model of Tabu Search for the Job-Shop Scheduling Problem},
publisher = {Springer},
year = {2005},
editor = {G. Kendall and E. Burke and S. Petrovic and M. Gendreau},
author = {J-P. Watson and L. D. Whitley and A. E. Howe},
note = {Selected},
abstract = {Although tabu search is one of the most effective meta-heuristics for solving the job-shop scheduling problem (JSP), very little is known about why this approach works so well and under what conditions it excels. Our goal is to develop models of tabu search algorithms for the JSP that answer these and other related research questions. We have previously demonstrated that the mean distance between random local optima and the nearest optimal solution, denoted [`(d)]lopt - optdlopt?opt, is highly correlated with problem difficulty for a well-known tabu search algorithm for the JSP introduced by Taillard. In this paper, we discuss various shortcomings of the [`(d)]lopt - optdlopt?optmodel and develop new models of problem difficulty that correct these deficiencies. We show that Taillard's algorithm can be modelled with exceptionally high fidelity using a surprisingly simple Markov chain. The Markov model also enables us to characterise the exact conditions under which different initialisation methods can be expected to improve performance. Finally, we analyse the relationship between the Markov and [`(d)]lopt - optdlopt?opt> models.},
doi = {10.1007/0-387-27744-7_12},
owner = {gxk},
timestamp = {2012.05.29} }