Year

1999

Degree Name

Master of Commerce (Hons.)

Department

Department of Business Systems

Abstract

Scheduling is the cornerstone of any fundamental application of Artificial Intelligence (AI) and Operations Research (OR). In general, scheduling problems are NP-hard. Many methods have been proposed and implemented in the past. Early approaches were only able to solve simplified versions of this problem. For approaching larger and more complicated problems, many heuristic methods were devised to find good solutions or simply feasible solutions. This research aims at developing an approach to implement an admissible learning heuristic search algorithm for solving resource-constrained project scheduling (RCPS) problems. The algorithm LB A* uses heuristic estimates as the criterion to search through solution space, and is featured with its heuristic learning capability in updating the solution path. This approach is developed using Object-Oriented design technique, and the system is written with C++ language and runs with IBM PC. The performance of this approach was tested using the commonly accepted 110 benchmark problems designed by Prof Jim Patterson. Although computationally expensive, this approach performed fairly well on a wide variety of problems. Most problems were solved in less than 99 seconds. In addition, this research attempted to identify those factors which are likely incur lengthy computational times. The statistical analysis showed that there is a high predictability that, the performance of our approach deteriorates as problems' characteristics become less related to heuristic estimation.

Share

COinS
 

Unless otherwise indicated, the views expressed in this thesis are those of the author and do not necessarily represent the views of the University of Wollongong.