Iterative Improvement Algorithms for the Blocking Job Shop - Robotics Institute Carnegie Mellon University

Iterative Improvement Algorithms for the Blocking Job Shop

Angelo Oddi, Riccardo Rasconi, Amedeo Cesta, and Stephen Smith
Conference Paper, Proceedings of 22nd International Conference on Automated Planning and Scheduling (ICAPS '12), pp. 199 - 206, June, 2012

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 assumes 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 Optimizer, 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.

BibTeX

@conference{Oddi-2012-7504,
author = {Angelo Oddi and Riccardo Rasconi and Amedeo Cesta and Stephen Smith},
title = {Iterative Improvement Algorithms for the Blocking Job Shop},
booktitle = {Proceedings of 22nd International Conference on Automated Planning and Scheduling (ICAPS '12)},
year = {2012},
month = {June},
pages = {199 - 206},
}