偶发实时系统可调度性分析问题的整数规划方法

偶发实时任务最早截止期优先（earliest deadline first，简称EDF）可调度分析是实时系统领域经典的NP困难问题.现有的伪多项式时间判定算法（pseudo-polynomail time decision algorithm，简称PTDA）均局限于利用率U严格小于1的同步任务系统.对于U≤1的同步系统或更加困难的异步系统，现有PTDA则不再适用.针对以上问题，为同步和异步两类实时系统建立了统一的整数规划模型，其规模并不依赖于利用率U的取值.基于多面体理论证明了模型维数和极大诱导不等式，进而提出了同/异步系统上EDF可调度性分析问题统一的多项式时间线性松弛求解方法.实验结果表明，该方法能够获得较紧的问题解下界，在异步和同步系统中，线性松弛解与最优解之间的平均百分界差gap分别为0.78%和1.27%.另外，随机生成了大量同步和异步系统的算例，用于该算法和传统算法进行性能比较.对于同步算例，实验结果表明，在U>0.99时，该算法能够对70%的算例给出判定结果，算法性能与QPA算法相比有指数级提升.对于异步算例，实验结果表明，该算法能够对近96%的算例给出可调度性判定.与传统算法相比，该方法将不能判定可调度性的算例比例平均降低了29.27%.对于剩余的4%的算例，该算法将可调度上界的值平均降低了近10⁴倍.

Integer Programming Approach for Schedulability of Sporadic Real-Time Systems