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

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

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.

Original languageEnglish
Title of host publicationAnalysis of Images, Social Networks and Texts - 9th International Conference, AIST 2020, Revised Selected Papers
EditorsWil 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
PublisherSpringer Science and Business Media Deutschland GmbH
Pages407-420
Number of pages14
ISBN (Print)9783030726096
DOIs
Publication statusPublished - 2021
Event9th International Conference on Analysis of Images, Social Networks and Texts, AIST 2020 - Moscow, Russian Federation
Duration: 15 Oct 202016 Oct 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12602 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th International Conference on Analysis of Images, Social Networks and Texts, AIST 2020
Country/TerritoryRussian Federation
CityMoscow
Period15.10.202016.10.2020

Keywords

  • Cumulative resources
  • Lower bound
  • Project management
  • PSPLIB
  • Renewable resources
  • Resource-constrained project scheduling problem

OECD FOS+WOS

  • 1.02 COMPUTER AND INFORMATION SCIENCES
  • 1.01 MATHEMATICS

Fingerprint

Dive into the research topics of 'Lower Bound Polynomial Fast Procedure for the Resource-Constrained Project Scheduling Problem Tested on PSPLIB Instances'. Together they form a unique fingerprint.

Cite this