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: | Bell Colin E., Park Kwangho |
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.