Problem difficulty for tabu search in job-shop scheduling

Problem difficulty for tabu search in job-shop scheduling

0.00 Avg rating0 Votes
Article ID: iaor2005167
Country: United States
Volume: 143
Issue: 2
Start Page Number: 189
End Page Number: 217
Publication Date: Feb 2003
Journal: Artificial Intelligence
Authors: , , ,
Keywords: tabu search, job shop
Abstract:

Tabu search algorithms are among the most effective approaches for solving the job-shop scheduling problem (JSP), Yet, we have little understanding of why these algorithms work so well, and under what conditions. We develop a model of problem difficulty for tabu search in the JSP, borrowing from similar models developed for SAT and other NP-complete problems. We show that the mean distance between random local optima and the nearest optimal solution is highly correlated with the cost of locating optimal solutions to typical, random JSPs. Additionally, this model accounts for the cost of locating sub-optimal solutions, and provides an explanation for differences in the relative difficulty of square versus rectangular JSPs. We also identify two important limitations of our model. First, model accuracy is inversely correlated with problem difficulty, and is exceptionally poor for rare, very high-cost problem instances. Second, the model is significantly less accurate for structured, non-random JSPs. Our results are also likely to be useful in future research on difficulty models of local search in SAT, as local search cost in both SAT and JSP is largely dictated by the same search space features. Similarly, our research represents the first attempt to quantitatively model the cost of tabu search for any NP-complete problem, and may possibly be leveraged in an effort to understand tabu search in problems other than job-shop scheduling.

Reviews

Required fields are marked *. Your email address will not be published.