
\chapter{The Rule-Based (Expert) Systems}

\section{Introduction}
We have implemented a fairly complex
rule-based expert system for solving the timetabling
problem, for three reasons. Firstly, it gives us a benchmark as to how
well other methods do in comparison to this standard technique. 
Secondly, a simplified version of the rule-based system is used to
provide sensible choices for moves in the simulated annealing
algorithm, rather than choosing swaps completely at random, and this
greatly improves the proportion of moves that are accepted.
Thirdly, we have used this system as a preprocessor for simulated
annealing, in order to provide a good initial solution.

Simulated annealing is a very time-consuming, computationally intensive 
procedure. Using an expert system as a preprocessor is a way of
quickly providing a good starting point for the annealing algorithm,
which reduces the time taken in the annealing procedure, and improves
the quality of the result. Our results clearly support this rationale
for the case of academic scheduling.

The rule-based expert system consists of a number of rules
(or heuristics) and conventional recursion to assist in carrying out
class assignments. We have developed this system specifically for the
problem of academic scheduling. The basic data structures or
components of the system are: 
\begin{enumerate}
\item
Distance matrix of values between each academic department and every
other building under use for scheduling. 
\item
Class data structure of each class scheduled anywhere in campus. 
These structures are capable of linking with each other. 
\item
Room data structure of each room (regardless of type) involved in the
scheduling process. Like classes, room structures are also linked with
each other. 
\item
Data structures for time periods to keep track of which hour or time
slot was occupied and which was not. 
\item
Department inclusion data structure giving department inclusion within
other larger departments or colleges. 
\item
Students structures indicating classes of various degree of
requirements and preferences for each student. 
\end{enumerate}

The basic function of the system is as follows: given data
files of classes, rooms and buildings, department-to-building distance
matrix, students data, and the inclusion data, using the
abovementioned data structures, the system builds an internal database
which in turn is used in carrying out the scheduling process. This
process involves a number of essential sub-processes such as checking
the distances between buildings, checking building, room
type and hours occupied, checking and comparing time slots for any
conflicts, checking rooms for any space conflict, and keeping track of
and updating the hours already scheduled.

The rule-based system uses an iterative approach. The basic procedure
for each iteration is as follows. 
The scheduling of classes is done by department, so each iteration
consists of a loop over all departments. The departments are chosen in
order of size, with those having the most classes being scheduled
first. The system first loops over all the currently unscheduled
classes, and attempts to assign them to the first unoccupied room and
timeslot that satisfies all the rules governing the constraints.   
Since constraints involving capacity of rooms are very difficult to 
satisfy, larger classes are scheduled first, to try to avoid not
having large enough rooms later for those class sections with large
enrollments.

In some cases the only rooms and timeslots that satisfy all the rules
will already be occupied by previously scheduled classes. In that
case, the system attempts to move one of these classes into a free
room and timeslot, to allow the unscheduled class to be scheduled.

Next, the system searches through all the scheduled classes, and
selects those that have a high cost, by checking the medium and soft
constraints such as how closely the room size matches the class size,
how many students have time conflicts, whether the class is in a
preferred time period or a preferred building, and so on. Selecting
threshold values for defining what is considered a ``high'' cost in
each case is a subjective procedure, but it is straightforward to
choose reasonable values. When a poorly scheduled class is identified,
the system searches for a class to swap it with, so  that the hard
constraints are still satisfied, but the overall cost of the medium
and soft constraints is reduced. 

This process of swapping rooms continues provided all the rules
are satisfied and no ``cycling'' (swapping of the same classes)
occurs. Once all the departments have been considered, this completes
one iteration. The system continues to follow this iterative procedure
until a complete iteration produces no changes to the schedule.

\section{Examples of Rule-based Constraints}
There are many rules dealing with space and hours, type of room, and  
priority of room. Many are quite complex, but some of the basic rules,
such as those implementing the hard constraints, can be quite 
straightforward.

\subsection{Time and Space}
The following is the basic rule for dealing with time and space
conflicts for a room:

{\it IF [room(capacity) $>$ class(space-requested)] and [no time
conflict in this room]
THEN assign the room to the class.}

[If more than a room having an identical availability time are present
in the database, then choose the one with the minimal magnitude of the
difference between room(capacity) and course(space-requested)].

{\bf\underline{Input:}}
CPS-615 requests space for 75 students and meeting hours of [MWF 10:40
- 11:35 am].

In the database we have, for example, the following rooms:

\begin{itemize}
\item room: 1-218 CST , capacity: 45 students, and pre-occupied hours:
none.
\item room: 207 HL, capacity 120 students, and pre-occupied hours: [MW
09:45 - 11:10 am]. 
\item room: Kitt-Aud HBC, capacity: 127 students, and pre-occupied
hours: [TTH 10:40 - 12:00 am].
\end{itemize}

{\bf\underline{Output:}}
Room Kitt-Aud is assigned to CPS-615. \ \

\subsection{Type of Room}

{\it IF [room(capacity) $>$ course(space-requested)] and [no time
conflict in assigning this room] and [type(room) matches
type(requested)]
THEN
   assign the room to the course:}
[If identical rooms in type are
present in the database, then choose the one with the minimal
magnitude of the difference between room(capacity) and
course(space-requested)].

{\bf\underline{Input:}}
BIO-615 requests space (not biology lab) for 35 students and meeting
hours in [MW 10:40 - 11:35]. 

In the database we have, for example, the following rooms:

\begin{itemize}
\item room: 1-218 CST, capacity: 45 students, type: classroom, and
pre-occupied hours: none.
\item room: 124-SIMS, capacity: 40 students, type: laboratory, and
pre-occupied hours: none.
\end{itemize}

{\bf\underline{Output:}}
Room 124-SIMS is assigned to BIO-615. \ \

\subsection{Room Priority}

Rooms are classified as:
\begin{enumerate}
\item General Purpose: used by all users.
\item Priority Rooms: are used based on certain priority of the class
or the department.
\item Special Purpose: are only assigned to specific users.
\end{enumerate}
\begin{itemize}

\item {\it IF [room(priority) == general] and [room(capacity) $>$
course(space-requested)] and [no time conflict in assigning this room]
and [type(room) matches type(requested)]  

THEN  assign any user to this room.}

\item {\it IF [room has a priority user] and [the user is already
assigned] and [room(capacity) $>$ course(space-requested)] and [no
time conflict in assigning this room] and [type(room) matches
type(requested)]

THEN  assign other users.}

\item {\it IF [room(priority) == special purpose] and [user belongs to
the special users of this room] and [room(capacity) $>$
course(space-requested)] and [no time conflict in assigning this room]
and [type(room) matches type(requested)]

THEN  assign the room to the user.}

\item {\it IF [room has a priority user] and [the user is already
assigned] and [room(capacity) $>$ course(space-requested)] and [no
time conflict in assigning this room] and [type(room) matches
type(requested)]

THEN  assign other users.}

\item {\it IF [room(priority) == special purpose] and [user belongs to 
the special users of this room] and [room(capacity) $>$
course(space-requested)] and [no time conflict in assigning this room]
and [type(room) matches type(requested)]

THEN  assign the room to the user.}

\end{itemize}

\subsection{The Rationale of Using a Preprocessor}
\begin{itemize}
\item It is a good practice when using heuristics such as
simulated annealing, to start at a good point in the search
space or with a partial solution of the problem; regardless of the
difficulty of the problem.

\item A good starting point can only have a positive effect on the
overall solution, and that is improving its quality.

\item A good starting point or a partial solution will also have a
positive effect on the convergence of the system; faster convergence
to the final solution.
\end{itemize}


When the rule-based system is used as a preprocessor, it produces a
partial schedule as an output, since it is usually unable to assign
all of the given classes to rooms and times slots. 
The output is divided into two parts: the first consists of classes, 
with their associated professors and students, assigned to various
rooms; and the second is a list of classes that could not be assigned 
due to constraint conflicts.

