CHAPTER ONE

1.1 INTRODUCTION

The class timetabling problem is a typical scheduling problem and a demanding task in every academic institution. In the past, timetables were prepared manually by one person or a group of people, and manual preparation often takes days and produces inefficient results (Alghamdi et al., 2020). Planning a school timetable is one of the most complex and error-prone administrative tasks, particularly when it is done by hand. This situation calls for a comprehensive approach in which a computer schedules the timetable automatically, using a technique borrowed from evolutionary biology known as the genetic algorithm (Katoch et al., 2021).

1.2 BACKGROUND OF STUDY

Scheduling is one of the important tasks that people encounter in daily life. There are various types of scheduling problems, including personnel scheduling, production scheduling and educational timetable scheduling (Schaerf, 1999).

In educational timetable scheduling, many constraints have to be satisfied before a workable solution is found, which makes it a very hard task. Educational timetabling is classified as NP-hard, which means that no algorithm is known that can find the optimal timetable in polynomial time for all cases (Alghamdi et al., 2020). Because of this, heuristic and metaheuristic techniques, such as evolutionary algorithms (EAs) and genetic algorithms (GAs), have been widely used to solve the timetable scheduling problem (Alghamdi et al., 2020; Hambali et al., 2020).

Scheduling conflicts arise in many different settings, as the following examples illustrate:

(i) Consider a school environment that requires the scheduling of a given set of courses and meetings between students and lecturers. Each course takes place in a particular lecture hall, and each hall has its own capacity. It must also be ensured that no student or lecturer is assigned to more than one appointment at the same time.

(ii) Consider a factory that produces different kinds of gadgets. Each gadget must first be processed by "machine 1", then "machine 2", "machine 3" and so on, and different gadgets require different amounts of processing time on different machines.

(iii) Consider the central processing unit of a computer, which must process a sequence of jobs that arrive over time.

Genetic Algorithms (GA)

A genetic algorithm is a procedure for finding suitable solutions to search and optimisation problems by applying principles of evolutionary biology. It is a population-based search algorithm inspired by natural selection and the survival of the fittest (Katoch et al., 2021). Genetic algorithms use biologically inspired operations such as natural selection, mutation, inheritance and recombination (crossover) to solve problems. They are usually executed as computer simulations in which an optimisation problem is specified. The members of the space of candidate solutions are represented in an abstract form called chromosomes, and the GA is an iterative process that evolves a working set of individuals, called a population, towards the goal set by a fitness function or objective function.

The evolutionary process of a GA is a simplified and stylised simulation of the biological process. It starts from a population of randomly generated individuals, and the population is updated in steps called generations. In each generation, individuals are selected from the current population according to their fitness, combined through crossover, and modified through mutation to form a new population (Katoch et al., 2021).

Crossover: The process of exchanging genetic material (substrings) between individuals, passing on rules, structural components and features of a machine learning, search or optimisation problem.

Selection: The process of applying the fitness criteria to choose which individuals of a population will go on to reproduce.

Replication: The propagation of individuals from one generation to the next.

Mutation: A sudden change in the composition of a gene, or the modification of the chromosomes of individual solutions. It helps to prevent stagnation in a population and is essential to the proper functioning of the algorithm (Alghamdi et al., 2020).

Theory of genetic algorithms: The theory consists of two main approaches, Markov chain analysis and schema theory. Markov chain analysis is concerned with characterising the stochastic dynamics of a GA system, that is, the behaviour of its random sampling mechanism over time. Its main limitation is that, although crossover is easy to implement, its dynamics are difficult to describe mathematically. Markov chain analysis of simple GAs has therefore been more successful in capturing the behaviour of evolutionary algorithms that use only selection and mutation.

Timetable: In institutions, the class timetable is a major administrative activity and a prerequisite for teaching. A timetable is a table of events and their schedule (Alghamdi et al., 2020). The timetable problem can be described as the problem of assigning a number of events to a limited number of time periods, in such a way as to satisfy, as nearly as possible, a set of desirable objectives. The problem is subject to many constraints, which are usually divided into two categories, "hard" and "soft" (Alghamdi et al., 2020).

Hard constraints: These are constraints that must be enforced. Examples include:

(iv) In each period, there must be enough resources (for example rooms and lecturers) available for all the events scheduled for that period.

(v) No lecturer should have different classes at the same time slot, and there cannot be more than two classes for a subject in one day.

Soft constraints: These are constraints that are desirable but not absolutely essential. In real-world situations it is sometimes impossible to satisfy all soft constraints (Alghamdi et al., 2020). Some soft constraints, in both examination and course timetabling, are:

(vi) Lecturers and students may prefer to have all their lectures in a certain number of days and to have a number of lecture-free days.

(vii) Lab classes should not be in consecutive hours.

(viii) Every staff member should get at least one first-hour class.

(ix) A particular class may need to be scheduled in a particular time period.

1.3 STATEMENT OF PROBLEM

Every problem has a set of valid results, which forms its solution space. In an optimisation problem, the main goal is to find results that maximise or minimise a set of criteria. If the solution space is viewed as an n-dimensional space, then the task is essentially to search for a global minimum or maximum in that space. The genetic algorithm is a type of algorithm for searching the solution space and finding maxima or minima, although it does not necessarily find the global maximum or minimum (Katoch et al., 2021).

Timetable scheduling is a complex optimisation problem that belongs to the NP-hard class (Alghamdi et al., 2020; Schaerf, 1999). For problems of this kind, for which no efficient exact algorithm is known, it is appropriate to apply a genetic algorithm to search the solution space. It should be noted that such scheduling is a general problem with immediate application in various forms of timetabling, including examinations, public transport and rosters, though it is by no means limited to these (Schaerf, 1999). In Nigerian tertiary institutions, automated lecture timetabling systems have been proposed precisely because manual timetabling is time-consuming and error-prone (Soyemi et al., 2017; Hambali et al., 2020).

1.4 AIMS AND OBJECTIVES

The project is a software application that many institutions, businesses and companies may need. It is, in essence, a simple case of an allocation problem.

(1) The project involves developing a program that can schedule a school timetable effectively. The prototype should be followed by the development of a booking system that can automatically allocate resources, and these resources are allocated automatically using a genetic algorithm.

(2) The main aim of the project is to solve timetable problems using evolutionary computing processes, and more specifically genetic algorithms.

(3) The difference between this project and other existing ones in the Faculty of Science is that the timetable it produces does not clash, and that it is more efficient and simpler to schedule using the ideas drawn from genetic algorithms.

1.5 SIGNIFICANCE OF STUDY

This project is topical and calls for research effort because of a conflict that recently occurred in the researcher's school. A junior lecturer from the Department of Computer Science was giving a lecture when a senior lecturer from another faculty walked in and asked the class to leave because he wanted to use the room for another lecture, and the class was discontinued as a result. Many similar instances have occurred and need urgent attention, so that a good learning environment can be achieved.

1.6 LIMITATION OF THE STUDY

The constraints on this project are many, but only the major ones are listed:

(x) To begin with, the project took a great deal of time to understand and research before it could be started.

(xi) There was no stable electric power supply during the research work.

(xii) The location where the research was carried out had poor network signal strength.

1.7 ORGANIZATION OF RESEARCH

This project is organised in five chapters. Chapter one is a general introduction to the whole research project. It gives an insight into the nature, problem and purpose of designing and implementing an automated system for solving the school timetable problem. In chapter two, the literature relevant to this research work is reviewed, with the main focus on determining the expert knowledge that has been applied so far to the subject matter. In chapter three, the system analysis and design are presented. Chapter four is concerned with the implementation and presentation of the results. Chapter five presents the summary, conclusion and recommendations.

1.8 DEFINITION OF TERMS

Automation: The technology by which a process or procedure is performed with minimum human assistance. Automation, or automatic control, is the use of various control systems to operate equipment such as machinery, processes in factories, boilers and heat-treating ovens, telephone network switching, and the steering and stabilisation of ships, aircraft and other vehicles, with minimal or reduced human intervention.

Timetable: A plan of the times at which particular events are to take place.

Scheduling: A method used to distribute valuable computing resources, usually processor time, bandwidth and memory, to the various processes, threads, data flows and applications that need them.

Information technology: The application of computers and telecommunications equipment to store, retrieve, transmit and manipulate data.

System: A collection of interacting and interdependent components that work together to achieve a goal.

Computer-aided instruction: A teaching process that uses a computer to present instructional material, often in a way that requires the student to interact with it.

References

Alghamdi, H., Alsubait, T., Alhakami, H., & Baz, A. (2020). A review of optimization algorithms for university timetable scheduling. Engineering, Technology & Applied Science Research, 10(6), 6410–6417.

Hambali, A. M., Olasupo, Y. A., & Dalhatu, M. (2020). Automated university lecture timetable using heuristic approach. Nigerian Journal of Technology, 39(1), 1–14. https://doi.org/10.4314/njt.v39i1.1

Katoch, S., Chauhan, S. S., & Kumar, V. (2021). A review on genetic algorithm: Past, present, and future. Multimedia Tools and Applications, 80(5), 8091–8126. https://doi.org/10.1007/s11042-020-10139-6

Schaerf, A. (1999). A survey of automated timetabling. Artificial Intelligence Review, 13(2), 87–127.

Soyemi, J., Akinode, J. L., & Oloruntoba, S. A. (2017). Automated lecture time-tabling system for tertiary institutions. International Journal of Applied Information Systems, 12(5), 20–27.