Resource Contention Metrics for Oversubscribed Scheduling Problems - Robotics Institute Carnegie Mellon University

Resource Contention Metrics for Oversubscribed Scheduling Problems

Laurence Kramer and Stephen Smith
Conference Paper, Proceedings of 16th International Conference on Automated Planning and Scheduling (ICAPS '06), pp. 406 - 409, June, 2006

Abstract

We investigate a task insertion heuristic for oversubscribed scheduling problems, max-availability, that uses a simple estimate of resource contention to assign tasks to intervals expected to have the best worst case resource availability. Prior research in value and variable ordering heuristics for scheduling problems indicated that sophisticated, but more costly measures of resource contention can outperform simpler ones by more reliably pruning the search space. We demonstrate that for oversubscribed, priority-based problems where a feasible, optimal solution may not even exist, max-availability generates schedules of similar quality to other contention based heuristics with much less computational overhead.

BibTeX

@conference{Kramer-2006-9504,
author = {Laurence Kramer and Stephen Smith},
title = {Resource Contention Metrics for Oversubscribed Scheduling Problems},
booktitle = {Proceedings of 16th International Conference on Automated Planning and Scheduling (ICAPS '06)},
year = {2006},
month = {June},
pages = {406 - 409},
keywords = {scheduling, heuristics},
}