New Meta-heuristics for the Resource-constrained Project Scheduling Problem

Author

Andrew LIM, Hong Kong University of Science and Technology
Hong MA, Zhejiang University
Brian RODRIGUES, Singapore Management UniversityFollow
Sun Teck TAN, National University of Singapore
Fei XIAO, Google Inc

Publication Type

Journal Article

Publication Date

6-2013

Abstract

In this paper, we study the resource-constrained project scheduling problem and introduce an annealing-like search heuristic which simulates the cooling process of a gas into a highly-ordered crystal. To achieve this, we develop diversification procedures that simulate the motion of high energy molecules as well as a local refinement procedure that simulates the motion of low energy molecules. We further improve the heuristic by incorporating a genetic algorithm framework. The meta-heuristic algorithms are applied to Kolisch’s PSPLIB J30, J60 and J120 RCPSP instances. Experimental results show that they are effective and are among the best performing algorithms for the RCPSP.

Keywords

Resource-constrained project scheduling problem, Meta-heuristics, Genetic algorithms

Discipline

Operations and Supply Chain Management

Research Areas

Operations Management

Publication

Flexible Services and Manufacturing Journal

Volume

25

Issue

1

First Page

48

Last Page

73

ISSN

1936-6582

Identifier

10.1007/s10696-011-9133-0

Publisher

Springer

Citation

LIM, Andrew; MA, Hong; RODRIGUES, Brian; TAN, Sun Teck; and XIAO, Fei. New Meta-heuristics for the Resource-constrained Project Scheduling Problem. (2013). Flexible Services and Manufacturing Journal. 25, (1), 48-73.
Available at: https://ink.library.smu.edu.sg/lkcsb_research/3803

Additional URL

https://doi.org/10.1007/s10696-011-9133-0