Page 152 - ASBIRES-2017_Preceedings

Dissanayake, Bandara & Dahanayaka
5 CONCLUSION
First we have selected level 1 subjects
to apply colouring methods and it was not
much applicable to reduce a number of time
slots. Because when we were in first year
there was only three combinations. So we
could find only two subjects which can be
scheduled same time. Therefore, number of
subjects is 13 and chromatic number is 12.
Then we had not prepared a time table
for level 2. That was because it is same as
level 1-time table. In other words, the
second year also we had studied under same
combinations as first year. Then we moved
to develop level 4-time table which was
much difficult than level 1-time table, due to
several subject combinations of joint major
and also specialized areas. After applying
graph colouring method we could find that,
although there were 17 number of subjects,
chromatic number was only 11. So we can
conclude that it can be minimized the
number of time slots by using graph
colouring method.
As our final target, we collected level 3
course details to prepare the time table by
using graph colouring method. This is the
most complicated time schedule in our
faculty. Because there are some students
who follow one of the specialized areas,
there is another set of students who studies
for general degree and others are divided
into above 12 joint major degree courses.
That is the reason for complexity of level 3-
time table. After applying graph coloring
method, we could found that, although there
were 18 number of subjects, chromatic
number was only 16. It means we can
arrange the time table using only 16
different time slots for 18 subjects. Although
we have considered only student clashes,
from this time table anyone can assign the
course to classrooms based on room
capacity & availability and also based on
availability of lecturers. This study can be
further developed by considering above
mentioned constraints. Once a course time
table is constructed, a conflict-free schedule
142
of final time table for the courses can quite
easily be obtained.
REFERENCES
 Akkoyunlu, A. (1973). A linear algorithm
for computing the optimum university
timetable. The Computer Journal, 16(4),
347–350. .
 Alvarez-Valdes., Martin, G., & Tamarit,
J.M. (1996). Constructing good solutions
for the Spanish school timetabling
problem. Journal of the Operational
Research Society.
 Brelaz, D. (1979). New Methods to Color
the Vertices of a Graph Comm. A.C.M. 7,
494-498.
 Burke, E.K., Elliman, E.D., & Weare, R.
(1993). A University Timetabling System
based on Graph Colouring and Constraint
Manipulation. Journal of Research on
Computing in Education, 26.
 Cangalovi. C., & Schreuder, J.A.M.
(1991). Exact coloring algorithm for
weighted graph applied to timetabling
problems with lectures of different length.
Journal of Operational Research, 51(2),
248–258.
 Elliman, B.D., & Weare, R. (1993).
Extensions to a university exam
timetabling system. In IJCAI-93
Workshop on knowledge-based
production, planning, scheduling and
control, 42–48, Chambery, France.
 Johnson, D.S. (1974). Worst Case
Behaviour of Graph Coloring Algorithms
in Proc. 5th SE Conf. on Combinatorics,
Graph Theory and Computing. Winnipeg,
Canada: Utilitas Mathematica Publishing,
513-528.
 Johnson, D.S., Aragon, C.R., Mcgeoch,
L.A., & Schevon, C. (1991). Optimization
by simulated Annealing: An Experimental
Evaluation; Part II. Graph Coloring and
Number Partitioning Operations
Research, 39, 378-406.
 Mathaisel, D.F.X., & Commc, L. (1991).
Course and classroom scheduling: An
interactive computer graphics approach.
Journal of Sys. Software, 15, 149-157.