Parallelizing a CLIPS-based course timetabling expert system

摘要

Course timetabling is a complex task that cannot be achieved using only a few general principles. This work integrates expert systems and constraint programming to generate a novel artificial intelligence approach for a course timetabling system. This approach can be easily reformulated and customized to sup-port requirement changes. Furthermore, the difference between hard and soft constraints can be also addressed easily. However, achieving a feasible timetable is very time consuming because the inference engine is CLIPS-based. Notably, CLIPS is a rule-based language that relies on the repeated matching of facts with rules to generate conclusions. To overcome the problem, this work parallelizes the execution of the timetabling system in emerging cluster systems. However, scheduling courses in parallel without solving assignment conflicts is difficult. To conquer the inherent serialization of the inference of course timetabling, courses are scheduled one by one and the schedule for one course is parallelized. This work utilizes the inference process for scheduling one course that behaves similar to the nested if-then-else structure. The rules for the inference process of scheduling one course are partitioned into multiple rule clusters, where each rule cluster is inferred by a slave process. After receiving all feasible solutions generated by slave processes, the master decides which solution to adopt for a current course according to rule priorities. However, improper division of rules can result in a false conclusion or runtime errors. To ensure that a correct timetable is obtained, two possible problems caused by improper rule division are identified. Three partitioning guidelines are then used to cope with these problems. For implementation, this work applied a novel programming model that transmits facts in C and infers rules in CLIPS. Experimental results demonstrate that the proposed parallel timetabling system achieves superlinear speedup when running in a cluster system. The proposed method also helps parallelize CLIPS-based expert systems that have similar inference behavior to that in the course timetabling system.