The development and implementation of a learning heuristic algorithm for project scheduling problem

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.