期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 275, 期 1, 页码 35-44出版社
ELSEVIER
DOI: 10.1016/j.ejor.2018.11.005
关键词
Project scheduling; Scheduling; RCPSP; Lower bounds; Pseudo-polynomial algorithms
资金
- Russian Foundation for Basic Research [18-37-00295 mol_a]
- Foundation of ISAE-SUPAERO
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. (C) 2018 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据