Tractable Optimal Competitive Scheduling

All Papers

In this paper we describe the problem of Optimal Competitive Scheduling, which consists of activities that compete for a shared resource. The objective is to choose a subset of activities to schedule, sequence them, and decide how much time they are allowed, in such a way that temporal and resource constraints are satisfied and overall schedule quality is maximized. While most such problems are NP-complete, very restricted versions of this problem are known to be tractable. In this work we describe tractable variations on this problem that correspond to realistic scheduling problems. The first class of tractable OCS problems arises due to limitations on the objective function that permit casting the problem as a Linear Program; with one additional assumption on activity feasibility windows, we identify a problem class where an optimal activity ordering can be found in polynomial time. The second class arises by reformulation of the problem as a Valued Constraint Satisfaction Problem and exploiting known results on tractability. We describe implementations of special-purpose algorithms designed to solve tractable OCS problems, and identify different solver performance characteristics based on properties of the problem instances.