A Biased Random-Key Genetic Algorithm with Forward-Backward Improvement for the Resource Constrained Project Scheduling Problem

José F. Gonçalves(jfgoncalfep.up.pt)
Mauricio G.C. Resende(mgcrresearch.att.com)
Jorge J. Mendes(jjmisep.ipp.pt)

Abstract: This paper presents a biased random-keys genetic algorithm for the Resource Constrained Project Scheduling Problem. The chromosome representation of the problem is based on random keys. Active schedules are constructed using a priority-rule heuristic in which the priorities of the activities are defined by the genetic algorithm. A forward-backward improvement procedure is applied to all solutions. The chromosomes supplied by the genetic algorithm are adjusted to reflect the solutions obtained by the improvement procedure. The heuristic is tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.

Keywords: Genetic algorithm, project scheduling, resource constrained project scheduling, random keys

Category 1: Applications -- OR and Management Sciences (Production and Logistics )

Category 2: Applications -- OR and Management Sciences (Scheduling )

Category 3: Combinatorial Optimization (Meta Heuristics )

Citation: AT&T Labs Research Technical Report, Florham Park, NJ 07932 USA, March 2009.

Download: [PDF]

Entry Submitted: 03/11/2009
Entry Accepted: 03/11/2009
Entry Last Modified: 03/11/2009

Modify/Update this entry