A heuristic search algorithm for solving resource-constrained project scheduling problems

A heuristic search algorithm for solving resource-constrained project scheduling problems

0.00 Avg rating0 Votes
Article ID: iaor20042014
Country: Singapore
Volume: 20
Issue: 2
Start Page Number: 143
End Page Number: 160
Publication Date: Nov 2003
Journal: Asia-Pacific Journal of Operational Research
Authors: ,
Keywords: scheduling, heuristics
Abstract:

This paper presents an artificial intelligence based heuristic search algorithm for resource-constrained project scheduling problems. The search process starts from an empty schedule and ends in a complete schedule. The procedure follows a stepwise generation of partial schedules that are connected by a lower bound on completion of unscheduled activities. A higher value of lower bound in a new partial schedule needs to update the search path with backtracking. We propose a composite multi-criteria search technique (CMST) to determine new partial schedules at each step. CMST combines three criteria instead of the single selection criterion of the previously developed search and learn A* (SLA*) algorithm. Our objective is to comparatively reduce the number of backtrackings and adapt the algorithm for approximate solutions of large problems. The performance of CMST is analyzed for different problems and different weights of the three criteria. Results show that the proposed CMST reduces backtracking as well as computational time to a large extent compared to SLA* with optimal or very close to optimal solution.

Reviews

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