Problem space search algorithms for resource-constrained project scheduling

Problem space search algorithms for resource-constrained project scheduling

0.00 Avg rating0 Votes
Article ID: iaor19972316
Country: Netherlands
Volume: 70
Issue: 1
Start Page Number: 307
End Page Number: 326
Publication Date: Apr 1997
Journal: Annals of Operations Research
Authors: , ,
Abstract:

The Resource-Constrained Project Scheduling (RCPS) problem is a well known and challenging combinatorial optimization problem. It is a generalization of the Job Shop Scheduling problem and thus is NP-hard in the strong sense. Problem Space Search is a local search ‘metaheuristic’ which has been shown to be effective for a variety of combinatorial optimization problems including Job Shop Scheduling. In this paper, the authors propose two problem space search heuristics for the RCPS problem. These heuristics are tested through intensive computational experiments on a 480-instance RCPS data set recently generated by Kolisch et al. Using this data set the authors compare the present heuristics with a branch-and-bound algorithm developed by Demuelemeester and Herreolen. The results produced by the heuristics are extremely encouraging, showing comparable performance to the branch-and-bound algorithm.

Reviews

Required fields are marked *. Your email address will not be published.