One-machine batching and sequencing of multiple-type items

The authors consider a single-machine scheduling problem in which a given number of simultaneously available items of different types are to be processed. The items must first be batched and then sequenced before processing begins. Only items of the same type can be batched together. A setup time is incurred whenever a batch of a certain type of item is formed. The flowtime of an item in a batch is defined as the completion time of the batch that contains it. The problem is to find an optimal schedule in terms of the optimal batching and sequencing decisions that minimizes the total item flowtime. The authors present a dynamic programming algorithm to solve this problem. The algorithm has a running time polynomial in the number of items but exponential in the number of types.