基于歸約復雜度的有向無環(huán)圖生成方法與實現(xiàn).pdf

1、項目調(diào)度是計算機應(yīng)用的重要領(lǐng)域。項目調(diào)度一般使用有向無環(huán)圖表示，由于有向無環(huán)圖能夠很好地表示出項目調(diào)度中任務(wù)的持續(xù)時間、任務(wù)間的偏序關(guān)系以及任務(wù)間的延遲時間，利用有向無環(huán)圖還可以驗證各種調(diào)度算法的正確性和可行性，因此根據(jù)各種輸入?yún)?shù)正確的生成有向無環(huán)圖是項目調(diào)度領(lǐng)域的重要研究內(nèi)容。本文主要研究了AOA網(wǎng)歸約復雜度的概念和基于歸約復雜度生成AOA網(wǎng)的方法。重點內(nèi)容為： 1.根據(jù)AON網(wǎng)和AOA網(wǎng)的結(jié)點和弧之間不同的概念，提出了AO

2、N網(wǎng)轉(zhuǎn)換成為AOA網(wǎng)的方法。轉(zhuǎn)換后的AOA網(wǎng)不存在虛結(jié)點并具有最小的歸約復雜度。 2.提出了兩種AOA網(wǎng)歸約復雜度的計算方法，分別是定義法和復雜圖最小結(jié)點覆蓋法。相比于定義法，復雜圖最小結(jié)點覆蓋法減少了歸約復雜度計算的時間復雜度。 3.提出并實現(xiàn)了有向無環(huán)圖生成的兩種方法：方法一是根據(jù)任務(wù)數(shù)和結(jié)點最大出度生成有向無環(huán)圖；方法二是根據(jù)給定的歸約復雜度生成AOA網(wǎng)，這種方法是由最小結(jié)點覆蓋的逆過程推導得出的。 4.設(shè)