This project is sponsored by Air Force Office of Scientific Research, Air Force Materiel Command, United States Air Force, under grant number F469620-03-1-0233.

Project Description

By studying scheduling algorithms and modeling their performance on real world, structured problems, we expect to significantly advance the understanding of scheduling and expedite the development of new algorithms for important applications. Our current project has shown significant progress modeling benchmark manufacturing scheduling problems by explaining how previously observed behaviors arose from the structure of problems. Both theory and practice indicate that specific algorithms must be adapted to specific problems. Methods that work well on "difficult randomly structured problems" do not necessarily generalize to real world structured problems. Our work in Satellite Scheduling also shows that heuristics that work well on older benchmarks may not work on recent datasets that are larger and more complex. We have developed metrics, models and theory to explain and predict performance in other scheduling applications, particularly oversubscribed problems in which more requests are received than can be accommodated.

Our models can motivate the design of new algorithms that can be expected to excel on specific applications. We have recently shown that much of the effectiveness of Tabu Search on Job Shop Scheduling problems can be explained by looking at the distance between local optima and globally optimal solutions. This insight has allowed us to develop even simpler memoryless algorithms which exploit this structure and which perform as well as Tabu Search on these problems. We will refine the methodology and apply it to a variety of Air Force applications. We will also evaluate these new algorithms in comparison to existing algorithms and their extensions to new applications.

We are a subgroup of the Artificial Intelligence Group in the Computer Science Department of Colorado State University.