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

\section{Introduction}
We have implemented a fairly complex rule-based expert system for
solving the course 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 tackling the three assignment-type 
problems ({\bf t, g, a}) of {\it timetabling}, {\it grouping}, and
{\it class assignment} 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{Forward and Backward Rules}

Our expert system also make use of the forward and the backward
chaining approach of Petrie {\it et al.}~\cite{PCSD:scheduling}. This
approach is quite suitable for planning/assignment-type problems such
as course scheduling. The problem's model can be viewed in a framework
as one where possible interpretations for each state (i.e. teacher)
are already specified at the outset as a constrained ordered set of
courses (the course database). Therefore, in order to generate a
solution, the problem-solver uses a generate-and-test strategy based
on this ordering.

An example to illustrate how forward/backward chaining works can be
considered given the following scenario: Suppose Johnson wants to
teach physics 300 (phy300) in the fall, and he has alternatives to
phy300 in the fall, namely phy310 and phy318. Suppose that the maximum 
allowable sections of phy300 have already been allocated for fall, and 
suppose Johnson is now up for consideration (Richards has already been
considered for phy300). The rules will try to assign phy300 to Johnson 
in the fall but fail becuase the maximum constraint has been satisfied 
for the semester.

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

