Scholarlink

<p>In ordinal scheduling problems, jobs are presented sorted by non-increasing sizes. However, it is not known in advance how many jobs of positive sizes will be presented, and what their exact sizes will be. This information is revealed only when the algorithm terminates. We analyze several variants for this problem with different objectives. The main studied model is where the number of machines <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(m\ge 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>m</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> is also not known in advance, and only an upper bound <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(M\ge m\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>M</mi> <mo>≥</mo> <mi>m</mi> </mrow> </math></EquationSource> </InlineEquation> is given. Jobs have to be partitioned into <i>M</i> inseparable groups called bags, which will be combined by the algorithm afterwards. The bags are to be merged one by one, where merging is applied until the actual number of machines <i>m</i> is reached, and the output consists of the <i>m</i> bags. We analyze this model with respect to maximization of the minimum load. We also discuss a variant where the merging process is based on the knowledge of <i>m</i> but not on job sizes, and we study additional objectives including makespan minimization.</p>

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

Variants and objectives for ordinal scheduling

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年3月24日

查看全文
  • Leah Epstein

摘要

In ordinal scheduling problems, jobs are presented sorted by non-increasing sizes. However, it is not known in advance how many jobs of positive sizes will be presented, and what their exact sizes will be. This information is revealed only when the algorithm terminates. We analyze several variants for this problem with different objectives. The main studied model is where the number of machines \(m\ge 2\) m ≥ 2 is also not known in advance, and only an upper bound \(M\ge m\) M ≥ m is given. Jobs have to be partitioned into M inseparable groups called bags, which will be combined by the algorithm afterwards. The bags are to be merged one by one, where merging is applied until the actual number of machines m is reached, and the output consists of the m bags. We analyze this model with respect to maximization of the minimum load. We also discuss a variant where the merging process is based on the knowledge of m but not on job sizes, and we study additional objectives including makespan minimization.