Premium
Worst‐case performance of critical path type algorithms
Author(s) -
Singh G.,
Zinder Y.
Publication year - 2000
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2000.tb00206.x
Subject(s) - critical path method , computer science , job shop scheduling , path (computing) , scheduling (production processes) , upper and lower bounds , generalization , algorithm , mathematical optimization , mathematics , schedule , mathematical analysis , systems engineering , engineering , programming language , operating system
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.