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.
Bianco, L., Caramia, M. (2012). Minimizing the Completion Time of a Project Under Resource Constraints and Feeding Precedence Relations: An Exact Algorithm. 4OR, 10(4), 361-377 [DOI: 10.1007/s10288-012-0205-0].
Minimizing the Completion Time of a Project Under Resource Constraints and Feeding Precedence Relations: An Exact Algorithm
BIANCO, LUCIO;CARAMIA, MASSIMILIANO
2012-01-01
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
