Minimizing total tardiness in a two parallel batch-and-single machines system with incompatible job families

Abstract

This thesis considers a problem of minimizing total tardiness on a two parallel batch-and-single machines system which consists of a batch-processing machine and a single machine. The batch-processing machine can process several jobs together according to its capacity, and all these jobs have the same completion time. The jobs are grouped in incompatible job families, where all jobs of the same family have identical processing times and jobs from other job families cannot be processed together on the batch-processing machine. Some solution properties and a SPT (shortest processing time) based lower bound are derived, and then applied in a Branch-and-Bound algorithm. Numerical experiments showed that solution properties and the lower bound contribute a lot to the performance of the algorithm.