DESIGN AND IMPLEMENTATION OF EXAM-TIME-TABLE GENERATING SYSTEM
ABSTRACT
This paper presents a graph-coloring-based algorithm for the exam scheduling application, with the objective of achieving fairness, accuracy, and optimal exam time period. Through the work, we consider few assumptions and constraints, closely related to the general exam scheduling problem, and mainly driven from accumulated experience at various collages. The performance of the algorithm is also a major concern of this paper.
CHAPTER ONE
1.1 INTRODUCTION
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 two nodes are adjacent if the two 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.
Leave a Reply
You must be logged in to post a comment.