A New Implementation of the Critical Path Method with O(|V|+|H|+|H|log|H|) Time Complexity

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F01%3APU21382" target="_blank" >RIV/00216305:26210/01:PU21382 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
čeština
Original language name
Návrh nové implementace metody CPM s časovou složitostí O(|V|+|H|+|H|log|H|)
Original language description
Metoda kritická cesty (CPM) je známým nástrojem projektového řízení k sestavení optimálního rozvrhu činností, kdy jejich doby trvání a precedenční vztahy jsou známy a kapacity zdrojů nejsou omezeny. V praxi tyto předpoklady obvykle nejsou splněny. Idealizovaná verze metody je však základem složitějších algoritmů pro rozvrhování projektů s omezenými zdroji (Resource Constrained Project Scheduling) a také v rozvrhování zakázkové výroby (Job Shop Scheduling, JSS), je-li problém JSS reprezentován disjunktníím grafem. Obě tyto úlohy patří mezi NP-úplné problémy a je nutné je řešit heuristicky. Počet iterací pro větší instance ůloh dosahuje desítky tisíc iterací, a tak je časová složitost algoritmu CPM pro trvání výpočtu podstatná. Příspěvek navrhuje novou implementaci CPM založenou na lexikografickém uspořádání hran síťového grafu a ukazuje, že časová složitost této implementace je nižší než u klasických přístupů. Tento závěr je ověřen na reprezentativní třídě testovacích příkladů.
Czech name
Návrh nové implementace metody CPM s časovou složitostí O(|V|+|H|+|H|log|H|)
Czech description
—

Publication year
2001
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Sborník referátů semináře DESP 2001 (DESign of Project)
ISBN
80-214-1797-8
ISSN
—
e-ISSN
—
Number of pages
12
Pages from-to
59-70
Publisher name
VUT FSI v Brně
Place of publication
Brno
Event location
Brno
Event date
Feb 7, 2001
Type of event by nationality
CST - Celostátní akce
UT code for WoS article
—

Similar results(10)