Constraint programming (CP) has been recently in the spotlight after new CP-based procedures have been incorporated into state-of-the-art solvers, most notably the CP Optimizer from IBM. Classical CP solvers were only capable of guaranteeing the optimality of a solution, but they could not provide bounds for the integer feasible solutions found if interrupted prematurely due to, say, time limits. New versions, however, provide bounds and optimality guarantees, effectively making CP a viable alternative to more traditional mixed-integer programming (MIP) models and solvers. We capitalize on these developments and conduct a computational evaluation of MIP and CP models on 12 select scheduling problems. 1 We carefully chose these 12 problems to represent a wide variety of scheduling problems that occur in different service and manufacturing settings. We also consider basic and well-studied simplified problems. These scheduling settings range from pure sequencing (e.g., flow shop and open shop) or joint assignment-sequencing (e.g., distributed flow shop and hybrid flow shop) to pure assignment (i.e., parallel machine) scheduling problems. We present MIP and CP models for each variant of these problems and evaluate their performance over 17 relevant and standard benchmarks that we identified in the literature. The computational campaign encompasses almost 6,623 experiments and evaluates the MIP and CP models along five dimensions of problem characteristics, objective function, decision variables, input parameters, and quality of bounds. We establish the areas in which each one of these models performs well and recognize their conceivable reasons. The obtained results indicate that CP sets new limits concerning the maximum problem size that can be solved using off-the-shelf exact techniques. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.1287 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2021.0326 ) at ( http://dx.doi.org/10.5281/zenodo.7541223 ).

We solve the type-2 assembly line balancing problem in the presence of sequence-dependent setup times, denoted SUALBP-2. The problem consists of a set of tasks of a product, requiring to be processed in different assembly stations. Each task has a definite processing and setup times. The magnitude of setup times for each task is dependent on the processing sequence within each station. Processing and setup times of tasks assigned to each station constitute the station time. The goal is to minimize the cycle time (the maximum station time) by optimally (i) assigning tasks to assembly stations and (ii) sequencing these tasks within each station. To solve this challenging optimization problem, we first improve upon an existing mixed-integer programming (MIP) model by our proposed lower and upper bounds. These enhancements reduce the MIP model’s (solved CPLEX) average optimality gap from 41.61% to 20.77% on extra-large instances of the problem. To further overcome the intractability of the MIP model, we develop an exact logic-based Benders decomposition (LBBD) algorithm. The LBBD algorithm effectively incorporates a novel two-phase solution approach, the lower and upper bounds, various preprocessing techniques, relaxations, and valid inequalities. Using existing benchmarks in the literature, we demonstrate that our LBBD algorithm finds integer feasible solutions for 100% of all 788 instances (64% for the MIP), verifies optimality for 47% of instances (37% for the MIP), and achieves an average optimality gap of 5.04% (7.72% for the MIP obtained over 64% solved small instances). The LBBD algorithm also significantly reduces the computational time required to solve these benchmarks. Summary of Contribution: Assembly line balancing plays a crucial role in productivity enhancement in manufacturing and service companies. A balanced assembly line ensures higher throughput rate and fairer distribution of workload among assembly stations (workers). Assembly line balancing, in its simplest form, is one of the most challenging combinatorial optimization problems. Its complexity is further intensified when the sequence of executing tasks assigned to each station influences the magnitude of the setup performed between any two successive tasks. In view of such complexity, most assembly line balancing problems have been solved by randomized search techniques that do not provide any guarantee on the quality of solutions found. The mission of this paper is to understand whether there is any special structure within the existing mathematical models in the literature and, if so, exploit them toward developing computationally efficient exact techniques that can provide guarantee on the quality of solutions. Indeed, we demonstrate that such a special mathematical structure exists and we thus develop the first decomposition technique in form of a logic-based Benders decomposition (LBBD) to efficiently solve the type-2 sequence-dependent assembly line balancing problem. Specifically, we show that our LBBD significantly reduces cycle time and the time required for decision making. Our LBBD generalizes the scope of exact techniques for decision-making beyond the assembly line problems and is extendable to many other shop scheduling problems that arrange their stations (machines) serially and there are sequence-dependent setup times among their tasks.