file.pdf (258.72 kB)

Searching Alternate Spaces to Solve Oversubscribed Scheduling Problems

Download (258.72 kB)
journal contribution
posted on 15.05.2007 by Laurence A. Kramer, Laura Barbulescu, Stephen F. Smith

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.


Publisher Statement

All Rights Reserved