论文标题
用于预先处理单层实时调度问题的先驱算法
Cutting-plane algorithms for preemptive uniprocessor real-time scheduling problems
论文作者
论文摘要
固定点迭代算法（例如RTA（响应时间分析）和QPA（快速处理器按需分析））可以说是解决预先避免使用的Uniprocessor FP（固定优先级）和EDF（最早的deadline-first）系统的最流行的方法。还针对这些问题提出了几种IP（整数程序）公式，但是尚不清楚解决这些配方的算法是否与RTA和QPA有关。通过发现问题和算法之间的连接，我们表明RTA和QPA实际上是FP和EDF调度性特定IP公式的次优的切割平面算法，其中根据收敛速率定义了最佳性。我们为这些IP配方提出了最佳的切削平面算法。我们将新算法与RTA和QPA进行比较，在大量合成系统中，以评估收敛速率和运行时间的提高。
Fixed-point iteration algorithms like RTA (response time analysis) and QPA (quick processor-demand analysis) are arguably the most popular ways of solving schedulability problems for preemptive uniprocessor FP (fixed-priority) and EDF (earliest-deadline-first) systems. Several IP (integer program) formulations have also been proposed for these problems, but it is unclear whether the algorithms for solving these formulations are related to RTA and QPA. By discovering connections between the problems and the algorithms, we show that RTA and QPA are, in fact, suboptimal cutting-plane algorithms for specific IP formulations of FP and EDF schedulability, where optimality is defined with respect to convergence rate. We propose optimal cutting-plane algorithms for these IP formulations. We compare the new algorithms with RTA and QPA on large collections of synthetic systems to gauge the improvement in convergence rates and running times.
