RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskretn. Anal. Issled. Oper., 2014, Volume 21, Number 3, Pages 11–24 (Mi da772)  

This article is cited in 1 scientific paper (total in 1 paper)

A stochastic greedy algorithm for the resource-constrained project scheduling problem

E. N. Goncharov

S. L. Sobolev Institute of Mathematics, SB RAS, 4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia

Abstract: We consider the resource constrained project scheduling problem (RCPSP) with precedence and resource constraints. All resources are renewable and the objective is to find a schedule that meets all resource and precedence constraints and minimizes the makespan. We propose a fast stochastic algorithm developed by the greedy algorithm based on deterministic solutions to this problem with the low-time complexity. Quality of this algorithm has been analyzed in a number of computational experiments with the standard sets J60 and J120 for the RCPSP from the PSPLIB [23]. The proposed algorithm takes some of the best positions among greedy algorithms and showed the best result on the set J60 from PSPLIB with the limit of schedules 50000. It is competitive among all the algorithms being second only to genetic algorithms and to combined ones based on them. Ill. 1, tab. 4, bibliogr. 33.

Keywords: resource constrained project scheduling problem, limited resource, renewable resource, heuristic algorithm.

Full text: PDF file (276 kB)
References: PDF file   HTML file

Bibliographic databases:
UDC: 519.8
Received: 30.08.2013
Revised: 29.01.2014

Citation: E. N. Goncharov, “A stochastic greedy algorithm for the resource-constrained project scheduling problem”, Diskretn. Anal. Issled. Oper., 21:3 (2014), 11–24

Citation in format AMSBIB
\Bibitem{Gon14}
\by E.~N.~Goncharov
\paper A stochastic greedy algorithm for the resource-constrained project scheduling problem
\jour Diskretn. Anal. Issled. Oper.
\yr 2014
\vol 21
\issue 3
\pages 11--24
\mathnet{http://mi.mathnet.ru/da772}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3242099}


Linking options:
  • http://mi.mathnet.ru/eng/da772
  • http://mi.mathnet.ru/eng/da/v21/i3/p11

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. E. N. Goncharov, V. V. Leonov, “Genetic algorithm for the resource-constrained project scheduling problem”, Autom. Remote Control, 78:6 (2017), 1101–1114  mathnet  crossref  mathscinet  isi  elib
  • Дискретный анализ и исследование операций
    Number of views:
    This page:337
    Full text:95
    References:39
    First page:29

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020