The paper investigates the problem of optimizing the university class schedule. Sequential and parallel methods for scheduling based on genetic search are developed. The proposed methods use adapted initialization, crossover, and selection operators. The algorithms minimize conflicts and the time interval between classes, taking into account recommendations for time and place. The developed methods contribute to efective planning of the educational process and avoidance of errors in scheduling. A comparative analysis of the classical and modified genetic algorithms is carried out, confirming the faster and more eficient functioning of the modified approach. The modified algorithm is also compared with diferent operators and parameters of the genetic algorithm to determine the optimal conditions. The obtained results indicate efective methods for improving the quality of the schedule and optimizing the educational process at the university.
Implementation of automatic systems for drawing up university timetables is an urgent task, that is of great importance for improving the management of the educational process. Over the last decades, many studies and developments have been carried out in order to optimize the process of the distribution of working time and resources in university educational institutions.
Lukas et al. [
Abduljabbar and Abdullah [
Alghamdi et al. [
The task of creating a schedule is to create an optimal schedule of classes, taking into account various restrictions and requirements. This issue belongs to the class of NP-complete problems because it is a combinatorial optimization problem in which the number of solutions increases with the size of the input data, constraints, and parameters.
The objective function for the scheduling problem defines the main optimization criteria, which include: • minimizing the number of windows between classes to reduce the downtime of teachers and students; • uniform distribution of the load during the week to increase work eficiency; • minimization of conflicts and overlaps of classes, which involves avoiding overlap between classes with joint groups, teachers or classrooms; • taking into account proposals regarding the schedule to meet the needs of students and teachers.
The objective function calculates the sum of the penalty functions that indicate violations of the constraints when creating the schedule. Each penalty function can have a weight depending on the importance of the corresponding constraint. We use the following notations: n is the number of groups, m is the number of teachers, k is the number of audiences, L is the number of classes, D is the number of school days, U is the maximum number of classes per day, Y is a type of couple, = [1, 2, . . . , ] is schedule relative to groups, = [1, 2, . . . , ] is timetable for teachers, = [1, 2, . . . , ] is the timetable for the classrooms, = [1, 2, . . . , ] is general schedule, X is the schedule of a separate group, teacher or classrooms. 1() is a function that calculates windows between classes and has a corresponding weighting factor 1. The function calculates the diference between the next class and the previous one within one day. Depending on the type of classes, the following diferences will be calculated: between two common classes, or between the common and the numerator or denominator, and between two classes in the numerator or denominator. In general, this function can be described as follows (1): 2() is a function that calculates the overlap of classes and has the corresponding weighting coeficient 2. This function checks whether classes in a certain group or audience do not overlap. the teacher An overlap is considered when two or more classes are scheduled for the same day of the week and class number, or diferent classes are held in the same auditorium. It should be noted that if two classes are held in the same time slot, the class type is the numerator and the denominator, respectively, then this is not considered overlapping. Mathematical model of function (2): 2(, ) is a Boolean function that can be described as follows (3):
2() = 2 ∑︁ ∑︁ 2(, )
=1 =+1 2(, ) = {︃1, if i=j .
0, else.
(1) (2) (3) 3() is a function that calculates compliance with the recommendations regarding the time of the lesson and has a corresponding weighting factor 3. The objective function will look like this (4):
2 2 () = ∑︁ ∑︁ ( ) + ∑︁ ∑︁ ( ) + 2 ∑︁ 2( ) + 3 ∑︁ 3( ) =1 =1 =1 =1 =1 =1 (4)
With the help of weighting coeficients, we can determine the importance of compliance with the corresponding restriction. If the value of the coeficient is high, the priority in the algorithm will be to minimize this limitation.
Planning training sessions is a complex combinatorial task, and traditional scheduling methods are not suitable for it. They use heuristic methods, such as genetic algorithms, which, although they do not guarantee the best solution, efectively search for optimal options.
During the analysis of the available methods of solving the problem, it was established that the most suitable algorithm for drawing up the optimal schedule of classes is the genetic algorithm. Therefore, it was decided to develop an adapted and modified genetic algorithm for solving the given problem.
The scheduling algorithm should minimize the value of the defined objective function (4). The work of the algorithm can be represented in the form of the following formula (5): () → , (5) where S is the class schedule; () is the objective function.
To evaluate the quality of the results of the algorithm, the objective function described above will be used, which shows the number of violations of the specified restrictions.
The purpose of the research is to develop a mathematical model for solving the task of creating an optimal schedule of classes for higher educational institutions.
To achieve this purpose, it was necessary to solve the following tasks: • to develop an adapted classic genetic algorithm for drawing up an optimal class schedule; • to develop a modified method of the classical genetic algorithm; • to present an experimental study of the proposed genetic methods.
An evolutionary genetic method was chosen to optimize the objective function. The genetic algorithm gradually approaches the optimal schedule by selecting, combining, and varying possible solutions.
The main steps of the genetic algorithm are [
The initial data for the system was obtained from the semester assignment information from the software department. This document included a list of subjects, a list of groups attending these subjects, the names of lecturers who give lectures or practical classes, and recommendations for the classrooms needed for the classes. The task was to create a schedule for 28 teachers and 40 groups, using 10 classrooms (6 lecture rooms and 4 laboratory rooms).
The input data for the algorithm were: • a list of classes, each of which included a teacher or teachers, one or more groups, a subject, a type of class, and the number of meetings; • recommended schedule for classes; • the number of school days; • the maximum number of classes per day; • list of classrooms.
The algorithm has the following parameters; • population size; • the number of iterations; • probability of mutation; • probability of crossing; • probability of gene mutation.
Initialization in the genetic algorithm is the process of creating an initial population of
individuals that will evolve in the future [
Two initialization methods were developed.
The first method is random initialization. Random initialization makes it possible to include
various solutions in the initial set, which increases the probability of finding an optimal
schedule. For each lesson, the day of the week, session number, type and audience are randomly
determined. If the class has a recommended schedule, it will be taken into account [
The second method is the initialization of the schedule, modification of the random one: we randomly generate a day of the week, choose an audience, then look for a possible time of the class. If this is the first lesson on the selected day, you can insert it randomly. If there is already a class, then the number is selected in such a way as to minimize violation of the restriction. As a result, we will get a schedule in which there will be no overlap of classes and a reduced number of windows. Using this initialization method will significantly speed up the work of the genetic algorithm.
Crossover is an operation in a genetic algorithm that is used to create a new population.
Crossbreeding consists in the exchange of genes between two parental individuals in order to
create ofspring with a new combination of genes [
It was decided to exchange only one random activity in two random schedules. This allows other genes to change in the next generation and preserve beneficial combinations.
The -point crossover method involves choosing points on the parental chromosomes,
dividing the chromosomes into + 1 segments, and exchanging these segments to create two
ofspring. An even multiple of ensures the division of segments into equal parts [
Advantages of this method include diversity in ofspring, preservation of useful genetic
combinations from parents, and prevention of collapse into a local minimum during optimization.
However, a large value of can lead to the loss of useful information from parental chromosomes
[
Mutation randomly changes one or more genes in a certain solution to increase diversity
and avoid local optima [
Mutation of all genes with a certain probability is used to get out of local optima and find
more optimal solutions [
In the context of a scheduling problem, a population represents diferent schedule options. A crossover involves changes in class numbers, days, or classrooms between two diferent schedule variants for a particular group or instructor. Mutation makes similar random changes in an individual schedule.
In the genetic algorithm, selection is the process of selecting the best solutions for forming
the next population. The essence of selection is to keep the best individuals and get rid of the
worst ones, which leads to a gradual improvement of decisions in each subsequent iteration.
The following selection methods were implemented [
An individual’s fitness determines his or her ability to efectively solve a task or meet certain optimality criteria. It is a numerical value that reflects how well a particular individual meets the requirements.
In the case of scheduling, an individual’s fitness can be measured by the number of conflicts in the schedule, the eficiency of resource use, and the satisfaction of students’ and teachers’ needs. In its algorithm, the function takes into account such strict constraints as overlapping class schedules, inconsistencies with the recommended schedule, and the number of breaks between classes.
Scaling of the adaptability of individuals was implemented in selection. Scaling of fitness values is one of the optimization methods of genetic algorithms, which allows to increase the speed of convergence, unit/s of the algorithm. The basic idea is to rescale the fitness values so that they lie in the range from to . This can be done using a scaling function that transforms the original range of fitness values into a new range corresponding to the range from to [7].
Scaling of the fitness of individuals helps to reduce the influence of diferent scales of fitness functions on the results of the genetic algorithm and allows to more eficiently find the optimal solution [7].
Also, to increase the chances of finding an optimal solution, you can use elitism, which preserves a part of the best individuals from one generation to another without changes. The preservation of elite individuals from the previous population allows to preserve diversity and prevent the loss of useful information [8].
Criteria for stopping the algorithm: • if the maximum number of iterations is reached; • if a schedule is found, the fitness value of which is equal to 0.
One of the methods for improving the classical genetic algorithm is its island model. The GA island model is a model in which the population is divided into several groups (islands). Each island contains its own subpopulation that evolves independently of other islands [9].
With the help of the migration mechanism, individuals can move from one island to another to speed up the convergence of the algorithm. This will help reduce the risk of falling into local minima [9].
In the island model, subpopulations can use diferent algorithm parameters, diferent crossing, mutation and selection operators [9].
Also, the genetic algorithm, like its island model, can be speeded up by parallel implementation. Parallel implementation of GA will speed up the convergence time of the algorithm using several processors [10].
The main idea of the genetic algorithm is to gradually create and improve schedules using operators such as mutation, crossover, and selection. The basic steps of a genetic algorithm include initialization, main cycle, crossover, mutation, calculation of fitness values, selection, termination, and saving the results.
The island model of the genetic algorithm is similar to the classical genetic algorithm, but involves the creation of separate groups of populations that function in parallel and can interact by exchanging individuals.
The island model of the genetic algorithm includes such operations as the initialization of individual islands with diferent parameters and the possibility of migration of individuals between these islands.
The main steps of the GA island model include initialization, initialization of schedules, main loop, island traversal, crossover, mutation, calculation of fitness values, selection, migration (if necessary), selection of best individuals, search of best schedules, replacement of individuals, termination, search of best individual, completing the algorithm and saving the results.
Input data for the system are: • data on classrooms: classroom name, type, capacity, established departments; • data on departments: name of the department and its abbreviated name; • data on specialties: specialty name, code, department; • data on disciplines: name, specialty, semester in which the discipline is taught; • group data: group name, number of students, current semester, specialty; • data on teachers: full name of the teacher and the department where he works; • data about classes: discipline, class type, number of classes per week, teachers, groups, recommended audiences, recommended time.
The initial data is the optimal schedule of classes compiled for the selected department, which takes into account the recommendations for conducting and minimizes the following parameters: • the number of overlapping classes for groups, teachers and classrooms; • the number of windows between classes for groups and teachers.
A computer with the following characteristics was used for the tests: processor AMD Ryzen 5 2600 with a frequency of 3.9 GHz, 6 cores and 6 threads, the amount of RAM is 8.00 GB with a speed of 3200 MHz, the type of hard disk is SSD, and the operating system is the Virtual Machine Windows Server 2022.
The speed of convergence parameter was used to compare the performance of the algorithm. The speed of convergence shows how quickly or eficiently the algorithm approaches its optimal solution. This parameter can be calculated using the following formula (6): where is the speed of convergence; is the initial fitness value; ( ) is the final value of iftness; is the initial time of the algorithm; is the final time.
The following abbreviations should also be noted: is the value of elitism, i.e. the percentage of the total population; is type of crossing: 1 – “custom one gene”, 2 – “-point”; is the number of crossing points; is the probability of crossing; is mutation type: 1 – “custom one gene”, 2 – “all genes”; is probability of gene mutation; is probability of mutation; is selection type: 1 – “roulette”, 2 – “ranging”, 3 – “tournament”; is initialization type: 1 – “random”, 2 – “simple algorithm”; is the maximum number of iterations of the algorithm; is the size of the population.
The following parameters were used for the tests: number of days for making a schedule – 6, number of classes for making a schedule – 6, penalty for windows in groups – 1, penalty for windows in teachers – 1, penalty for overlapping classes – 5, and penalty for inconsistency recommended class time – 5.
Table 1 lists the test run parameters for the genetic algorithm, including the population size (500) and the maximum number of iterations (2000). According to table 1, the results of these tests are given. It is important to note that each entry in table 2 represents the average value of the results of three conducted experiments with the same parameters.
Genetic algorithm parameters, such as population size and maximum number of iterations, were kept constant for all tests to ensure comparability of results between diferent experiments.
Table 3 presents the parameters used during tests of the genetic algorithm modification – the island model. Table 4 contains the results of these tests, and each test was performed three times, after which the average value of the results was calculated. All tests used the same parameters: a population size of 500 and a maximum number of iterations of 2000.
The following designations should be entered: is the number of islands; is a step of increasing the values in the islands; is the number of iterations through which to migrate between islands; is the number individuals participated in migration.
Analyzing table 2, we can draw the following conclusions about the highest convergence rate for the GA parameters: mutation probability – 0.2; mutation type – single gene mutation; crossover probability – 0.6; elitism value – 0.2; sampling type – roulette; crossover type – single gene crossover.
To analyze the efect of the parameter = 2 (using a modified initialization parameter), we calculate how much the algorithm’s running time has decreased on average compared to the values of = 1. To do this, let’s calculate the average value of the algorithm execution time for both variants.
The average value of the GA running time at = 1 is 1888.429 s.
The average value of the GA running time at = 2 is 1115.938 s.
The reduction in the running time of the GA algorithm with = 2 compared to = 1 is approximately 40.9%. A 40.9% reduction in running time indicates an improvement in algorithm performance by using = 2.
After analyzing table 4, we can draw the following conclusions about the fastest convergence rate for the island model parameters: number of islands – 6 (number of logical processor cores); parameter divergence step – 7; number of iterations to perform migration – 10; number of individuals to participate in migration – 0.1.
The average running time of the island model at = 1 is 2335.027 s.
The average running time of the island model at = 2 is 1313.531 s.
When using the modified initialization method, the island GA model is on average 1.8 times faster. This can improve the performance of the algorithm, which saves time and resources in solving the problem.
Let’s test the algorithms with the parameters that give the best results (table 5).
A modified genetic method has been developed that uses an initialization operator based on a priori information about the learning process that is available from the given constraints. The use of the developed approach to initializing the genetic method can significantly (several times) reduce the search time.
Also, a modified island model of the developed genetic method was developed to solve the problem of drawing up an optimal schedule of classes. The fundamental diference between the proposed method and existing analogues is the use of a modified initialization operator that tries to reduce the initial fitness value by simply searching through possible options. Using the modified initialization operator, the running time of the classical genetic algorithm was reduced by 40.9%. It is also worth noting that the running time of the island model of the genetic algorithm with the modified initialization operator was reduced by 1.8 times compared to the use of the classical initialization method. This means that the application of this method has significantly saved the algorithm execution time. The modified initialization method improves the performance and speed of the genetic algorithm for scheduling classes, which is important 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 № 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
for efective problem solving.
An experimental study of the proposed genetic methods was performed. The island model of the genetic algorithm proved to be more eficient both in terms of speed and quality of the solutions obtained. On average, the island model of the GA works much faster – the execution time was reduced by 41.3% on average, it has a better fitness function result, the average fitness value is 0, which means that the algorithm has found the ideal solution and makes it a more eficient algorithm for this problem.
The work was carried out with the support of the state budget research project of the state budget of the National University “Zaporozhzhia Polytechnic” “Intelligent methods and tools for diagnosing and predicting the state of complex objects” (state registration number 0122U000972). [7] I. Mulyava, The solution of the problem of automated formation of schedule of educational institutions with genetic algorithms, Mizhnarodnyi naukovyi zhurnal “Internauka” (2018) 77–83. URL: http://nbuv.gov.ua/UJRN/mnj_2018_9%281%29__20. [8] V. V. Kysil, I. V. Drach, T. M. Kysil, Task of creation and optimization of learning schedule that supplements s trict and volatile requirements model, Scientific notes of Taurida National V.I. Vernadsky University. Series: Technical Sciences 6 (2019) 65–70. doi:10. 32838/2663-5941/2019.6-1/12. [9] W. A. Indha, N. S. Zamzam, A. Saptari, J. A. Alsayaydeh, N. b. Hassim, Development of Security System Using Motion Sensor Powered by RF Energy Harvesting, in: 2020 IEEE Student Conference on Research and Development (SCOReD), 2020, pp. 254–258. doi:10.1109/SCOReD50371.2020.9250984. [10] JavaTpoint, Genetic Algorithm in Machine Learning, 2021. URL: https://www.javatpoint. com/genetic-algorithm-in-machine-learning.