Searching Alternate Spaces to Solve Oversubscribed Scheduling Problems

Oversubscribed scheduling problems have been approached using both direct representations of the solution space and indirect, permutation-based representations(coupled with a schedule builder to produce the corresponding schedule). In some problem contexts, permutation-based search methods have been shown to outperform schedule-space search methods, 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 dominate 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. Experimental results provide insights into when schedule-space methods and permutation-based methods may be most appropriate. Finally, we consider opportunities for improving performance by integrating the two approaches into a hybrid approach that exploits both search spaces.