Proposal of New Implementation of Critical Path Method with Lexicographical Order of Edges of Network Graph
The result's identifiers
Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
čeština
Original language name
Návrh nové implementace metody CPM s lexikografickým uspořádáním hran síťového grafu
Original language description
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ů.
Czech name
Návrh nové implementace metody CPM s lexikografickým uspořádáním hran síťového grafu
Czech description
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ů.
Classification
Type
D - Article in proceedings
CEP classification
BB - Applied statistics, operational research
OECD FORD branch
—
Result continuities
Project
—
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2000
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Sborník konference Project management PRONT 2000
ISBN
80-7082-648-7
ISSN
—
e-ISSN
—
Number of pages
12
Pages from-to
221-232
Publisher name
EVIDA Plzeň
Place of publication
Mariánské Lázně
Event location
Mariánské Lázně
Event date
May 30, 2000
Type of event by nationality
CST - Celostátní akce
UT code for WoS article
—