Tractable optimal competitive scheduling
Jeremy Frank, James M. Crawford, Lina Khatib, Ronen I. Brafman · 2006
In this paper we describe the problem of Optimal Competi-tive Scheduling, which consists of activities that compete for a shared resource. The objective is to choose a subset of activ-ities 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 max-imized. 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 op-timal activity ordering can be found in polynomial time. The second class arises by reformulation of the problem as a Val-ued Constraint Satisfaction Problem and exploiting known re-sults on tractability. We describe implementations of special-purpose algorithms designed to solve tractable OCS prob-lems, and identify different solver performance characteris-tics based on properties of the problem instances.