Abstract In the considered coupled task problem (CTP) we have to schedule n jobs on a single machine, each consisting of two tasks with exact time delay between them, while the objective is to minimize the total completion time of the jobs. We analyze a greedy type algorithm – called SDF (Shortest Delay First) – from worst case point of view, and we give bounds for the asymptotic behavior of SDF for the special case where each task has equal length processing time p. For this case, the best-known upper bound on the asymptotic performance ratio of algorithm SDF is 53 1. 666. 5 3 ≈ 1. 666 …. We improve this bound to a general upper bound 21p-3 (43p²-28p+4) -66p 21 p - 3 (43 p 2 - 28 p + 4) - 6 6 p that holds for all p 2. p ≥ 2. Using constructions to compute lower bounds, we give narrow intervals for the asymptotic behavior of algorithm SDF as a function of the parameter p.
Békési et al. (Thu,) studied this question.