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

Ali Husseinzadeh Kashan and Onur Ozturk

European Journal of Operational Research, 2025, vol. 327, issue 3, 754-775

Abstract: 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.

Keywords: Scheduling; Batch processing machine; Lower bound; Worst-case performance ratio analysis; valid inequality (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722172500445X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:327:y:2025:i:3:p:754-775

DOI: 10.1016/j.ejor.2025.05.047

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().