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

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

Аннотация

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.

Язык оригиналаанглийский
Название основной публикацииAnalysis of Images, Social Networks and Texts - 9th International Conference, AIST 2020, Revised Selected Papers
Редакторы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
Страницы407-420
Число страниц14
ISBN (печатное издание)9783030726096
DOI
СостояниеОпубликовано - 2021
Событие9th International Conference on Analysis of Images, Social Networks and Texts, AIST 2020 - Moscow, Российская Федерация
Продолжительность: 15 окт 202016 окт 2020

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том12602 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция9th International Conference on Analysis of Images, Social Networks and Texts, AIST 2020
СтранаРоссийская Федерация
ГородMoscow
Период15.10.202016.10.2020

Предметные области OECD FOS+WOS

  • 1.02 КОМПЬЮТЕРНЫЕ И ИНФОРМАЦИОННЫЕ НАУКИ
  • 1.01 МАТЕМАТИКА

Fingerprint

Подробные сведения о темах исследования «Lower Bound Polynomial Fast Procedure for the Resource-Constrained Project Scheduling Problem Tested on PSPLIB Instances». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать