Scholarlink

<p>The Triangle Scheduling (TS) Problem, defined by Dürr et al. (J Sched 21:305–312, 2018. <a href="https://doi.org/10.1007/s10951-017-0533-1">https://doi.org/10.1007/s10951-017-0533-1</a>), is a geometric model for non-preemptive scheduling of jobs with different criticality levels on a single machine. The jobs have a criticality equal to the worst-case execution time and are scheduled off-line. In this article, we describe, implement and analyze the Bintree algorithm on TS, which is an algorithm based on a binary tree construction. It has <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(O(n\log (n))\)</EquationSource> </InlineEquation> runtime and its approximation ratio is between 1.35 and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(2\ln (2) \approx 1.386\)</EquationSource> </InlineEquation>. Bintree is, therefore, the first polynomial-time approximation algorithm for TS with an approximation ratio below 1.5. We also explore Bintree’s relation to a previously defined algorithm, Greedy, and a potential hybrid algorithm that runs both and chooses the shorter schedule, which we suspect to be better than either algorithm by itself. We analyze the behavior of Bintree on small values of input sizes formalizing its quadratic integer programming model.</p>

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

Computational analysis of a binary tree based algorithm for the triangle scheduling problem

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年5月5日

查看全文
  • János Balogh,
  • József Békési,
  • Nóra Büki,
  • György Dósa,
  • Zsolt Tuza

摘要

The Triangle Scheduling (TS) Problem, defined by Dürr et al. (J Sched 21:305–312, 2018. https://doi.org/10.1007/s10951-017-0533-1), is a geometric model for non-preemptive scheduling of jobs with different criticality levels on a single machine. The jobs have a criticality equal to the worst-case execution time and are scheduled off-line. In this article, we describe, implement and analyze the Bintree algorithm on TS, which is an algorithm based on a binary tree construction. It has \(O(n\log (n))\) runtime and its approximation ratio is between 1.35 and \(2\ln (2) \approx 1.386\) . Bintree is, therefore, the first polynomial-time approximation algorithm for TS with an approximation ratio below 1.5. We also explore Bintree’s relation to a previously defined algorithm, Greedy, and a potential hybrid algorithm that runs both and chooses the shorter schedule, which we suspect to be better than either algorithm by itself. We analyze the behavior of Bintree on small values of input sizes formalizing its quadratic integer programming model.