Minimizing the completion time of a project under resource constraints and feeding precedence relations: an exact algorithm

In this paper we study an extension of the Resource-Constrained Project Scheduling Problem (RCPSP) with minimum makespan objective by introducing a special type of precedence constraints called “Feeding Precedences” (FP). To the best of our knowledge no exact algorithm exists for this problem. Explo...

Full description

Saved in:
Bibliographic Details
Published in:4OR 2012-12, Vol.10 (4), p.361-377
Main Authors: Bianco, Lucio, Caramia, Massimiliano
Format: Article
Language:English
Subjects:
Algorithms
Business and Management
Completion time
Industrial and Production Engineering
Lower bounds
Mathematical models
Operations research
Operations Research/Decision Theory
Optimization
Precedence constraints
Production planning
Project management
Research Paper
Resource scheduling
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we study an extension of the Resource-Constrained Project Scheduling Problem (RCPSP) with minimum makespan objective by introducing a special type of precedence constraints called “Feeding Precedences” (FP). To the best of our knowledge no exact algorithm exists for this problem. Exploiting the lower bound and the mathematical formulation proposed in Bianco and Caramia (4OR 9(4):371–389 2011 ) for the RCPSP with FP, in this paper we propose an exact algorithm based on branch and bound rules. A computational experimentation on randomly generated instances and a comparison with the results achieved by a commercial solver, show that the proposed approach is able to behave satisfactorily.
ISSN:1619-4500
1614-2411
DOI:10.1007/s10288-012-0205-0