A Parallel CLIPS-based Course Timetabling Expert System

Abstract

Course timetabling is a complex problem that cannot be dealt with by using only a few general principles. We proposed an artificial intelligence approach that inte-grates expert systems and constraint programming to im-plement a course timetabling system. By adopting the ap-proach, it is easy to formulate and customize for support-ing requirement changes and the difference between hard and soft constraints can be also addressed. However, it is very time consuming to achieve a feasible timetable be-cause the inference engine is CLIPS-based. CLIPS is a rule-based language and relies on repeatedly matching facts and rules to draw conclusions. To address the prob-lem, we propose parallelizing the execution of the time-tabling system in emerging cluster systems. We parallelize the inference process of one course by partitioning CLIPS rules into multiple running pieces, where each running piece is inferred by a slave process. To ensure achieving correct solutions, we identify four possible problems that might occur if rules are divided improperly. Furthermore, how to avoid these problems and how to deal with them are also introduced. In the implementation of the system, the MPICH library is embedded into the C-based infe-rence engine for interprocess communication. In addition, a programming model, which we transmit facts in C and infer rules in CLIPS, is also proposed. Experimental re-sults show that the proposed parallel timetabling system achieves superlinear speedup when running in a cluster system.