Efficiency Analysis of the Kaufmann and Desbazeille Algorithm for the Deadline Problem

Abstract

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. (original abstract)