Page 149 - ASBIRES-2017_Preceedings

th
Proceedings of the 9 Symposium on Applied Science, Business & Industrial Research – 2017
ISSN 2279-1558, ISBN 978-955-7442-09-9

Scheduling Time Tables by Using Graph Colouring

Dissanayake MMIS, Bandara DMS, Dahanayaka SD
Department of Mathematical Sciences, Wayamba University of Sri Lanka
indunilsachini@gmail.com

ABSTRACT

Creating time table is the scheduling of a set of related events in a minimal block of
time such that no resource is required simultaneously by more than one event. In
university time tabling, the resources involved, which we assume may be required by no
more than one course at any particular time, are instructors, classrooms, and students.
University timetabling is a practical application of graph colouring. We develop and
describe a mathematical method for creating university timetables using techniques of
graph coloring that incorporates the satisfaction of both essential and preferential
timetabling conditions. The model involves creating a conflict graph from assembled
university course data, properly coloring the conflict graph, and transforming this
colouring into a conflict-free timetable of courses. From this timetable, one can then assign
the courses to classrooms based on room capacity and availability. Once a course timetable
is constructed, a conflict-free schedule of final examinations for the courses can quite easily
be obtained.

KEYWORDS: Conflict-free, Graph colouring, Style, Vertex colouring

1 INTRODUCTION 1.2 Constraints
1.1 Graph Colouring The university course timetabling
problem consists in scheduling a set of
Graph colouring is a special case of lectures for each course within a given
graph labeling. It is an assignment of labels number of rooms and time periods. If two
traditionally called "colours" to elements of courses have common students then they
a graph subject to certain constraints. In its conflict, and they cannot be scheduled at the
simplest form associating a colour or a same period.
colour label with the vertices, edges or faces
of a graph whilst fulfilling some certain In addition, in the university problem,
criteria is called graph colouring.Vertex availability of lecture rooms and their size
colouring is the starting point of the subject, plays an important role. Several many other
and other coloring problems can be constraints can also be identified.
transformed into a vertex version. For an According to the scope of this project, we
example, an edge coloring of a graph is just have only considered about clashes for the
a vertex coloring of its line graph, and a face students. Depending on this basis we have
colouring of a plane graph is just a vertex developed the university time table. In this
colouring of its dual. Edge colouring is use time table scheduling the problem we use
to colour the edges in the graph in such a vertex colouring among the above
way that two adjacent edges do not have the mentioned three types of colouring.
same colour. Two edges are adjacent if they Timetabling is the allocation, subject to
are connected to a common vertex. Face constraints, of given resources to objects in
colouring is use to colour the faces in a space-time domain to satisfy a set of
planer graph in such a way that two adjacent desirable objectives as nearly as possible.
colour the faces in a planer graph in such a Particularly, the university timetable
way that two adjacent faces do not have the scheduling problem for courses can be
same colour. Two faces are adjacent if they viewed as fixing in time and space a
share a common edge. sequence of meetings between lecturers and

139