We study sublinear time algorithms for the classical makespan minimization problem of scheduling n jobs on m parallel machines. Under uniform random sampling setting, we consider the problem with constrained processing times, which remains NP-hard. We first consider the problem where the processing times of all jobs differ by no more than a constant factor c. We develop the first sublinear time approximation scheme for this problem when the number of machines m is at most <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="186_2025_898_Article_IEq1.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="20" /> </InlineMediaObject> <EquationSource Format="TEX">\(\tfrac{n \epsilon }{20 c }\)</EquationSource> </InlineEquation>. We then extend our algorithm to the more general problem where the largest <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="186_2025_898_Article_IEq2.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="24" /> </InlineMediaObject> <EquationSource Format="TEX">\(\alpha n\)</EquationSource> </InlineEquation> jobs have processing times that differ by no more than c factor for some constant <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="186_2025_898_Article_IEq3.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="14" /> </InlineMediaObject> <EquationSource Format="TEX">\(\alpha \)</EquationSource> </InlineEquation>, <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="186_2025_898_Article_IEq4.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="74" /> </InlineMediaObject> <EquationSource Format="TEX">\(0 < \alpha \le 1\)</EquationSource> </InlineEquation>. When <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="186_2025_898_Article_IEq5.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="63" /> </InlineMediaObject> <EquationSource Format="TEX">\(m \le \tfrac{ \alpha n \epsilon }{20 c^2 }\)</EquationSource> </InlineEquation>, our algorithm is a randomized <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="186_2025_898_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="49" /> </InlineMediaObject> <EquationSource Format="TEX">\((1+\epsilon )\)</EquationSource> </InlineEquation>-approximation scheme that runs in sublinear time. We further generalize our algorithms to the scheduling problems with precedence constraints where the precedence graph has a bounded depth h. Our work not only provides an algorithmic solution to the studied scheduling problem under big data environment, but also gives a methodological framework for designing sublinear time approximation algorithms for other scheduling problems.

Sublinear time approximation schemes for makespan minimization on parallel machines

期刊论文
发表日期：

2025年6月1日

查看全文

Bin Fu,
Yumei Huo,
Hairong Zhao

摘要

We study sublinear time algorithms for the classical makespan minimization problem of scheduling n jobs on m parallel machines. Under uniform random sampling setting, we consider the problem with constrained processing times, which remains NP-hard. We first consider the problem where the processing times of all jobs differ by no more than a constant factor c. We develop the first sublinear time approximation scheme for this problem when the number of machines m is at most \(\tfrac{n \epsilon }{20 c }\) . We then extend our algorithm to the more general problem where the largest \(\alpha n\) jobs have processing times that differ by no more than c factor for some constant \(\alpha \) , \(0 < \alpha \le 1\) . When \(m \le \tfrac{ \alpha n \epsilon }{20 c^2 }\) , our algorithm is a randomized \((1+\epsilon )\) -approximation scheme that runs in sublinear time. We further generalize our algorithms to the scheduling problems with precedence constraints where the precedence graph has a bounded depth h. Our work not only provides an algorithmic solution to the studied scheduling problem under big data environment, but also gives a methodological framework for designing sublinear time approximation algorithms for other scheduling problems.