.png){kind=icon}
.png){kind=icon}
Return
Computational analysis of a binary tree based algorithm for the triangle scheduling problem
.png){kind=icon}
PRE
AI
DOI：10.1007/s00291-026-00857-y.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The Triangle Scheduling (TS) Problem, defined by D & uuml;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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n\log (n))$$\end{document} runtime and its approximation ratio is between 1.35 and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2\ln (2) \approx 1.386$$\end{document}. 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.
Keywords:
Mixed criticality scheduling
Off-line scheduling
Triangle scheduling algorithms
Binary tree
Approximation ratio
Journal
O
IF:
1.9
Papers:
30
Citations:
1.9K