OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

An efficient pseudo-polynomial algorithm for finding a lower bound on the makespan for the Resource Constrained Project Scheduling Problem

Arkhipov, Dmitry I. and Battaïa, Olga and Lazarev, Alexander A. An efficient pseudo-polynomial algorithm for finding a lower bound on the makespan for the Resource Constrained Project Scheduling Problem. (2019) European Journal of Operational Research, 275 (1). 35-44. ISSN 0377-2217

[img]
Preview
(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
1MB

Official URL: https://doi.org/10.1016/j.ejor.2018.11.005

Abstract

Several algorithms for finding a lower bound on the makespan for the Resource Constrained Project Scheduling Problem (RCPSP) were proposed in the literature. However, fast computable lower bounds usually do not provide the best estimations and the methods that obtain better bounds are mainly based on the cooperation between linear and constraint programming and therefore are time-consuming. In this paper, a new pseudo-polynomial algorithm is proposed to find a makespan lower bound for RCPSP with time-dependent resource capacities. Its idea is based on a consecutive evaluation of pairs of resources and their cumulated workload. Using the proposed algorithm, several bounds for the PSPLIB benchmark were improved. The results for industrial applications are also presented where the algorithm could provide good bounds even for very large problem instances.

Item Type:Article
HAL Id:hal-02002548
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:Université de Toulouse > Institut Supérieur de l'Aéronautique et de l'Espace - ISAE-SUPAERO (FRANCE)
Other partners > Moscow Institute of Physics and Technology - MIPT (RUSSIA)
Other partners > Lomonosov Moscow State University - MSU (RUSSIA)
Other partners > Trapeznikov Institute of Control Sciences (RUSSIA)
Other partners > National Research University Higher School of Economics (RUSSIA)
Laboratory name:
Statistics:download
Deposited By: Olga Battaïa
Deposited On:31 Jan 2019 16:24

Repository Staff Only: item control page