Solving resource-constrained project scheduling problems by A* search

Solving resource-constrained project scheduling problems by A* search

0.00 Avg rating0 Votes
Article ID: iaor1989917
Country: United States
Volume: 37
Issue: 1
Start Page Number: 61
End Page Number: 84
Publication Date: Feb 1990
Journal: Naval Research Logistics
Authors: ,
Abstract:

A new exact method is presented for finding a minimum makespan schedule for a multiresource constrained project scheduling problem. This method employs the philosophical approach used earlier to develop a successful heuristic algorithm for the same class of problems. The approach repairs resource conflicts rather than constructing detailed schedules by dispatching activities. Resource-violating sets of activities are identified whose concurrent execution would violate resource constraints. Repairs are made by imposing a precedence constraint to sequence two activities in such a resource-violating set. Computational results are discussed for a standard set of test problems. An A* algorithm is employed. The most successful version of our algorithm involves some perhaps surprising design choices which might be relevant to the design of A*-like search algorithms in other contexts.

Reviews

Required fields are marked *. Your email address will not be published.