偶發(fā)實時任務(wù)最早截止期優(yōu)先（earliest deadline first，簡稱EDF）可調(diào)度分析是實時系統(tǒng)領(lǐng)域經(jīng)典的NP困難問題．現(xiàn)有的偽多項式時間判定算法（pseudo-polynomail time decision algorithm，簡稱PTDA）均局限于利用率U嚴格小于1的同步任務(wù)系統(tǒng)．對于U≤1的同步系統(tǒng)或更加困難的異步系統(tǒng)，現(xiàn)有PTDA則不再適用．針對以上問題，為同步和異步兩類實時系統(tǒng)建立了統(tǒng)一的整數(shù)規(guī)劃模型，其規(guī)模并不依賴于利用率U的取值．基于多面體理論證明了模型維數(shù)和極大誘導不等式，進而提出了同／異步系統(tǒng)上EDF可調(diào)度性分析問題統(tǒng)一的多項式時間線性松弛求解方法．實驗結(jié)果表明，該方法能夠獲得較緊的問題解下界，在異步和同步系統(tǒng)中，線性松弛解與最優(yōu)解之間的平均百分界差gap分別為0.78%和1.27%．另外，隨機生成了大量同步和異步系統(tǒng)的算例，用于該算法和傳統(tǒng)算法進行性能比較．對于同步算例，實驗結(jié)果表明，在U>0.99時，該算法能夠?qū)?0%的算例給出判定結(jié)果，算法性能與QPA算法相比有指數(shù)級提升．對于異步算例，實驗結(jié)果表明，該算法能夠?qū)?6%的算例給出可調(diào)度性判定．與傳統(tǒng)箅法相比，該方法將不能判定可調(diào)度性的算例比例平均降低了29.27%．對于剩余的4%的算例，該算法將可調(diào)度上界的值平均降低了近10-4倍．
?