Exam Timetabling Using Graph Colouring Approach Computer Science Essay

Abstract – Timetabling at big covering many different types of jobs which have their ain alone features. In instruction, the three most common academic timetabling jobs are school timetable, university timetable and test timetable. Exam timetable is important but hard to be done manually due to the complexness of the job due to some grounds such as double academic calendar, increasing pupil registrations, restrictions of resources and etc. This survey presents a solution method for test timetable job in Centre for foundation surveies and extension instruction ( FOSEE ) , Multimedia University, Malaysia. The method of solution is a heuristic attack that include graph coloring, bunch heuristic and consecutive heuristic.

Keywords- test timetabling, graph coloring heuristic, cluster heuristic

Introduction

Timetabling is at big covering many different types of jobs which have their ain alone features. Normally, timetable is designed in a tabular signifier utilizing room-time slot matrix information. A timetable is presented for events to take topographic point and it does non needfully connote the allotment of resources [ 1 ] . However, in world it is of import to cognize whether the resources available are sufficient or non for the given event to take topographic point at a peculiar clip.

In instruction, the three most common academic timetabling jobs are school timetable, university timetable and test timetable. University timetables are more complex compared to school timetables which have equal clip slot and it is hebdomadal repeated during a semester [ 2 ] . Time slot for university timetable is non equal in length, some topics are taught every hebdomad in weekdays, some of them are merely taught during weekends, others are merely taught in first seven hebdomads in the semester, etc. At the terminal of each semester or trimester, most educational establishment must fix a set of scrutiny agendas for their pupils. Normally, a timetable that has been used antecedently will be recycled and used once more. Some minor accommodations may necessitate to be made and this can be done manually so that the new test timetable is acceptable. Exam timetabling attack is divided into four categorizations [ 6 ] which are bunch or decomposition methods [ 7 ] , [ 8 ] , [ 9 ] , consecutive methods [ 10 ] , [ 11 ] , constraint-based attacks [ 12 ] , [ 13 ] and meta-heuristic methods [ 14 ] , [ 15 ] , [ 16 ] .

Examination TIMETABLING

Exam timetabling is the sub category of timetabling job which its events take topographic point in the university. Exam timetabling refers to a procedure of delegating exam entities to peculiar slots and suites in the timetable. Students are required to sit for one test in the specific room during a specific clip slot. Exam timetabling is one of NP-hard job [ 3 ] ; hence making an test timetable is hard to be done manually due to the complexness of the job. The complexness of the job arises due to some grounds such as double academic calendar, increasing pupil registrations, restrictions of resources, etc. Constraints involved in this job can be divided into two classs which are difficult restraints and soft restraints.

Difficult constrains are unacceptable jobs which can non happen at any per centum in order for the timetable to be considered as executable. Burke et Al. hold carried out a study on differences between difficult and soft restraints among British universities [ 3 ] . The most common difficult restraints can be summarized as follows:

Every test must be scheduled in precisely one clip slot

Every test must be assigned to a room ( s ) of sufficient size and assigned an invigilator ( s )

No pupil must be scheduled to be in two different tests at the same clip

There must be adequate seats in each period for all tests scheduled

Certain tests must be scheduled into specific clip slots or suites

Certain exams must take topographic point at the same time

Normally, exam timetable will fulfill all difficult restraints but the job is how to mensurate that it is a good timetable. Therefore, soft restraints will be used as the measuring which will measure either the timetable is good and practical or non. Soft restraints can be considered as penchants which will carry through some of the user demands to maximise the flawlessness of the timetable [ 4 ] .

In general, non all soft restraints can be satisfied. Soft restraints are frequently encountered, which include the undermentioned [ 3 ] :

Examinations for each pupil should be spread as far apart as possible

A pupil should non be required to take ten tests in Y periods

Time windows for certain tests

No more than ten tests taking topographic point at the same time

No more than y pupils scheduled to sit tests at any one clip

Examinations should non be split across suites

No more than one test in a room at a clip

Teacher or pupil penchants

Distance between suites keeping a given test should be minimized ( when the test is split across two or more suites )

The entire figure of periods should be minimized

Difficult restraints and soft restraints are really subjective to specify and it depends on the demands of the universities [ 4 ] . In some instances, restraint on room handiness is unneeded because that university have a big sum of suites that can be used for test. The restraints such as some tests must happen before other tests may non be relevant in some universities due to all tests have the same degree and non a pre-requisite test. For some exam timetabling jobs, it is hard to happen a executable solution at all [ 3 ] . Whereas for other jobs, there is a big figure of executable solutions and the focal point of the job work outing are really much directed to the minimisations of soft restraint misdemeanors [ 3 ] [ 4 ] .

Exam timetabling jobs in universities begin with the integrating of scrutiny informations and procedures from assorted sections, Centres, modules and/or subdivisions. It is a complex job due to the figure of tests that needs to be scheduled. The purpose of an test timetable is to vouch that all tests are scheduled and pupils can sit all the tests that they are required to make. The nonsubjective map in timetabling refers to burden punishment, where it is assigned to soft restraints that are non satisfied [ 5 ] .

PROBLEM STATEMENT

The current system at FOSEE, MMU merely considers the difficult restraints and ignores the soft restraints. For illustration, if the continuance for the test is seven yearss, the system will do certain the full test involve will be spread out within that continuance without look intoing the resources allotment and pupil restraints. There are no criterions for solution qualities that measure either the test timetable is executable or non. The system analyst merely makes certain that there is no colliding between topics and pupils can be fit in the specific room. Exam timetables should hold a standard solution quality so that if the individual in charge resigns or alteration, the new individual in-charge has a benchmark to mensurate the quality of test timetable.

This paper focuses on test informations for foundation pupil in MMU, Malaysia. The test timetabling job for trimester 2, 2009/2010 session consists of be aftering 39 different tests in six yearss utilizing eight locales with different capacity. This exam involves five foundations with two consumption of pupil. Furthermore, each twenty-four hours there are merely two slots available which are forenoon session and afternoon session. The chief aim of an test timetable is to vouch that all tests are scheduled and pupils can sit all the tests that they are required to make.

EXAMINATION TIMETABLING HEURISTICS

In exam timetabling job, topics need be to schedule into limited figure of clip slot. Clustering heuristic will be applied to divide exams into different group and struggle between tests is represented by struggle matrix. The nonsubjective map will be used to find the solution quality for test timetabling job. The graph coloring heuristic will be used to find the figure of exam slot for this job.

Decomposition of topic

Students are enrolled in the different topic harmonizing to their foundation and consumption. They have been group in the bunch based on their foundation and consumption. All foundation pupils will be stream in a specific bunch, hence a big figure of pupils can be dealt as a individual entity with a certain figure of pupils.

For decomposition of capable, topics will be divided into little group called as bunch. Two characteristic that will be used for decomposition are foundation and consumption. Each bunch will hold different coloring materials that represents their group. With this method, the job size becomes smaller and easy to find the struggle matrix between the topics based on coloring method. The research worker used four stairss in break uping capable into bunch which are: –

Stairss 1: Subjects will be divided into specific foundation. There are five foundations involve which are direction, technology, information engineering, jurisprudence and biological scientific discipline

Stairss 2: Subject will be divided into specific consumption. There are two consumptions involve which are intake 1 – Jun 2009/2010 and intake 2 – October 2009/2010

Stairss 3: Kind all the topics based on intake – Subject for first consumption will be sorted foremost because it has more topics and pupils compare to 2nd consumption. Subjects in specific group will be sorted harmonizing to pupil registration and codification for each topic will be assigned based on the sorting list.

Measure 4: Assigned specific coloring material for intake 1 group followed by consumption 2 group. The coloring material for each bunch will be assigned after topics have been sorted.

Table

The Clusters for Capable Decomposition

Cluster / Group

Description Group

Foundation

Consumption

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 capable merely suited for topic in one foundation and consumption but it did n’t back up topics with combination foundation or consumption. Due to this job, a particular group called as particular bunch has been created for pupil from combination of foundation or consumption. After topics have been group in particular bunch, it will be sorted harmonizing to pupil registration.

Then, codification will be assigned to stand for the topic and this topic did n’t hold any specific coloring material because it comes from combination foundation and consumption. After grouping, so the topic will sorted based on pupil registration ( kind in their group merely ) . Then codification topic will be assign to each topic. In Table II, S31 is an illustration of topic in particular bunch which enrol by pupil in either different foundation or consumption.

Stating the Constraints

The test timetabling job is to delegate tests to specific clip slot which must fulfill the difficult restraints with the aim of minimising the soft restraints misdemeanor [ 3 ] .

For this research, difficult restraints that must be satisfied are:

Exam restraint – there is merely one test for each topic.

Student struggle – a pupil can non take two tests at the same clip or slot.

Seating limitation – the figure of pupils seated for an test can non transcend the room capacity

Soft restraints for this job are: –

A pupil should non hold more than one exam per twenty-four hours

Examinations should non be split across suites

Objective maps will be used to mensurate how good the soft restraints are satisfied. This is of import to find the solution quality of the test timetable. Penalty = 1 will be given if the soft restraints are unsated. In this job, nonsubjective maps that minimize the figure of pupils holding two scrutinies in the same twenty-four hours and minimizes the figure of exams split into different room are used.

Conflict matrix

The struggle matrix is one of the most of import facets in test timetabling job stand foring difficult restraint or a brace of colliding tests. The building of the struggle matrix helps in determines the restraints that no pupil must go to more one test at the same clip. Two capable struggle with each other if there are at least one pupil take both topic. Researcher has to set up the struggle matrix that helps them to look into if two tests conflict with each other or non. Based on pupil ‘s class enrollment in each semester, research worker can calculate the struggle matrix.

In Table II below, the ‘x ‘ represents those braces of colliding tests based on their group coloring material. Code such as S17, will be used to stand for the topic alternatively of utilizing the topic name.

Table

Conflict matrix for Foundation Biological Science bunchs.

S17

S18

S19

S20

S31

Conflict Matrix

S17

ten

ten

ten

ten

4

S18

ten

ten

ten

ten

4

S19

ten

ten

ten

ten

4

S31S20

ten

ten

ten

ten

4

ten

ten

ten

ten

4

Conflict Matrix

4

4

4

4

4

Graph coloring for exam choice

The orders in which exams are selected are based on graph coloring attack. In graph coloring attack, each test is represented by different vertex where the borders between vertices represent the test struggle [ 18 ] , [ 19 ] . Coloring the graph is the procedure of apportioning the different coloring material to each vertex so that two next vertices will hold different coloring materials and each coloring material is tantamount to one period in the test timetable [ 17 ] , [ 18 ] .

The aim of graph coloring is to happen the minimal figure of coloring materials applied on the vertices of a graph so that no two next vertices have the same coloring material [ 20 ] . The chromatic figure of a graph is the least figure of colorss it takes to color its vertices so that next vertices have different colorss [ 20 ] . Based on the literature, graph coloring in considered as NP-complete job due to the fact that there is no efficient polynomial-time algorithm that can happen the chromatic figure for the graph.

Another manner of look intoing the struggle matrix is to see it from a graph position [ 19 ] . From a graph position, the entire figure of borders for the vertex peers to the struggle matrix for each topic in the matrix. As the illustration refer capable S19. This capable belongs to constellate Bio1 represent by violet coloring material. Entire struggle matrix for this topic is four ( refer Table II ) there for entire borders for the vertex in the graph coloring should be four.

Black

Tap

Cyan

Silver

Red

S31

S18

S17

S20

S19

Fig. 1 Graph for S19

Fig. 1 proved that struggle matrix in Table II can be used to happen entire figure of borders in graph coloring. Vertex S19 coloured by purple because it represent cluster group coloring material while for vertex S31, it combine four colorss because pupil from different foundation enrol in this topic. Five vertexes represent that this group of pupil enrol in five capable and these topics can non be agenda at the same period due.

Based on the literature, vertices with the same border must stand for with different coloring material. These colorss refer to chart coloring material non a group coloring material. These procedures will continuously choosing a vertex and delegating it a new coloring material such that no two next vertices have the same coloring material.

A solution exists if the coloring material is equal to the figure of vertexes in the bunch. Fig. 1 has five vertexes with the same border and the coloring material should be five colorss which represent five different slots. The five colorss in fig. 1 are black, bluish green, tap, Ag and ruddy. However, the entire struggle can non be applied for particular bunch due to combination of characteristic.

RESULT AND ANALYSIS

In this survey, all the 39 topics will be group into their bunch which have the same feature. The full topic will be group into eight different bunch based on their foundation and consumption. The full bunch will hold a group of topic and it can stand for as coloring material or group name. For illustration topic for foundation direction, intake spare 1 can stand for as g1 = Mgmt1. Decomposition topic will assist research in cut downing the job size and it really utile for determine the struggle matrix between topics. Based on decomposition, research worker can specify either the topic can slot or delegate in the same slot or non in the test timetable.

Table

Subjects based on bunch group for consumption 1 and 2

INTAKE 1 – Jun 2009/2010

Code

Capable

Bunch: Mgmt1

S1

PHD0015

S2

PPE0025

S3

PCA0025

S4

PFM0025

Bunch: Engin1

S5

PCE0015

S6

PMC0025

S7

PPH0025

S8

PMC0055

Bunch: IT1

S9

PPT0015

S10

PFE0015

S11

PPC0045

S12

PMT0055

Bunch: Law1

S13

PCR0015

S14

PGL0025

S15

PIL0015

S16

PAL0015

Bunch: Bio1

S17

PBB0025

S18

PMB0015

S19

PCA0055

S20

PPB0025

INTAKE 2 – October 2009/2010

Bunch: Mgmt2

S21

PBM0035 / PFM0015

S22

PAT0025

S23

PPE0015

S24

PAT0035

Bunch: Engin2

S25

PPH0075

S26

PMC0045

Bunch: IT2

S27

PPC0035

S28

PMT0045

S29

PCA0045

S30

PCT0015

For this job, 39 topics should be agenda but nevertheless, merely 30 topics have been group in the bunch group. Cluster group for decomposition of capable merely suited for topic in one foundation and consumption but it did n’t back up topics with combination foundation or consumption.

Therefore another nine topics can non be group in the current bunch. Due to this job, a particular group called as particular bunch has been created for pupil from combination of foundation or consumption. After topics have been group in particular bunch, it will be sorted harmonizing to pupil registration. Then, codification will be assigned to stand for the topic.

After decomposition of topics, struggle between topics will be determine by utilizing struggle matrix tabular array. For this job, maximal figure of struggle is 23 for capable S31. Subject S31 is a nucleus topic where four group of pupil enrol in this topic. For normal group, capable under Mgmt1 and Engin1 group have the maximal figure of struggle, eight. Based on struggle matrix, it shows that nine colorss are used in the graph coloring for this test job. These nine colorss represent nine slots that should be used for this job.

Fig. 2 The overall graph coloring

Fig 2 shows the overall graph coloring heuristic that used nine different colorss that represent nine slots. While Table IV below show the full nine colors and the topic for each coloring material with the pupil registration.

Table

Summary of graph coloring and capable

Graph Colour

Code

Student registration

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

Tap

S35, S5, S17, S25, S14

507

Silver

S36, S8, S18, S15

271

After topics have been group harmonizing to specific coloring material for programming, the test slot ( coloring material ) now sorted harmonizing to figure of pupil registration per slot. Examination with the highest figure of pupil registrations should be scheduled foremost. Constructive heuristic with largest registration will bring forth initial solution by consecutive choosing an test and delegating the test to a executable slot without go againsting any difficult restraints.

In this survey, the constructive heuristic used in happening an initial solution is the largest registration graph coloring heuristic. This algorithm begins with an test with the highest registration and assigns it to the first available slot. If a slot is non available, the test is put into the following available slot. A slot is executable if it fulfil the soft restraint where a pupil should non hold more than one exam per twenty-four hours. In this heuristic, the possible punishment of delegating test to each period is calculated and the period with minimal punishment is selected.

Table

Slot agreement based on largest registration

Slot Agreement

Graph Colour ( Exam )

Student registration

1

Orange

1323

2

Green

1145

3

Red

1116

4

Yellow

953

5

Magenta

893

6

Tap

507

7

Cyan

401

8

Black

384

9

Silver

271

Period choice utilizing nine slots

The test will be assign into test timetable based on pupil registration. To delegate the test into period or slot, algorithm will look into the soft restraint which is pupil merely can sit for one test per twenty-four hours. If impracticable, it will travel to the following slot until reach the last slot which is slot nine. Then it will get down once more from empty slot and this clip punishment of delegating test to each period is calculated and the period with minimal punishment is selected.

As the consequence utilizing nine slots, merely 16 out of 39 topics will go against the soft restraint. With nine slots, all topics that have conflict matrix nine will go against the soft restraint because figure of slot available is equal to figure of struggle matrix.

Based on this period choice, it shows that the test timetable for trimester 2, 2009-2010 merely used nine slots compare to the original test timetable which used 12 slots. With this method research workers save three slots and it means they besides save the resources such as room and invigilator. Even though this method non an optimizing option, but with this executable solution it will assist the direction and academician in their day-to-day undertaking with minimal figure of exam slot. These methods give more advantages to the direction side comparison to student side. It possibly burdens the pupil due to diminishing figure of slot from 12 slots to nine slots merely.

Period choice utilizing 12 slots

In this subdivision, research workers will utilize the full 12 slot provided by the direction. In the current test timetable, university has allocated 12 slots for FOSEE pupils to sit for their test in trimester2, 2009/2010. All the procedure is same as period choice utilizing nine slots and the lone different is slot will be increase from nine to 12 slots.

Experiment show that the 2nd method gives merely 10 punishments but in term of resources, research workers drag the test until Saturday and there are three slots is fresh for this method. There merely a little different for punishment but it has a large impact for the resources. In this test timetabling job, the maximal struggle matrix is nine and with 12 clip slot, merely three of nine topics will carry through the first soft restraints. Capable with six or less than six conflict matrix should carry through the first soft restraint. However with graph coloring heuristic, researcher merely indiscriminately choose the topic and did n’t used any method to look into the sequence of coloring material group in the graph.

Based on the experiment with 12 slots, pupils can hold more clip to analyze due to breach for the test. However with 10 punishments, it shows that non all pupils have gap for the following test.

Period choice without punishment

In this subdivision researcher attempt to come out with exam timetables that have zero or no punishment at all. This method will give pupil more clip to analyze but it drag the exam continuance and hard to be implement in FOSEE, MMU due to restriction of clip and resources.

To guarantee that pupils did n’t hold two tests in the same twenty-four hours, direction demand to supply 17 slot which equivalent to nine yearss. Based on struggle matrix upper limit capable per group are nine which equivalent to nine slots for test. This test can non be agenda in the same slot and twenty-four hours due to difficult restraint and soft restraint. Therefore, the test should be agenda in the forenoon slot and no test for afternoon slot.

Student in FOSEE merely have a hebdomad interruption before they start a new trimester. If direction drag the exam continuances more than one hebdomad, it means at the same clip it consequence the pupil vacation. Possibly pupil did n’t hold holiday at all. This besides will burthen the academician and direction. Academician demand to fight to tag the exam paper and at the same clip they need to fix for new trimester.

Room choice

After bring forthing the test timetable for all the topics, distribution of pupils among the room will be done utilizing choice heuristic. The job of suiting pupils into room is tantamount to the backpack filling job where research workers have a set of tests to be fitted into a set of suites [ 18 ] , [ 19 ] , [ 20 ] . The aim is to suit as many pupils as possible into each room to maximise the usage or room. For this job, a sorted list of topic for a specific period will suit in the room based on: –

largest first – the largest infinites available will be fit first to optimise the use of largest infinite and minimise the figure of locale and invigilators.

best tantrum – test will be fit in the smallest sum of staying room capacity

The room choice plants by make fulling up the largest suites foremost, so go oning on with the smallest sum of staying capacity until all tests are assigned to the room [ 20 ] . One of the major job in room choice is the figure of pupils can non be fit in one locale or more than one tests are scheduled in the same room at one clip [ 18 ] , [ 19 ] , [ 20 ] . In this room choice, punishment of suiting same topics in different room is calculated and the room with minimal punishment is selected.

Comparison

At the terminal of every semester, pupil in the university will sit for their concluding tests based on topic that have been registered. The continuance for concluding test in FOSEE, MMU for trimester 2, 2009-2010 is six yearss including Saturday. It involves 12 slots which are forenoon slot and afternoon slot. The exams screen 39 topics from assorted foundation and consumption. Eight suites with different capacity have been provided as the test locale.

Based on the experiment, continuance for concluding test for this job can be reduced if the effectual methods in bring forthing test timetable have been applied. Using the bunch heuristic and graph coloring heuristic attack, research worker can cut down exam continuance from six yearss ( 12 slots ) to merely five yearss ( nine slots ) . Comparison for first soft restraint which is exam punishment ( more than one exam per twenty-four hours ) between current timetable and suggestion timetable has been made. Therefore with current test timetable, the test punishment is 14 while with suggestion test timetable, the test punishment is 16. Difference for test punishment between this two timetables merely two topics. It shows that if research workers arrange the topic efficaciously they can minimise the test punishment and it proved that continuance for the test did n’t act upon the test punishment.

Analyzing sing maximal and minimal figure of pupils per test in one slot has been made and it shows that the current test timetable did n’t use the use of the slot because it shows a large spread between the current test timetable and suggestion test timetable. Suggestion exam timetable can schedule the test for maximal 1323 pupils per slot and minimal 271 pupils per slot while current test timetable merely schedule maximal 1263 pupils per slot and minimal 95 pupils per slot.

With the longer exam continuance, current test timetable usage about 39 locale or room to back up the full topic for the test while suggestion test timetable merely used 31 locales to back up all tests. Room punishment show that current test timetable is non truly good assigned because the different merely five topic.

Table

Comparison between current timetable and suggestion method

Current timetable

Suggestion timetable

Exam continuance ( in yearss )

6

5

Slot used to schedule the test

12

9

Exam Penalty – more than one exam per twenty-four hours

14

16

Minimal pupil in one slot

95

271

Maximal pupil in one slot

1263

1323

Room Penalty – split capable in different room

19

14

Room used

39

31

CONCLUSION AND SUGGESTION

An test timetable is considered as good quality if all soft restraints under consideration are minimized. For illustration, if the scrutiny period is short ( less than one hebdomad ) , it might be ineluctable or hard to delegate one test per twenty-four hours for pupils to sit and it should be minimized the figure of pupils that have more than one exam per twenty-four hours. The usage of constellating heuristic is really of import to break up the topic based on their characteristic ( foundation and consumption ) and this filtering technique really of import when research worker applies the struggle matrix to observe colliding capable. With the struggle matrix tabular array it help the research worker to recheck the clashing of capable based on bunch coloring material.

The graph coloring heuristic is used to group the topic based on coloring material and one coloring material is represent one test. Each topic will stand for as a vertex and the struggle are represent by the borders between the vertexes. Vertex with the some borders can non be agenda in the same clip slot. To slot the tests in test timetable, the largest registration attack will be used. This attack will choose the tests with highest figure of pupil to suit in the slot foremost.

This survey has produced a executable attack for exam timetable in FOSEE, MMU utilizing a new technique such as combination of constellating and graph coloring heuristic. Even though this survey may be able to bring forth a good test timetable, there are still many affairs to be studied.

Based on the experiment, graph coloring heuristic is suited for the job that focal point on difficult restraint but it is hard to work out the soft restraints. To acquire the optima solution, meta-heuristic attack should be use together with graph coloring attack such as familial algorithm, taboo hunt, etc.

This research merely provides method or attack that can be apply for test timetable but it did n’t hold any automated or computerized system. It will be good thoughts if this method can be apply as machine-controlled system utilizing a specific tool and linguistic communication. Using a computerized system, the end product can be more consistent and the experiment can be applied for any job size.

It will be a better thought if the system is a web-based test timetable. Therefore, academician can easy look into and formalize the topic involve in scrutiny and system analyst besides will acquire a faster respond from academician.

The research worker found that this method can be extended to another module in MMU. This is because the survey has fulfilled a basic demand of the test timetable and all modules in MMU have the same modus operandi in developing the test timetable.