SRI SAIRAM COLLEGE OF ENGINEERING
CONSULTANCY REPORT
The Project ‘Exam Scheduling System’ aims to develop an expert system
that minimizes the human effort in preparing the exam schedule and to
generate an optimal schedule to overcome all constraints in exam
scheduling process.
August 2021 – August 2022
By
Mr. Guruprasath V A
1
CONTENTS
1. INTRODUCTION
[Link] of the Project
[Link] Statement
1.3. Objectives of the Project
[Link] Objective
[Link] Objectives
[Link] of the Study
[Link] and Delimitation
[Link] of Term
2. SYSTEM REQUIREMENTS AND ANALYSIS
[Link] Review
[Link] Requirements Analysis
[Link] and Non-functional Requirements
3. PROJECT DESIGN
[Link] Design
[Link] Relation Diagram (ERD) and its description
[Link] Flow Diagram (DFD) and its description
[Link] Design
4 . SYSTEM IMPLEMENTATION
5. CONCLUSION AND RECOMMENDATIONS
2
[Link]
This chapter discusses about the background of the Project, Problem, Objectives(General, Specific),
Significance of the Study, Scope and Delimitation, at the end definition of Terms.
1.1 BACKGROUND OF THE PROJECT
The examination scheduling can be done in many ways starting from manual scheduling to
automated one. There are number attempts made to automate this process. The most popular way of
automating scheduling process is using a logical language. The features of logical languages,
including searching techniques help to solve this problem easily. Prolog is such a logical language
that has additional feature of backtracking. Backtracking helps the programmer to analyze the effect
of different permutations and combinations that lies in a problem solution. Thus, it helps to find out
an optimum solution to a scheduling problem. Therefore, in this project, we are attempting to
automate the examination scheduling using Prolog language.
1.2 PROBLEM STATEMENT
The examination scheduling in Higher Educational Institutions is highly complex problem because
of very large amount of constraints it contains. The modularity nature of the higher educational
programs has increased the complexity of the problem to the extent that the manual scheduling
became almost impossible solution. Examination scheduling includes assigning fixed time slots, the
rooms and invigilators to each exam, satisfying a set of different constraints. The constraints include
limitations in the physical and human resources, clashing between courses, sequence of courses to
be followed, limitation in number of days etc. Due to the constraints and the complexity of this
problem, neither the structured programming languages nor Object Oriented Programming
Languages are able to solve it. The logic programming languages like Prolog those use constraint
satisfaction techniques (Luis Paulo Reis, 1995), are having extraordinary efficiency in solving the
problems like scheduling, timetabling, resource allocation etc.
1.3 OBJECTIVE OF THE PROJECT
1.3.1 General Objective:
To develop an expert system that minimizes the human effort in preparing the exam schedule.
To generate an optimal schedule to overcome all constraints in exam scheduling process.
To achieve optimal resource utilization in examination process and enhance its efficiency.
1.3.2 Specific Objective:
Allow an expert to add new information / facts to the Knowledge Base(KB). Translate added new
information / facts in to rules and add them to the KB.
3
1.4 SIGNIFICANCE OF THE PROJECT
The project can be used by any higher educational institution. The schedule will be prepared based on the
input course list and clash list. The study shows that all Colleges of Technology in Oman are accomplishing
this scheduling task manually or using Unitime software. The automated systems they use at present help
them to a certain extent in minimizing the number of clashes (a clash is defined here as a student having two
exams in one day) but they don’t completely solve the problem. Therefore, there is a good level of scope for
the higher education sector of Oman to use such an expert system to solve their academic administrative
tasks like exam scheduling.
1.5 SCOPE AND DELIMITATION
This scope of this study is focused on the preparing the exam schedule without clash, if not possible with
minimum clash and overcome all constraints in exam scheduling process. The target group is Higher
Educational Institutions.
1.6 DEFINITION OF TERMS
Definition all the difficult word in the report and abbreviations for help the reader to understand the word
easily and clearly.
- Artificial Intelligence: is concerned with methods of developing systems that display aspects of
intelligent behavior. These systems are designed to imitate the human capabilities of thinking
and sensing.
- Residents: people who live in same state.
- expert system: is a knowledge-based system that employs knowledge about its application
domain and uses an inferencing (reason) procedure to solve problems that would otherwise
require human competence or expertise.
- Clash: Clash is defined as if two exams conflict each other. That is, two exams are having at
least one common student.
- Knowledge Base:- Collection of facts and rules.
4
[Link] REQUIREMENTS AND ANALYSIS
System Requirement and analysis is a process of gathering and interpreting facts, diagnosing problems
and the information to recommend improvements on the system. It is a problem solving activity that
requires intensive communication between the system users and system developers. The system is
viewed as a whole and the input to the system are identified. The outputs from the organizations are
traced to the various processes. System analysis is concerned with becoming aware of the problem,
identifying the relevant and decisional variables, analyzing and synthesizing the various factors and
determining an optimal or at least a satisfactory solution or program of action.
2.1 LITERATURE REVIEW
In 1968, Wood devised an examination scheduling algorithm that was implemented at the University of
Manchester (England). His primary concern [1] was that examinations had to be scheduled into a set of
designated rooms. Moreover, he tried to minimize the number of conflicts (no consecutive examinations
on the same day for any student). For this, Wood implemented a look-ahead algorithm and assigned the
selected room with the "closest fit," namely, the least acceptable number of places.
In 1978, Carter developed an algorithm for final examination scheduling at the University of Waterloo
(Canada). This system [2] was extended in 1985 for scheduling all area high school examinations. The
basic algorithm uses graph coloring techniques and integrates the ability to take into account preferred
constraints such as that several courses must be preassigned to fixed time periods or that no student
should be required to sit for three or more consecutive exams.
In 1978, Desroches, Laporte and Rousseau [3] presented the system HOREX, a name derived from the
French "Horaire" for timetable. Their method consisted of the following general steps: First, they find p
sets of non-conflicting examinations, where p is the number of periods (graph coloring algorithm). Then
they combine these sets in order to have a minimum number of students having two examinations the
same day (branch and bound code for integer linear programming). In order to maximize the number of
examinations scheduled in the morning, they use a heuristic for the knapsack problem. Finally, the days
are ordered using a traveling salesman problem heuristic in order to minimize the number of
"successions" in which a student must take examinations on consecutive days.
2.2 SYSTEM REQUIREMENTS ANALYSIS
FUNCTIONAL AND NON-FUNCTIONAL REQUIREMENTS
2.2.1 Functional Requirements
User Requirements System Requirements
5
The user can input the course list The system creates the knowledge
and clash list base that contains course details
and clash details
The user can input Hard and Soft The system assigns weightage to
constraints each course based on number of
clashing courses and number of
common students between courses.
The user selects the list convenient Based on weightage, the system
to him. will generate the different non-
clash list for first day of
examination.
The system generates the non-clash
course list for rest of the days.
The user can view all the lists The system generate output CSV
generated by the system. file containing exam schedule.
2.2.2 Non Functional Requirements
Usability:
Anybody who has knowledge in prolog can use this project. Alternatively the person in charge for
examination scheduling can be trained to use this project easily.
Performance:
The system should produce exam schedule with addressing all the conditions like clashing, resource
limitations etc.
Reliability:
The system should generate the exam schedule consistently considering all constraints.
Security:
Only the admin will be using this software in his/her standalone system.
Operational:
The design of system is compatible with operating system for computer.
6
[Link] DESIGN
User requirements are a detailed analysis of the system and how it works. There are several tools to
analyze the system and design. In this unit we will explain this Data Flow Diagram and Entity
relationship, which we use for analysis and design of the system.
3.1 LOGICAL DESIGN
Logical design is an abstract concept in computer programming by which programmers arrange data
in a series of logical relationships known as attributes or entities. An entity refers to a chunk of
information, whereas an attribute defines the unique properties of an entity.
3.1.1 DATA FLOW DIAGRAM (DFD)
DFD is a graphical representation of the "flow" of data through an information system? It shows what
kind of information will be input to and output from the system, where the data will come from and go
to and where the data will be stored. It does not show information about the timing of processes or
information about whether processes will operate in sequence.
The symbol use in DFD-diagram:
SYMBOL DESCRIPTION
Processes represent work
being performed in the system
process
and should be named using a
clear name makes it easier to
understand what the process
is accomplishing.
Data stores: represent the
places where data is stored.
The arrow shows movement
of data from one point to
another, with the head of
arrow pointing toward the
Data’s destination.
Context Level – Data Flow Diagram
7
Figure 3.1 Context Level of the Examination Scheduling System.
Figure 3.1 there is shows that the a user prolog knowledge base that contains clashes and courses. The
system generates the exam schedule for 9 days .
Level 1- Data Flow Diagram
At this level present how the system is divided into sub-systems (processes).
Venue Allocation Module
8
Figure 3.2 Level 0 Data Flow Diagram for venue allocation.
Figure 3.2 depicts the venue allocation module. In this module the user inputs Exam schedule generated
through first module, Venue list with capacity and venue for special courses such as IT lab. The system
allocates venue according to the constraints given. The system takes the section size and allocates
according to the capacity of the venue. If the section size is less, the system adds two or three sections
in one venue.
First Invigilators Allocation Module
Figure 3.3 Level 0 Data Flow Diagram for first invigilator allocation.
Figure 3.3 explains the first invigilator module. The user inputs the invigilators list and exam schedule
with venues. The system allocates the first invigilators based on the constraints given by the user. The
constraints used here are number of duties per staff and IT staff for IT lab.
Second Invigilators Allocation Module
9
Figure 3.4 Level 0 Data Flow Diagram for second invigilator allocation.
Figure 3.3 explains the second invigilator allocation module. In this module user inputs the invigilators
list and exam schedule with venues and first invigilator. The system allocates the second invigilators
based on the constraints given by the user.
3.2 PHYSICAL DESIGN
The physical design relates to the actual input and output processes of the system. This is explained in
terms of how data is input into a system, how it is verified/authenticated, how it is processed, and how
it is displayed. In physical design, the following requirements about the system are decided.
Figure 3.5 Examination Scheduling Block Diagram.
In 3.5, shows the schematic diagram of the examination scheduling system. The system has four modules
namely, Exam schedule, Venue allocation, Firs invigilator allocation and second invigilator allocation
module. The results of all modules are saved as Prolog Knowledge Base .
10
[Link] IMPLEMENTATION
The system implementation phase is the stage of a project during which the theory is converted / turned
into practical. The conversion is one of the most crucial and expensive activities in the system
development life cycle because the data from the old system needs to be converted to operate in the new
format of the new system. Before actually implementing the new system into operation, a test run of the
system is done for removing the bugs, if any. It is an important phase of a successful system. After
codifying the whole programs of the system, a test plan should be developed and run on a given set of
test data. The output of the test run should match the expected results.
This chapter discusses about the system execution and result generation. The system is tested with the
actual inputs. The semester -1 class list and clash list of Ibri College of Technology is taken from
Colleges Information Management System (CIMS) has been given as inputs to the system.
Totally 147 courses and 2894 clash records were given as input to the system. The system generated the
exam schedule for 12 days without any clash. The exam was restricted for 9 days. Therefore, the system
allocated the remaining courses (courses for 10th day to 12th day, 10 course) from day 1 to day 9 so that
it would cause a minimum possible clashes (40). The system doesn’t find the best solution, but it finds
an optimum solution.
The inputs for venue allocation were the list of exam schedule and 44 venues including 13 IT labs. The
system allocated venue for all exams. The exam schedule with allocated venue was given as input to the
invigilator allocation module. Apart from the invigilator list, a constraint that assigns IT lecturer to IT
lab courses has been given as input. The number of invigilation duty was restricted to 3 for first
invigilators. The system allocated invigilator for all the venues (exams).
The output generated by first invigilator allocation module was given as input to the second invigilator
allocation module. The number invigilation duty was given as 5. The system allocated second invigilator
to all exams.
11
[Link] AND RECOMMENDATIONS
5.1 CONCLUSION
The scheduling module was tested two times; one during midterm examination for semester-1 and
second time during the final examination for the same semester. It found that the system gives an
optimum solution. Also the system replaced the manual scheduling system.
As explained in the above section, we used three heuristic functions for the test. We used a data set of
a college where Choice Based Credit System is practiced. The data set includes 175 courses from
different disciplines. we had 1727 clash records. Nearly 3000 students were studying these courses.
The following were the results:
No. of 7 8 9 10 11
Examination
days
No. of 5 1 0 - -
courses
Clashing
No. of 14 2 0 - -
Students
Clashing
Test results for the heuristic function, h1 = Number of clashing courses
5.2 RECOMMENDATIONS
As it has been funded by The Research Council of Oman(TRC), the project will be continued to add the
following features.
1. A suitable front-end will be interfaced to enable a smooth user interaction through GUI.
2. Direct interaction with database.
3. Venue allocation based on resource availability will be added.
4. Invigilator allocation based on their preferred dates.
5. Providing decisions /suggestions during the course registration in order to enable a flexible
examination scheduling.
6. System to calculate automatically the maximum number of invigilation duties.
12