A Constraint-Based Method for Project Scheduling with Time Windows

A. Cesta, A. Oddi, and Stephen Smith
tech. report CMU-RI-TR-00-34, Robotics Institute, Carnegie Mellon University, February, 2000


Download
  • Adobe portable document format (pdf) (281KB)
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
This paper presents a heuristic algorithm for solving RCPSP/max, the resource constrained project scheduling problem with generalized precedence relations. The algorithm relies, at its core, on a constraint satisfaction problem solving (CSP) search procedure, which generates a consistent set of activity start times by incrementally removing resource conflicts from an otherwise temporally feasible solution. Key to the effectiveness of the CSP search procedure is its heuristic strategy for conflict selection. A conflict sampling method biased toward selection of minimal conflict sets that involve activities with higher-capacity requests is introduced, and coupled with a non-deterministic choice heuristic to guide the base conflict resolution process. This CSP search is then embedded within a larger iterative-sampling search framework to broaden search space coverage and promote solution optimization. The efficacy of the overall heuristic algorithm is demonstrated empirically on a large set of previously studied RCPSP/max benchmark problems.

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, "A Constraint-Based Method for Project Scheduling with Time Windows," tech. report CMU-RI-TR-00-34, Robotics Institute, Carnegie Mellon University, February, 2000

BibTeX Reference
@techreport{Smith_2000_3755,
   author = "A. Cesta and A. Oddi and Stephen Smith",
   title = "A Constraint-Based Method for Project Scheduling with Time Windows",
   booktitle = "",
   institution = "Robotics Institute",
   month = "February",
   year = "2000",
   number= "CMU-RI-TR-00-34",
   address= "Pittsburgh, PA",
}