在旋风调度问题中，每个任务 $i$ 关联一个正整数 $a_i$，称为其周期。我们的目标是每天调度一个任务，以确保每个任务 $i$ 至少在每 $a_i$ 天内执行一次。可调度性的一个显然必要条件是密度，即执行率之和 $\sum \frac{1}{a_i}$，不超过 $1$。我们证明了所有密度不超过 $\frac{5}{6}$ 的实例都是可调度的，这一结论最早是由 Chan 和 Chin 在 1993 年提出的猜想。
与已知部分进展类似，我们的证明涉及对大量有限实例的计算机搜索。我们将问题推广到适当的分数（非整数）周期，这是我们减少到这些有限案例的关键思路。
通过这些思路，我们还获得了一个简单的证明，表明每个具有两个不同周期且密度最多为 $1$ 的实例是可调度的，并且为竹园修剪问题提供了一种快速算法，近似比为 $\frac{4}{3}$。
博主点评： 本文不仅证明了密度阈值猜想，还通过计算机搜索的方法展示了调度问题的复杂性。将问题推广到分数周期的思路非常巧妙，为进一步研究提供了新的视角，尤其是在算法设计方面的应用潜力值得关注。