CHAPTER
ONE
1.1 INTRODUCTION
The class timetabling problem is a
typical scheduling problem that appears to be a stressful job in every academic
institute. In previous years, timetable scheduling was done manually with a
single person or group of individuals involved in the task of scheduling it
manually. Planning of timetable is one of the most complex and error-prone
applications because it is actually done manually. This situation demands a
comprehensive approach where a computer can be used to schedule a timetabling
problem by being automated using a concept gotten from evolutional biology
called Genetic algorithm.
1.2 BACKGROUND OF STUDY
Scheduling
is one of the important tasks that we encountered in our daily life situations.
There are various types of scheduling problems which includes personnel
scheduling, production scheduling, educational timetable scheduling etc.
In
educational timetable scheduling, there are many constraints that need to be
satisfied in order to get a clear solution which has made it a very hard task.
Educational timetable scheduling can be called a non-polynomial hard (NP hard)
which means that, there are no exact algorithms that can solve this problem of
timetable scheduling. Hence, evolutionary techniques have been used to solve
the time table scheduling problem. Techniques like Evolutionary Algorithms
(EAs), Genetic Algorithms (GAs) etc.
Scheduling conflicts arise in different
varieties of settings as illustrated by the following examples:
(i) Consider
a school environment that requires the scheduling of a given set of courses and
meetings between students and lecturers. Each course will take place in a
particular lecture hall and each hall has its own capacity. We must also make
sure that no student or lecturer is fixed up in more than one particular
appointment.
(ii) Consider
a factory that produces different sorts of gadgets. Each gadget must first be
processed by a “machine 1”,“machine 2”,“machine 3” and so on where different
gadgets requires different amount of processing time on different machines.
(iii)
Consider the central processing unit of
a computer that must process a sequence of jobs that arrive over time.
Genetic
Algorithms (GA)
This is a procedure
that is used to find an appropriate solution to search problems through the
application of evolutionary biology. These kind of algorithm uses biological
techniques such as natural selection, mutation, genetic inheritance and sexual
reproductions (recombination or cross over), along with Genetic programming
(GP) to solve problems. Genetic algorithms are primarily executed using
computer simulations in which an optimization problem is specified. For this
problem, members of a space called Candidate solutions are represented using
abstract representations called chromosomes. The GA consists of an iterative
process that evolves a working set of individuals called a Population towards a
fitness function or an objective function.
The evolutionary
process of a GA is a simplified and stylized simulation of the biological
version. The starting point is the population of individuals randomly generated
according to the probability distribution usually informs and updates this
population in steps called Generations. Each generation of multiple individuals
are randomly selected from the current population based on some application of
fitness using crossover and modified through mutation to form a new population.
Crossover: - This is
the process of exchanging Genetic materials (substrings), donating rules, and
structural components, features of a machine learning, search, or optimization
problem.
Selection: - this is
the process of applying the fitness criteria to choose which individuals from a
population will go on to reproduce.
Replication:-The
propagation of individuals from one generation to the next generation.
Mutation: - it is said
to be the sudden change in the composition of a gene or the modification of
chromosomes for single individuals.
Theory of Genetic
Algorithm: The theory consists of two main approaches.
They are as follows;
Markov chain analysis and Schema theory. The Markov chain is primarily
concerned with characterizing the stochastic dynamics of a GA system. i.e the
behavior of the random sampling mechanism of a GA over time. The highest
limitation of this approach is that while crossover is easy to implement, its
dynamics are difficult to describe mathematically. Markov chain analysis of
simple GAs has therefore been more successful at capturing the behavior of
evolutionary algorithms with selection and mutation only.
Time
table
In institutions, the class time table is a
major administrative activity which is prerequisite.
The time table problem
or conflict can be said to be the problem of assigning a number of events into
a limited number of time period. Wren defines timetable as follows “Timetable
is the allocation of subject to constraints of
given a objects being in space time in such a way as to satisfy as
nearly as possible a set of desirable objectives”, Wren A.(1995).The problem
of the time table is subject to many
constraints which are usually divided into two categories: “hard” and “soft”.
Hard
Constraints:
These are constraints
that must be enforced. Some examples of such constraints are:
(iv)
In each period, there should be
sufficient resources (e.g. rooms and lecturers) available for all the events
that have been scheduled for that time period.
(v) No
lecturer should have different classes at the same time slot. There cannot be
more than two classes for a subject in one day.
Soft
Constraints
Soft constraints are
those that are desirable but not absolutely essential. Sometimes it is
impossible to satisfy all soft constraints in real world situations. Some of
the soft constraints (in both exams and course timetabling) are:
(vi)
Lecturers and students may prefer to
have all their lectures in some number of days and to have a number of
lecture-free days
(vii)
Lab classes may not be in consecutive
hours
(viii)
Every staff should get at least one
first hour
(ix)
A particular class may need to be
scheduled in a particular time period.
1.3
STATEMENT OF PROBLEM
Any problem has a set
of valid results. It is said to form the solution space. In an optimization
problem, the main aim or goal is to find results that maximize or minimize a
set of criteria. If we look at the solution space as an n-dimensional space then
essentially we are searching for a global minima or maxima in the solution
space. The Genetic Algorithm is a type of algorithm for searching the solution
space and finding maxima or minima, though not necessarily the global maxima or
minima.
Timetable scheduling is always said to be a complex
optimization problem which has shown to be related to the clique of
minimization problem which is called NP complete. In such kind of problem where
no efficient algorithm is known, it is ideal to apply genetic algorithm to such
kind of problem which is used for search a solution space. It is necessary to
realize that such scheduling is a world problem that has an immediate
application in various forms of timetabling including, examinations, public
transport and roster, though in no way limited to.
1.4
AIMS AND OBJECTIVES
The project is a
software application that many Institutions, businesses and some companies may
actually need. This is a simple case of an allocation problem.
(1) The
project involves developing a program that can schedule time table effectively
for school. The prototype of this work should be followed by the development of
a booking system that can automatically allocate resources. These resources are
allocated automatically using a Genetic Algorithm.
(2) The main principal of this project is to solve
timetable problems with evolutionary computing processes and more specifically
using Genetic algorithms.
(3) The
actual different between this project with other one existing in the faculty of
science is that the timetable does not clash and it is more efficient and
simple to schedule using the idea gotten from Genetic algorithm.
1.5
SIGNIFICANCE OF STUDY
This project is a topical one demanding a
research effort due to conflict that recently occurred in my school. Recently a
junior lecturer from the department of computer science was having a lecture
with us and a senior lecturer from another faculty walked in and said that we
should leave the class because he want to use the class for another lecture and
so the class discontinue because of the lecture. Many more of these types of
instances has happen and so need an urgent attention so that a good learning
environment can be achieved.
1.6
LIMITATION OF THE STUDY
The lists of constraint on this project
are so many but just the few major ones will be listed:
(x) To start with, the project took a lot
of time to understand, researched on before embarking on it.
(xi)
Unavailability of electric power
supply during the research work.
(xii)
The location where this research was
performed was not good enough in terms of network signals strength which is
usually on the poor side.