AAAI Publications, Sixth European Conference on Planning

Font Size: 
Toward an Understanding of Local Search Cost in Job-Shop Scheduling
Jean-Paul Watson, Chris Beck, Adele Howe, Darrell Whitley

Last modified: 2014-05-21


Local search algorithms are among the most effective approaches for solving the JSP, yet we have little understanding of why these algorithm work so well, and under what conditions. We develop descriptive cost models of local search for the job-shop scheduling problem (JSP), borrowing from the models developed for MAX-SAT. We show that several factors known to influence the difficulty of local search in MAX-SAT directly carry over to the general JSP, including the number of optimal solutions, backbone size, the distance between initial solutions and the nearest optimal solution, and an analog of backbone robustness. However, these same factors only weakly influence local search cost in JSPs with workflow, which possess structured constraints. While the factors present in the MAX-SAT cost models provide an accurate description of local search cost in the general JSP, our results for workflow JSPs raise concerns regarding the applicability of cost models derived using random problems to those exhibiting specific structure.


job shop scheduling; local search; empirical algorithm models

Full Text: PDF