Task Swapping for Schedule Improvement: A Broader Analysis

Abstract

In this paper we analyze and extend a recently developed "task-swapping procedure" for improving schedules in oversubscribed situations. In such situations, there are tasks which cannot be directly added to the current schedule without introducing capacity conflicts. A schedule is improved if one or more of these tasks can be feasibly included, and the goal of task swapping is to rearrange some portion of the current schedule to make this possible. Key to effective task swapping is an ability to exploit the scheduling flexibility inherent in the constraints associated with various scheduled tasks, and previous work has shown that the use of retraction heuristics that favor tasks with greater rescheduling flexibility can give rise to strong schedule improvement capabilities. We extend this work by developing and evaluating several improvements to the core task swapping procedure. We introduce three pruning techniques and show that each significantly improves computational efficiency while maintaining solution quality. We then investigate the possibility of improving the "end" solutions by stochastically exploring the "neighborhood" around them, and demonstrate that improved solutions are possible given the ability to spend additional time.