Understanding Algorithm Performance on an Oversubscribed Scheduling Application

December 2006

Understanding Algorithm Performance on an Oversubscribed Scheduling Application

Authors:

Laura Barbulescu, Adele E. Howe, Mark Roberts, and L. Darrell Whitley

Abstract:

The best performing algorithms for a particular oversubscribed scheduling application, Air Force Satellite Control Network (AFSCN) scheduling, appear to have little in common. Yet, through careful experimentation and modeling of performance in real problem instances, we can relate characteristics of the best algorithms to characteristics of the application. In particular, we find that plateaus dominate the search spaces (thus favoring algorithms that make larger changes to solutions) and that some randomization in exploration is critical to good performance (due to the lack of gradient information on the plateaus). Based on our explanations of algorithm performance, we develop a new algorithm that combines characteristics of the best performers; the new algorithm's performance is better than the previous best. We show how hypothesis driven experimentation and search modeling can both explain algorithm performance and motivate the design of a new algorithm.
@article{Barbulescu-2006-126301,
author = {Laura Barbulescu And Adele E. Howe And Mark Roberts And L. Darrell Whitley},
title = {Understanding Algorithm Performance on an Oversubscribed Scheduling Application},
journal = {Proceedings of Journal of Artificial Intelligence Research},
year = {2006},
month = {December},
volume = {27},
number = {1},
pages = {577 - 615},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.