An expert system using an exchange heuristic for the resource-constrained scheduling problem

摘要

In this paper, we discuss the development and implementation of an expert system for the resource-constrained scheduling problem. The objective of the system is to minimize the makespan (or duration of a project). This approach can accommodate up to 400 operations (activities) and 50 different resources. The knowledge contained in the expert system is based upon an exchange heuristic algorithm that has been applied succesfully to various resource-constrained scheduling problems and has been shown to be a very general and efficient search method for large-sized problems. The exchange heuristic takes an initial schedule and improves upon it via exchanging and rearranging operations, while continually maintaining feasibility. In this system, a forward chaining strategy is used as the inference process. These production system language OPS83 with external C-language links is utilized as the system development tool. In order to evaluate the performance of the expert system, we compared it with an earlier heuristic programming version and found that superior computation performance and enhanced software maintenance were achieved. A number of large-sized problems have been tested on this system, and the results have shown that the makespans were reduced by 10–16 percent compared to initial schedules. Advanced programming techniques were utilized to reduce computer memory requirements and to increase the search speed. Therefore, the system can deal with large-sized problems on PC-compatible machines (with 640KB RAM or more), running MS-DOS, with short CPU execution times.