Scheduling Multi-Capacitated Resources under Complex Temporal Constraints

June 1998

Scheduling Multi-Capacitated Resources under Complex Temporal Constraints

Authors:

Amedeo Cesta, Angelo Oddi, and Stephen Smith
Technical Report
CMU-RI-TR-98-17

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.
@techreport{Cesta-1998-14709,
author = {Amedeo Cesta And Angelo Oddi And Stephen Smith},
title = {Scheduling Multi-Capacitated Resources under Complex Temporal Constraints},
year = {1998},
month = {June},
institute = {Carnegie Mellon University},
address = {Pittsburgh, PA},
number = {CMU-RI-TR-98-17},
}
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.