The Robotics Institute

Carnegie Mellon Robotics Institute

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

Most CSP scheduling models make the restrictive assumption that a resource can only support a single activity at a time (i.e., it is either available or in-use). However, in many practical domains, resources in fact have the capability to si- multaneously support multiple activities, and hence availability at any point is a function of unallocated capacity. In this paper, we develop and evaluate algorithms for solving multi-capacitated scheduling problems. We First define a basic CSP model for this extended problem class, which provides a basic framework for formu- lating alternative solution procedures. Using this model, we then develop variants of two different solution approaches that have been recently proposed in the literature: (1) a profile-based procedure - which relies on local analysis of potential resource con icts to heuristically direct the problem solving process, and (2) a clique-based procedure - which exploits a global analysis of resource conflicts at greater computa- tional cost. In each case, improvements are made to previously proposed techniques. Performance results are given on a series of problems of increasing scale and con- strainedness, indicating the relative strengths of each procedure.

Notes

Text Reference

Amedeo Cesta, Angelo Oddi, and Stephen Smith , "Scheduling Multi-Capacitated Resources under Complex Temporal Constraints," tech. report CMU-RI-TR-98-17, Robotics Institute, Carnegie Mellon University, June, 1998

BibTeX Reference

@techreport{Smith__1998_2551,
   author = "Amedeo Cesta and Angelo Oddi and Stephen {Smith }",
   title = "Scheduling Multi-Capacitated Resources under Complex Temporal Constraints",
   booktitle = "",
   institution = "Robotics Institute",
   month = "June",
   year = "1998",
   number= "CMU-RI-TR-98-17",
   address= "Pittsburgh, PA",
}

The Robotics Institute

Menu