A Variable Elimination Approach for Optimal Scheduling with Linear Preferences

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 works achieve 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.