Publication Type

Journal Article

Version

publishedVersion

Publication Date

3-2006

Abstract

In the last few decades, several effective algorithms for solving the resource-constrained project scheduling problem have been proposed. However, the challenging nature of this problem, summarised in its strongly NP-hard status, restricts the effectiveness of exact optimisation to relatively small instances. In this paper, we present a new meta-heuristic for this problem, able to provide near-optimal heuristic solutions for relatively large instances. The procedure combines elements from scatter search, a generic population-based evolutionary search method, and from a recently introduced heuristic method for the optimisation of unconstrained continuous functions based on an analogy with electromagnetism theory. We present computational experiments on standard benchmark datasets, compare the results with current state-of-the-art heuristics, and show that the procedure is capable of producing consistently good results for challenging instances of the resource-constrained project scheduling problem. We also demonstrate that the algorithm outperforms state-of-the-art existing heuristics.

Keywords

Project scheduling, Heuristics, Scatter search, Electromagnetism

Discipline

Business Administration, Management, and Operations | Theory and Algorithms

Research Areas

Operations Management

Publication

European Journal of Operational Research

Volume

169

Issue

2

First Page

638

Last Page

653

ISSN

0377-2217

Identifier

10.1016/j.ejor.2004.08.020

Publisher

Elsevier: 24 months

Embargo Period

8-31-2021

Download

Share

COinS