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.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.