Exact approach to joint order acceptance and non-permutation flow shop scheduling via logic-based benders decomposition

This is the authors' abstract. We don't add key points for this paper.

In modern make-to-order (MTO) manufacturing, decision-makers face the critical challenge of simultaneously selecting profitable orders and scheduling them efficiently under finite capacity constraints. This paper studies the order acceptance and scheduling problem in a non-permutation flow shop (OAS-NPFS), maximising the normalised net contribution of accepted orders minus the makespan-related production cost. We formulate the problem using both mixed-integer linear programming (MILP) and constraint programming (CP), and exploit a classical dominance property to reduce the scheduling search space. An exact logic-based Benders decomposition (LBBD) framework is then developed, in which an MILP master selects orders and a CP subproblem evaluates the makespan of each accepted set and generates valid Benders cuts from certified lower bounds. The framework is strengthened by makespan-bounding inequalities, an iterated greedy (IG) warm start, and a branch-and-check (B&C) implementation. Experiments on instances with up to seven machines and 100 orders show that the proposed method achieves optimality for all 90 small-scale instances, 136 of 160 medium-scale instances, and 105 of 160 large-scale instances. Its average certified relative gaps are 0.0975% and 0.1325% for the medium- and large-scale sets, respectively. An industry-calibrated case further illustrates its ability to improve the acceptance–scheduling trade-off over benchmark policies.