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

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.