Greedy Algorithms for the Multi-Capacitated Metric Scheduling Problem - Robotics Institute Carnegie Mellon University

Greedy Algorithms for the Multi-Capacitated Metric Scheduling Problem

A. Cesta, A. Oddi, and S. F. Smith
Conference Paper, Proceedings of 5th European Conference on Planning (ECP ’99), pp. 213 - 225, September, 1999

Abstract

This paper investigates the performance of a set of greedy algorithms for solving the Multi-Capacitated Metric Scheduling Problem (MCM-SP). All algorithms considered are variants of ESTA (Earliest Start Time Algorithm), previously proposed in [3]. The paper starts with an analysis of ESTA's performance on different classes of MCMSP problems. ESTA is shown to be effective on several of these classes, but is also seen to have difficulty solving problems with heavy resource contention. Several possibilities for improving the basic algorithm are investigated. A first crucial modification consists of substituting ESTA's pairwise analysis of resource conflicts with a more aggregate and thus more powerful Minimal Critical Set (mcs) computation. To cope with the combinatorial task of enumerating mcss, several approximate sampling procedures are then defined. Some systematic sampling strategies, previously shown effective on a related but different class of scheduling problem, are found to be less effective on MCM-SP. On the contrary, a randomized mcs sampling technique is introduced, forming a variant of ESTA that is shown to be quite powerful on highly constrained problems.

BibTeX

@conference{Cesta-1999-120508,
author = {A. Cesta and A. Oddi and S. F. Smith},
title = {Greedy Algorithms for the Multi-Capacitated Metric Scheduling Problem},
booktitle = {Proceedings of 5th European Conference on Planning (ECP ’99)},
year = {1999},
month = {September},
pages = {213 - 225},
}
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.