Colorado State University
Empirical modeling and analysis of local search algorithms for the job-shop scheduling problem.
Degree: PhD, Computer Science, 2003, Colorado State University
Local search algorithms are among the most effective approaches for locating high-quality solutions to a wide range of combinatorial optimization problems. However, our theoretical understanding of these algorithms is very limited, leading to significant problems for both researchers and practitioners. Specifically, the lack of a theory of local search impedes the development of more effective algorithms, prevents practitioners from identifying the algorithm most appropriate for a given problem, and allows widespread conjecture and misinformation regarding the benefits and/or drawbacks of particular algorithms. This thesis represents a significant step toward a theory of local search. Using empirical methods, we develop theoretical models of the behavior of four well-known local search algorithms: a random walk, tabu search, iterated local search, and simulated annealing. The analysis proceeds in the context of the well-known job-shop scheduling problem, one of the most difficult NP-hard problems encountered in practice. The large volume of prior research on the job-shop scheduling problem provides a diverse range of available algorithms and problem instances, in addition to numerous empirical observations regarding local search algorithm behavior; the latter are used to validate our behavioral models. We show that all four local search algorithms can be modeled with high fidelity using straightforward variations of a generalized one-dimensional Markov chain. The states in these models represent sets of solutions a given fixed distance from the nearest optimal solution. The transition probabilities in all of the models are remarkably similar, in that search is consistently biased toward solutions that are roughly equidistant from the nearest optimal solution and solutions that are maximally distant from the nearest optimal solution. Surprisingly, the qualitative form of the transition probabilities is simply due to the structure of the representation used to encode solutions: the binary hypercube. The models account for between 96% and 99% of the variability in the cost required to locate both optimal and sub-optimal solutions to a wide range of problem instances, and provide explanations for numerous phenomena related to problem difficulty for local search in the job-shop scheduling problem. In the course of our analysis, we also disprove many conjectures regarding the behavior and benefits of particular algorithms. Our research indicates that despite their effectiveness, local search algorithms for the job-shop scheduling problem exhibit surprisingly simple run-time dynamics. Further, we observe minimal differences between the dynamical behavior of different algorithms. As expected given similar run-time dynamics, although contrary to numerous reports appearing in the literature, we also show that the performance of different algorithms is largely indistinguishable. Ultimately, our behavioral models serve to unify and provide explanations for a large body of observations regarding problem difficulty for local…
Advisors/Committee Members: Howe, Adele E. (advisor), Whitley, L. Darrell (advisor), Chong, Edwin Kah Pin (committee member), Bohm, Anton Willem (committee member).
Subjects/Keywords: random walk; tabu search; job-shop scheduling problem; empirical methods; local search algorithms; iterated local search; simulated annealing; Production scheduling – Computer simulation
to Zotero / EndNote / Reference
APA (6th Edition):
Watson, J. (2003). Empirical modeling and analysis of local search algorithms for the job-shop scheduling problem. (Doctoral Dissertation). Colorado State University. Retrieved from http://hdl.handle.net/10217/26811
Chicago Manual of Style (16th Edition):
Watson, Jean-Paul. “Empirical modeling and analysis of local search algorithms for the job-shop scheduling problem.” 2003. Doctoral Dissertation, Colorado State University. Accessed March 09, 2021.
MLA Handbook (7th Edition):
Watson, Jean-Paul. “Empirical modeling and analysis of local search algorithms for the job-shop scheduling problem.” 2003. Web. 09 Mar 2021.
Watson J. Empirical modeling and analysis of local search algorithms for the job-shop scheduling problem. [Internet] [Doctoral dissertation]. Colorado State University; 2003. [cited 2021 Mar 09].
Available from: http://hdl.handle.net/10217/26811.
Council of Science Editors:
Watson J. Empirical modeling and analysis of local search algorithms for the job-shop scheduling problem. [Doctoral Dissertation]. Colorado State University; 2003. Available from: http://hdl.handle.net/10217/26811