Abstract

Generating a timetable manually for educational institutions can be a tedious task for educators, as each grade has a predefined education scheme and faculty workload that needs to be taken into account. The challenge lies in preparing a timetable that does not overlap with the schedules of the faculty members and can efficiently utilize all available resources. To overcome these difficulties, our project proposes the use of algorithms such as Evolutionary Algorithm, Tabu Search, Simulated Annealing, and scatter search. The proposed system will take inputs such as grade-wise subjects, teachers, and workload, and generate a possible timetable for the working days of the week. The system will integrate these inputs to make optimal use of all resources while adhering to the predefined constraints. This will help overcome the constraints that appear in the manual timetable generation process, resulting in timetables for any number of courses and grades. The implementation of this proposed system will provide a dynamic solution with the best approach, making it easier for educationalists to manage and set timetables. It will eliminate the complexity of manually generating and managing timetables, providing an efficient and effective solution to this challenging task

Introduction

I. INTRODUCTION

A timetable is a schedule that outlines the specific times at which certain events are planned to occur. When educationalists manually prepare a timetable, their main task is to ensure the availability and workload of faculty members for each subject. Additionally, they must generate a timetable that adheres to the predefined government scheme for each subject of a particular grade. It is crucial to schedule time slots for each subject smoothly, without any overlap with slots assigned to the same faculty member teaching different grades. To simplify the process of setting and managing timetables, our project proposes a machine learning-based system that takes inputs such as grade-wise subjects, faculty members, and faculty workload. The system will use these inputs to generate a possible timetable for the working days of the week, ensuring optimal use of all available resources. Our suggested solution aims to tackle the limitations inherent in the conventional method of generating timetables, alleviating the monotonous task of manually creating timetables. With the use of machine learning algorithms, this proposed system will eliminate the complexity of manually generating and managing timetables, providing an efficient and effective solution to this challenging task. It will help educationalists prepare timetables in a smooth and streamlined manner, improving the overall efficiency of the educational institution.

II. LITERATURE SURVEY

A literature survey is an essential report that evaluates the information found in literature related to a proposed work. During research, a literature review plays a crucial role as it covers all previous studies on the subject, setting the foundation for the current research. It is a critical part of any report because it provides direction and helps set a goal for analysis. [1] One such proposed work is "Time Table Scheduling using Genetic Artificial Immune Network," which highlights the importance of scheduling in real-life situations such as personnel scheduling, production scheduling, and educational schedule scheduling. [2] Educational schedule scheduling can be particularly challenging due to the various constraints that must be met to achieve a feasible solution. [6]  Although Genetic Algorithms (GAs) have been used with mixed success, this work proposes a solution using N Queen algorithm-based approach to solve the heavily constrained Education timetable problem. [3] A review of the scheduling system at our institute revealed the need for a feasible lecture/tutorial timetable for a department, which has been a continuous challenge in educational establishments. [5] The N Queen algorithm-based approach proved to be a useful solution; however, certain issues still need to be addressed. [7] By reviewing existing literature and proposing innovative solutions to existing problems, this work contributes to the advancement of knowledge in the field of educational scheduling. The proposed approach has the potential to simplify and optimize the scheduling process, making it more efficient for educational institutions. [8]

A. N Queen Algorithm

The Algorithm is the fine chess algorithm of Queen. No two queen can be at its diagonal or straight. This is used to be known as Clash.  The objective is to find a solution where each queen is placed in a different row and column. To solve the problem, we start by placing queens one by one in each column, beginning from the leftmost column. After placing a queen in a column, we check for any conflicts with already placed queens. If there is no conflict in the current row, we mark this row and column as part of the solution. However, if we cannot find a row where there is no conflict, we backtrack and try a different row in the same column until we find a solution or return false if there is no solution

B. Genetic Algorithm

The concept of a genetic algorithm is based on the theory of natural evolution proposed by Charles Darwin. In this algorithm, the fittest individuals are selected for reproduction to produce the offspring of the next generation, reflecting the process of survival. The algorithm begins by selecting the fittest individuals from a population, which then produce offspring that inherit the characteristics of their parents and are added to the next generation. If the parents have better fitness, their offspring are more likely to survive and be better than their parents. This iterative process continues until a generation with the fittest individuals is found. This concept can be applied to solve various problems by considering a group of solutions and selecting the set of the best ones

A genetic algorithm typically involves a series of five phases:

• Initial population
• Fitness function
• Selection
• Crossover
• Mutation

1. Initial population: The initial step of the genetic algorithm involves creating a population of potential solutions to the problem being tackled. These solutions are encoded in each member of the population. The fitness function is then used to evaluate and assign a fitness value to each individual in the population. The success of the algorithm depends on the quality of the initial population. A well-constructed and sufficiently large initial population increases the chances of finding a good solution. Conversely, a poorly constructed or inadequate initial population can make it challenging for the algorithm to discover a desirable solution.
2. Selection: The selection operator plays a crucial role in a genetic algorithm, as it determines which chromosomes within the population will be chosen for reproduction. The probability of selection is proportional to the fitness value of each chromosome, so fitter solutions have a higher chance of being selected. This process is repeated during each generation, with a portion of the population being chosen to create a new generation of solutions. The fitness-based selection ensures that the best solutions are more likely to be chosen, increasing the chances of finding an optimal solution to the problem at hand.
3. Crossover: The crossover is a crucial genetic mechanism that is employed to introduce variation into the programming of one or multiple chromosomes between successive generations. It imitates the biological process of reproduction and genetic recombination that underpins genetic algorithms. In a crossover, multiple parent solutions are combined to produce a new child solution. Various techniques can be employed to select the parent chromosomes. During the crossover process, segments of chromosomes before and after a particular locus are randomly exchanged between two parent chromosomes to produce two new offspring chromosomes. Essentially, the crossover operator simulates the natural recombination process that occurs between two individual organisms with a single chromosome.
4. Mutation: In genetic algorithms, mutation is a mechanism to maintain diversity in a population of chromosomes from one generation to another, similar to natural mutation. This process involves altering one or more gene values in a chromosome from its original state. Through mutation, the resulting solution may be significantly different from the previous one, providing opportunities for the algorithm to improve. Typically, mutation occurs at each bit position in a string with a low probability.
5. Fitness function: The fitness function evaluates the quality of a solution represented in the genetic form and measures the level of performance of the represented solution. In fields such as genetic algorithms and genetic programming, each solution is represented in a genetic form, and after each iteration, the objective is to eliminate the 'n' worst solution representations. A solution needs to be assigned a score to indicate how well it met the overall requirement, and this score is generated by applying the fitness function to the test results obtained from that solution.

III. PROPOSED SYSTEM

Currently, timetables for academic institutions are created manually by faculty members, which can be a time-consuming and challenging task. One of the main responsibilities at the beginning of each academic year is to create a timetable for all grades, considering the availability of faculty members for each subject. However, this can become complex due to various factors such as the education scheme, workload of faculty members, and optimization of resources such as labs and rooms.

To address this issue, an automated system can be developed to generate timetables for all grades based on predefined education schemes and the availability of faculty members. This system will optimize resources by generating possible timetables for teaching faculty, taking into account the constraints of working days of the week. With this approach, the system will save time and effort for institute administration.

A. Constraints

1. Each subject has a predefined education scheme.
2. Faculty members’ workload is taken into consideration.
3. No slot clashes should occur for a faculty member.
4. Priority is given to scheduling practical slots followed by tutorial slots.
5. Labs are provided for tutorials, if required.

Creating a timetable for each grade at the beginning of every academic year is a complex challenge that requires taking into account the availability of faculty members across all grades. The manual process of creating timetables can be time-consuming for faculty members. Therefore, an automated system can help to save time and energy for institute administration. The automated timetable generator will work for all grades and optimize the use of available resources, including faculty members, labs, and rooms. By taking into account the predefined education scheme for each subject and the workload of faculty members, the system will generate feasible timetables for the working days of the week. It will ensure that practical slots are given priority, followed by tutorial slots, and will allocate labs for tutorials when needed. Overall, the system will make optimal use of resources to meet the scheduling constraints.

Each faculty member is required to register themselves on the portal using their unique faculty identification number or employee identification number. The system will then take inputs such as branch, division, grade, number of subjects, and workload of the faculty member. To ensure slot availability for a particular subject in a grade, the system follows specific rules and constraints stored in its knowledge base, providing all possible slots. Our project uses algorithms that streamline the process of generating timetables, employing various strategies to optimize resources and minimize difficulties.

IV. METHODOLOGY

A design methodology refers to a systematic approach of applying a set of methods to create a plan. To develop an efficient timetable generation system, the following steps should be taken:

1. Understand the total requirements of the system, including the timetable strategy.
2. Develop a repository to preserve all the essential data.
3. Generate a timetable for the Senior Secondary class by entering the details of the High School.
4. Consider the workload assigned to each faculty member while scheduling their classes.
5. Read the faculty and subject details and store them in the database.
6. Retrieve the Senior Secondary timetable timeslots and assign them to the respective faculty members.
7. Assign labs for tutorials, if required.
8. Schedule theory lectures in the remaining slots after practicals and tutorials.
9. Enter the faculty ID while generating the timetable for the 11th grade.
10. Show all the slots assigned to a particular faculty member as invalid to avoid clashes.

V. SYSTEM ANALYSIS

A. Flowchart

A flowchart is a visual representation of an algorithm, workflow, or process that displays the different steps in a series of boxes and connects them with arrows to indicate their order. The following diagram depicts the detailed procedure of the automatic timetable generator in a step-by-step manner.

B. Use Case Diagram

A use case diagram is a visual representation of the interactions between the users and the system, depicting the specifications of each use case. It provides a high-level view of the system's functionality and the different types of users who interact with it. Typically, a use case diagram is used in conjunction with other types of diagrams to give a comprehensive view of the system. In our system, the staff will input the grade and subject details, and the system will process this information to generate the timetable.

C. Data Flow Diagram

A data flow diagram is a visual tool that illustrates how data moves through a system. It provides a graphical representation of the processes involved in an information system and the flow of data between them. With a DFD, you can see the different types of information that are input to and output from the system, as well as where the data originates from and where it is stored. This diagram helps to identify any potential bottlenecks or inefficiencies in the data flow process and can assist in optimizing the system's overall performance.

VI. IMPLEMENTATION

The implementation phase is the crucial stage where all the planning and conceptualization is brought to life. Our project has been developed using software development approaches, with a focus on creating modules that cater to specific requirements. The key languages that have been used in our project include HTML and CSS, with the database being powered by MYSQL. Additionally, we have leveraged the power of XML framework to optimize the development process. The Machine Learning server provided by our college has been used as the primary server, while the operating system used for development is Windows 7+.

Our project comprises various modules that have been designed to address specific needs. These include:

A. Class Details

To collect all the necessary data required to create the timetable, you need to gather information such as the names of the classes, the subjects taught in each class, and the preferred times for each subject. The class module will contain full details of each class and the subjects taught in them, which may differ across different grades.

B. Subject Details

The subject details contain information about the subjects taught in each grade and section, from lower to higher classes. It includes details of the staff members teaching each subject in each grade. The subject details module holds the overall data about subjects and staff details.

C. Automatic Time Table Generation

The timetable is generated using a genetic algorithm that utilizes data from the class details and subject details modules. Because it uses a genetic algorithm, there are no clashes in the automatically generated timetable. The timetable shuffles whenever the generate button is triggered.

D. Timetable for each Class

The timetable for each class is generated using a genetic algorithm for each grade and its sections. It uses data from the teachers, subjects, and classroom details to generate an automated timetable for each grade. Once the 'generate new' button is triggered, the entire timetable shuffles without causing clashes with other grades.

E. Timetable for each teacher

The timetable for each teacher is generated individually and automatically using the genetic algorithm. It uses data from the class timetable to generate the timetable for each teacher. If a new timetable is generated, it will be reflected in both the teacher's timetable and the class timetable.

Conclusion

Managing faculty members and assigning them to subjects manually is a complex task. Our proposed system aims to address this issue and facilitate the creation of timetables for any number of courses and multiple grades. Our user-friendly system offers a faster and more efficient way to generate timetables, saving time and reducing the need for manual labor. By implementing this project, we aim to reduce the time and effort required to create timetables manually.

References

[1] Thakur, G., Sivakumar, S., & Sharma, R. (2022). An Efficient Approach for Automatic Timetable Generation Using Genetic Algorithm. International Journal of Intelligent Engineering and Systems, 15(2), 224-231. [2] Zhao, X., He, C., Yu, H., & Li, J. (2020). A novel approach to automatic timetable generation using artificial intelligence. Journal of Intelligent & Fuzzy Systems, 38(4), 4625-4634. [3] Wang, L., & Zhao, H. (2021). Automatic timetable generation based on ant colony algorithm. IEEE Access, 9, 6852-6860. [4] Naveed, K., Sajjad, S., & Wahab, A. (2020). A comprehensive review on automatic timetable generation using artificial intelligence. Intelligent Automation & Soft Computing, 26(3), 631-647. [5] Chen, S., Li, S., Li, B., & Li, C. (2022). Automatic Timetable Generation Algorithm Based on Improved Genetic Algorithm. IEEE Access, 10, 5977-5986. [6] Shukla, N., Singh, N. K., & Jain, N. (2019). Hybrid approach for automatic timetable generation using particle swarm optimization and taboo search. Journal of Ambient Intelligence and Humanized Computing, 10(9), 3463-3473. [7] Hassanien, A. E., & Fahmy, A. A. (2022). A multi-objective genetic algorithm for automatic timetable generation. Applied Intelligence, 52(1), 36-53. [8] Yang, X., & Zhang, Q. (2020). Automatic Timetable Generation Based on Improved Particle Swarm Optimization Algorithm. Journal of Physics: Conference Series, 1636(1), 012008. [9] Chen, J., & Wang, J. (2021). Automatic timetable generation based on hybrid algorithm combining ant colony algorithm and simulated annealing. IOP Conference Series: Materials Science and Engineering, 1106(1), 012053. [10] Nair, R. R., Vashisht, A., & Sinha, S. K. (2019). Automatic timetable generation using hybrid particle swarm optimization and tabu search. International Journal of Advanced Intelligence Paradigms, 12(2), 122-143.

Copyright

Copyright © 2023 P. Uma, P. S. Sharvesh, M. Pradeep, P. Sathishkumar, R. Senthilnathan. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.