Page 151 - ASBIRES-2017_Preceedings

SCHEDULING TIME TABLES BY USING GRAPH COLOURING

3 METHODILOGY 4 DATA REPRESENTATION AND
RESULTS
3.1 Data Collection
• When we schedule a time table for the Although the final target was
university students, very first we have to list preparation of level 3 semester, I time table
down different subjects and students using graph coloring initially we selected
enrolled in each and every subject. level 1 semester I time table to develop it
using graph coloring. There were 13
• Many subjects would have common different subjects. Some of them are S1-
students. Therefore, the problem is to Introduction to Probability and Statistics I,
schedule the time table, that any two S2-Introduction to Mathematics I, S3-
subjects with a common student can’t
schedule at the same time. Business Economics, S12-English Language
Proficiency Course I, and S13-Information
• Example for the different subjects and & Communication Technology. Among
subjects clashes with each other can be these 13 subjects S13 can be scheduled with
represented as follows. S6 or S7 or S9, after applying graph
Table 1: Different subjects and subject colouring concept. So that needed a number
clashes of time slots can be reduced by one.
Therefore, chromatic number is 12.
Clashes
No Subject Name with Then selected level- 4 semester I-time
1 Algebra 2,3,4 table to develop using graph colouring. This
2 Probability Theory 1,4,5 is complex for some extent, comparing to
3 Graph Theory 1,4,6,7 the level 1-time table. Because there are
4 Java Programming 1,2,3,5,6,7,9 much more combinations than first year.
5 Sampling 2,4,7,8,9 The combinations are three specialized areas
6 Accounts 3,4,7 and 12 joint major areas. Hence there are
7 Economics 3,4,5,6 about 15 number of different combinations.
8 English 5 There were 17 different number of
9 Magnetism 4,5 subjects to be scheduled. Among these

subjects Quality Control & Programmable
• Then have to allocate minimum Logic Device, Optoelectronics & Computer
number of time slots which are needed to based Modeling and Simulation, Stochastic
schedule all the subjects.
Processes & Communication Technology,
3.2 Chromatic Number Communication Theory & Complex
Variables can be scheduled in same time
• Chromatic number is the smallest
number of colours needed to colour a graph slots. Therefore, the number of needed time
G so that no two adjacent vertices share the slots can be reduced by 6. So that chromatic
same colour. number is 11. As our final goal we have
•The chromatic number of a graph G is developed conflict-free time table for the
most commonly denoted χ(G), but 3rd year students while minimizing number
occasionally γ(G) also can be used. of time slots. There were 18 number of
different subjects. After applying graph
3.3 Graph Representation colouring, number of time slots can be
• This problem can be represented as a reduced by 2. Because Advanced Calculus
graph where every vertex is a subject and an & Operations Management II, Advanced
edge between two vertices means there is a Calculus & Rapid Application
common student. Development, Mathematical Methods &
•In this graph colouring problem, Environmental Management subjects can be
minimum number of time slots required is scheduled in same time slots. So that
equal to the chromatic number of the graph. chromatic number is 16.

141