Genetic Algorithm for Solving the Resource Constrained Project Scheduling Problem

Genetic Algorithm for Solving the Resource Constrained Project Scheduling Problem

Touihri Alaa (Faculty of Law, Economics and Management, University of Jendouba, Jendouba, Tunisia), Krichen Saoussen (Tunis Higher Institute of Management, University of Jendouba, Jendouba, Tunisia) and Guitouni Adel (Peter B. Gustavson School of Business, University of Victoria, Victoria, Canada)
Copyright: © 2015 |Pages: 16
DOI: 10.4018/IJAMC.2015040104

Abstract

The present paper develops a multi–dimensional genetic algorithm for the Resource constrained project scheduling problem. This algorithm performs a series of perturbations in an attempt to improve the current solution, applying some problem dependant genetic operators. The procedure used is efficient and easy to implement. The approach was tested on sets of standard problems freely available on the Internet (PSPLIB) and the results were compared to those found in the literature. It was found that the algorithm used is able to generate competitive results compared to the best methods known so far and computes, for the first time, four optimal solutions for four benchmark instance.
Article Preview

1. 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

d1 = dn = 0 and r1k = rnk = 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.

2. 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.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2019): Forthcoming, Available for Pre-Order
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
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