Detail publikace
Řešení problému rozvrhování projektů s omezenými zdroji jako posloupnosti problémů vícekapacitního batohu
ŠEDA, M.
Český název
Řešení problému rozvrhování projektů s omezenými zdroji jako posloupnosti problémů vícekapacitního batohu
Anglický název
Solving Resource-Constrained Project Scheduling Problem As a Sequence of Multi-Knapsack Problems
Typ
článek ve sborníku ve WoS nebo Scopus
Jazyk
en
Originální abstrakt
This paper describes a new technique for solving the duration minimization in a resource-constrained network. It is based on a transformation of the resource-constrained project scheduling problem (RCPSP) to a sequence of (multi)knapsack problem (MKP) solutions. In the first part, three deterministic approaches are summarized and their time complexity is discussed. Due to the combinatorial nature of the problem for large projects with many constraints, heuristic techniques are applied. A genetic algorithm approach is proposed and compared with simulated annealing.
Český abstrakt
Příspěvek popisuje novou techniku pro výpočet minimální doby trvání projektu v síti s omezenými zdroji. Je založena na transformaci problému rozvrhování projektů s omezenými zdroji na posloupnost řešení problémů vícekapacitního batohu. V první části jsou shrnuty tři deterministické přístupy a je diskutována jejich časová složitost. Vzhledem ke kombinatorické povaze problému jsou pro projekty velkého rozsahu použity heuristické metody. Jsou navrženy přístupy využívající genetický algoritmus a simulované žíhání a provedeno jejich srovnání.
Anglický abstrakt
This paper describes a new technique for solving the duration minimization in a resource-constrained network. It is based on a transformation of the resource-constrained project scheduling problem (RCPSP) to a sequence of (multi)knapsack problem (MKP) solutions. In the first part, three deterministic approaches are summarized and their time complexity is discussed. Due to the combinatorial nature of the problem for large projects with many constraints, heuristic techniques are applied. A genetic algorithm approach is proposed and compared with simulated annealing.
Klíčová slova česky
problém rozvrhování projektů s omezenými zdroji, problém vícekapacitního batohu
Klíčová slova anglicky
Resource-Constrained Project Scheduling Problem, Multi-Knapsack Problem
Rok RIV
2006
Vydáno
01.07.2006
Nakladatel
WSEAS
Místo
Athens
ISBN
960-8457-47-5
Kniha
Proceedings of the 10th WSEAS International Conference on Computers
Počet stran
7
BIBTEX
@inproceedings{BUT20352,
author="Miloš {Šeda},
title="Solving Resource-Constrained Project Scheduling Problem As a Sequence of Multi-Knapsack Problems",
booktitle="Proceedings of the 10th WSEAS International Conference on Computers",
year="2006",
month="July",
publisher="WSEAS",
address="Athens",
isbn="960-8457-47-5"
}