Návrh nové implementace metody CPM s lexikografickým uspořádáním hran síťového grafu

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F00%3APU56191" target="_blank" >RIV/00216305:26210/00:PU56191 - 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 lexikografickým uspořádáním hran síťového grafu

Popis výsledku v původním jazyce

Metoda CPM je velmi známým nástrojem k sestavení rozvrhu činností projektu, kde trvání činností a jejich návaznosti jsou známy a zdroje činnostmi nárokované nejsou omezeny. To v praxi téměř nikdy není splněno. Přesto však algoritmus CPM je základem obecnějších metod jako je PERT, řešení problému rozvrhování projektů s omezenými zdroji nebo v řešení problému rozvrhování zakázkové výroby (job shop scheduling) při jeho reprezentaci disjunktivním grafem. Poslední dva problémy jsou NP-těžké a je nutné je řeššit heuristickými metodami. Efektivita výpočtu CPM zde vzhledem k velkému počtu iterací hraje podstatnou roli. Příspěvek navrhuje novou implementaci CPM s lexikografickým uspořádáním hran projektu a dokazuje, že její časová složitost je nižší než u klasických přístupů. Tvrzení je ověřeno na řadě testovacích příkladů.

Název v anglickém jazyce

Proposal of New Implementation of Critical Path Method with Lexicographical Order of Edges of Network Graph

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í

2000

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 konference Project management PRONT 2000

ISBN

80-7082-648-7

ISSN

—

e-ISSN

—

Počet stran výsledku

12

Strana od-do

221-232

Název nakladatele

EVIDA Plzeň

Místo vydání

Mariánské Lázně

Místo konání akce

Mariánské Lázně

Datum konání akce

30. 5. 2000

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

CST - Celostátní akce

Kód UT WoS článku

—