AN ARTIFICIAL INTELLIGENCE APPROACH TO COURSE TIMETABLING

摘要

Course Timetabling is a complex problem that cannot be dealt with by using only a few general principles. The various actors (the administrator, the chairman, the instructor and the student) have their own objectives, and these objectives usually conflict. The complexity of the relationships among time slots, classes, classrooms, and instructors makes it difficult to achieve a feasible solution. In this article, we propose an artificial intelligence approach that integrates expert systems and constraint programming to implement a course timetabling system. Expert systems are utilized to incorporate knowledge into the timetabling system and to provide a reasoning capability for knowledge deduction. Separating out the knowledge base, the facts, and the inference engine in expert systems provides greater flexibility in supporting changes. The constraint hierarchy and the constraint network are utilized to capture hard and soft constraints and to reason about constraints by using constraint satisfaction and relaxation techniques. In addition, object-oriented software engineering is applied to improve the development and maintenance of the course timetabling system. A course timetabling system in the Department of Computer Science and Information Engineering at the National Changhua University of Education (NCUE) is used as an illustrative example of the proposed approach.