Solving Job Shop Scheduling with Setup Times through Constraint-based Iterative Sampling: An Experimental Analysis

Angelo Oddi, Riccardo Rasconi, Amedeo Cesta, and Stephen Smith
Annals of Mathematics and Artificial Intelligence, 62:371-402, August 2011. , August, 2011.


Download
  • Adobe portable document format (pdf) (769KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
This paper presents a heuristic algorithm for solving a job-shop scheduling problem with sequence dependent setup times and min/max separation constraints among the activities (SDST-JSSP/max ). 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 e ectiveness of the search procedure is a con ict sam-pling method biased toward selection of most critical con icts and coupled with a non-deterministic choice heuristic to guide the base con ict resolution process. This constraint-based search is then embedded within a larger iterative-sampling search framework to broaden search space coverage and promote solution optimization. The ecacy of the overall heuristic algorithm is demonstrated empirically both on a set of previously studied job-shop scheduling benchmark problems with sequence depen-dent setup times and by introducing a new benchmark with setups and generalized precedence constraints.

Keywords
random-restart, constraint-based reasoning, job-shop scheduling, setup times, generalized precedence constraints

Notes

Text Reference
Angelo Oddi, Riccardo Rasconi, Amedeo Cesta, and Stephen Smith, "Solving Job Shop Scheduling with Setup Times through Constraint-based Iterative Sampling: An Experimental Analysis," Annals of Mathematics and Artificial Intelligence, 62:371-402, August 2011. , August, 2011.

BibTeX Reference
@inproceedings{Oddi_2011_7051,
   author = "Angelo Oddi and Riccardo Rasconi and Amedeo Cesta and Stephen Smith",
   title = "Solving Job Shop Scheduling with Setup Times through Constraint-based Iterative Sampling: An Experimental Analysis",
   booktitle = "Annals of Mathematics and Artificial Intelligence, 62:371-402, August 2011. ",
   month = "August",
   year = "2011",
   number= "CMU-RI-TR-",
}