Minimizing the completion time of a project under resource constraints and feeding precedence relations: a Lagrangian relaxation based lower bound |
| |
Authors: | Lucio Bianco Massimiliano Caramia |
| |
Institution: | 1. Dipartimento di Ingegneria dell??Impresa, Universit?? di Roma ??Tor Vergata??, Via del Politecnico, 1, 00133, Rome, Italy
|
| |
Abstract: | In this paper we study the Resource Constrained Project Scheduling Problem (RCPSP) with “Feeding Precedence” (FP) constraints
and minimum makespan objective. This problem typically arises in production planning environment, like make-to-order manufacturing,
where the effort associated with the execution of an activity is not univocally related to its duration percentage and the
traditional finish-to-start precedence constraints or the generalized precedence relations cannot completely represent the
overlapping among activities. In this context, we need to introduce in the RCPSP the FP constraints. For this problem we propose
a new mathematical formulation and define a lower bound based on the Lagrangian relaxation of the resource constraints. A
computational experimentation on randomly generated instances of sizes of up to 100 activities shows a better performance
of this lower bound when compared to other lower bounds. Moreover, for the optimally solved instances, its value is very close
to the optimal one. Furthermore, in order to show the effectiveness of the proposed lower bound on large instances for which
the optimal solution is known, we adapted our approach to solve the benchmarks of the basic RCPSP from the PSLIB with 120
activities. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|