Abstract - Timetabling at large covering many different types of problems which have their own unique characteristics. In education, the three most common academic timetabling problems are school timetable, university timetable and exam timetable. Exam timetable is crucial but difficult to be done manually due to the complexity of the problem due to some reasons such as dual academic calendar, increasing student enrolments, limitations of resources and etc. This study presents a solution method for exam timetable problem in centre for foundation studies and extension education (FOSEE), Multimedia University, Malaysia. The method of solution is a heuristic approach that include graph colouring, cluster heuristic and sequential heuristic.
Keywords- exam timetabling, graph colouring heuristic, cluster heuristic
INTRODUCTION
Timetabling is at large covering many different types of problems which have their own unique characteristics. Normally, timetable is designed in a tabular form using room-time slot matrix information. A timetable is presented for events to take place and it does not necessarily imply the allocation of resources [1]. However, in reality it is important to know whether the resources available are sufficient or not for the given event to take place at a particular time.
In education, the three most common academic timetabling problems are school timetable, university timetable and exam timetable. University timetables are more complex compared to school timetables which have equal time slot and it is weekly repeated during a semester [2]. Time slot for university timetable is not equal in length, some subjects are taught every week in weekdays, some of them are only taught during weekends, others are only taught in first seven weeks in the semester, etc. At the end of each semester or trimester, most educational institution must prepare a set of examination schedules for their students. Normally, a timetable that has been used previously will be recycled and used again. Some minor adjustments may need to be made and this can be done manually so that the new exam timetable is acceptable. Exam timetabling approach is divided into four classifications [6] which are cluster or decomposition methods [7], [8], [9], sequential methods [10], [11], constraint-based approaches [12], [13] and meta-heuristic methods [14], [15], [16].
EXAMINATION TIMETABLING
Exam timetabling is the sub class of timetabling problem which its events take place in the university. Exam timetabling refers to a process of assigning exam entities to particular slots and rooms in the timetable. Students are required to seat for one exam in the specific room during a specific time slot. Exam timetabling is one of NP-hard problem [3]; therefore creating an exam timetable is difficult to be done manually due to the complexity of the problem. The complexity of the problem arises due to some reasons such as dual academic calendar, increasing student enrolments, limitations of resources, etc. Constraints involved in this problem can be divided into two categories which are hard constraints and soft constraints.
Hard constrains are unacceptable problems which cannot occur at any percentage in order for the timetable to be considered as feasible. Burke et al. have carried out a survey on differences between hard and soft constraints among British universities [3]. The most common hard constraints can be summarized as follows:
Every exam must be scheduled in exactly one time slot
Every exam must be assigned to a room(s) of sufficient size and assigned an invigilator(s)
No student must be scheduled to be in two different exams at the same time
There must be enough seats in each period for all exams scheduled
Certain exams must be scheduled into specific time slots or rooms
Certain exams must take place simultaneously
Normally, exam timetable will satisfy all hard constraints but the problem is how to measure that it is a good timetable. Thus, soft constraints will be used as the measurement which will evaluate either the timetable is good and practical or not. Soft constraints can be considered as preferences which will fulfil some of the user requirements to maximize the perfection of the timetable [4].
In general, not all soft constraints can be satisfied. Soft constraints are often encountered, which include the following [3]:
Exams for each student should be spread as far apart as possible
A student should not be required to take x exams in y periods
Time windows for certain exams
No more than x exams taking place simultaneously
No more than y students scheduled to sit exams at any one time
Exams should not be split across rooms
No more than one exam in a room at a time
Teacher or student preferences
Distance between rooms holding a given exam should be minimized (when the exam is split across two or more rooms)
The total number of periods should be minimized
Hard constraints and soft constraints are very subjective to define and it depends on the requirements of the universities [4]. In some cases, constraint on room availability is unnecessary because that university have a large amount of rooms that can be used for exam. The constraints such as some exams must occur before other exams may not be relevant in some universities due to all exams have the same level and not a pre-requisite exam. For some exam timetabling problems, it is difficult to find a feasible solution at all [3]. Whereas for other problems, there is a large number of feasible solutions and the focus of the problem solving are very much directed to the minimizations of soft constraint violations [3] [4].
Exam timetabling problems in universities begin with the integration of examination data and processes from various departments, centres, faculties and/or branches. It is a complex problem due to the number of exams that needs to be scheduled. The aim of an exam timetable is to guarantee that all exams are scheduled and students can sit all the exams that they are required to do. The objective function in timetabling refers to weighted penalty, where it is assigned to soft constraints that are not satisfied [5].
PROBLEM STATEMENT
The current system at FOSEE, MMU only considers the hard constraints and ignores the soft constraints. For example, if the duration for the exam is seven days, the system will make sure the entire exam involve will be spread out within that duration without checking the resources allocation and student constraints. There are no standards for solution qualities that measure either the exam timetable is feasible or not. The system analyst just makes sure that there is no clashing between subjects and students can be fit in the specific room. Exam timetables should have a standard solution quality so that if the person in charge resigns or change, the new person in-charge has a benchmark to measure the quality of exam timetable.
This paper focuses on exam data for foundation student in MMU, Malaysia. The exam timetabling problem for trimester 2, 2009/2010 session consists of planning 39 different exams in six days using eight venues with different capacity. This exam involves five foundations with two intake of student. Furthermore, each day there are only two slots available which are morning session and afternoon session. The main objective of an exam timetable is to guarantee that all exams are scheduled and students can sit all the exams that they are required to do.
EXAMINATION TIMETABLING HEURISTICS
In exam timetabling problem, subjects need be to schedule into limited number of time slot. Clustering heuristic will be applied to split exams into different group and conflict between exams is represented by conflict matrix. The objective function will be used to determine the solution quality for exam timetabling problem. The graph colouring heuristic will be used to determine the number of exam slot for this problem.
Decomposition of subject
Students are enrolled in the different subject according to their foundation and intake. They have been group in the cluster based on their foundation and intake. All foundation students will be stream in a specific cluster, therefore a large number of students can be dealt as a single entity with a certain number of students.
For decomposition of subject, subjects will be divided into small group called as cluster. Two characteristic that will be used for decomposition are foundation and intake. Each cluster will have different colour that represents their group. With this method, the problem size becomes smaller and easy to determine the conflict matrix between the subjects based on colouring method. The researcher used four steps in decomposing subject into cluster which are:-
Steps 1: Subjects will be divided into specific foundation. There are five foundations involve which are management, engineering, information technology, law and biological science
Steps 2: Subject will be divided into specific intake. There are two intakes involve which are intake 1 - Jun 2009/2010 and intake 2 - October 2009/2010
Steps 3: Sort all the subjects based on intake - Subject for first intake will be sorted first because it has more subjects and students compare to second intake. Subjects in specific group will be sorted according to student enrolment and code for each subject will be assigned based on the sorting list.
Step 4: Assigned specific colour for intake 1 group followed by intake 2 group. The colour for each cluster will be assigned after subjects have been sorted.
TABLE
The Clusters for Subject Decomposition
Cluster / Group
Description Group
Foundation
Intake
g1
Mgmt1
Management
Trimester 1
g2
IT1
Information Technology
Trimester 1
g3
Engin1
Engineering
Trimester 1
g4
Law1
Law
Trimester 1
g5
Bio1
Biological Science
Trimester 1
g6
Mgmt2
Management
Trimester 2
g7
IT2
Information Technology
Trimester 2
g8
Engin2
Engineering
Trimester 2
Cluster group for decomposition of subject only suitable for subject in one foundation and intake but it didn't support subjects with combination foundation or intake. Due to this problem, a special group called as special cluster has been created for student from combination of foundation or intake. After subjects have been group in special cluster, it will be sorted according to student enrolment.
Then, code will be assigned to represent the subject and this subject didn't have any specific colour because it comes from combination foundation and intake. After grouping, then the subject will sorted based on student enrolment (sort in their group only). Then code subject will be assign to each subject. In Table II, S31 is an example of subject in special cluster which enrol by student in either different foundation or intake.
Stating the Constraints
The exam timetabling problem is to assign exams to specific time slot which must satisfied the hard constraints with the objective of minimizing the soft constraints violation [3].
For this research, hard constraints that must be satisfied are:
Exam constraint - there is only one exam for each subject.
Student conflict - a student cannot take two exams at the same time or slot.
Seating restriction - the number of students seated for an exam cannot exceed the room capacity
Soft constraints for this problem are:-
A student should not have more than one exam per day
Exams should not be split across rooms
Objective functions will be used to measure how well the soft constraints are satisfied. This is important to determine the solution quality of the exam timetable. Penalty = 1 will be given if the soft constraints are unsatisfied. In this problem, objective functions that minimize the number of students having two examinations in the same day and minimizes the number of exams split into different room are used.
Conflict matrix
The conflict matrix is one of the most important aspects in exam timetabling problem representing hard constraint or a pair of clashing exams. The construction of the conflict matrix helps in determines the constraints that no student must attend more one exam at the same time. Two subject conflict with each other if there are at least one student take both subject. Researcher has to establish the conflict matrix that helps them to check if two exams conflict with each other or not. Based on student's course registration in each semester, researcher can compute the conflict matrix.
In Table II below, the 'x' represents those pairs of clashing exams based on their group colour. Code such as S17, will be used to represent the subject instead of using the subject name.
TABLE
Conflict matrix for Foundation Biological Science clusters.
S17
S18
S19
S20
S31
Conflict Matrix
S17
x
x
x
x
4
S18
x
x
x
x
4
S19
x
x
x
x
4
S31S20
x
x
x
x
4
x
x
x
x
4
Conflict Matrix
4
4
4
4
4
Graph colouring for exam selection
The orders in which exams are selected are based on graph colouring approach. In graph colouring approach, each exam is represented by different vertex where the edges between vertices represent the exam conflict [18], [19]. Colouring the graph is the process of allocating the different colour to each vertex so that two adjacent vertices will have different colour and each colour is equivalent to one period in the exam timetable [17], [18].
The objective of graph colouring is to find the minimum number of colour applied on the vertices of a graph so that no two adjacent vertices have the same colour [20]. The chromatic number of a graph is the least number of colours it takes to colour its vertices so that adjacent vertices have different colours [20]. Based on the literature, graph colouring in considered as NP-complete problem due to the fact that there is no efficient polynomial-time algorithm that can find the chromatic number for the graph.
Another way of checking the conflict matrix is to view it from a graph perspective [19]. From a graph perspective, the total number of edges for the vertex equals to the conflict matrix for each subject in the matrix. As the example refer subject S19. This subject belongs to cluster Bio1 represent by purple colour. Total conflict matrix for this subject is four (refer Table II) there for total edges for the vertex in the graph colouring should be four.
Black
Pink
Cyan
Silver
Red
S31
S18
S17
S20
S19
Fig. 1 Graph for S19
Fig. 1 proved that conflict matrix in Table II can be used to find total number of edges in graph colouring. Vertex S19 coloured by purple because it represent cluster group colour while for vertex S31, it combine four colours because student from different foundation enrol in this subject. Five vertexes represent that this group of student enrol in five subject and these subjects cannot be schedule at the same period due.
Based on the literature, vertices with the same edge must represent with different colour. These colours refer to graph colour not a group colour. These processes will continuously selecting a vertex and assigning it a new colour such that no two adjacent vertices have the same colour.
A solution exists if the colour is equal to the number of vertexes in the cluster. Fig. 1 has five vertexes with the same edge and the colour should be five colours which represent five different slots. The five colours in fig. 1 are black, cyan, pink, silver and red. However, the total conflict can not be applied for special cluster due to combination of characteristic.
RESULT AND ANALYSIS
In this study, all the 39 subjects will be group into their cluster which have the same characteristic. The entire subject will be group into eight different cluster based on their foundation and intake. The entire cluster will have a group of subject and it can represent as colour or group name. For example subject for foundation management, intake trimester 1 can represent as g1 = Mgmt1. Decomposition subject will help research in reducing the problem size and it very useful for determine the conflict matrix between subjects. Based on decomposition, researcher can define either the subject can slot or assign in the same slot or not in the exam timetable.
TABLE
Subjects based on cluster group for intake 1 and 2
INTAKE 1 - Jun 2009/2010
Code
Subject
Cluster : Mgmt1
S1
PHD0015
S2
PPE0025
S3
PCA0025
S4
PFM0025
Cluster : Engin1
S5
PCE0015
S6
PMC0025
S7
PPH0025
S8
PMC0055
Cluster : IT1
S9
PPT0015
S10
PFE0015
S11
PPC0045
S12
PMT0055
Cluster : Law1
S13
PCR0015
S14
PGL0025
S15
PIL0015
S16
PAL0015
Cluster : Bio1
S17
PBB0025
S18
PMB0015
S19
PCA0055
S20
PPB0025
INTAKE 2 - October 2009/2010
Cluster : Mgmt2
S21
PBM0035 / PFM0015
S22
PAT0025
S23
PPE0015
S24
PAT0035
Cluster : Engin2
S25
PPH0075
S26
PMC0045
Cluster : IT2
S27
PPC0035
S28
PMT0045
S29
PCA0045
S30
PCT0015
For this problem, 39 subjects should be schedule but however, only 30 subjects have been group in the cluster group. Cluster group for decomposition of subject only suitable for subject in one foundation and intake but it didn't support subjects with combination foundation or intake.
Therefore another nine subjects cannot be group in the current cluster. Due to this problem, a special group called as special cluster has been created for student from combination of foundation or intake. After subjects have been group in special cluster, it will be sorted according to student enrolment. Then, code will be assigned to represent the subject.
After decomposition of subjects, conflict between subjects will be determine by using conflict matrix table. For this problem, maximum number of conflict is 23 for subject S31. Subject S31 is a core subject where four group of student enrol in this subject. For normal group, subject under Mgmt1 and Engin1 group have the maximum number of conflict, eight. Based on conflict matrix, it shows that nine colours are used in the graph colouring for this exam problem. These nine colours represent nine slots that should be used for this problem.
Fig. 2 The overall graph colouring
Fig 2 shows the overall graph colouring heuristic that used nine different colours that represent nine slots. While Table IV below show the entire nine colours and the subject for each colour with the student enrolment.
TABLE
Summary of graph colouring and subject
Graph Colour
Code
Student enrolment
Red
S31 , S37
1116
Yellow
S10 , S3 , S39 , S23 , S27
953
Green
S9 , S2 , S33 , S24 , S29
1145
Magenta
S11 , S1 , S38 , S28
893
Cyan
S12, S4, S6, S16, S19
401
Orange
S32, S7, S30, S21
1323
Black
S34, S20, S26, S22, S13
384
Pink
S35, S5, S17, S25, S14
507
Silver
S36, S8, S18, S15
271
After subjects have been group according to specific colour for scheduling, the exam slot (colour) now sorted according to number of student enrolment per slot. Exam with the highest number of student enrolments should be scheduled first. Constructive heuristic with largest enrolment will generate initial solution by sequentially selecting an exam and assigning the exam to a feasible slot without violating any hard constraints.
In this study, the constructive heuristic used in finding an initial solution is the largest enrolment graph colouring heuristic. This algorithm begins with an exam with the highest enrolment and assigns it to the first available slot. If a slot is not available, the exam is put into the next available slot. A slot is feasible if it fulfil the soft constraint where a student should not have more than one exam per day. In this heuristic, the potential penalty of assigning exam to each period is calculated and the period with minimum penalty is selected.
TABLE
Slot arrangement based on largest enrolment
Slot Arrangement
Graph Colour (Exam)
Student enrolment
1
Orange
1323
2
Green
1145
3
Red
1116
4
Yellow
953
5
Magenta
893
6
Pink
507
7
Cyan
401
8
Black
384
9
Silver
271
Period selection using nine slots
The exam will be assign into exam timetable based on student enrolment. To assign the exam into period or slot, algorithm will check the soft constraint which is student only can seat for one exam per day. If unfeasible, it will go to the next slot until reach the last slot which is slot nine. Then it will start again from empty slot and this time penalty of assigning exam to each period is calculated and the period with minimum penalty is selected.
As the result using nine slots, only 16 out of 39 subjects will violate the soft constraint. With nine slots, all subjects that have conflict matrix nine will violate the soft constraint because number of slot available is equal to number of conflict matrix.
Based on this period selection, it shows that the exam timetable for trimester 2, 2009-2010 only used nine slots compare to the original exam timetable which used 12 slots. With this method researchers save three slots and it means they also save the resources such as room and invigilator. Even though this method not an optimizing option, but with this feasible solution it will help the management and academician in their daily task with minimum number of exam slot. These methods give more advantages to the management side compare to student side. It maybe burdens the student due to decreasing number of slot from 12 slots to nine slots only.
Period selection using 12 slots
In this section, researchers will use the entire 12 slot provided by the management. In the current exam timetable, university has allocated 12 slots for FOSEE students to seat for their exam in trimester2, 2009/2010. All the process is same as period selection using nine slots and the only different is slot will be increase from nine to 12 slots.
Experiment show that the second method gives only 10 penalties but in term of resources, researchers drag the exam until Saturday and there are three slots is unused for this method. There only a small different for penalty but it has a big impact for the resources. In this exam timetabling problem, the maximum conflict matrix is nine and with 12 time slot, only three of nine subjects will fulfil the first soft constraints. Subject with six or less than six conflict matrix should fulfil the first soft constraint. However with graph colouring heuristic, researcher just randomly choose the subject and didn't used any method to check the sequence of colour group in the graph.
Based on the experiment with 12 slots, students can have more time to study due to gap for the exam. However with 10 penalties, it shows that not all students have gap for the next exam.
Period selection without penalty
In this section researcher try to come out with exam timetables that have zero or no penalty at all. This method will give student more time to study but it drag the exam duration and difficult to be implement in FOSEE, MMU due to limitation of time and resources.
To ensure that students didn't have two exams in the same day, management need to provide 17 slot which equivalent to nine days. Based on conflict matrix maximum subject per group are nine which equivalent to nine slots for exam. This exam cannot be schedule in the same slot and day due to hard constraint and soft constraint. Therefore, the exam should be schedule in the morning slot and no exam for afternoon slot.
Student in FOSEE only have a week break before they start a new trimester. If management drag the exam durations more than one week, it means at the same time it effect the student holiday. Maybe student didn't have holiday at all. This also will burden the academician and management. Academician need to struggle to mark the exam paper and at the same time they need to prepare for new trimester.
Room selection
After producing the exam timetable for all the subjects, distribution of students among the room will be done using selection heuristic. The problem of fitting students into room is equivalent to the knapsack filling problem where researchers have a set of exams to be fitted into a set of rooms [18], [19], [20]. The objective is to fit as many students as possible into each room to maximize the use or room. For this problem, a sorted list of subject for a specific period will fit in the room based on:-
largest first - the largest spaces available will be fit first to optimize the usage of largest space and minimize the number of venue and invigilators.
best fit - exams will be fit in the smallest amount of remaining room capacity
The room selection works by filling up the largest rooms first, then continuing on with the smallest amount of remaining capacity until all exams are assigned to the room [20]. One of the major problem in room selection is the number of students cannot be fit in one venue or more than one exams are scheduled in the same room at one time[18], [19], [20]. In this room selection, penalty of fitting same subjects in different room is calculated and the room with minimum penalty is selected.
COMPARISON
At the end of every semester, student in the university will seat for their final exams based on subject that have been registered. The duration for final exam in FOSEE, MMU for trimester 2, 2009-2010 is six days including Saturday. It involves 12 slots which are morning slot and afternoon slot. The exams cover 39 subjects from various foundation and intake. Eight rooms with different capacity have been provided as the exam venue.
Based on the experiment, duration for final exam for this problem can be reduced if the effective methods in producing exam timetable have been applied. Using the cluster heuristic and graph colouring heuristic approach, researcher can reduce exam duration from six days (12 slots) to only five days (nine slots). Comparison for first soft constraint which is exam penalty (more than one exam per day) between current timetable and suggestion timetable has been made. Therefore with current exam timetable, the exam penalty is 14 while with suggestion exam timetable, the exam penalty is 16. Difference for exam penalty between this two timetables only two subjects. It shows that if researchers arrange the subject effectively they can minimize the exam penalty and it proved that duration for the exam didn't influence the exam penalty.
Analyzing regarding maximum and minimum number of students per exam in one slot has been made and it shows that the current exam timetable didn't utilize the usage of the slot because it shows a big gap between the current exam timetable and suggestion exam timetable. Suggestion exam timetable can schedule the exam for maximum 1323 students per slot and minimum 271 students per slot while current exam timetable only schedule maximum 1263 students per slot and minimum 95 students per slot.
With the longer exam duration, current exam timetable use about 39 venue or room to support the entire subject for the exam while suggestion exam timetable only used 31 venues to support all exams. Room penalty show that current exam timetable is not really well assigned because the different only five subject.
TABLE
Comparison between current timetable and suggestion method
Current timetable
Suggestion timetable
Exam duration (in days)
6
5
Slot used to schedule the exam
12
9
Exam Penalty - more than one exam per day
14
16
Minimum student in one slot
95
271
Maximum student in one slot
1263
1323
Room Penalty - split subject in different room
19
14
Room used
39
31
CONCLUSION AND SUGGESTION
An exam timetable is considered as good quality if all soft constraints under consideration are minimized. For example, if the examination period is short (less than one week), it might be unavoidable or difficult to assign one exam per day for students to sit and it should be minimized the number of students that have more than one exam per day. The use of clustering heuristic is very important to decompose the subject based on their characteristic (foundation and intake) and this filtering technique very important when researcher applies the conflict matrix to detect clashing subject. With the conflict matrix table it help the researcher to recheck the clashing of subject based on cluster colour.
The graph colouring heuristic is used to group the subject based on colour and one colour is represent one exams. Each subject will represent as a vertex and the conflict are represent by the edges between the vertexes. Vertex with the some edges cannot be schedule in the same time slot. To slot the exams in exam timetable, the largest enrolment approach will be used. This approach will select the exams with highest number of student to fit in the slot first.
This study has produced a feasible approach for exam timetable in FOSEE, MMU using a new technique such as combination of clustering and graph colouring heuristic. Even though this study may be able to produce a good exam timetable, there are still many matters to be studied.
Based on the experiment, graph colouring heuristic is suitable for the problem that focus on hard constraint but it is difficult to solve the soft constraints. To get the optima solution, meta-heuristic approach should be apply together with graph colouring approach such as genetic algorithm, tabu search, etc.
This research only provides method or approach that can be apply for exam timetable but it didn't have any automated or computerized system. It will be good ideas if this method can be apply as automated system using a specific tool and language. Using a computerized system, the output can be more consistent and the experiment can be applied for any problem size.
It will be a better idea if the system is a web-based exam timetable. Therefore, academician can easy check and validate the subject involve in examination and system analyst also will get a faster respond from academician.
The researcher found that this method can be extended to another faculty in MMU. This is because the study has fulfilled a basic requirement of the exam timetable and all faculties in MMU have the same routine in developing the exam timetable.
