A Variable Elimination Approach for Optimal Scheduling with Linear Preferences

Meuleau, N.; Morris, R. A.; and Yorke-Smith, N. A Variable Elimination Approach for Optimal Scheduling with Linear Preferences. Proceedings of CP/ICAPS'08 Joint Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems, Sydney, Australia, September 2008.

Abstract: In many practical scheduling problems, feasible solutions can be partially ordered according to differences between the temporal objects in each solution. Often, these orderings can be computed from a compact value function that combines the local preference values of the temporal objects. However, in part because it is natural to view temporal domains as continuous, finding complete, preferred solutions to these problems is a challenging optimization task. Previous work achieves tractability by making restrictions on the model of temporal preferences, including limiting representations to binary and convex preferences. We propose an application of Bucket Elimination (BE) to solve problems with piecewise linear constraints on temporal preferences with continuous domains. The key technical hurdle is developing a tractable elimination function for such constraints. This proof of concept takes a step toward an ability to solve scheduling problems with richer models of preference than previously entertained. Further, it provides a complementary approach to existing techniques for restricted models, because the complexity of BE, while exponential in the treewidth of the problem, is polynomial in its size.

PDF (723K) | Bibtex entry

Workshop homepage