Exploiting Iterative Flattening Search to Solve Job Shop Scheduling Problems with Setup Times
Abstract
This paper presents a heuristic algorithm for solving a jobshop scheduling problem with sequence dependent setup times (SDST-JSSP). This strategy, known as Iterative Flattening Search (IFS), iteratively applies two steps: (1) a relaxation-step, in which a subset of scheduling decisions are randomly retracted from the current solution; and (2) a solving-step, in which a new solution is incrementally recomputed from this partial schedule. The algorithm relies on a core constraint-based search procedure, which generates consistent orderings of activities that require the same resource by incrementally imposing precedence constraints on a temporally feasible solution. Key to the effectiveness of the search procedure is a conflict sampling method biased toward selection of the most critical conflicts. The efficacy of the overall heuristic optimization algorithm is demonstrated empirically on a set of well known SDST-JSSP benchmarks.
BibTeX
@workshop{Oddi-2010-120513,author = {A. Oddi and R. Rasconi and A. Cesta and S. F. Smith},
title = {Exploiting Iterative Flattening Search to Solve Job Shop Scheduling Problems with Setup Times},
booktitle = {Proceedings of 28th Workshop of the UK Planning and Scheduling Special Interest Group - organized jointly with 4th Italian Workshop on Planning and Scheduling},
year = {2010},
month = {December},
}