Iterative Improvement Algorithms for the Blocking Job Shop

Angelo Oddi, Riccardo Rasconi, Amedeo Cesta, and Stephen Smith
Proceedings 22nd International Conference on Automated Planning and Scheduling, Atibaia, Sao Paulo, Brazil, June 2012., July, 2012.


Download
  • Adobe portable document format (pdf) (256KB)
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 provides an analysis of the efficacy of a known iterative improvement meta-heuristic approach from the AI area in solving the Blocking Job Shop Scheduling Problem (BJSSP) class of problems. The BJSSP is known to have significant fallouts on practical domains, and differs from the classical Job Shop Scheduling Problem (JSSP) in that it as-sumes that there are no intermediate buffers for storing a job as it moves from one machine to another; according to the BJSSP definition, each job has to wait on a machine until it can be processed on the next machine. In our analysis, two specific variants of the iterative improvement meta-heuristic are evaluated: (1) an adaptation of an existing scheduling algorithm based on the Iterative Flattening Search and (2) an off-the-shelf optimization tool, the IBM ILOG CP Opti-mizer, which implements Self-Adapting Large Neighborhood Search. Both are applied to a reference benchmark problem set and comparative performance results are presented. The results confirm the effectiveness of the iterative improvement approach in solving the BJSSP; both variants perform well individually and together succeed in improving the entire set of benchmark instances.

Notes
Associated Center(s) / Consortia: Center for Integrated Manfacturing Decision Systems
Associated Lab(s) / Group(s): Intelligent Coordination and Logistics Laboratory
Associated Project(s): Partial Order Scheduling Procedures

Text Reference
Angelo Oddi, Riccardo Rasconi, Amedeo Cesta, and Stephen Smith, "Iterative Improvement Algorithms for the Blocking Job Shop," Proceedings 22nd International Conference on Automated Planning and Scheduling, Atibaia, Sao Paulo, Brazil, June 2012., July, 2012.

BibTeX Reference
@inproceedings{Oddi_2012_7050,
   author = "Angelo Oddi and Riccardo Rasconi and Amedeo Cesta and Stephen Smith",
   title = "Iterative Improvement Algorithms for the Blocking Job Shop",
   booktitle = "Proceedings 22nd International Conference on Automated Planning and Scheduling, Atibaia, Sao Paulo, Brazil, June 2012.",
   month = "July",
   year = "2012",
   number= "CMU-RI-TR-",
}