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