Resource Contention Metrics for Oversubscribed Scheduling

We investigate a task insertion heuristic for oversubscribed scheduling problems, max-availability, that uses a simple es-timate of resource contention to assign tasks to intervals ex-pected to have the best worst case resource availability. Prior research in value and variable ordering heuristics for schedul-ing 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 fea-sible, optimal solution may not even exist, max-availability generates schedules of similar quality to other contention based heuristics with much less computational overhead