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

• A new class of lower bound methods with worst-case ratio no worse than 4/7. • A graph-theoretic pseudo-polynomial time algorithms to compute the bound. • Lower bound-driven valid inequalities to attain stronger MILP formulations. • Up to 96.2% of the problem instances solved optimally by MILP formulations. • Enhanced B & B algorithms performing better than existing B&B / B&P methods. 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 (LB m) and its improved variant (ILB m). 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 LB m and ILB m 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 VI s help increase the number of solved problems by more than 30%, achieving an optimality rate exceeding 96% across a wide range of problem instances. [ABSTRACT FROM AUTHOR]

Copyright of European Journal of Operational Research is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)