The Nature of the Problem:
-------------------------
A combinatorial optimization problem tackled by methods such as
simulated annealing, mean field annealing, genetic algorithms, and
expert systems among others.

The Timetabling Problem:
-----------------------
One of the problems that has no single objective to minimize, but is
rather a purely constraint satisfaction problem (CSP) is the
NP-complete ``teachers and classes'' timetabling problem.
Briefly, the problem is defined as follows:

For a certain school having Np teachers, Nq classes, Nx
classrooms or lecture halls, and Ns students; it is required to
schedule Nl lessons (defined as teacher-class pairs) within a time
limit of Nt lesson periods (or time slots). 

A schedule needs to be found satisfying a set of constraints, some are
hard, some are medium, and some are soft.
A schedule that does not violate any of the hard
constraints is a legal schedule, and it is the kind of schedule that
need to be produced.

Constraints of Timetabling:
--------------------------
In a nutshell, timetabling is the assignment of time slots to a set of
events, subject to constraints on these assignments. 
These constraints are divided into three types: hard, medium, and
soft.

Example(1): Two or more classes taught by the same professor can not be 
scheduled at the same time.
Example(2): A class and its recitation or/and lab can not be scheduled
at the same time.
Example(3): A class can not be assigned to a particular room unless
size(room) >= enrollment(class).

... and so on ...

Some Methods for Tackling Timetabling:
-------------------------------------
Academic scheduling or timetabling has been tackled by many
researchers, mostly in the field of operations research. 
Lately, there have been a number of ``non-conventional'' (or novel)
methods utilized to tackle this problem from different angles. Chief 
among them are neural networks, simulated annealing, genetic
algorithms, tabu search, and various combinations of two or more of these 
techniques. Among these techniques we have used the following:

Simulated Annealing (SA):
------------------------
This approach depends heavily on the annealing schedule. The most
widely used one is the geometric cooling schedule. Others, such as
geometric re-heating as a function of cost can also be used.

Rule-based System (ES):
----------------------
This system is used with a number of heuristics and conventional
recursion to assist in carrying out course assignments. 
Those heuristics are implemented to take care of various cases that
arise when carrying out the scheduling. 

The Nature of the Following two Problem:
---------------------------------------
A combinatorial optimization problem tackled by methods such as
simulated annealing, mean field annealing, genetic algorithms, and
expert systems among others.

Graph Matching (GM):
-------------------
The graph matching problem is to find out if two graph have the same
topology (the way its nodes are linked together), that is, if the two
graphs are in fact the same. For simple graphs, this is not difficult
to determine but for more complicated graphs, this becomes quite
difficult. It is not known whether this problem is in the NP-complete
class or not, but, except for some special cases, no polynomial
algorithm is known.

A quite useful class of matching problems are those described by
specifying n points in the plane to match so as to minimize the
distance between the pairs. In term of graphs, this basically means we
have the complete graph on $n$ nodes with the weight of each edge
being the distance between its end points (under some metric).

Graph Coloring (GC):
-------------------
Briefly, given a graph G=(V,E) we have to find a coloring of its
vertices with as few colors as possible. The main constraint is that
two vertices linked by an edge should not receive the same color (such
coloring are called feasible coloring). One could define the set $S$
of feasible solutions as the set of feasible coloring which do not use
more than a given number of colors; for example, this upper bound may
be the number of colors used in the initial solution. For more
information, take a look at Mike Trick's
http://mat.gsia.cmu.edu/resource.html.

Mapping Sketch of Timetabling onto Graph Coloring:
-------------------------------------------------

1. The courses are the vertices of a graph.
2. The time periods correspond to the colors.
3. Two vertices are linked by an edge if the corresponding courses
   cannot be given at the same time.
4. Additional constraints have to be taken into account and mapped
   onto the graph.

What need to be done:
--------------------
Tasks

1. Carry out timetabling using SA. 
2. Tackle GC or GM using SA with different cooling schedules.
scaling.
3. Create an interface between the user and the simulator. Such an
interface has to allow entering the data and the scheduling
constraints in a nice fashion. 

Furtherwork
-----------
1. Experiment with different cooling schedules for task [1] and
compare the results.
2. Use more constraints for tasks [1].
3. Tackle timetabling or (and) either GC or GM  using ES and  compare
results with those obtained from SA or MFA. 
4. Investigate the issues of parallelism and scaling for the above tasks.

Requirements
------------
The student ought to be quite knowledgeable (and have already done a
at least one medium to large size project) in using a programming
language, such as C or C++. Any mathematical knowledge (calculus and
graph theory) and perhaps knowing some awk or perl is a plus.
Java and JavaScript will need to be used in creating the
abovementioned interface.

For more info:
--------------
Contact Paul Coddington (paulc@npac.syr.edu) or Saleh Elmohamed
(saleh@npac) or may be Hon Yau (hwyau@npac).



