December
2010
Exploiting Iterative Flattening Search to Solve Job Shop Scheduling Problems with Setup Times
Authors:
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.
copied = false, 2000);
">
@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},
}
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},
}