NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Collections About News Help Login
Back to Results
Generating effective project scheduling heuristics by abstraction and reconstitutionA project scheduling problem consists of a finite set of jobs, each with fixed integer duration, requiring one or more resources such as personnel or equipment, and each subject to a set of precedence relations, which specify allowable job orderings, and a set of mutual exclusion relations, which specify jobs that cannot overlap. No job can be interrupted once started. The objective is to minimize project duration. This objective arises in nearly every large construction project--from software to hardware to buildings. Because such project scheduling problems are NP-hard, they are typically solved by branch-and-bound algorithms. In these algorithms, lower-bound duration estimates (admissible heuristics) are used to improve efficiency. One way to obtain an admissible heuristic is to remove (abstract) all resources and mutual exclusion constraints and then obtain the minimal project duration for the abstracted problem; this minimal duration is the admissible heuristic. Although such abstracted problems can be solved efficiently, they yield inaccurate admissible heuristics precisely because those constraints that are central to solving the original problem are abstracted. This paper describes a method to reconstitute the abstracted constraints back into the solution to the abstracted problem while maintaining efficiency, thereby generating better admissible heuristics. Our results suggest that reconstitution can make good admissible heuristics even better.
Document ID
19930009486
Acquisition Source
Legacy CDMS
Document Type
Conference Paper
Authors
Janakiraman, Bhaskar (California Univ. Davis, CA, United States)
Prieditis, Armand (California Univ. Davis, CA, United States)
Date Acquired
September 6, 2013
Publication Date
May 1, 1992
Publication Information
Publication: NASA. Ames Research Center, Working Notes from the 1992 AAAI Spring Symposium on Practical Approaches to Scheduling and Planning
Subject Category
Cybernetics
Accession Number
93N18675
Distribution Limits
Public
Copyright
Work of the US Gov. Public Use Permitted.

Related Records

IDRelationTitle19930009470Collected WorksWorking Notes from the 1992 AAAI Spring Symposium on Practical Approaches to Scheduling and Planning
No Preview Available