We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A HEURISTIC SEARCH ALGORITHM FOR SOLVING RESOURCE-CONSTRAINED PROJECT SCHEDULING PROBLEMS.
- Authors
Ahsan, M. Kamrul; Tsao, De-bi
- 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.
- Subjects
ALGORITHMS; DATABASE searching; ARTIFICIAL intelligence; PRODUCTION scheduling; COMPUTATIONAL intelligence; OPERATIONS research
- Publication
Asia-Pacific Journal of Operational Research, 2003, Vol 20, Issue 2, p143
- ISSN
0217-5959
- Publication type
Article