Minimizing maximum completion time in a two-batch-processing-machine flowshop with dynamic arrivals allowed

Abstract

This paper considers a scheduling problem concerned with a flowshop composed of two batch processing machines where a finite number of jobs arrive dynamically at the first machine of the flowshop. On each batch processing machine, jobs are processed in batch, and each batch is allowed to contain jobs possibly up to the maximum capacity of the associated machine. The objective is to find the optimal batching schedule which minimizes the maximum completion time of all jobs. In the analysis, several solution properties are characterized, based on which an efficient dynamic programming algorithm is developed.