A graph edge colouring approach for school timetabling problems

Rakesh P. Badoni and D.K. Gupta

International Journal of Mathematics in Operational Research, 2014, vol. 6, issue 1, 123-138

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. (search for similar items in EconPapers)
Date: 2014
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=57853 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijmore:v:6:y:2014:i:1:p:123-138

Access Statistics for this article

More articles in International Journal of Mathematics in Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().