A Contribution to Time Complexity of CPM-Based Problems

Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
A Contribution to Time Complexity of CPM-Based Problems
Original language description
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.
Czech name
—
Czech description
—

Publication year
2006
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Book/collection name
Katalinic, B. (ed.): DAAAM International Scientific Book 2006
ISBN
3-901509-47-X
Number of pages of the result
10
Pages from-to
—
Number of pages of the book
684
Publisher name
DAAAM International
Place of publication
Wien (Austria)
UT code for WoS chapter
—

Similar results(10)