Limited-resource scheduling by generalized rule-based system

摘要

A general paradigm for solving resource allocation, time-tabling, and scheduling problems is presented. The paradigm is based on an expert system approach, which looks for a feasible solution that satisfies the problem's real-life constraints. The new paradigm includes generic concepts for resources, activities, constraints, and allocations. The general control strategy of the new paradigm is suitable for a large family of resource allocation and time-tabling problems. This control strategy includes three parts that deal with allocation, constraint checking, and changes to allocations.The proposed paradigm was tested on three real-world problems: crew assignment to air force missions, class scheduling for a university department, and time-tabling of final examinations for the faculty of natural sciences. All cases were solved well in a few minutes of central processing unit time, by Prolog-based systems that implemented the proposed paradigm. These case studies are described in the paper in some detail, and an overall evaluation of the methodology is given.