Premium
Performance of Garey–Johnson algorithm for pipelined typed tasks systems
Author(s) -
Benabid A.,
Hanen C.
Publication year - 2010
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.2009.00758.x
Subject(s) - computer science , constant (computer programming) , upper and lower bounds , generalization , algorithm , parallel computing , programming language , mathematics , mathematical analysis
This paper studies the generalization of the first Garey–Johnson algorithm, which minimizes the maximum lateness on two parallel processors to the case of unitary typed tasks systems with constant delays. The performance of the extended algorithm is evaluated through worst‐case analysis. If all the tasks have the same type and no delay is considered, then the upper bound obtained coincides with the upper bound for the Garey–Johnson algorithm on identical processors, which is one of the best known for the maximum lateness problem.