Batching Problems

Batching means that sets of jobs which are processed on the same machine must be grouped into batches. A batch is a set of jobs which must be processed jointly. The finishing time of all jobs in a batch is defined to be equal to the finishing time of the last job in the batch. There is a setup time s for each batch, which is assumed to be the same for all batches. A batching problem is to group the jobs on each machine into batches and to schedule these batches. Depending on the calculation of the length of a batch, two types of batching problems have been considered. For sbatching (p-batching) problems the length is the sum (maximum) of the processing times of the jobs in the batch. Batching problems have been identified by adding the symbol “s-batch” or “p-batch” to the β-field of our classification scheme.