Improved MILP formulation equipped with valid inequalities for scheduling a batch processing machine with non-identical job sizes

Ali Husseinzadeh Kashan and Onur Ozturk

Omega, 2022, vol. 112, issue C

Abstract: We consider the problem of minimizing makespan on a single batch processing machine with a limited capacity. The machine can simultaneously process a group (batch) of jobs, each of them having different sizes and processing times. The processing time of a batch is the longest processing time of all jobs in the batch. We analyze the strength of the LP-relaxations of two mixed integer linear programming (MILP) formulations: a straightforward formulation and an advanced formulation. We prove that while the LP-relaxation of the straightforward formulation can perform arbitrarily bad in providing an LP bound on the optimal makespan, the LP-relaxation of the advanced formulation have some merit in providing a relatively good bound of makespan. With a detailed analysis of the problem, we prove a number of properties of the optimal solution and derive their respective valid inequalities (VI). These VIs are exploited in a novel MILP formulation for the problem. Extensive computations reveal that, with the help of the VIs, the proposed MILP formulation can solve large instances of the problem.

Keywords: Scheduling; Batch processing machine; Mixed integer linear formulation; LP-relaxation; Valid inequality (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305048322000809
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:jomega:v:112:y:2022:i:c:s0305048322000809

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.omega.2022.102673

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().