<p>We study an online scheduling problem on <i>m</i> identical parallel batch machines to minimize the maximum flow time, where the batch capacity is unbounded and the flow time of a job is the difference of its completion time and arrival time. Jobs with unit processing times arrive online over time. There are two incompatible job families, where jobs in different families cannot be processed in the same batch. For this problem, we develop a lower bound of competitive ratio and provide a best possible online algorithm with the competitive ratio of <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40305_2025_604_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="52" /> </InlineMediaObject> <EquationSource Format="TEX">$1+\alpha _m$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>+</mo> <msub> <mi>α</mi> <mi>m</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40305_2025_604_Article_IEq3.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="24" /> </InlineMediaObject> <EquationSource Format="TEX">$\alpha _m$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>α</mi> <mi>m</mi> </msub> </math></EquationSource> </InlineEquation> is the positive root of equation <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40305_2025_604_Article_IEq4.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="169" /> </InlineMediaObject> <EquationSource Format="TEX">$\alpha _{m}^2+\left( \lfloor \frac{ m }{2}\rfloor +1\right) \alpha _{m}=1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>α</mi> <mrow> <mi>m</mi> </mrow> <mn>2</mn> </msubsup> <mo>+</mo> <mfenced close=")" open="("> <mo>⌊</mo> <mfrac> <mi>m</mi> <mn>2</mn> </mfrac> <mo>⌋</mo> <mo>+</mo> <mn>1</mn> </mfenced> <msub> <mi>α</mi> <mi>m</mi> </msub> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>.</p>

A Best Possible Algorithm for Online Unbounded Batch Scheduling with Two Incompatible Families to Minimize Maximum Flow Time

期刊论文
发表日期：

2025年6月4日

查看全文

Ran Lin,
Wen-Hua Li,
Xiao Ma,
Sheng-Nan Hu

摘要

We study an online scheduling problem on m identical parallel batch machines to minimize the maximum flow time, where the batch capacity is unbounded and the flow time of a job is the difference of its completion time and arrival time. Jobs with unit processing times arrive online over time. There are two incompatible job families, where jobs in different families cannot be processed in the same batch. For this problem, we develop a lower bound of competitive ratio and provide a best possible online algorithm with the competitive ratio of $1+\alpha _m$ $1 + α_{m}$ , where $\alpha _m$ $α_{m}$ is the positive root of equation $\alpha _{m}^2+\left( \lfloor \frac{ m }{2}\rfloor +1\right) \alpha _{m}=1$ $α_{m}^{2} + (⌊ \frac{m}{2} ⌋ + 1) α_{m} = 1$ .