We present a simple greedy algorithm and a novel complete algorithm for finding utilitarian optimal solutions to Simple Temporal Problems with Preferences. Unlike previous algorithms, ours does not restrict preference functions to be convex. We present experimental results showing that (1) a single iteration of the greedy algorithm produces high-quality solutions, (2) multiple iterations, bounded by the square of the number of constraints, produce near-optimal solutions, and (3) our complete, memory-boundable algorithm has compelling anytime properties and outperforms a branch-and-bound algorithm.
展开▼
