Efficiency analysis of the Kaufmann and Dezbazeille algorithm for the deadline problem

• Authors: Marcin ANHOLCER , Helena GASPARS-WIELOCH
• Languages of publication: EN

Abstracts

EN

Time-cost tradeoff analysis is a very important issue in project management. The Kaufmann–Desbazeille algorithm is considered by numerous authors to be an exact algorithm to solve this problem. In the paper, we prove that this claim is not true. In particular, we perform a worst-case analysis. The accuracy of the KDA is the worst when: the network has many critical and subcritical paths with a lot of common arcs (i), shortening costs are constant (ii), the level of shortening costs for a given activity depends on its type.

Keywords

EN

time-cost trade-off analysis; network, critical path; accuracy of an algorithm; project compression time; time-cost curves

• Publisher: Politechnika Wrocławska. Oficyna Wydawnicza Politechniki Wrocławskiej
• Journal: Operations Research and Decisions
• Year: 2011
• Volume: 21
• Issue: 1
• Pages: 5-18

Contributors

author

Marcin ANHOLCER

• Department of Operations Research, Poznań University of Economics, al. Niepodleglości 10, 61 - 875 Poznań, Poland

author

Helena GASPARS-WIELOCH

• Department of Operations Research, Poznań University of Economics, al. Niepodleglości 10, 61 - 875 Poznań, Poland

References

• BERMAN E.B., Resource allocation in a PERT network under continuous activity time-cost functions, Management Science, 1964, 10 (4), 734–745.
• BLADOWSKI S., Metody sieciowe w planowaniu i organizacji pracy, PWE, Warszawa, 1970.
• CORMEN T.H., LEISERSON C.E., RIVEST R.L., Introduction to Algorithms, MIT Press, Cambridge, 2001.
• CROWSTON W.B., THOMPSON G.L., Decision CPM: A method for simultaneous planning, scheduling, and control of projects, Operations Research, 1967, 15, 407–426.
• DE P., DUNNE E.J., GOSH J.B., WELLS C.E., The discrete time-cost tradeoff problem revisited, European Journal of Operations Research, 1995, 81, 225–238.
• DE P., DUNNE E.J., GOSH J.B., WELLS C.E., Complexity of the discrete time-cost trade-off problem for project networks, Operations Research, 1997, 45, 302–306.
• EDMONDS J., KARP R.M., Theoretical improvements in the algorithmic efficiency for network flow problems, Journal of the ACM, 1972, 19, 248–264.
• FALK J.E., HOROWITZ J.L., Critical path problems with concave cost–time curves, Management Science, 1972, 19, 446–455.
• FONDHAL J.W., A Non-Computer Approach to the Critical Path Method for the Construction Industry, Construction Institute Technical Report No. 9, Construction Institute, Stanford University, 1961.
• FORD L.R., FULKERSON D.R, Flows in Networks, Princeton University Press, Princeton, New York, 1962.
• FULKERSON D.R., A network flow computation for project cost curves, Management Science, 1961, 7 (2), 167–178.
• FUSEK A., NOWAK K., PODLESKI H., Analiza drogi krytycznej (CPM i PERT). Instrukcja programowana, PWE, Warszawa, 1967.
• GASPARS H., Analiza czasowo-kosztowa (CPM-COST). Algorytm a model optymalizacyjny, Badania Operacyjne i Decyzje, 2006, nr 1, 5–19.
• GASPARS H., Propozycja nowego algorytmu w analizie czasowo-kosztowej przedsięwzięć, Badania Operacyjne i Decyzje, 2006, nr 3–4, 5–27.
• GASPARS-WIELOCH H., Metody optymalizacji czasowo-kosztowej przedsięwzięcia, Thesis, Poznań, University of Economics, Poznań, 2009.
• GASPARS-WIELOCH H., Przegląd wybranych metod skracania czasu realizacji przedsięwzięcia, [w:] Metody i zastosowania badań operacyjnych, Prace Naukowe Akademii Ekonomicznej w Katowicach, D. Kopańska-Bródka (red.), Wydawnictwo Akademii Ekonomicznej w Katowicach, 2008.
• GEDYMIN O., Metody optymalizacji w planowaniu sieciowym, PWN, Warszawa, 1974.
• GOYAL S.K., A note on a simple CPM time-cost tradeoff algorithm, Management Science, 1975, 21 (6), 718–722.
• HENDRICKSON C., AU T., Project Management for Construction. Fundamental Concepts for Owners, Engineers, Architects and Builders, Prentice Hall, 1989.
• HINDELANG T.J., MUTH J.F., A dynamic programming algorithm for Decision CPM networks, Operations Research, 1979, 27 (2), 225–241.
• IDŹKIEWICZ A.Z., PERT. Metody analizy sieciowej, PWN, Warszawa, 1967.
• KAUFMANN A., DESBAZEILLE G., VENTURA E., La méthode du chemin critique, Dunod, Paris, 1964.
• KELLEY J.E., Critical path planning and scheduling: mathematical basis, Operations Research, 1961, 9 (3), 296–320.
• KORZAN B., Elementy teorii grafów i sieci. Metody i zastosowania, Wydawnictwa Naukowo- -Techniczne, Warszawa, 1978.
• Badania operacyjne w przykładach i zadaniach, K. Kukuła (red.), PWN, Warszawa, 1996.
• LIU L., BURNS S.A., FENG C.-W., Construction time-cost tradeoff analysis using LP/IP hybrid method, Journal of Construction Engineering and Management, 1995, 121 (4), 446–453.
• MODER J.J., PHILLIPS C.R., Project Management with CPM and PERT, Reinhold Publishing Corporation, New York, 1964.
• MOUSSOURAKIS J., HAKSEVER C., Flexible Model for Time/Cost Tradeoff Problem, Journal of Construction Engineering and Management, 2004, 130 (3), 307–314.
• MULLER Y., Exercices d’organisation et de la recherche opérationnelle, Eyrolles, Paris, 1965.
• MULLER Y., Organisation et recherche opérationnelle, Eyrolles, Paris, 1964.
• PANAGIOTAKOPOULOS D., A CPM time-cost computational algorithm for arbitrary activity cost functions, INFOR, 1977, 15 (2), 183–195.
• PHILLIPS S.J., DESSOUKY M.I., Solving the time/cost tradeoff problem using the minimum cut concept, Management Science, 1977, 24 (4), 393–400.
• PRAGER W., A structural method of computing project cost polygons, Management Science, 1963, 9 (3), 394–404.
• SCHRIJVER A., Combinatorial Optimization, Springer, Berlin, Vol. A, 2003, p. 76, Corollary 5.20.B.
• SIEMENS N., A simple CPM time-cost tradeoff algorithm, Management Science 1971, 17 (6), 354–363.
• SIUDAK M., Badania operacyjne, Oficyna Wydawnicza Politechniki Warszawskiej, Warszawa, 1998.
• SKUTELLA M., Approximation algorithms for the discrete time-cost tradeoff problem, Mathematics of Operations Research, 1998, 23 (4), 909–928.
• TROCKI M., GRUCZA B., OGONEK K., Zarządzanie projektami, PWE, Warszawa, 2003.
• WATERS D., A Practical Introduction to Management Science, Second Ed., Addison-Wesley Longman, 1998.