AUTOMATED SYSTEM FOR SOLVING SCHOOL TIME TABLE

AUTOMATED SYSTEM FOR SOLVING SCHOOL TIME TABLE

Chapter One

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.

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

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. 

AUTOMATED SYSTEM FOR SOLVING SCHOOL TIME TABLE

Chapters: 1 - 5

Delivery: Email

Number of Pages: 70

Price: 3000 NGN

In Stock

Buy the Complete Material Now