Parallelizing a CLIPS-based course timetabling expert system

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)7517-7525
Number of pages9
JournalExpert Systems with Applications
Volume38
Issue number6
DOIs
Publication statusPublished - 2011 Jun 1

Fingerprint

Expert systems
Scheduling
Inference engines
Artificial intelligence

All Science Journal Classification (ASJC) codes

  • Engineering(all)
  • Computer Science Applications
  • Artificial Intelligence

Cite this

@article{29632434ece645b3953f4ec88bf525d3,
title = "Parallelizing a CLIPS-based course timetabling expert system",
abstract = "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.",
author = "Chao-Chin Wu",
year = "2011",
month = "6",
day = "1",
doi = "10.1016/j.eswa.2010.12.116",
language = "English",
volume = "38",
pages = "7517--7525",
journal = "Expert Systems with Applications",
issn = "0957-4174",
publisher = "Elsevier Limited",
number = "6",

}

Parallelizing a CLIPS-based course timetabling expert system. / Wu, Chao-Chin.

In: Expert Systems with Applications, Vol. 38, No. 6, 01.06.2011, p. 7517-7525.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Parallelizing a CLIPS-based course timetabling expert system

AU - Wu, Chao-Chin

PY - 2011/6/1

Y1 - 2011/6/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=79951576867&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79951576867&partnerID=8YFLogxK

U2 - 10.1016/j.eswa.2010.12.116

DO - 10.1016/j.eswa.2010.12.116

M3 - Article

AN - SCOPUS:79951576867

VL - 38

SP - 7517

EP - 7525

JO - Expert Systems with Applications

JF - Expert Systems with Applications

SN - 0957-4174

IS - 6

ER -