Worst-case performance of two critical path type algorithms

The critical path method remains one of the most popular approaches in practical scheduling. This paper characterizes this method by the worst-case analysis of Hu's algorithm and the Brucker–Garey–Johnson algorithm. Both algorithms are based on the idea of the critical path method and were developed for the model with unit execution time operations, precedence constraints and parallel identical processors. We present a tight upper bound for the Brucker–Garey–Johnson algorithm and tight performance guarantees for Hu's algorithm. The previously known bound for Hu's algorithm derived by Chen is only asymptotically achievable. It is also shown that in some sense Chen's bound cannot be generalized for the Brucker–Garey–Johnson algorithm.