Standard

Lower Bound Polynomial Fast Procedure for the Resource-Constrained Project Scheduling Problem Tested on PSPLIB Instances. / Gimadi, E. Kh; Goncharov, E. N.; Shtepa, A. A.

Analysis of Images, Social Networks and Texts - 9th International Conference, AIST 2020, Revised Selected Papers. ed. / Wil M. van der Aalst; Vladimir Batagelj; Dmitry I. Ignatov; Michael Khachay; Olessia Koltsova; Andrey Kutuzov; Sergei O. Kuznetsov; Irina A. Lomazova; Natalia Loukachevitch; Amedeo Napoli; Alexander Panchenko; Panos M. Pardalos; Marcello Pelillo; Andrey V. Savchenko; Elena Tutubalina. Springer Science and Business Media Deutschland GmbH, 2021. p. 407-420 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12602 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Gimadi, EK, Goncharov, EN & Shtepa, AA 2021, Lower Bound Polynomial Fast Procedure for the Resource-Constrained Project Scheduling Problem Tested on PSPLIB Instances. in WM van der Aalst, V Batagelj, DI Ignatov, M Khachay, O Koltsova, A Kutuzov, SO Kuznetsov, IA Lomazova, N Loukachevitch, A Napoli, A Panchenko, PM Pardalos, M Pelillo, AV Savchenko & E Tutubalina (eds), Analysis of Images, Social Networks and Texts - 9th International Conference, AIST 2020, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12602 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 407-420, 9th International Conference on Analysis of Images, Social Networks and Texts, AIST 2020, Moscow, Russian Federation, 15.10.2020. https://doi.org/10.1007/978-3-030-72610-2_31

APA

Gimadi, E. K., Goncharov, E. N., & Shtepa, A. A. (2021). Lower Bound Polynomial Fast Procedure for the Resource-Constrained Project Scheduling Problem Tested on PSPLIB Instances. In W. M. van der Aalst, V. Batagelj, D. I. Ignatov, M. Khachay, O. Koltsova, A. Kutuzov, S. O. Kuznetsov, I. A. Lomazova, N. Loukachevitch, A. Napoli, A. Panchenko, P. M. Pardalos, M. Pelillo, A. V. Savchenko, & E. Tutubalina (Eds.), Analysis of Images, Social Networks and Texts - 9th International Conference, AIST 2020, Revised Selected Papers (pp. 407-420). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12602 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-72610-2_31

Vancouver

Gimadi EK, Goncharov EN, Shtepa AA. Lower Bound Polynomial Fast Procedure for the Resource-Constrained Project Scheduling Problem Tested on PSPLIB Instances. In van der Aalst WM, Batagelj V, Ignatov DI, Khachay M, Koltsova O, Kutuzov A, Kuznetsov SO, Lomazova IA, Loukachevitch N, Napoli A, Panchenko A, Pardalos PM, Pelillo M, Savchenko AV, Tutubalina E, editors, Analysis of Images, Social Networks and Texts - 9th International Conference, AIST 2020, Revised Selected Papers. Springer Science and Business Media Deutschland GmbH. 2021. p. 407-420. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-72610-2_31

Author

Gimadi, E. Kh ; Goncharov, E. N. ; Shtepa, A. A. / Lower Bound Polynomial Fast Procedure for the Resource-Constrained Project Scheduling Problem Tested on PSPLIB Instances. Analysis of Images, Social Networks and Texts - 9th International Conference, AIST 2020, Revised Selected Papers. editor / Wil M. van der Aalst ; Vladimir Batagelj ; Dmitry I. Ignatov ; Michael Khachay ; Olessia Koltsova ; Andrey Kutuzov ; Sergei O. Kuznetsov ; Irina A. Lomazova ; Natalia Loukachevitch ; Amedeo Napoli ; Alexander Panchenko ; Panos M. Pardalos ; Marcello Pelillo ; Andrey V. Savchenko ; Elena Tutubalina. Springer Science and Business Media Deutschland GmbH, 2021. pp. 407-420 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{acf0050f0787463bb8ce0a6d5e75c1e8,
title = "Lower Bound Polynomial Fast Procedure for the Resource-Constrained Project Scheduling Problem Tested on PSPLIB Instances",
abstract = "We consider the Resource-Constrained Project Scheduling Problem (RCPSP) with respect to the makespan minimization criterion. The problem accounts for technological constraints of activities precedence together with resource constraints. No activity preemption is allowed. We consider relaxation of RCPSP with special types of non-renewable resources to get a lower bound of the problem. We present new lower bound algorithm for the RCPSP with time complexity depending on the number of activities n as O(nlog n), and we test it on PSPLIB instances. Numerical experiments demonstrate that the proposed algorithm produces on some series of instances lower bounds very close to the best existing lower bounds published in the PSPLIB, while their calculation time is a fraction of a second. We get especially good marks for large-sized instances.",
keywords = "Cumulative resources, Lower bound, Project management, PSPLIB, Renewable resources, Resource-constrained project scheduling problem",
author = "Gimadi, {E. Kh} and Goncharov, {E. N.} and Shtepa, {A. A.}",
note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.; 9th International Conference on Analysis of Images, Social Networks and Texts, AIST 2020 ; Conference date: 15-10-2020 Through 16-10-2020",
year = "2021",
doi = "10.1007/978-3-030-72610-2_31",
language = "English",
isbn = "9783030726096",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "407--420",
editor = "{van der Aalst}, {Wil M.} and Vladimir Batagelj and Ignatov, {Dmitry I.} and Michael Khachay and Olessia Koltsova and Andrey Kutuzov and Kuznetsov, {Sergei O.} and Lomazova, {Irina A.} and Natalia Loukachevitch and Amedeo Napoli and Alexander Panchenko and Pardalos, {Panos M.} and Marcello Pelillo and Savchenko, {Andrey V.} and Elena Tutubalina",
booktitle = "Analysis of Images, Social Networks and Texts - 9th International Conference, AIST 2020, Revised Selected Papers",
address = "Germany",

}

RIS

TY - GEN

T1 - Lower Bound Polynomial Fast Procedure for the Resource-Constrained Project Scheduling Problem Tested on PSPLIB Instances

AU - Gimadi, E. Kh

AU - Goncharov, E. N.

AU - Shtepa, A. A.

N1 - Publisher Copyright: © 2021, Springer Nature Switzerland AG. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.

PY - 2021

Y1 - 2021

N2 - We consider the Resource-Constrained Project Scheduling Problem (RCPSP) with respect to the makespan minimization criterion. The problem accounts for technological constraints of activities precedence together with resource constraints. No activity preemption is allowed. We consider relaxation of RCPSP with special types of non-renewable resources to get a lower bound of the problem. We present new lower bound algorithm for the RCPSP with time complexity depending on the number of activities n as O(nlog n), and we test it on PSPLIB instances. Numerical experiments demonstrate that the proposed algorithm produces on some series of instances lower bounds very close to the best existing lower bounds published in the PSPLIB, while their calculation time is a fraction of a second. We get especially good marks for large-sized instances.

AB - We consider the Resource-Constrained Project Scheduling Problem (RCPSP) with respect to the makespan minimization criterion. The problem accounts for technological constraints of activities precedence together with resource constraints. No activity preemption is allowed. We consider relaxation of RCPSP with special types of non-renewable resources to get a lower bound of the problem. We present new lower bound algorithm for the RCPSP with time complexity depending on the number of activities n as O(nlog n), and we test it on PSPLIB instances. Numerical experiments demonstrate that the proposed algorithm produces on some series of instances lower bounds very close to the best existing lower bounds published in the PSPLIB, while their calculation time is a fraction of a second. We get especially good marks for large-sized instances.

KW - Cumulative resources

KW - Lower bound

KW - Project management

KW - PSPLIB

KW - Renewable resources

KW - Resource-constrained project scheduling problem

UR - http://www.scopus.com/inward/record.url?scp=85104756010&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-72610-2_31

DO - 10.1007/978-3-030-72610-2_31

M3 - Conference contribution

AN - SCOPUS:85104756010

SN - 9783030726096

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 407

EP - 420

BT - Analysis of Images, Social Networks and Texts - 9th International Conference, AIST 2020, Revised Selected Papers

A2 - van der Aalst, Wil M.

A2 - Batagelj, Vladimir

A2 - Ignatov, Dmitry I.

A2 - Khachay, Michael

A2 - Koltsova, Olessia

A2 - Kutuzov, Andrey

A2 - Kuznetsov, Sergei O.

A2 - Lomazova, Irina A.

A2 - Loukachevitch, Natalia

A2 - Napoli, Amedeo

A2 - Panchenko, Alexander

A2 - Pardalos, Panos M.

A2 - Pelillo, Marcello

A2 - Savchenko, Andrey V.

A2 - Tutubalina, Elena

PB - Springer Science and Business Media Deutschland GmbH

T2 - 9th International Conference on Analysis of Images, Social Networks and Texts, AIST 2020

Y2 - 15 October 2020 through 16 October 2020

ER -

ID: 28470819