A Two-Stage Constraint Programming Approach for Artificial Teeth Scheduling

Abstract

The large-scale requirements of modern tooth manufacturing call for automated scheduling methods that can optimize multiple cost objectives while accounting for complex constraints. Previously, the artificial teeth scheduling problem (ATP) was formally introduced, along with exact and heuristic methods to approach challenging real-life scenarios. Although existing approaches provide feasible solutions for all practical benchmarks evaluated, optimal results remain unknown. We propose a novel solver-independent constraint modeling approach that solves the ATP through an innovative two-stage process. The first stage uses a subproblem formulation that batches product demands into compact jobs via constraint programming or column generation. In the second phase, the job sequence is optimized using a single-machine model with interval variables and global scheduling constraints. Experimental results with state-of-the-art constraint solvers and a heuristic demonstrate the approach’s effectiveness, yielding improved solutions across the majority of realistically sized benchmark instances.