A Contribution to Time Complexity of CPM-Based Problems

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F06%3APU63357" target="_blank" >RIV/00216305:26210/06:PU63357 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

A Contribution to Time Complexity of CPM-Based Problems

Popis výsledku v původním jazyce

Critical Path Method (CPM) is a 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, this is usually not satisfied. In spite of this,the CPM serves as a base for more general methods such as PERT, solving the Resource Constrained Project Scheduling Problem (RCPSP), and Job Shop Scheduling Problem (JSSP) when it is represented by a disjunctive graph. RCPSP and JSSP are NP-hard problemsand therefore it is necessary to solve them by heuristic methods. Here, with respect to the high number of iterations, the effectiveness of the CPM calculations plays a substantial role. This contribution proposes a new implementation of the CPM using alexicographical ordering of edges in network graphs and shows that its time complexity is lower than that of classical approaches. This conclusion is verified using a representative sample of benchmarks.

Název v anglickém jazyce

A Contribution to Time Complexity of CPM-Based Problems

Popis výsledku anglicky

Critical Path Method (CPM) is a 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, this is usually not satisfied. In spite of this,the CPM serves as a base for more general methods such as PERT, solving the Resource Constrained Project Scheduling Problem (RCPSP), and Job Shop Scheduling Problem (JSSP) when it is represented by a disjunctive graph. RCPSP and JSSP are NP-hard problemsand therefore it is necessary to solve them by heuristic methods. Here, with respect to the high number of iterations, the effectiveness of the CPM calculations plays a substantial role. This contribution proposes a new implementation of the CPM using alexicographical ordering of edges in network graphs and shows that its time complexity is lower than that of classical approaches. This conclusion is verified using a representative sample of benchmarks.

Druh

C - Kapitola v odborné knize

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í

2006

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 knihy nebo sborníku

Katalinic, B. (ed.): DAAAM International Scientific Book 2006

ISBN

3-901509-47-X

Počet stran výsledku

10

Strana od-do

—

Počet stran knihy

684

Název nakladatele

DAAAM International

Místo vydání

Wien (Austria)

Kód UT WoS kapitoly

—