Iterative Improvement Algorithms for the Blocking Job Shop

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.

Publication type: 
Contributo in atti di convegno
Author or Creator: 
Oddi, Angelo
Rasconi, Riccardo
Cesta, Amedeo
Smith, Stephen F.
AAAI Press, Menlo Park [CA], USA
Twenty-Second International Conference on Automated Planning and Scheduling, 2012, pp. 199–206, Atibaia, São Paulo, Brazil, 25-29 June 2012
Resource Identifier:
ISTC Author: 
Angelo Oddi's picture
Real name: 
Riccardo Rasconi's picture
Real name: 
Amedeo Cesta's picture
Real name: