Heuristic Search vs. Constraint Programming for Single Machine Scheduling
Abstract: In the scheduling literature, single-machine scheduling problems are defined to isolate challenging problem characteristics and investigate the boundary between P and NP-completeness. Typically, problems in the latter class are solved with mixed-integer linear programming, customized branch-and-bound, or dynamic programming. In this tutorial, I will use two recently proposed single-machine scheduling problems to introduce approaches to scheduling using domain-independent dynamic programming (DIDP) and constraint programming (CP). Inspired by AI planning, DIDP is a model-and-solve approach to combinatorial optimization problems that models problems as dynamic programs in a solver-independent modeling language and, currently, solves the models using heuristic search. CP is a well-developed approach to combinatorial optimization with a mature set of concepts for scheduling problems. My primary goals are to introduce the SoCS community to DIDP as a potential area for heuristic search research and to present the higher-level constructs that make CP a state-of-the-art approach to scheduling problems.
Bio: J. Christopher Beck is a Professor in the Department of Mechanical & Industrial Engineering at the University of Toronto. For over 25 years, Chris has explored intelligent problem solving in Artificial Intelligence and Operations Research through the frameworks of constraint programming, mixed integer programming, heuristic search, and, most recently, dynamic programming. He has published over 170 papers in international conferences and journals. He has served as the President of both the Executive Committee of the International Conference on Automated Planning and Scheduling and of the Association for Constraint Programming and is an Editor-in-Chief of the Journal of Artificial Intelligence Research. Chris was elected as a AAAI Fellow in 2025.