Abstract 

Optimization and constraint satisfaction problems are extraordinarily complex and varied. At the same time, these problems have high interest, as well in the scientific-technical aspect, as in the applied aspect. Therefore, having efficient and flexible algorithmic solutions supposes an extra value in different application environments. Among the most typical problems of this type are scheduling problems, which imply the execution of activities that requiere resources whose availability is limited and therefore must be allocated efficiently.

Among the wide variety of scheduling problems, the problem of resource constrained project scheduling problem is one of the most studied. This problem considers a set of activities that has to be performed in accordance with a set of precedence constraints, a set of scarce resources and a set of performance measures, and decide the best way to  allocate those resources to activities in order to optimize the performance measure.

The standard version of the resource constrained project scheduling problem (RCPSP) includes a single execution mode for each activity. This problem has been widely studied in literature and the solving methods proposed are both exact and approximated. As for the problem that considers the possibility that each activity is implemented in one of several possible ways (MRCPSP), his study is not as comprehensive as the previous case.

The objective of this thesis is to obtain an optimized allocation of resources in this complex scheduling problem. Particularly we have designed and developed new approaches to the problems mentioned above. First we followed a refining process for the proposed heuristics and a genetic algorithm to solve the problem RCPSP selectively using the method of improving feasible schedules FBI.

In the case of MRCPSP we have designed an improvement method for feasible schedules and an allocation method that generates mode feasible sequences in more than 90 \% of cases. These methods have been incorporated into a genetic algorithm for which we have designed a fitness function that adequately guide the evolution of the algorithm.

One of the assumptions implicit in these two problems is that the project's development environment is deterministic. Therefore the durations of activities during the project execution remain as planned, the availability of resources are not affected by contingencies and the schedule can be executed without changes. However, it is clear that these assumptions are not fulfilled in practice. This is the motivation to solve the problem of generating schedules that are stable in their execution.

To address this problem, we designed a genetic algorithm that inserts time intervals while reserving the necessary resources to prevent the spread of the primary delays along the schedule. This algorithm incorporates an evaluation function of individuals consisting of a measurement \textsl{ex-ante} the robustness of the schedules generated. On the other hand develop two measures of the stability of the programs that are subject to a simulation process with two stages of variability of the duration of activities.

All the methods proposed have been implemented and their results have been evaluated by solving the problems of standard libraries. The effectiveness of these algorithms are contrasted by comparing with the best published methods.