Iterative Improvement Algorithms for the Blocking Job Shop

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.