A Problem Reduction and Decomposition Approach for Scheduling for a Flowshop of Batch Processing Machines

Abstract

This paper considers a scheduling problem for a multi-stage flowshop of batch processing machines (BPM) where each BPM can process a batch of jobs simultaneously so that all jobs contained in each batch are released together to the next machine after their processing. With respect to any regular measure of performance, several solution properties are characterized to exploit a problem reduction procedure (PRP) for removing dominated machines. The reduction procedure is incorporated into two efficient heuristic solution algorithms for minimizing two corresponding regular measures of performance including 'makespan' and 'sum of completion times'. Several numerical experiments show that the proposed reduction procedure contributes to remove many non-bottleneck machines for the two heuristics to generate good schedules. (C) 2000 Elsevier Science B.V. All rights reserved.