Article ID: | iaor20002737 |
Country: | United States |
Volume: | 2 |
Issue: | 1 |
Start Page Number: | 87 |
End Page Number: | 104 |
Publication Date: | Jan 1996 |
Journal: | Journal of Heuristics |
Authors: | Valls Vicente, Mart Rafael, Lino Pilar |
Keywords: | scheduling, heuristics |
In this article, we analyze the precedence diagramming method, the only published algorithm for time-only project scheduling with activity splitting allowed. The criteria used in this method (forward and backward pass computations) for deciding when an activity has to be interrupted are shown to be invalid in some situations. We look into the causes of these failures and propose new formulae that always provide feasible solutions. The new algorithm has been tested on 240 randomly generated problems ranging up to 600 activities and 7,200 precedence relationships, resulting in an average deviation from optima of less than 1 percent.