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:
Filename Description Size
Thumbnail2010004989OK.pdf343.61 kB
Adobe PDF
Full metadata record
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: