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

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

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