Scholarlink

<p>We consider the problem of energy-efficient scheduling across multiple processors with a power-down mechanism. In this setting a set of <i>n</i> jobs with individual release times, deadlines, and processing volumes must be scheduled across <i>m</i> parallel processors while minimizing the consumed energy. When idle, each processor can be turned off to save energy, while turning it on requires a fixed amount of energy. For the special case of a single processor, the greedy Left-to-Right algorithm [<CitationRef CitationID="CR1">1</CitationRef>] guarantees an approximation factor of 2. We generalize this simple greedy policy to the case of <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2025_10226_Article_IEq1.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="47" /> </InlineMediaObject> <EquationSource Format="TEX">\(m \ge 1\)</EquationSource> </InlineEquation> processors running in parallel and show that the energy costs are still bounded by <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2025_10226_Article_IEq2.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="84" /> </InlineMediaObject> <EquationSource Format="TEX">\(2 {{\,\textrm{OPT}\,}}+ P\)</EquationSource> </InlineEquation>, where <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2025_10226_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="37" /> </InlineMediaObject> <EquationSource Format="TEX">\({{\,\textrm{OPT}\,}}\)</EquationSource> </InlineEquation> is the energy consumed by an optimal solution and <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2025_10226_Article_IEq4.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="76" /> </InlineMediaObject> <EquationSource Format="TEX">\(P &lt; {{\,\textrm{OPT}\,}}\)</EquationSource> </InlineEquation> is the total processing volume. Our algorithm has a running time of <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2025_10226_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="83" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal {O}(n f \log d)\)</EquationSource> </InlineEquation>, where <i>d</i> is the difference between the last deadline and the earliest release time, and <i>f</i> is the running time of a maximum flow calculation in a network of <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2025_10226_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="38" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal {O}(n)\)</EquationSource> </InlineEquation> nodes.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Greedy Minimum-Energy Scheduling

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年6月25日

查看全文
  • Gunther Bidlingmaier

摘要

We consider the problem of energy-efficient scheduling across multiple processors with a power-down mechanism. In this setting a set of n jobs with individual release times, deadlines, and processing volumes must be scheduled across m parallel processors while minimizing the consumed energy. When idle, each processor can be turned off to save energy, while turning it on requires a fixed amount of energy. For the special case of a single processor, the greedy Left-to-Right algorithm [1] guarantees an approximation factor of 2. We generalize this simple greedy policy to the case of \(m \ge 1\) processors running in parallel and show that the energy costs are still bounded by \(2 {{\,\textrm{OPT}\,}}+ P\) , where \({{\,\textrm{OPT}\,}}\) is the energy consumed by an optimal solution and \(P < {{\,\textrm{OPT}\,}}\) is the total processing volume. Our algorithm has a running time of \(\mathcal {O}(n f \log d)\) , where d is the difference between the last deadline and the earliest release time, and f is the running time of a maximum flow calculation in a network of \(\mathcal {O}(n)\) nodes.