Detail publikace

A New Implementation of the Critical Path Method Using Lexicographical Ordering of Edges

ŠEDA, M.

Anglický název

A New Implementation of the Critical Path Method Using Lexicographical Ordering of Edges

Typ

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

Jazyk

en

Originální 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.

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, PERT, time complexity, lexicographical ordering

Rok RIV

2001

Vydáno

05.05.2001

Nakladatel

MARQ Ostrava

Místo

Ostrava

ISBN

80-85988-57-7

Kniha

Proceedings of the 35th Spring International Conference Modelling and Simulation of Systems MOSIS '01

Počet stran

6

BIBTEX


@inproceedings{BUT6611,
  author="Miloš {Šeda},
  title="A New Implementation of the Critical Path Method Using Lexicographical Ordering of Edges",
  booktitle="Proceedings of the 35th Spring International Conference Modelling and Simulation of Systems MOSIS '01",
  year="2001",
  month="May",
  publisher="MARQ Ostrava",
  address="Ostrava",
  isbn="80-85988-57-7"
}