Batch sizing and job sequencing on a single machine

The authors study a single-machine scheduling problem in which the items to be processed have to be batched as well as sequenced. Since processed items become available in batches, flow times are defined to be the same for all items in the same batch. A constant set-up delay is incurred between consecutive batches. For any fixed, but arbitrary item sequence, the authors present an algorithm that finds a sequence of batches such that the total flow time of the items is minimized; they prove that for a set of n items, the algorithm runs in O(n) time. The authors show that, among all sequences, the one leading to the minimum flow time has the items in non-decreasing order of running times. Thus, the optimal algorithm for the combined problem, called the batch-sizing problem, runs in O(nlogn) time. The authors also prove that this algorithm yields an improved solution to a scheduling problem recently studied by Baker.