Scheduling Multi-Capacitated Resources under Complex Temporal Constraints - Robotics Institute Carnegie Mellon University

Scheduling Multi-Capacitated Resources under Complex Temporal Constraints

Amedeo Cesta, Angelo Oddi, and Stephen Smith
Tech. Report, CMU-RI-TR-98-17, Robotics Institute, Carnegie Mellon University, June, 1998

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.

BibTeX

@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},
}