A graph edge colouring approach for school timetabling problems. (1st January 2014)

• Record Type: Journal Article
• Authors: Badoni, Rakesh P.; Gupta, D.K.
• Is Part Of: International journal of mathematics in operational research. Volume 6:Number 1(2014)
• Page Start: 123
• Page End: 138
• Publication Date: 2014-01-01
• Subjects: bipartite multigraph -- graph edge colouring -- scheduling -- CPU time -- requirement matrix -- constraint; Operations research -- Mathematical models -- Periodicals; Operations research -- Mathematics -- Periodicals; Decision making -- Mathematical models -- Periodicals; 658.4033
• Languages: English
• ISSNs: 1757-5850

Abstract

School timetabling problems require weekly scheduling of lectures for subjects between teachers and classes in fixed time periods such that a set of constraints are satisfied. In this paper, a school timetabling problem is solved using a graph edge coloring algorithm in two phases. A bipartite multigraph is used in the first phase to get daily requirement matrices for each day of the week from weekly requirement matrix obtained by solving a system of linear equations for the variables taking integer values. Next, bipartite graphs are used in the second phase to assign lectures over unconstrained time slots for each day. The algorithm is tested on a number of randomly generated data sets and a timetable for a simple data set is given. The performance of the algorithm measured in terms of the number of iterations required and amount of CPU time in seconds is summarised in a table.