Computational analysis of a binary tree based algorithm for the triangle scheduling problem
研究并实现了一种基于二叉树构造的Bintree算法，用于解决单机非抢占式作业调度问题，该算法运行时间为O(n log n)，近似比在1.35到1.386之间，是首个近似比低于1.5的多项式时间算法。
Abstract 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.