In this paper we study an extension of the Resource-Constrained Project Scheduling Problem (RCPSP) with minimum makespan objective by introducing as precedence constraints the so called “Feeding Precedences” (FP). For the RCPSP with FP we propose a new mathematical formulation and a branch and bound algorithm exploiting the latter formulation. The exact algorithm takes advantage also of a lower bound based on a Lagrangian relaxation of the same formulation. 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.

Bianco, L., Caramia, M. (2009). An Exact algorithm to minimize the makespan in project scheduling with scarce resources and feeding precedence relations.

An Exact algorithm to minimize the makespan in project scheduling with scarce resources and feeding precedence relations

BIANCO, LUCIO;CARAMIA, MASSIMILIANO
2009-07-07

Abstract

In this paper we study an extension of the Resource-Constrained Project Scheduling Problem (RCPSP) with minimum makespan objective by introducing as precedence constraints the so called “Feeding Precedences” (FP). For the RCPSP with FP we propose a new mathematical formulation and a branch and bound algorithm exploiting the latter formulation. The exact algorithm takes advantage also of a lower bound based on a Lagrangian relaxation of the same formulation. 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.
7-lug-2009
en
branch and bound
feeding precedences
Lagrangian relaxation
Bianco, L., Caramia, M. (2009). An Exact algorithm to minimize the makespan in project scheduling with scarce resources and feeding precedence relations.
Bianco, L; Caramia, M
Altro
File in questo prodotto:
File Dimensione Formato  
RR_07_09.pdf

accesso aperto

Dimensione 226.82 kB
Formato Adobe PDF
226.82 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/912
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact