Automated Timetable Generation using Genetic Algorithm

Automated Timetable Generation using Genetic Algorithm

1Shraddha Thakare

(Student) Department of Computer

Engineering

New Horizon Institute of Technology and Management Thane, India

2Tejal Nikam

(Student) Department of Computer

Engineering

New Horizon Institute of Technology and Management Thane, India

3Prof. Mamta Patil (Assistant Professor) Department of Computer Engineering

New Horizon Institute of Technology and Management Thane, India

AbstractIn this paper we have proposed system to design an effective model for timetable scheduling using a genetic algorithm. The objective of the research is to create a model using genetic algorithm, which can be effectively used to resolve difficult combinatorial optimization problem. The algorithm was tested on small and large cases of the problem. Algorithm performance was significantly enhanced with modification of basic genetic operators, which restrain the creation of new conflicts in the individual. The scheduling solution presented in this paper is an adaptive one, with a primary aim of obtaining best the optimal solutions.

1. INTRODUCTION

   This article describes an implementation of timetable scheduling problem using genetic algorithm. The timetable scheduling problem is very common to all educational institutions. Main algorithm goal is to minimize the number of conflicts in the timetable scheduling. Reduction to encoding of search space was also implemented.

   This paper is about Genetic Algorithms used in timetable management at university or colleges. The objectives of this project are, first, to introduce Genetic Algorithm and, secondly, to use it to solve a timetable scheduling problem. The objectives are to define what Genetic Algorithms are and how its work, to define what is timetable management and its actual problems and to make a prototype of an automated timetable scheduling system without using the classical approach but the Genetic Algorithm. The current timetable system in Coventry University is estimated adequate. This thesis does not propose an alternative solution.

2. REVIEW OF LITERATURE

   The existing system formulated a class or teacher timetabling problem by considering that each lecture contained one group of students, one teacher, and any number of times which could be chosen freely. Since then the problem is being continuously studied using different conditions. Initially it was mostly applied to schools. Since the problem in schools are relatively simple because of their simple class structures, classical methods, such as linear or integer programming approaches could be used easily. However, the gradual consideration of the cases of higher secondary schools and universities, which contain different

   types of complicated class-structures, is increasing the complexity of the problem.

3. REQUIREMENT ANALYSIS

   1. Functional Requirements

   2. Non Functional Requirements

   1. Functional Requirements:

      The following are functional requirements of the system:

      • To implement a User interface on the system

      • User-friendly front-end design using Cascading Style Sheets.

      • Strong authentication while performing various operations.

      • Java script validations and alerts wherever needed.

   2. Non-Functional Requirements:

      The following are non-functional requirements of the system:

      1. Secure access of confidential data (users details). SSL can be used.

      2. Better component design to get better performance at peak time.

      3. Flexible service-based architecture will be highly desirable for future extension.

4. PROPOSED SYSTEM ARCHITECTURE

   Fig 1 Proposed Architecture

   Proposed System

   • The proposed systems were developed to solve the timetable generation being faced by college every academic year.

   • We can reduce high cost and slow turnaround involved in the generation of near-optimal timetables.

   • The system has capabilities for input of the various courses, halls of lectures, departments, programs, lecturers and the specification of a few constraints from which the timetable is constructed.

   • The proposed timetable system for this project seeks to generate maximum error free timetables using the principles of genetic algorithm (selection and crossover).

   Advantages of Proposed System

   1. Unlike the manual timetabling system, the system offers flexibility.

   2. It utilizes minimal processing/computing power.

   3. It greatly reduces the time needed to generate maximum error free timetables.

   4. It provides an easy means for data entry and revision through an intuitive interface.

   5. It increases productivity.

   6. Timetables generated are between to 60% – 80% best solution.

   7. It almost eliminates paperwork.

   8. It simplifies the timetabling process.

5. SYSTEM DESIGN

   The whole method of scheduling based on genetic algorithm is explained in detail in this section. A scheduling procedure is divided into several important modules are as follows,

   Evaluation of population: The fitness of a solution is the estimation of how good the solution is, using soft constraints. At this range, the solution is valid.

   The evaluation of the population is the heart of the Genetic Algorithm. this step evaluate which solution is better than other using a fitness function.

   The fitness can be given using a range between 0 and 1, where 1 is estimated as the best solution of the population, using other the other individuals to range them. In this case, there will be always a solution that the fitness is 1, and a solution that the fitness is 0.

   Fitness Function:

   Fitness [11] of the timetable is calculated by below eq.:

   F(X)=

   Where,

   x = timetable under evaluation process. w = number of Constraints.

   t = total fitness value.

   Crossover Evolution: The crossover evolution is a method used for the creation of a new population, based on older population. The simple crossover evolution uses two chromosomes and permit to create X new chromosomes. It consists of splitting the two chromosomes in parts and creating new chromosomes using different parts.

   1. Data encoding and decoding

   2. Initial population

   3. Evaluation of population

   4. Crossover Evolution

   5. Mutation

   6. New Population

   Data encoding and decoding: Data encoding is the first step before starting Genetic Algorithm. It transforms a solution into a chromosome to get a simple value, like a string. It is used to improve speed of the algorithm. An easy way to do is to converting the data into a binary string. A Gene is a part of Chromosome and it can be converted to a binary string either. Conversion the data to this type permits an easier treatment for the algorithm. The chromosome string is composed of side-by-side genes strings.

   Initial population: It is the first step in GA. It consists of creating a number of random individuals using hard constraints. The population choice depends on the needs of the user. A small amount of population will get smaller and destroy the full population after some generations because of evolution. On the other hand, a large amount of population will give better results but will require more resources and will be slower. The population can be representd as a set.

   Mutation: Mutation is used to get the algorithm moving. It consists of changing the values of a gene randomly, resulting in a new unexpected solution. These solutions offer a new point of view for the fitness function. The mutation changes only the chromosome, without affecting others solutions.

   New Population: The crossover and the mutation permit to create a new population of original solutions.

6. APPLICATION

   • University Timetable Management.

   • School Timetable Management.

   • Any organization timetable management.

7. CONCLUSION

   The initial timetabling problem with large number of binary variables has been reduced to the acceptable size by eliminating certain dimensions of the problem and incorporating those dimensions into constraints. The grouping of several binary variables into one gene value significantly reduced the individual size. Now it is possible to try to solve the full-size problem (problem of the whole FER schedule) with genetic algorithm approach. Such a representation of the scheduling problem achieves the

   acceptable algorithm speed, so small size problems are solved in tens of seconds. Significant improvements have been achieved by using intelligent operators. The intelligent algorithm converges much faster than the basic algorithm and represents a good starting point for complete solving of the full-scale problem.

8. REFERENCES

1. Leon Bambrick, Lecture Timetabling Using Genetic Algorithms

   Available:http://secretgeek.net/content/bambrilg.pdf

2. Burke, E.K. and Petrovic, S., 2002. Recent research directions in automated timetabling European Journal of Operational Research, 140(2), pp.266Y280.

3. Chowdhary A., Kande, P., Dhone, S., Ingle, S., Rushiya, R. And Gawande, D.,2014 Timetable Generation system. International Journal of Computer Science and Mobile Computing, 3(2).

4. Bhaduri, A., 2009, October. University timetable scheduling using genetic artificial immune network. In Advances in Recent Technologies in Communication and Computing, 2009. ARTCom'09. International Conference on (pp. 289Y292). IEEE.