Maximizing Availability: A Commitment Heuristic for Oversubscribed Scheduling Problems

Abstract

In this paper we reconsider a "task-swapping" procedure for improving schedules in the face of resource oversubscription. Prior work has demonstrated that use of a retraction heuristic to determine which tasks to rearrange in an existing schedule allows for addition of new tasks which would otherwise fail to be scheduled. The existing task swap procedure employs a variable ordering heuristic for task insertion that is the same as the retraction heuristic, but scored in the reverse. That is, the least constrained tasks are retracted, and of these the most constrained are committed first. Value selection for commitment is defaulted to a task's earliest feasible start time. We have found that by applying a value selection heuristic, max-availability, to the choice of where to assign the retracted tasks, both solution quality and runtime performance of task swap can be improved greatly. Max-availability considers resource contention for an unassigned task and places it where availability is predicted to be maximal over the range of that task. This heuristic is applicable not only in a repair context, but can also promote resource levelling in the context of constructive task allocation. Finally, we show that use of max-availability in task swapping promotes schedule stability when compared to the prior greedy task insertion policy.