Batching and scheduling jobs on batch and discrete processors

The authors 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, the authors analyze a class of two-machine batching and scheduling problems in which the batch processor plays an important role. Specifically, they consider two performance measures: the makespan and the sum of job completion times. The authors 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, they extend their analysis to the case of multiple families and to the case of three-machine batching.