A new class of lower bounds for scheduling a batch processing machine to minimize makespan

This paper addresses the problem of minimizing makespan on a batch-processing machine with limited capacity. Each job has a size and processing time, and multiple jobs can be processed simultaneously in a batch, provided the machine’s capacity is not exceeded. The batch processing time is determined by the longest processing time in batch. We show that the existing lower bound method has a worst-case performance ratio of 1/2, and propose a class of lower bound procedures (LBm) and its improved variant (ILBm). The new procedures take integer m, used to partition jobs depending on whether their sizes are greater than B/m or not, and provide tighter bounds as m increases. We prove that the worst-case performance ratio of LBm and ILBm is no worse than 4/7. Additionally, we show that they can be computed efficiently for m≤3. Based on the structure of the proposed lower bound procedures, we introduce different valid inequalities (VI) and embed them into an existing MILP model to achieve a formulation with a tighter LP bound. To gain understanding on the quality of the bounds, we employ them in a branch and bound (B&B) algorithm. Results indicate that the B&B with new lower bound methods increases the number of optimally solved problem instances by 44% and 35% compared to the existing B&B and branch and price algorithms, respectively. Furthermore, the lower bound-driven VIs help increase the number of solved problems by more than 30%, achieving an optimality rate exceeding 96% across a wide range of problem instances.