Publication detail

Solving Resource-Constrained Project Scheduling Problem As a Sequence of Multi-Knapsack Problems

ŠEDA, M.

Czech title

Řešení problému rozvrhování projektů s omezenými zdroji jako posloupnosti problémů vícekapacitního batohu

English title

Solving Resource-Constrained Project Scheduling Problem As a Sequence of Multi-Knapsack Problems

Type

journal article - other

Language

en

Original abstract

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.

Czech abstract

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

English abstract

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.

Keywords in Czech

problém rozvrhování projektů s omezenými zdroji, problém vícekapacitního batohu

Keywords in English

Resource-Constrained Project Scheduling Problem, Multi-Knapsack Problem

RIV year

2006

Released

01.07.2006

ISSN

1790-0832

Journal

WSEAS Transactions on Information Science and Applications

Volume

3

Number

10

Pages count

7

BIBTEX


@article{BUT43698,
  author="Miloš {Šeda},
  title="Solving Resource-Constrained Project Scheduling Problem As a Sequence of Multi-Knapsack Problems",
  journal="WSEAS Transactions on Information Science and Applications",
  year="2006",
  volume="3",
  number="10",
  month="July",
  issn="1790-0832"
}