On the Utility of Bottleneck Reasoning for Scheduling

Abstract

The design of better schedulers requires a deeper un-derstanding 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 heuris-tic information used by bottleneck-centered, oppor-tunistic scheduling systems to solve constraint sat-isfaction scheduling problems. Different configura-tions of a single scheduling framework are applied to a benchmark set of scheduling problems and com-pared 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.