  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.
