<p>We explore lower bounds concerning the makespan of any online scheduling algorithm for the parallel processor scheduling problem with four processors. We prove that any online algorithm exhibits a makespan of at least <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10951_2025_843_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="28" /> </InlineMediaObject> <EquationSource Format="TEX">$\sqrt{3}$</EquationSource> <EquationSource Format="MATHML"><math> <msqrt> <mn>3</mn> </msqrt> </math></EquationSource> </InlineEquation> times that of an optimal offline schedule, minus an additional constant of <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10951_2025_843_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="53" /> </InlineMediaObject> <EquationSource Format="TEX">$2-\sqrt{3}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mo>-</mo> <msqrt> <mn>3</mn> </msqrt> </mrow> </math></EquationSource> </InlineEquation>, thus yielding an asymptotic competitive ratio of <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10951_2025_843_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="28" /> </InlineMediaObject> <EquationSource Format="TEX">$\sqrt{3}$</EquationSource> <EquationSource Format="MATHML"><math> <msqrt> <mn>3</mn> </msqrt> </math></EquationSource> </InlineEquation>. Moreover, specific absolute competitive ratios <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10951_2025_843_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="62" /> </InlineMediaObject> <EquationSource Format="TEX">$\sqrt{3}-\epsilon _r$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msqrt> <mn>3</mn> </msqrt> <mo>-</mo> <msub> <mi>ϵ</mi> <mi>r</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10951_2025_843_Article_IEq5.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="45" /> </InlineMediaObject> <EquationSource Format="TEX">$\epsilon _r>0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>ϵ</mi> <mi>r</mi> </msub> <mo>></mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation> depends on the number of tasks that have to be scheduled, are established for scenarios involving a finite number of tasks.</p>

Lower bounds for online scheduling on four processors

期刊论文
出版模式：

开放获取
发表日期：

2025年5月29日

查看全文

O. Braun,
F. Chung,
R. L. Graham

摘要

We explore lower bounds concerning the makespan of any online scheduling algorithm for the parallel processor scheduling problem with four processors. We prove that any online algorithm exhibits a makespan of at least $\sqrt{3}$ $\sqrt{3}$ times that of an optimal offline schedule, minus an additional constant of $2-\sqrt{3}$ $2 - \sqrt{3}$ , thus yielding an asymptotic competitive ratio of $\sqrt{3}$ $\sqrt{3}$ . Moreover, specific absolute competitive ratios $\sqrt{3}-\epsilon _r$ $\sqrt{3} - ϵ_{r}$ , where $\epsilon _r>0$ $ϵ_{r} > 0$ depends on the number of tasks that have to be scheduled, are established for scenarios involving a finite number of tasks.