Iterative algorithms for batching and scheduling to minimise the total job tardiness in two-stage hybrid flow shops

This study considers the batching and scheduling problem in two-stage hybrid flow shops in which each job with a distinct due-date is processed through two serial production stages, each of which has identical machines in parallel. Under the fundamental trade-off that large batch sizes with less frequent changeovers may reduce setup costs and hence increase machine utilisation, while small batch sizes may reduce job flow times and hence improve scheduling performance, the problem is to determine the number of batches, the batch compositions, the allocation of batches to the parallel machines at each stage, and the sequence of the batches allocated to each machine for the objective of minimising the total job tardiness. A mixed integer programming model is developed for the reduced problem in which the number of batches is given, and then, three iterative algorithms are proposed in which batching and scheduling are done repeatedly until a good solution is obtained. To show the performance of the algorithms, computational experiments were done on a number of test instances, and the results are reported. In particular, we show that the number of batches decreases as the ratio of the batch setup time to the job processing time increases.