Detail publikace

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

ŠEDA, M.

Český název

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

Anglický název

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

Typ

článek ve sborníku ve WoS nebo Scopus

Jazyk

cs

Originální abstrakt

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

Český abstrakt

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

Anglický abstrakt

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

Klíčová slova anglicky

CPM, time complexity, heuristic

Vydáno

01.09.2000

Nakladatel

EVIDA Plzeň

Místo

Mariánské Lázně

ISBN

80-7082-648-7

Kniha

Sborník konference Project management PRONT 2000

Počet stran

12

BIBTEX


@inproceedings{BUT21011,
  author="Miloš {Šeda},
  title="Návrh nové implementace metody CPM s lexikografickým uspořádáním hran síťového grafu",
  booktitle="Sborník konference Project management PRONT 2000",
  year="2000",
  month="September",
  publisher="EVIDA Plzeň",
  address="Mariánské Lázně",
  isbn="80-7082-648-7"
}