The Robotics Institute

Carnegie Mellon Robotics Institute

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 eectiveness 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-",
}

The Robotics Institute

Menu