Branch-Relax-and-Check: A tractable decomposition method for order acceptance and identical parallel machine scheduling

Bahman Naderi and Vahid Roshanaei

European Journal of Operational Research, 2020, vol. 286, issue 3, 811-827

Abstract: We model and solve an order acceptance and scheduling problem in an identical parallel machine setting. The goal is to maximize profit by making four decisions: (i) accept or reject an order, (ii) assign accepted orders to identical parallel machines, (iii) sequence accepted orders, and (iv) schedule order starting times. First, we develop a mixed-integer model that simultaneously optimizes the above four decisions. We enhance the model with pre-processing techniques, valid inequalities, and dominance rules. Second, we show that the model has a special structure that allows us to develop both classical and combinatorial Benders decomposition. We thus develop a classical Benders decomposition approach and two combinatorial Benders variants: (i) logic-based Benders decomposition and (ii) Branch-Relax-and-Check (BRC). The BRC, as the primary contribution of this paper, extends the literature in three ways: (1) it incorporates novel sequencing sub-problem relaxations that expedite convergence, (2) it employs a novel cutting-plane partitioning procedure that allows these sub-problem relaxations to be separately optimized outside the master problem, and (3) it uses temporary Benders cuts that communicate sub-problem relaxation solutions to the master problem. Third, we demonstrate that the BRC outperforms significantly other methods and finds integer feasible solutions for 100% of instances, guarantees optimality in 50% of instances, and achieves an average optimality gap of 3.20% within our time limit.

Keywords: Combinatorial optimization; Order acceptance identical parallel machine scheduling; Mixed-integer programming; Benders decomposition; Temporary cuts (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719308495
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:286:y:2020:i:3:p:811-827

DOI: 10.1016/j.ejor.2019.10.014

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 ().