On the Utility of Bottleneck Reasoning for Scheduling

Planning and Scheduling

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 12

Scheduling

The design of better schedulers requires a deeper understanding of each component technique and of their interactions. Although widely accepted in practice, bottleneck reasoning for scheduling has not yet been sufficiently validated, either formally or empirically. This paper reports an empirical analysis of the heuristic information used by bottleneck-centered, opportunistic scheduling systems to solve constraint satisfaction scheduling problems. Different configurations of a single scheduling framework are applied to a benchmark set of scheduling problems and compared with respect to number of problems solved and processing time. We show superior performances for schedulers that use bottleneck information. We also show that focusing at the bottleneck might not only provide an effective "most constrained first" heuristic but also, unexpectedly, increase the utility of other heuristic information.