Constraint programming paradigm in solving scheduling problems: an analytical survey

Abstract

The study considers an approach to solving scheduling problems based on the paradigm of constraint programming. Any method of constraint satisfaction includes two mandatory parts: a) the component responsible for the search; b) the component performing reasoning on constraints (constraint propagation). When implementing the former component, a certain type of depth-first search is usually used using heuristics to select the successor of the current node in the search tree. The latter component is implemented using the mechanism of global constraints. Global constraints can be considered as composite constraints, which are a set of simpler same-type constraints. Algorithms of global constraint propagation, as a rule, are supported by appropriate full-fledged theories, which allow organizing high performance computations. The constraint programming technology makes it possible to implement general methods for solving complex combinatorial problems, and also makes it possible to integrate existing methods of operation research theory aimed at solving narrow classes of problems using the mechanism of global constraints. When solving scheduling problems, the main constraints can be classified as follows: constraints on the order of operations, constraints on unary (distributive) resources, constraints on cumulative resources. This study reviews the main classes of scheduling problems and focuses on the constraints types that are used in them. To solve these problems, general-purpose constraint satisfaction methods can be used, but the use of specialized heuristics and global constraints is considered more promising. The study provides an overview of the most popular heuristics used in solving scheduling problems, as well as global constraints such as: global constraint on disjunctive resources, global constraint on cumulative resources, global constraint on the cardinality set of. The study discusses the features of the implementation of various classes of scheduling problems using modern constraint programming environments and libraries.