Batching and Scheduling Jobs on Batch and Discrete Processors

Abstract

We consider a situation in which the manufacturing system is equipped with batch and discrete processors. Each batch processor can process a batch (limited number) of jobs simultaneously. Once the process begins, no job can be released from the batch processor until the entire batch is processed. In this paper, we analyze a class of two-machine batching and scheduling problems in which the batch processor plays an important role. Specifically, we consider two performance measures: the makespan and the sum of job completion times. We analyze the complexity of this class of problems, present polynomial procedures for some problems, propose a heuristic, and establish an upper bound on the worst case performance ratio of the heuristic for the NP-complete problem. In addition, we extend our analysis to the case of multiple families and to the case of three-machine batching.