zbMATH — the first resource for mathematics

Performance of critical path type algorithms with communication delay. (English) Zbl 1145.90395
Summary: The Brucker-Garey-Johnson algorithm and Hu’s algorithm are based on the idea of the critical path method and were developed for the model with unit execution time tasks, precedence constraints and parallel identical processors. The performance guarantees for these algorithms have been presented in [G. Singh and Y. Zinder, Asia-Pac. J. Oper. Res. 17, No. 1, 101–122 (2000; Zbl 1042.90566) and “Worst-case performance of critical path type algorithms”, Int. Trans. Oper. Res. 7, 383–399 (2000)]. We present upper bounds for the Brucker-Garey-Johnson algorithm with communication delays, which can be seen as a generalization of the performance guarantees in Singh and Zinder (loc. cit.). As a particular case this also gives performance guarantees for Hu’s algorithm with communication delays and therefore, also generalizes the previously known performance guarantees for this algorithm.
90B35 Deterministic scheduling theory in operations research