This work considers a semi-online version of scheduling on m identical machines, where the objective is to minimize the makespan. In the variant studied here, jobs are presented sorted by non-increasing sizes, and a buffer of size k is available for storing at most k jobs. Every arriving job has to be either placed into the buffer until its assignment, or else it has to be assigned immediately to a machine. We prove a lower bound greater than 1 on the competitive ratio of the problem for any m and any buffer size. To complement this negative result, we design a simple algorithm for any m whose competitive ratio tends to 1 as the buffer size grows. Using those results, we show the best possible competitive ratio is <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1293_Article_IEq1.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="67" /> </InlineMediaObject> <EquationSource Format="TEX">$1+\Theta (\frac{m}{k})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>+</mo> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <mfrac> <mi>m</mi> <mi>k</mi> </mfrac> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. We provide additional bounds for small values of m. In particular, we show that for <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1293_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="46" /> </InlineMediaObject> <EquationSource Format="TEX">$m=2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>m</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> the case <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1293_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">$k=1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> is not different from the case without a buffer, while <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1293_Article_IEq4.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">$k=2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> admits an improved competitive ratio.

Semi-online scheduling with non-increasing job sizes and a buffer

期刊论文
出版模式：

开放获取
发表日期：

2025年4月28日

查看全文

Leah Epstein,
Hanan Zebedat-Haider

摘要

This work considers a semi-online version of scheduling on m identical machines, where the objective is to minimize the makespan. In the variant studied here, jobs are presented sorted by non-increasing sizes, and a buffer of size k is available for storing at most k jobs. Every arriving job has to be either placed into the buffer until its assignment, or else it has to be assigned immediately to a machine. We prove a lower bound greater than 1 on the competitive ratio of the problem for any m and any buffer size. To complement this negative result, we design a simple algorithm for any m whose competitive ratio tends to 1 as the buffer size grows. Using those results, we show the best possible competitive ratio is $1+\Theta (\frac{m}{k})$ $1 + Θ (\frac{m}{k})$ . We provide additional bounds for small values of m. In particular, we show that for $m=2$ $m = 2$ the case $k=1$ $k = 1$ is not different from the case without a buffer, while $k=2$ $k = 2$ admits an improved competitive ratio.