Page 150 - ASBIRES-2017_Preceedings

Dissanayake, Bandara & Dahanayaka
students, while simultaneously satisfying a
number of various essential conditions or
constraints.
The model takes advantage of the
structural properties of conflict graph
instances that arise from university
timetabling problems, and is based on the
effectiveness of a variety of graph colouring
approaches.
Graph colouring algorithm is one of the
most used algorithms. In a typical semester,
the courses are required to be scheduled at
different time slots in order to avoid
conflict. The problem of determining the
minimum number of time slots need to be
scheduled for all the courses subject to
restrictions is a graph colouring problem.
1.3 Objectives
Main objective of this project is
scheduling a time table for the university
students while minimizing the number of
time slots. Our final aim was to prepare a
balance, conflict-free weekly time table for
the level 3 students of the Faculty of
Applied Sciences of the Wayamba
University of Sri Lanka.
We are selecting this time table
scheduling the problem that is because of
considering past two years there were very
complicated time schedule for level 3
students. In other words, that time table was
scheduled from 7.30 am to 8.30 pm.
Since our scope of this project is to
consider only the clashes for students, we
have used graph colouring to eliminate
clashes of two subjects which are following
by common students.
Once a course timetable is constructed
based on students clashes, a conflict-free
final time schedule based on all other
constraints, can quite easily be obtained.
From that initial timetable, one can then
assign the courses to classrooms based on
room capacity and availability, and can
assign relevant lecturers for the courses
based availability and comfort ability of
them.
140
2 LITRETURE REVIEW
The literature on timetabling includes
several surveys. We now briefly discuss
their scope and contribution. Schmidt and
Strohlein (1979) provide an annotated
bibliography including more than 200
entries, listing virtually all papers on the
field that appeared up to 1979.
Junginger (1986) describes the research
in Germany on the school timetabling
problem. In particular, he describes the
various software products implemented, and
their actual utilization by the staffs of the
paper.tex; 1/02/1999; 16:48; no v.; p.3 4 A.
SCHAERF institutions. The paper also
describes the underlying approaches, most
of which are based on direct heuristics.
Be Werra (1985) states the various
problems in a formal way, and provides
different formulations for them. He also
describes the most important approaches to
the problem (up to date), stressing the graph
theoretic ones. We follow mostly his paper
for the terminology and the problem
formulations. Carter (1986) surveys the
approaches to the examination timetable
problem. He mainly focuses on the
approaches based on the reduction to the
graph coloring problems.
Corne et al. (1994a) provides a survey
of the application of genetic algorithms to
time tabling. The paper also discusses future
perspectives of such an approach, and
compares its results obtained so far with
respect to some other approaches. Other
surveys are given in (Dempster et al., 1973;
Hilton, 1981; Klein, 1983; Vincke, 1984;
Ferland et al., 1986). There is also a Web
page and a mailing list for the timetabling
community, which includes bibliographies
and papers. Souza (2000) defines a
timetable as the total schedule of a specific
teaching, which will be attended by a group
of students and the lecturer, at a specified
time. It requires specific resources such as,
room, teaching aid and etc. Scheduling is
parallel to the resources made available
besides fulfilling other needs.