Worst-case performance of critical path type algorithms
- Australian Society for Operations Research
- Publication Type:
- Conference Proceeding
- 15th National Conference of Australian Society for Operations Research, 2000, 7 pp. 383 - 399
- Issue Date:
The critical path method remains one of the most popular approaches in practical scheduling. Being developed for the makespan problem this method can also be generalized to the maximum lateness problem. For the unit execution time task system and parallel processors this generalization is known as the Brucker±Garey±Johnson algorithm. We characterize this algorithm by introducing an upper bound on the deviation of the criterion from its optimal value. The bound is stated in terms of parameters characterizing the problem, namely number of processors, the length of the longest path, and the total required processing time. We also derive a similar bound for the preemptive version of the Brucker-Garey-Johnson algorithm.
Please use this identifier to cite or link to this item: