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

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: A New Implementation of the Critical Path Method with O(|V|+|H|+|H|log|H|) Time Complexity Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	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. (en) 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ů.
Title	A New Implementation of the Critical Path Method with O(\|V\|+\|H\|+\|H\|log\|H\|) Time Complexity (en) Návrh nové implementace metody CPM s časovou složitostí O(\|V\|+\|H\|+\|H\|log\|H\|) Návrh nové implementace metody CPM s časovou složitostí O(\|V\|+\|H\|+\|H\|log\|H\|) (cs)
skos:prefLabel	A New Implementation of the Critical Path Method with O(\|V\|+\|H\|+\|H\|log\|H\|) Time Complexity (en) Návrh nové implementace metody CPM s časovou složitostí O(\|V\|+\|H\|+\|H\|log\|H\|) Návrh nové implementace metody CPM s časovou složitostí O(\|V\|+\|H\|+\|H\|log\|H\|) (cs)
skos:notation	RIV/00216305:26210/01:PU21382!RIV/2002/MSM/262102/N
http://linked.open.../vavai/riv/strany	59-70
http://linked.open...avai/riv/aktivita	Z
http://linked.open...avai/riv/aktivity	Z(MSM 261100009)
http://linked.open...vai/riv/dodaniDat	2002
http://linked.open...aciTvurceVysledku	Šeda, Miloš
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Vysoké učení technické v Brně / Fakulta strojního inženýrství
http://linked.open...dnocenehoVysledku	688322
http://linked.open...ai/riv/idVysledku	RIV/00216305:26210/01:PU21382
http://linked.open...riv/jazykVysledku	cze - čeština
http://linked.open.../riv/klicovaSlova	CPM, PERT, time complexity, lexicographical ordering (en)
http://linked.open.../riv/klicoveSlovo	PERT lexicographical ordering time complexity CPM
http://linked.open...ontrolniKodProRIV	[A1EE81B3D5F9]
http://linked.open...v/mistoKonaniAkce	Brno
http://linked.open...i/riv/mistoVydani	Brno
http://linked.open...i/riv/nazevZdroje	Sborník referátů semináře DESP 2001 (DESign of Project)
http://linked.open...in/vavai/riv/obor	BB
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	1 (xsd:int)
http://linked.open...ocetUcastnikuAkce	0 (xsd:int)
http://linked.open...nichUcastnikuAkce	0 (xsd:int)
http://linked.open...UplatneniVysledku	2001
http://linked.open...iv/tvurceVysledku	Šeda, Miloš
http://linked.open...vavai/riv/typAkce	CST - Celostátní
http://linked.open.../riv/zahajeniAkce	2001-02-07 (xsd:date)
http://linked.open...n/vavai/riv/zamer	http://linked.opendata.cz/resource/domain/vavai/zamer/MSM%20261100009
number of pages	12 (xsd:int)
http://purl.org/ne...btex#hasPublisher	Vysoké učení technické v Brně. Fakulta strojního inženýrství
https://schema.org/isbn	80-214-1797-8
http://localhost/t...ganizacniJednotka	26210

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 107 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software