Návrh nové implementace metody CPM s časovou složitostí O(|V|+|H|+|H|log|H|)

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

čeština

Název v původním jazyce

Návrh nové implementace metody CPM s časovou složitostí O(|V|+|H|+|H|log|H|)

Popis výsledku v původním jazyce

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ů.

Název v anglickém jazyce

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

Popis výsledku anglicky

Critical Path Method (CPM) is well known tool in project scheduling where time duration of activities and their precedence relationships are defined and resource capacities are not limited. In practice it usually is not satisfied. In spite of this, the CPM is a base of more general methods as PERT, solving the Resource Constrained Project Scheduling Problem (RCPSP), and Job Shop Scheduling Problem (JSSP) when it is represented by the disjunctive graph. RCPSP and JSSP are NP-hard problems and therefore iit is necessary to solve them by heuristic methods. Here, with respect to high number of iterations, the effectiveness of the CPM calculations plays a substantial role. This contribution proposes a new implementation of the CPM using a lexicographical ordering of edges in network graphs and shows that its time complexity is lower than the time complexity of classical approaches. This conclusion is verified using the representative class of benchmarks.

Druh

D - Stať ve sborníku

CEP obor

BB - Aplikovaná statistika, operační výzkum

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2001

Kód důvěrnosti údajů

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

Název statě ve sborníku

Sborník referátů semináře DESP 2001 (DESign of Project)

ISBN

80-214-1797-8

ISSN

—

e-ISSN

—

Počet stran výsledku

12

Strana od-do

59-70

Název nakladatele

VUT FSI v Brně

Místo vydání

Brno

Místo konání akce

Brno

Datum konání akce

7. 2. 2001

Typ akce podle státní příslušnosti

CST - Celostátní akce

Kód UT WoS článku

—