A branch and bound algorithm to minimise total weighted tardiness on a single batch processing machine with ready times and incompatible job families

Abstract

This research deals with developing a branch and bound algorithm for minimising total weighted tardiness on a single batch processing machine with characteristics similar to those seen in the diffusion operation in semiconductor manufacturing. Dominance properties are utilised in order to increase the efficiency of the algorithm. The developed algorithm is implemented in C++ and tested on different cases. We find the algorithm is capable of solving problems with up to 32 jobs. Computational results are presented along with a discussion of the effectiveness of the proposed algorithm and the effects of various parameters on the efficiency of the algorithm. The branch and bound algorithm can be used to solve relatively small problems as well as provide a means by which researchers can evaluate the effectiveness of their heuristics.

Keywords:

• Wafer production
• Batch processing
• Scheduling
• Branch and bound