AUTOMATED SYSTEM FOR SOLVING SCHOOL TIME TABLE PROBLEM


AUTOMATED SYSTEM FOR SOLVING SCHOOL TIME TABLE PROBLEM  

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.

CHAPTER TWO

LITERATURE REVIEW

2.0 INTRODUCTION:

These chapter deals with the implementation of a computer program that employs the use of Genetic Algorithms (GAs) to solve an optimization problems such as school timetable scheduling, it also contain some brief history of genetic algorithms and explains an example usage of Genetic Algorithm (GAs) for finding optimal solutions to the problem of class timetable, related work on Genetic Algorithm and some trend. This program is written in C++ and it incorporates a repair strategy for faster evolution. 

2.1 History of Genetic Algorithm

The history of genetics all started with the work done by Augustinian Friar Gregor Johann Mendel. He worked on pea plants, which was published in 1866, and was known as Mendel Ian Inheritance. Before and after several decades after Mendel’s work, wide variety of theories of heredity proliferated. The field of Genetic and Evolutionary computation (GEC) was first explored by who suggested an early template for the genetic algorithm. In 1960s and 1970s, much of the foundational works on GEC was performed by Holland. His goal of understanding the processes of natural adaptation and designing biologically-inspired artificial systems led him to the formation of the simple genetic algorithm (Holland, 1975).

 Since then up to date, GAs has being many times successfully applied to many significant problems in machine learning and data mining, pattern detectors and predictors, payoff-driven reinforcement learning(Goldberg,1989) and even scheduling problems.

.


TYPE IN YOUR TOPIC AND CLICK SEARCH.






RESEARCHWAP.COM

Researchwap.com is an online repository for free project topics and research materials, articles and custom writing of research works. We’re an online resource centre that provides a vast database for students to access numerous research project topics and materials. Researchwap.com guides and assist Postgraduate, Undergraduate and Final Year Students with well researched and quality project topics, topic ideas, research guides and project materials. We’re reliable and trustworthy, and we really understand what is called “time factor”, that is why we’ve simplified the process so that students can get their research projects ready on time. Our platform provides more educational services, such as hiring a writer, research analysis, and software for computer science research and we also seriously adhere to a timely delivery.

TESTIMONIES FROM OUR CLIENTS


Please feel free to carefully review some written and captured responses from our satisfied clients.

  • "Exceptionally outstanding. Highly recommend for all who wish to have effective and excellent project defence. Easily Accessable, Affordable, Effective and effective."

    Debby Henry George, Massachusetts Institute of Technology (MIT), Cambridge, USA.
  • "I saw this website on facebook page and I did not even bother since I was in a hurry to complete my project. But I am totally amazed that when I visited the website and saw the topic I was looking for and I decided to give a try and now I have received it within an hour after ordering the material. Am grateful guys!"

    Hilary Yusuf, United States International University Africa, Nairobi, Kenya.
  • "Researchwap.com is a website I recommend to all student and researchers within and outside the country. The web owners are doing great job and I appreciate them for that. Once again, thank you very much "researchwap.com" and God bless you and your business! ."

    Debby Henry George, Massachusetts Institute of Technology (MIT), Cambridge, USA.
  • "I love what you guys are doing, your material guided me well through my research. Thank you for helping me achieve academic success."

    Sampson, University of Nigeria, Nsukka.
  • "researchwap.com is God-sent! I got good grades in my seminar and project with the help of your service, thank you soooooo much."

    Cynthia, Akwa Ibom State University .
  • "Great User Experience, Nice flows and Superb functionalities.The app is indeed a great tech innovation for greasing the wheels of final year, research and other pedagogical related project works. A trial would definitely convince you."

    Lamilare Valentine, Kwame Nkrumah University, Kumasi, Ghana.
  • "Sorry, it was in my spam folder all along, I should have looked it up properly first. Please keep up the good work, your team is quite commited. Am grateful...I will certainly refer my friends too."

    Elizabeth, Obafemi Awolowo University
  • "Am happy the defense went well, thanks to your articles. I may not be able to express how grateful I am for all your assistance, but on my honour, I owe you guys a good number of referrals. Thank you once again."

    Ali Olanrewaju, Lagos State University.
  • "My Dear Researchwap, initially I never believed one can actually do honest business transactions with Nigerians online until i stumbled into your website. You have broken a new legacy of record as far as am concerned. Keep up the good work!"

    Willie Ekereobong, University of Port Harcourt.
  • "WOW, SO IT'S TRUE??!! I can't believe I got this quality work for just 3k...I thought it was scam ooo. I wouldn't mind if it goes for over 5k, its worth it. Thank you!"

    Theressa, Igbinedion University.
  • "I did not see my project topic on your website so I decided to call your customer care number, the attention I got was epic! I got help from the beginning to the end of my project in just 3 days, they even taught me how to defend my project and I got a 'B' at the end. Thank you so much researchwap.com, infact, I owe my graduating well today to you guys...."

    Joseph, Abia state Polytechnic.
  • "My friend told me about ResearchWap website, I doubted her until I saw her receive her full project in less than 15 miniutes, I tried mine too and got it same, right now, am telling everyone in my school about researchwap.com, no one has to suffer any more writing their project. Thank you for making life easy for me and my fellow students... Keep up the good work"

    Christiana, Landmark University .
  • "I wish I knew you guys when I wrote my first degree project, it took so much time and effort then. Now, with just a click of a button, I got my complete project in less than 15 minutes. You guys are too amazing!."

    Musa, Federal University of Technology Minna
  • "I was scared at first when I saw your website but I decided to risk my last 3k and surprisingly I got my complete project in my email box instantly. This is so nice!!!."

    Ali Obafemi, Ibrahim Badamasi Babangida University, Niger State.
  • To contribute to our success story, send us a feedback or please kindly call 2348037664978.
    Then your comment and contact will be published here also with your consent.

    Thank you for choosing researchwap.com.