Profile-Based Algorithms to Solve Multi-Capacitated Metric Scheduling Problems

A. Cesta, A. Oddi, and Stephen Smith
Proceedings 5th International Conference on Artificial Intelligence Planning Systems, June, 1998.


Download
  • Adobe portable document format (pdf) (233KB)
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.

Abstract
Though CSP scheduling models have tended to assume fairly general representations of temporal constraints, most work has restricted attention to problems that require allocation of simple, unit-capacity resources. This paper considers an extended class of scheduling problems where resources have capacity to simultaneously support more than one activity, and resource availability at any point in time is consequently a function of whether sufficient unallocated capacity remains. We present a progression of algorithms for solving such multiple-capacitated scheduling problems, and evaluate the performance of each with respect to problem solving ability and quality of solutions generated. A previously reported algorithm, named the Conflict Free Solution Algorithm (CFSA), is first evaluated against a set of problems of increasing dimension and is shown to be of limited effectiveness. Two variations of this algorithm are then introduced which incorporate measures of temporal flexibility as an alternative heuristic basis for directing the search, and the variant making broadest use of these search heuristics is shown to yield significant performance improvement. Observations about the tendency of the CFSA solution approach to produce unnecessarily overconstrained solutions then lead to development of a second heuristic algorithm, named Earliest Start Time Algorithm (ESTA). ESTA is shown to be the most effective of the set, both in terms of its ability to efficiently solve problems of increasing scale and its ability to produce schedules that minimize overall completion time while retaining solution robustness.

Notes
Associated Center(s) / Consortia: Center for Integrated Manfacturing Decision Systems
Associated Lab(s) / Group(s): Intelligent Coordination and Logistics Laboratory

Text Reference
A. Cesta, A. Oddi, and Stephen Smith, "Profile-Based Algorithms to Solve Multi-Capacitated Metric Scheduling Problems," Proceedings 5th International Conference on Artificial Intelligence Planning Systems, June, 1998.

BibTeX Reference
@inproceedings{Smith_1998_3186,
   author = "A. Cesta and A. Oddi and Stephen Smith",
   title = "Profile-Based Algorithms to Solve Multi-Capacitated Metric Scheduling Problems",
   booktitle = "Proceedings 5th International Conference on Artificial Intelligence Planning Systems",
   month = "June",
   year = "1998",
}