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

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

conference paper

cs

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

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

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.

CPM, time complexity, heuristic

01.09.2000

EVIDA Plzeň

Mariánské Lázně

80-7082-648-7

Sborník konference Project management PRONT 2000

12