Article ID: | iaor20108142 |
Volume: | 13 |
Issue: | 6 |
Start Page Number: | 609 |
End Page Number: | 627 |
Publication Date: | Dec 2010 |
Journal: | Journal of Scheduling |
Authors: | Dubois Didier, Fargier Hlne, Zielinski Pawel, Fortin Jrme |
Keywords: | networks: scheduling |
This paper reconsiders the Project Evaluation and Review Technique (PERT) scheduling problem when information about task duration is incomplete. We model uncertainty on task durations by intervals. With this problem formulation, our goal is to assert possible and necessary criticality of the different tasks and to compute their possible earliest starting dates, latest starting dates, and floats. This paper combines various results and provides a complete solution to the problem. We present the complexity results of all considered subproblems and efficient algorithms to solve them.