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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\frac{5}{3}\approx 1.666\ldots .$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mfrac> <mn>5</mn> <mn>3</mn> </mfrac> <mo>≈</mo> <mn>1.666</mn> <mo>…</mo> <mo>.</mo> </mrow> </math></EquationSource> </InlineEquation> We improve this bound to a general upper bound <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\frac{21p-\sqrt{3(43p^2-28p+4)}-6}{6p}$</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mrow> <mn>21</mn> <mi>p</mi> <mo>-</mo> <msqrt> <mrow> <mn>3</mn> <mo stretchy="false">(</mo> <mn>43</mn> <msup> <mi>p</mi> <mn>2</mn> </msup> <mo>-</mo> <mn>28</mn> <mi>p</mi> <mo>+</mo> <mn>4</mn> <mo stretchy="false">)</mo> </mrow> </msqrt> <mo>-</mo> <mn>6</mn> </mrow> <mrow> <mn>6</mn> <mi>p</mi> </mrow> </mfrac> </math></EquationSource> </InlineEquation> that holds for all <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$p\ge 2.$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>≥</mo> <mn>2</mn> <mo>.</mo> </mrow> </math></EquationSource> </InlineEquation> Using constructions to compute lower bounds, we give narrow intervals for the asymptotic behavior of algorithm SDF as a function of the parameter p.

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

期刊论文
出版模式：

开放获取
发表日期：

2026年5月21日

查看全文

József Békési,
György Dósa,
Gábor Galambos

摘要

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 .$ $\frac{5}{3} \approx 1.666 \dots .$ We improve this bound to a general upper bound $\frac{21p-\sqrt{3(43p^2-28p+4)}-6}{6p}$ $\frac{21 p - \sqrt{3 (43 p^{2} - 28 p + 4)} - 6}{6 p}$ that holds for all $p\ge 2.$ $p \geq 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.