Understanding performance tradeoffs in algorithms for solving oversubscribed scheduling

In recent years, planning and scheduling research has paid increasing attention to problems that involve resource over-subscription, where cumulative demand for resources out-strips their availability and some subset of goals or tasks must be excluded. Two basic classes of techniques to solve oversubscribed scheduling problems have emerged: search-ing directly in the space of possible schedules and searching in an alternative space of task permutations (by relying on a schedule builder to provide a mapping to schedule space). In some problem contexts, permutation-based search methods have been shown to outperform schedule-space search meth-ods, while in others the opposite has been shown to be the case. We consider two techniques for which this behavior has been observed: TaskSwap (TS), a schedule-space repair search procedure, and Squeaky Wheel Optimization (SWO), a permutation-space scheduling procedure. We analyze the circumstances under which one can be expected to domi-nate the other. Starting from a real-world scheduling problem where SWO has been shown to outperform TS, we construct a series of problem instances that increasingly incorporate characteristics of a second real-world scheduling problem, where TS has been found to outperform SWO. Experimen-tal results provide insights into when schedule-space methods and permutation-based methods may be most appropriate