An Iterative Sampling Procedure for Resource Constrained Project Scheduling with Time Windows

A. Cesta, A. Oddi, and Stephen Smith
Proceedings 16th International Joint Conference on Artificial Intelligence (IJCAI '99), August, 1999.


Download
  • Adobe portable document format (pdf) (193KB)
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
In this paper, we extend and integrate previously reported techniques for resource constrained scheduling to develop a CSP procedure for solving RCPSP/max, the resource constrained project scheduling problem with time windows (generalized precedence relations between start time of activities). RCPSP/max is a well-studied problem within the Operations Research community and the presence of a large set of benchmark problems provides a good opportunity for comparative performance analysis. Our base CSP scheduling model generalizes previous profile-based approaches to cumulative scheduling by focusing on global analysis of minimal conflicting sets rather than pairwise conflict analysis. This generalization increases the tendency for more effective conflict resolution. Since RCPSP/max is an optimization problem, other ideas from prior work are adapted to embed this base CSP model within a multi-pass, iterative sampling procedure. The overall procedure, called ISES (Iterative Sampling Earliest Solutions), is applied to the above mentioned set of benchmark problems. ISES is shown to perform quite well in comparison to current state-of-the-art procedures for RCPSP/max, particularly as search space size becomes limiting for systematic procedures.

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, "An Iterative Sampling Procedure for Resource Constrained Project Scheduling with Time Windows," Proceedings 16th International Joint Conference on Artificial Intelligence (IJCAI '99), August, 1999.

BibTeX Reference
@inproceedings{Smith_1999_2788,
   author = "A. Cesta and A. Oddi and Stephen Smith",
   title = "An Iterative Sampling Procedure for Resource Constrained Project Scheduling with Time Windows",
   booktitle = "Proceedings 16th International Joint Conference on Artificial Intelligence (IJCAI '99)",
   month = "August",
   year = "1999",
}