Practical temporal reasoning for real scheduling applications

Summary form only given. Presents a set of requirements for modelling and solving scheduling problems, including a somewhat unconventional definition of the term “solution”. These requirements, distilled from experience implementing and fielding scheduling systems in a wide variety of domains, strongly constrain the nature of a useful scheduling system. Using a set of example problems drawn from this experience, the author motivates and explicates an approach to temporal reasoning for scheduling in which the system dynamics encoded in the temporal representation are “convex”, in the sense that all disjunction is treated as a range, rather than as a set of discrete points or regions of feasibility. Non-convex disjunction is encoded explicitly in a set of variables, such that finding a complete assignment to the set of variables is equivalent to constructing a feasible schedule. The problem is then solved as a Constraint Satisfaction Problem. Finally, the author discusses some recent extensions of this work, applying the same approach to problems involving a more complex system dynamic