Scheduling batches with simultaneous job processing for two-machine shop problems

We consider the problem of scheduling independent jobs on two machines in a n open shop, a job shop and a flow shop environment. Both machines are batc hing machines, which means that several operations can be combined into a b atch and processed simultaneously on a machine. The batch processing time i s the maximum processing time of operations in the batch, and all operation s in a batch complete at the same time. Such a situation may occur, for ins tance, during the final testing stage of circuit board manufacturing, where burn-in operations are performed in ovens. We consider cases in which ther e is no restriction on the size of a batch on a machine, and in which a mac hine can process only a bounded number of operations in one batch. For most of the possible combinations of restrictions, we establish the complexity status of the problem. Copyright (C) 2001 John Wiley & Sons, Ltd.