A New Exam Scheduling Algorithm Using Graph Coloring
Exam scheduling is a challenging task that universities and colleges face several times every year. The challenge is to schedule so many exams of courses in a limited, and usually short, period of time. An Exam schedule should avoid conflicts, in the sense that no two or more exams for the same student are scheduled at the same time. Part of the challenge is to achieve fairness for the students.
A fair schedule does not schedule more than two exams, for example for a student on one day. In the meantime, a fair schedule does not leave a big gap between exams for the students.
Overview
An undirected graph $G$ is an ordered pair $(V, E)$ where $V$ is a set of nodes and $E$ is a set of non-directed edges between nodes. Two nodes are said to be adjacent if there is an edge between them. The graph coloring is a well-known problem. Node coloring assigns colors to the nodes of the graph such that no two adjacent nodes have the same color. Edge coloring assigns colors to the edges of the graph such that no two adjacent edges have the same color. Two edges are said to be adjacent if they both share a node in common. General graph coloring algorithms are well known and have been extensively studied by researchers.
Exam scheduling is a challenging task that universities and colleges face several times every year. The challenge is to schedule so many exams of courses in a limited, and usually short, period of time. An Exam schedule should avoid conflicts, in the sense that no two or more exams for the same student are scheduled at the same time. Part of the challenge is to achieve fairness for the students. A fair schedule does not schedule more than two exams, for example for a student on one day. In the meantime, a fair schedule does not leave a big gap between exams for the students. The exam scheduling problem is defined as follows: "We first represent the courses by nodes of a graph, where 2 nodes are adjacent if the 2 corresponding courses are registered by at least one student. Then, it is required to assign each course represented by a node a time slot, such that no two adjacent nodes have the same slot, in condition that a set of constraints imposed on the problem are also met." We solve this problem by using node graph coloring technique.
This study provides a mechanism for automatic exam-schedule generation that achieves fairness, and minimizes the exam period. As a result, this paper presents a graph-coloring-based algorithm for the exam scheduling application which achieves the objectives of fairness, accuracy, and optimal exam time period. Numerous studies have considered the problem of exam scheduling. The main difference between various studies is the set of assumptions and constraints taken into consideration. Burke, Elliman and Weare, for example, followed a similar approach using graph coloring. However, in their algorithm, they addressed only the conflicts without any constraints. Moreover, the algorithm presented in [9] does not eliminate conflicts, and only aims at minimizing conflicts. In this paper, we consider few but important assumptions and constraints, closely related to the general exam scheduling, and mainly driven from the real life requirements collected through the experience at various universities. Such assumptions and constraints are distinct from those present in more general graph coloring problems. We summarize the main assumptions and constraints as follows:
- The number of exam periods per day (Time Slots ($TS$)) can be set by the user. TS depend on college/department specific constraints. For example, a university that uses a 2-hours exam period and begins the exam day at 8:00 am and finish at 8:00 pm, may set $TS$ to 5.
- The number of concurrent exam sessions or concurrency level ($N_p$) depends on the number of available halls, and the availability of faculty to conduct the exams. Np is determined by the registrar's office. This paper assumes that $N_p$ is a system parameter and the scheduling algorithm has been examined with several $N_p$ values.
- A student shall not have more than ($y$) exams per day (fairness requirement), and is treated as a system tunable parameter.
- A student shall not have a gap of more than ($x$) days between two successive exams, and this factor is to be determined by the college or department (another fairness requirement).
- The schedule shall be done in the minimal possible period of time, i.e., minimize the number of exam slots and/or number of exam days. The exam time period is an outcome of the scheduling algorithm.
- Next, we give some more definitions that are relevant to the underlined problem. Let $C$ be a list of all courses to be scheduled. The length of this list is $n$. In other words, $n$ is the number of courses in the list. A course at position $i$ in the list $C$ is referred to using an index $c_i$. Let $G$ be the graph that represents the list $C$ of courses. We impose a weight $w_{ij}$ to each edge of $G$, where $w_{ij}$ is defined as the number of students present in both courses $c_i$ and $c_j$. An edge $e_{ij}$ exists between nodes $c_i$ and $c_j$ iff $w_{ij}$ is not $0$. We define a weight matrix $W$ to be an $nxn$ matrix, where $n$ is the number of courses to be scheduled for the exams, and $wij$ equals the weight of the edge $e_{ij}$ that joins the courses $c_i$ and $c_j$. Such a weight imposed on the edges of $G$ represents the exam conflict complexity present in courses $c_i$ and $c_j$. A multi-section course is considered as one course. However, the number of sections per course is taken into consideration in the process of hall assignment.
The degree $d_i$ of a node $c_i$ is defined as the number of edges connected to a node. A large degree of a node $c_i$ indicates that there is a large number of students registered in this course and $d_i$ other courses. The degree $d_i$ is also a measure of conflict complexity. An example of a weighted graph $G$ and the corresponding weight matrix $W$ is given in Figure 1 and , respectively. In Figure 1, $c_2$ and $c_5$ both have degree $3$. In Table 1, the weight of the edge $e_{15}$ is $4$.
| $C1$ | $C2$ | $C3$ | $C4$ | $C5$ | |
|---|---|---|---|---|---|
| $C1$ | $0$ | $2$ | $0$ | $0$ | $4$ |
| $C2$ | $2$ | $0$ | $1$ | $0$ | $3$ |
| $C3$ | $0$ | $1$ | $0$ | $4$ | $0$ |
| $C4$ | $0$ | $0$ | $4$ | $0$ | $3$ |
| $C5$ | $4$ | $3$ | $0$ | $3$ | $0$ |
$$ \text{Table 1. A weight matrix W of the graph.} $$
The Coloring Scheme
The coloring scheme for the exam-scheduling problem uses a double indexed color ($R_{IJ}$), where the index ($I$) represents the day of the exam and ($J$) represents the exam time slot on a given day. The range of ($J$), i.e., the number of exam time slots is determined by the registrar and/or the faculty.
The range of the index ($I$) is a parameter generated as an outcome by the algorithm. Minimizing the index ($I$) is one objective of the algorithm. The parameter $I$ can also be set by the registrar and/or the faculty. It is bound by the absolute minimal number of colors for the given graph. However, finding the absolute minimal is known to be $NP$ complete. The algorithm presented in this paper is claimed to achieve near optimal performance (close to minimal number of colors) in polynomial time.
We define the weight of a color to be $W (R_{IJ}) = (I-1) * k + J$; $k$ is the range of $J$. A color $R_{IJ}$ is said to be smaller than color $R_{GH}$ if the weight $W(R_{IJ})$ is smaller than $W(R_{GH})$. The coloring scheme allows two or more non-adjacent nodes to have the same color ($R_{IJ}$). The number of nodes having the same color provides the number of concurrent exam sessions, which is bounded by the number of available halls and the maximum allowable concurrent sessions by the registrar and/or the faculty. In general graph coloring problems, there is no restriction on the assignment of the same color to non-adjacent nodes in the graph. The exam-scheduling problem as explained above imposes a constraint on the maximum number of nodes assigned the same color. The scheduling algorithm (provided in the next section) allows the user to impose a maximum limit on the number of available instances of color $R_{IJ}$. The number of instances of a color $R_{IJ}$ is referred to as the concurrency limit of the color $R_{IJ}$ denoted $CL(R_{IJ}$). Note that a course with multiple sections is assigned one color. However, the multiple sections will consume multiple instances of the same color, assuming that each section will make the exam in a separate hall.
Fairness of the Algorithm
In order to achieve fairness, as discussed in the introduction, the algorithm defines the following parameters:
- Internal distance ($D_1$): This is the distance between two colors ($R_{IJ}$) and ($R_{IK}$) with the same index ($I$) and indexes $J$ and $K$, and defined by
$$ D_1 = \lvert K-J \rvert \qquad \qquad \qquad \qquad (1) $$
$D_1$ represents the exam scattering on the same day $I$ for the same set of students.
- External distance ($D_2$): This is the distance between two colors ($R_{IJ}$) and ($R_{KL}$), and defined by
$$ D_2 = \lvert K-I \rvert \qquad \qquad \qquad \qquad (2) $$
$D_2$ represents the exam scattering across different days.
- The total distance between colors ($R_{IJ}) and ($R_{KG}) is given by
$$ D = \gamma * D_2 + D_1 \qquad \qquad \qquad \qquad (3) $$
or
$$ D = \gamma * (\lvert K-I \rvert) +\lvert G-J \rvert \qquad (4) $$
The factor ($\gamma$) can be varied to provide a different coloring scheme. The distance $D$ is a major design parameter of the algorithm.
Specific Considerations
The scheduling problem has its own peculiarities, which have to be taken into consideration at the implementation level. For example, the node with a large degree represents a course in which many students are registered to many other courses (different group of students may be registered to different courses). Also, nodes with large degrees have large number of students as well. In order to have an efficient schedule; the nodes with larger degrees should be colored first. Giving priority to the nodes with the larger degrees is in line with typical university schedules which tend to schedule the university required courses early in the exam period. The nodes representing university and college requirement courses have large degrees.
The weight of an edge indicates the number of common students registered at both courses (nodes) connected to that edge. Giving priority in the coloring algorithm to nodes connected to a large weight-edge will enable a solution optimization geared towards the larger groups of students. Another point to consider before we describe the algorithm is the multi-section courses. Multi-sections of a multi-sections course should be scheduled at the same time, and thus the corresponding nodes should have one color. Also, they typically occupy several halls. The number of halls used by a course has an impact on the concurrency level per time slot. When such multi-sections are scheduled for a time slot, i.e. assigned a color, the concurrency level is to be reduced by the number of sections for that course. For implementation purposes, we augment the nodes of the graph with a value equal to the number of sections in the course; we shall call this value the course concurrency level $CL(c_i)$. Thus, we assign a concurrency limit for each color $N_p(C_{IJ})$. After assigning a color to a node $C_i$, we reduce the concurrency limit of the color by $CL(c_i)$. The concurrency limit is set by the registrar and depends on the number of available halls, and staff to monitor the exams.
Algorithm Color Schedule
The algorithm consists of two major steps. The first step builds the weight matrix and graph. The second step assigns colors to the nodes of the graph.
Conclusion and Future Work
As discussed above, the number of concurrent exam sessions or concurrency level (Np) depends on the number of available halls, and the availability of faculty to conduct the exams. The value of Np is usually determined by the registrar's office, and the paper assumes that Np is a system parameter, and we will run the scheduling algorithm with several Np values. In a later work, the actual distribution of exam sessions to halls will be included. Also, the algorithm presented in this paper is claimed to achieve near optimal performance (close to minimal number of colors) in polynomial time. We are currently investigating a modification of the algorithm, which will achieve the absolute minimal for a certain set of graphs.
Love,
Ahmed Jazzar