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

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 $$\frac{5}{3}\approx 1.666\ldots .$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mfrac> <mml:mn>5</mml:mn> <mml:mn>3</mml:mn> </mml:mfrac> <mml:mo>≈</mml:mo> <mml:mn>1.666</mml:mn> <mml:mo>…</mml:mo> <mml:mo>.</mml:mo> </mml:mrow> </mml:math> We improve this bound to a general upper bound $$\frac{21p-\sqrt{3(43p^2-28p+4)}-6}{6p}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mfrac> <mml:mrow> <mml:mn>21</mml:mn> <mml:mi>p</mml:mi> <mml:mo>-</mml:mo> <mml:msqrt> <mml:mrow> <mml:mn>3</mml:mn> <mml:mo>(</mml:mo> <mml:mn>43</mml:mn> <mml:msup> <mml:mi>p</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>-</mml:mo> <mml:mn>28</mml:mn> <mml:mi>p</mml:mi> <mml:mo>+</mml:mo> <mml:mn>4</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:msqrt> <mml:mo>-</mml:mo> <mml:mn>6</mml:mn> </mml:mrow> <mml:mrow> <mml:mn>6</mml:mn> <mml:mi>p</mml:mi> </mml:mrow> </mml:mfrac> </mml:math> that holds for all $$p\ge 2.$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> <mml:mo>.</mml:mo> </mml:mrow> </mml:math> Using constructions to compute lower bounds, we give narrow intervals for the asymptotic behavior of algorithm SDF as a function of the parameter p .