A Hybrid Approach for the Artificial Teeth Scheduling Problem

Session date: 27 January 2025

Session host: Felix Winter

Summary:

Modern-day artificial tooth manufacturing relies on a highly automated production process that utilizes complex machine environments. The large-scale requirements in this area thus require automated scheduling methods that can efficiently minimize a multi-objective cost function while considering many complex constraints.

We propose a novel approach to the ATSP that hybridizes exact and heuristic approaches in an innovative two-stage solution process. The first phase utilizes a novel subproblem formulation to efficiently batch product demands into compact jobs using exact solution methods based on constraint programming and column generation. In the second phase, the sequence of the resulting batch jobs is optimized using local search-based metaheuristics and hyper-heuristics.

Experimental results show that the proposed method can successfully hybridize the strengths of the exact and heuristic methods to efficiently solve all benchmark instances. The objective costs of almost all instances are significantly improved compared with existing approaches, and we provide new upper bounds for all evaluated real-life instances.