Publication detail

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

ŠEDA, M.

Original Title

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

English Title

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

Type

conference paper

Language

Czech

Original Abstract

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

English abstract

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.

Key words in English

CPM, time complexity, heuristic

Authors

ŠEDA, M.

Released

1. 9. 2000

Publisher

EVIDA Plzeň

Location

Mariánské Lázně

ISBN

80-7082-648-7

Book

Sborník konference Project management PRONT 2000

Pages from

221

Pages to

232

Pages count

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",
  pages="12",
  publisher="EVIDA Plzeň",
  address="Mariánské Lázně",
  isbn="80-7082-648-7"
}