Title: A graph edge colouring approach for school timetabling problems

Authors: Rakesh P. Badoni; D.K. Gupta

Addresses: Department of Mathematics, Indian Institute of Technology, Kharagpur 721 302, West Bengal, India ' Department of Mathematics, Indian Institute of Technology, Kharagpur 721 302, West Bengal, India

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 colouring 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.

Keywords: bipartite multigraph; graph edge colouring; CPU time; requirement matrix; constraints; school timetabling; lecture scheduling; timetable scheduling; school classes; class scheduling.

DOI: 10.1504/IJMOR.2014.057853

International Journal of Mathematics in Operational Research, 2014 Vol.6 No.1, pp.123 - 138

Received: 18 Sep 2012
Accepted: 11 Nov 2012

Published online: 28 Jun 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article