Constraint Reasoning research has provided a new perspective on scheduling, planning and configuration problems. Traditional mathematical programming methods while very successful are limited to linear constraints, batch processing and inflexible uniform constraint solver algorithms. Recent research has shown that techniques for solving large constraint satisfaction problems (CSPs) can be applied directly to industrial problems. In this talk, we describe the underlying methodology of constraint reasoning. We contrast two classes of constraint solvers: constructive backtrack solvers and iterative improvement techniques. The latter recently has shown the ability to provide efficient solutions to very large scheduling problems. Although suboptimal, these methods frequently find good solutions quickly and are inherently anytime algorithms. Likewise, progress is being made in constructive methods including a new algorithm called dynamic backtracking which purports to be complete yet as flexible as iterative improvement. As well, research proceeds on distributed algorithms for CSPs which will prevail as problem solving moves onto the internet. All of these results are already being applied to industrial problems in scheduling, planning and configuration. We describe a number of such applications from our own experience as well as other applications in the literature. In each case, it is shown that significant improvements are being made in our ability to solve large problems; to express complicated constraints directly to the constraint solver; to use domain knowledge go guide the solution process; and to interact with the scheduling system in a natural way.
The concept of an anytime algorithm resurfaced with artificial intelligence work on reasoning about time and action. However, the concept of dynamic incremental problem solving has existed long before the recent renaming. Areas in which such ideas have been pursued include formal reasoning, cognitive psychology, operations research, and many experimental areas of computing science. We review the basic concepts, some of the ideas arising in the different background areas, and explain the challenges for the aplication of anytime concepts. Examples include those from formal reasoning and automated planning, especially the impact on software architectures for anytime problem solving.