TABLE OF CONTENTS
CHAPTER
ONE
1.0 INTRODUCTION
1.1 General
Overview
1.2 Statement
of the Problem
1.3
Aim and Objective of the Study
1.4 Limitation
of the Project
1.5 Scope
of the Study
1.6 Significant
of the Project
CHAPTER
TWO
2.0 LITERATURE REVIEW
2.1 Simulated
Annealing
2.3 Annealing
Process Stages
2.4 Hard
and Soft Constraints
2.4.1 Hard
Constraints
2.5 Timetables
2.6 Breeding
Timetables in GA
2.6.1
Parameters
2.6.2 Representation
in GA
2.6.3 Creation
of initial population
2.7 Generating Time Table in SA
2.7.1 The Basic Iteration
2.7.2 The
Neighbors Of A State
2.7.3 The
Annealing Schedule
2.7.4 Selecting
the Parameters for SA
CHAPTER
THREE
3.0 METHODOLOGY
3.1 Timetable
Generation
3.2.2
The Genetic Algorithm Process.
3.3
Simulated Annealing
CHAPTER
FOUR
RESULT AND DISCUSSION
4.0 Analysis
of Result
4.1 Results
for GA / SA
CHAPTER
FIVE
5.0 SUMMARY,
CONCLUSION AND RECOMMENDATION
5.1 Summary
and Conclusion
5.2 Recommendation
REFERENCES
CHAPTER ONE
1.0 INTRODUCTION
1.1
General Overview
The difficulties of developing
appropriate examination time table for institutions and tertiary is increasing.
Institutions are enrolling more students into wider variety of courses in many
different fields. For example, at Osun State Polytechnic, Iree, approximately
14,000 students have to be filled into about 150 exams over two and a half
week’s period.
The examination timetable problem
regards the scheduling for the exams of a set of polytechnic courses, avoiding
overlaps of exams of courses having common students, and spreading the exams
for the students as much as possible.
Examination scheduling (timetabling) is
a very important process in education institutions. The main challenge is to
schedule examinations to timeslots and rooms over a specific period while
satisfying a set of constraints. The previous attempts were based on the graph
coloring concept. In this case the vertices represent causes, and join two
vertices only if they cannot be scheduled at the same time. The problem is
therefore to find the chromatic number of resulting graph.
One of the major approaches in exam
timetabling over the years has been constraint programming approach (Simulated
Annealing). This method constraint programming logic language (chip) also to
solve exam timetabling problem. Constraint programme phase provide an initial
solution and a simulated annealing phase to improve the quality of solutions.
The local search approaches play an
important role in the exam timetabling literature. White and Xie and Di Gaspero
and Schaef used tabu search method in exam timetabling. White and Xie Kept two
table lists, the used short-term table list, and the long-term tabu lists keeps
tracks of the most moved exams, Di Gaspero and Scheaf used a single table list,
but when exams are added to this list, its for a randomly determined number of
iterations.
The polytechnic has two semesters per
each academic year. Each semester per each academic year. Each semester is made
up of up to fifteen weeks of teaching, by followed by two weeks of examination.
There are two examination sessions per day except on Saturday where student are
allowed to rest and start of Sabbath for seventh day Adventist. Examinations
are mostly three hours long with a few exceptions which deviates for half an
hour or two hours.
There are an increasing number of
courses which cut across facilities and polytechnics-wide courses which are
offered to more than a thousands students at the same time. The problem is also
complicated by the freedom of choices by students on optimal courses, where
students have wide range of choices which cut across department and faculties.
The Examination Timetable Problem (ETP)
is usually modeled as an NP-Hard (non-deterministic polynomial time hard
problem) combinatorial optimization problem. The problem demands that a given
number of exams are scheduled in a limited number of periods and venues in such
a way that no student will have more than one exam at a time and other
constraint are satisfied.
Although consideration will be based in
particular on exams timetabling, the ideas presented here can be extended to
many other application, which include not only other scheduling problems but
also multi-criteria problems. In general, the reason to present an application
to exams time tabling is justified by the affiliation of the auditors and their
awareness of the increased difficulty that some recent strategies have
introduced in this academic task. Just as an example monitoring the tendency
forwards the flexibility of curricular and the increase of the number of
students enrolled in each course.
1.2 Statement of the Problem
In this project work, we present a new
solution method for examination timetabling, consisting of two phase: a generic
algorithm phase to improve provide an initial solution and a simulated
annealing phase to improve the quality of solution. The simulated annealing
applies kempe chain neighborhood and includes a mechanism that allow the user
to define a certain period of time in which the algorithm should run. We
perform preliminary experiments of the algorithm on the real data set from the
OSUN STATE POLYTECHNIC, IREE.
However, the main different between the
two approach is that our simulated annealing phase is equipped with more refine
mechanisms that help to determine crucial cooling schedule parameter.
1.3 Aim and Objective of the Study
The principle aim of this project aim of
this project work is develop examination timetabling software that will be
useful to our education institutions, using Generic Algorithms and simulated
annealing.
The following are the set objective
-
Exploratory study of Generic Algorithm
and simulated annealing in resolving conflicts associated with exam
timetabling.
-
Develop a computer software to
automatically generate exam timetable using the two appropriate by considering
Osun State Polytechnic exam time table data.
-
To evaluate and compare the performance
of the two algorithms in term of their
computational complexity.
1.4 Limitation of the Project
The project is developed to cover the
fixing of examination timetables for all students in this institution of Osun
State Polytechnic, Iree but it can be implemented in any other tertiary
institution, this can be achieved by merely adjusting the input design of the
program.
1.5 Scope of the study
In this project, attention is focused in
formulating mathematical models for the examinations timetable at Osun State
Polytechnic, Iree. This will act as a benchmark for testing heuristic algorithms (describe an algorithm
that modifies itself in response to the user) and help future reformations of
the problem models. The Examination Timetabling Problems (ETP) differ
considerably from the polytechnic curse scheduling problem.
1.6 Significant of the project
The significant of the research work is
to assist to curb the examination timetable problems that may arise in the
future, based on the following concussion and recommendation made by the
researcher.
The finding of this study will enable us
to understand and the importance of good examination timetable system for the
tertiary institution easy and effective also with the used of appropriate
examination timetable tom stimulate the timetable of various resources
combination so as to encourage better
timetable planning and information gathering.
To minimize the length of examination period with
the constraint given to used rate determine every student academic performance
and also to allocate inugolator to time and venues.
To give a technical knowledge and the competence of
each student.
Buyers has the right to create
dispute within seven (7) days of purchase for 100% refund request when
you experience issue with the file received.
Dispute can only be created when
you receive a corrupt file, a wrong file or irregularities in the table of
contents and content of the file you received.
ProjectShelve.com shall either
provide the appropriate file within 48hrs or
send refund excluding your bank transaction charges. Term and
Conditions are applied.
Buyers are expected to confirm
that the material you are paying for is available on our website
ProjectShelve.com and you have selected the right material, you have also gone
through the preliminary pages and it interests you before payment. DO NOT MAKE
BANK PAYMENT IF YOUR TOPIC IS NOT ON THE WEBSITE.
In case of payment for a
material not available on ProjectShelve.com, the management of
ProjectShelve.com has the right to keep your money until you send a topic that
is available on our website within 48 hours.
You cannot change topic after
receiving material of the topic you ordered and paid for.
Login To Comment