Article Preview
TopIntroduction
The resource Constrained project scheduling problem (RCPSP) is a classical and changeable optimization problem that has attracted many researchers and a well-known problem where the activity of a project must be scheduling to minimize its makespan (Brucker et al., 1999; Herroelen et al., 1998; Kolisch & Hartmann, 1998). Not only exact solution procedures, but also many heuristic methods have been proposed to solve RCPSP. Lancasrer and Ozbayrak (2007) and Kolisch and Hartmann (2005) have provided detailed history of the work conducted in this area to the date.
Being an NP-hard problem, Alcaraz and Maroto (2001) mentioned that the optimal solution can be achieved by exact solution procedures but only in small projects, usually with less 60 activities. Heuristic methods are designed to solve large and high resource-constrained projects. Möhring et al., (2003) have mentioned that RCPSP is one of the most intractable problems in operations research; and many optimization techniques have applied to solve it. Many effective heuristic and meta-heuristic algorithms are also proposed for RCPSP. Several authors have suggested different methods to solve this problem. They can be classified into three categories, the exact methods (Brucker et al., 1998; Demeulemeester & Herroelen, 1992; Christofiedes et al., 1987; Mingozzi et al., 1998; Patterson, 1984) generated optimal solutions for small size problems. There are many exact algorithms proposed for RCPSP, which are mainly based on the branch-and-bound strategy. For example, Demeulemesster and Herroelon (1997) developed depth-first branching rules. Brucker et al. (1998) presented a branch and bound algorithm where its branching scheme is applied on a set of conjunctions of disjunctions to pair of activities. As an NP-hard problem, the optimal solution can only be achieved by exact methods in small projects, which are not highly resource constraints.
Heuristic procedures are the algorithms for large projects, the best ones gives good solutions with few computational requirements in a reasonable computation time .We can mention the general work of Brucker et al. (1998) as well as the work of Kolisch and Hartmann (1998) which focuses on heuristic algorithms to solve the problem. Due to limitations of exact algorithms, some authors proposed heuristic algorithms for RCPSP.For example, Möhring et al. (2003) proposed a heuristic based on the Lagrangian relaxation and minimum cut computations .The heuristic methods which are based on priority rules can be divided into two classes: Single-pass methods and multi-pass methods which were presented in Boctor, 1990. The forward-backward methods were also proposed in Li & Willis 1992.