A Dynamic Model of Tabu Search for the Job-Shop Scheduling Problem

Jean-Paul Watson (), L. Darrell Whitley () and Adele E. Howe ()
Additional contact information
Jean-Paul Watson: Sandia National Laboratories
L. Darrell Whitley: Colorado State University
Adele E. Howe: Colorado State University

A chapter in Multidisciplinary Scheduling: Theory and Applications, 2005, pp 247-266 from Springer

Abstract: 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 $$\bar d_{lopt - 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 $$\bar d_{lopt - opt} $$ model 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 $$\bar d_{lopt - opt} $$ > models.

Keywords: tabu search; job-shop; scheduling (search for similar items in EconPapers)
Date: 2005
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:sprchp:978-0-387-27744-8_12

Ordering information: This item can be ordered from
http://www.springer.com/9780387277448

DOI: 10.1007/0-387-27744-7_12

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().