At Adesoft, we believe that research and technologies can help us achieve great things! With this in mind, we have always thought about our solutions so that they are at the forefront of innovation. Our R&D team struggle every day to find the most optimal solution, the most efficient response, and the easiest use for you. In order to go even further in our desire to innovate, we announced that we were calling to the UTT (Université Technologique de Troyes) as part of a partnership. Almost a year later, where are we?

In this article, we want you to discover the premises of the common work we have undertaken to integrate graph theory into our timetabling solutions. Step into the backside and discover this technique with us!

Graph theory

First, “graph theory”, what is it?

As you can see, in “graph thory”, there is “graph”. So, a graph is a structure that is used to model a use case where a collection of objects are interconnected in a sparse way. A great example of this are the links between users of a social network like LinkedIn.

This graph then has vartices that represent the users of the social network, and edges that link between two people if they’re connected in the social network.

More formally, graph theory is a mathematical field that studies graph representations, explorations and algorithms to solve graph problems that model real work problems in many domains especially in computer science, networks, databases and timetabling.

Graph theory and timetabling

Graph theory is widely used to model timetabling problems. One of the examples is the graph coloring problem which aims to color vertices with a set of colours in a way that each adjacent vertices (have an edge between them) are colored using different colors. The basic example of this is if we want to color countries in a map and we want to color neighboring countries with different colors. Fun tip: we only need 4 colors to color the whole globe!

Let’s try to see where graph coloring can be used in scheduling and timetabling problems. Suppose we have N events to schedule, each of these events can use mj resources from the R resources we have. We then create a graph where vertices are the events, we then link between events i, i with an edge if they use the same resource. The edge means the events are in conflict and can’t be scheduled at the same time and the resulting graph is called the conflict graph.

If we apply a powerful graph coloring algorithm on the conflict graph we can assign one time slot to each color of our events and schedule them according to their colors. We can then ensure that there will be no conflicts in terms of resource usage. This is a simplistic modeling of a timetabling problem. In practice, we handle many constraints of resource availability and workload which are all treated and incorporated into ADE.

Bibliography:

Ganguli, R. & Roy, S. (2017), A study on course timetable scheduling using graph coloring approach, International Journal of Computational and Applied Mathematics, 12(2), 469-485.

Redl, T. A. (2007), University timetabling via graph coloring: An alternative approach, Congressus Numerantium, 187, 174.

Miner, S., Elmohamed, S. & Yau, H. W. (1995), Optimizing timetabling solutions using graph coloring, NPAC, Syracuse University, 99-106.