A New Genetic Algorithm for the RCPSP in Large Scale

A New Genetic Algorithm for the RCPSP in Large Scale

Hossein Zoulfaghari (Department of Industrial Engineering, University of Tabriz, Tabriz, Iran), Javad Nematian (Department of Industrial Engineering, University of Tabriz, Tabriz, Iran), Nader Mahmoudi (Department of Industrial Engineering, University of Tabriz, Tabriz, Iran) and Mehdi Khodabandeh (Department of Industrial Engineering, University of Tabriz, Tabriz, Iran)
Copyright: © 2013 |Pages: 12
DOI: 10.4018/jaec.2013040103
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

The Resource Constrained Project Scheduling Problem (RCPSP) is a well-studied academic problem that has been shown to be well suited to optimization via Genetic Algorithms (GA). In this paper, a new method will be designed that would be able to solve RCPSP. This research area is very common in industry especially when a set of activities needs to be finished as soon as possible subject to two sets of constraints, precedence constraints and resource constraints. The presented algorithm in this paper is used to solve large scale RCPSP and improves solutions. Finally, for comparing, results are reported for the most famous classical problems that are taken from PSPLIB.
Article Preview

Introduction

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.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 8: 4 Issues (2017): 3 Released, 1 Forthcoming
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing