Batch machine production with perishability time windows and limited batch size

This article provides a theoretical analysis of the problem of scheduling jobs in batches by family on a batch-processing machine, in the presence of perishability time windows of equal length. The problem arises in the context of production planning in a microbiological laboratory, and has application in wafer-fab production and for wireless broadcasting. The combined features of multiple families and time windows are new to the literature. The study is restricted to unit job processing times. We prove that the problem is NP-hard, thus solving an open problem by Uzsoy [24]. A Dynamic Programme is developed, with running time polynomial in the input variables of maximum batch size, the number of families and the length of the demand time horizon. In addition, we show that an heuristic approach to minimising the perishability time window can provide a 2-approximation to the optimum.