Timetabling by Coloring and Clustering by Neuronal Networks

Abstract

Designing a university course timetable requires assigning events(course lectures, tutorials, colloquia) to locations(on/off-line classrooms) and time slots, while avoiding clashes - for example, lectures of two courses that a particular student subscribes to cannot run concurrently. In designing the timetable, we can consider the events(or classes) as the vertices of a graph and the conflicts between them as edges between the corresponding vertices. This formulation allows us to state the university timetabling problem as a graph vertex coloring problem. Vertices with the same color, in any coloring of such a graph, can give us the set of events that can share the same time-slot, while different colors represent groups of events that must be assigned different time-slots.We propose using the dynamics of neuronal networks to solve the graph coloring problem. We will assign neurons to each vertex of the constraint graph and interactions between them will be inhibitory. Inhibitory neurons compete with each other, when one fires, it prevents those connected to it from firing. Therefore, vertices with the same color do not compete and can fire synchronously. In earlier work by Chowdhary S. and Assisi C., this idea was used to arrive at solutions of the Sudoku puzzle which can also be mapped to a vertex coloring problem. Here we propose using this approach to solve a particular instance of the university timetabling problem.