A coupled task scheduling approximation algorithm for minimizing the sum of completion times

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 5/3≈ 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 .