Article Preview
Top1. Introduction
Formally, the RCPSP is described as follows. A project consists of a set V = {1……..n} of n activities. Activities 1 and n are dummy activities to model the start and end of the project. The activities are interrelated by two kinds of constraints:
- •
Precedence constraints force each activity j to be scheduled after al predecessor activities Pred j are completed.
- •
Activities require resources with limited capacities. Concerning the second constraint, while being processed, activity j requires rjk units of resource type 
during every time instant of its non-preemptable duration dj. Resource type has a limited capacity of Rk at any point in time.
For the project scheduling problem considered in this paper, without loss of generality, parameters dj, rjk and Rk are assumed to be integer, non-negative, deterministic and known at the initial time of scheduling. For the project’s start and end activities, it is assumed that
d
1 = d
n = 0 and r
1k = r
nk = 0.
An instance of the RCPSP is solved by finding starting (or ending) times of each activity satisfying both precedence and resource constraints, such that the total duration of the project (i.e., the makespan), noted as Cmax, is minimized. The related literature is very extensive, including exact methods, heuristic and meta-heuristic solution approaches. It has been shown by Blazewicz et al. (1983) that the RCPSP, as a generalization of the classical job shop scheduling problem, belongs to the class of NP-hard optimization problems, therefore justifying the use of heuristics when solving large scaled problems. In general, restricting all feasible solutions to find the best solution seems to be impossible even for a problem of medium size. Therefore, we can address the resolution of the RCPSP by means of approximate methods, especially heuristics and metaheuristics methods. As with many other meta-heuristics used to solve these problems, the success of genetic algorithms (GAs) is, to a large extent, due to its ability to recover the search process from getting stuck in a local optimum. GAs has shown a remarkable efficiency on many problems (scheduling, packing and vehicle routing) and often surpasses the best solutions previously found by other approaches. Various solutions approaches were proposed for the RCPSP.
Top2. Literature Review
The RCPSP is known to be an NP-hard optimization problem (Blazewicz et al., 1983). This features makes the problem hard to solve optimally where addressing large scaled instances. Some surveys for the RCPSP are provided by Icmeli et al (1993), Herroelen et al. (1998), Brucker et al. (1999), Klein (1999), Hartmann and Kolisch (2000), Kolisch and Padman (2001) and Montoya-Torres 2009).Several exact methods to solve the RCPSP are proposed in the literature. Currently, the most competitive exact algorithms seem to be the ones of Demeulemeester and Herroelen (1997), Brucker et al. (1998), Klein and Scholl (1998a,b), Mingozzi et al. (1998), and Sprecher (2000). Stork and Uetz (2005) present several complexity results related to generation and counting of all circuits of an independence system, and study their relevance in the solution of RCPSP.Several authors propose procedures for computing lower bounds on the makespan. Brucker and Knust (2003) presented a destructive lower bound for the multimode Resource-Constrained Project Scheduling Problem with minimal and maximal time-lags. Brucker and Knust (2003) developed a destructive lower bound for the RCPSP, where the lower bound calculations are based on two methods to prove infeasibility of threshold values for the makespan.