For the task of automated scheduling of classes in the higher educational institutions, a model of the space of all possible states of the lesson schedule has been developed. The model is developed in terms of relational algebra. The solution to the problem is found by means of a relational DBMS. Using the proposed approach allows you to get an initial solution to the problem of scheduling classes in a higher educational institution. Also, the model of the space of possible states of the lessons schedule allows you to adjust the schedule when it is further optimized or if it is necessary to make changes to the finished class schedule. The initial solution to the problem is found using an iterative process, which at each step chooses the lesson with the least freedom of scheduling or the lesson of the teacher who has the most busy schedule. Freedom of scheduling classes and the density of teachers' schedules are variables that are calculated at each iteration for a subset of classes not yet scheduled. The optimality of scheduling each lesson is determined by a set of criteria that are summed up using fuzzy logic methods.
The multicriteria task of scheduling classes in the higher educational institutions (HEIs) still does not have a generally accepted solution. R. A. Oude Vrielink, E. A. Jansen, E. W. Hans, J. van Hillegersberg in their article “Practices in timetabling in higher education institutions: a systematic review” made a very detailed review of methods and programs for scheduling classes in higher educational institutions, developed since the 70s years of the 20th century and up to 2017 inclusive [1]. They showed that the problem of automated scheduling of classes still does not have a generally accepted solution. At the same time, the need to obtain an acceptable solution does not decrease over the years, but only increases, since the number of restrictions to the optimal schedule increases.
The works of recent years are mainly devoted to the development of genetic algorithms and swarm algorithms, sometimes modifications of the simulated annealing method are being developed [2] – [7]; in this case, the initial approximation of the solution to the problem is obtained using the Tabu method or graph coloring [8].
“These approaches are defined as heuristics that solve strategies that are used for complex optimization problems. A specific set of algorithms, called heuristic algorithms, have proven to be effective in generating the best nonoptimal solution. Such algorithms can give an approximation that is considered an acceptable solution. Thus, heuristic algorithms seem to be superior to traditional methods, and such algorithms are even combined to strengthen each other” [1].
Mathematical model of the ( , 1. 2. 3. schedule.
The purpose of this work is to develop a new method for automated scheduling of classes and its practical implementation by means of relational DBMS. The mathematical model is built in terms of relational algebra; practical implementation involves the development of a database and server software for it.
The proposed method belongs to a variety of simulation methods. An algorithm based on the principles of simulation should have a set of nonformal (heuristic) rules:
Choosing the next lesson from the list.
Determining the best position for it in the Evaluating the resulting schedule.
To select the next lesson from the list, a multilevel sorting of the list of unallocated lessons is used according to the criteria of increasing the freedom of the arrangement of the lesson in the schedule and
decreasing the density of the teacher's lessons. Fuzzy logic methods with heuristic coefficients determining the weight of each of a large set of criteria for evaluating the optimality of the lesson schedule are used to determine the best position for taking a position in the schedule and assess the resulting schedule. problem being solved in terms of relational algebra
The task of automated scheduling of classes is characterized by a large amount of data that must be stored in a database. However, the tools of relational 2.1.
of the space of possible states of the lesson schedule
Consider the formulation of the problem of scheduling classes in a university in terms of the theory of relations and relational algebra. Let's call one academic pair in one academic group in one academic discipline “lesson”. Let the relation describe academic groups; – possible types of activities (lectures, seminars, laboratory studies); – academic disciplines; – University curricula.
The relations , , , are tables that contain the initial data for the task of scheduling classes. Also, the initial data is contained in the relation – the list of teachers, and in relation to the – list of recitation room.
( , , ℎ, ℎ ) is a derived relation (associative type of entity) that describes the distribution of academic hours between different types of classes in academic disciplines of all curricula: – curriculum identifier; – discipline ID; ℎ – activity ID.
The public budget. The main purpose of the public budget is to empower citizens and NGOs to propose their own local development projects and influence the allocation of a certain share of the budget funds by voting for certain projects.
Let the derived relation
,
) describe
the attachment of groups to curricula; here
academic groups ID. Then the classroom load of
academic groups is described by the relation
is
(
,
(
– the relational operation of naturally joining a relation with a relation over the entire set of common attributes.
The curriculum
for each course in each specialty contains data on the number of academic weeks in a semester.
From the relation Q the stored procedure of the
for
unambiguous
identification
within
one
academic week of each pair of classes in the case
when in a certain discipline for a certain type of
classes, for example, lectures,
hours are
provided per week, where
> 2. Then, for this
type of lesson in this discipline, there should be
training pairs in the schedule (
the set of attributes ) is a unique key.
Composite key identification is inconvenient, so
the primary key
is added to the
relation.
activities to be scheduled are described by the
relation (
allowed for classes, respectively, for teachers,
academic groups and classrooms;
(
describes all possible options for a class schedule.
The ratio is calculated using relational algebra
operations by the formulas (
←
(
,
(
Let
(
what streams.
derived relation
formula (
) (stReam) describes the list of and the associative entity type , ) describes the composition of the stream: which groups are included in the stream. , For the convenience of fetching data and describes the distribution of classes among calculation formulas when setting classes in the teachers, where – teacher identifier. Then the schedule, it is desirable that the attribute . receive its values from the same domain as the attribute, and that the sets of values of these attributes do not overlap. This can be easily achieved if, when assigning a streaming lecture, a (13): where ,
3 is intermediate relational variable; is a derived relation that describes the sets of admissible study pairs for academic streams.
The set of study pairs for each stream is equal to the intersection of the sets of admissible study pairs of all groups included in the stream.
Classes of academic groups can also be conducted with a breakdown of the academic group into subgroups, for example, when conducting laboratory classes in specialized classrooms.
The derived relation ( In relation to SS, the primary key is composite: 2 ← ⊳⊲
⊳⊲ ← , ,
2 is intermediate relational variable.
Each streaming lecture in relation up as many tuples as there are groups in the stream. Let's introduce an additional key attribute – the stream lesson ID.
By projecting the relation onto the , , , um
attributes, we obtain the
relation – a list of all streaming lectures (
(
3 ← ← ⊳⊲ , , , ⊳⊲ ( 3) , , , , ×
Then the ratio , which describes all possible options for the schedule for classes in subgroups, is represented by the formula (15) – (16):
4 is intermediate relational variable.
contains all of the academic including those highlighted as streaming lectures and laboratory sessions conducted by subgroups. To obtain the final list of classes that are conducted for one whole group, and schedule these classes, we need to subtract from the relation the tuples that entered the relations and (17) – (20) using the relational difference operation: 1 ← , , , ℎ, 2 ← , , , ℎ, ( ( ), ), 3 ← ← ( ,
, 3 −
4 is intermediate relational variable.
The curriculum may include disciplines that
have an odd number of academic hours per week
for some types of classes, for example, 3 hours of
lectures, or 1 hour of practical training (seminar).
In this case, lesson by number
will be held
once every two weeks (
To distinguish between weekly and biweekly lessons, add an attribute of type bit (bool) to the relation.
For lessons that are held weekly, = 1, for the rest – = 0. The values of the attribute for the tuples of the relation
are assigned by the stored procedure, which forms the relation from the relation .
The
attribute will also be included in all projections of the relations , ,
relation, that is, in the , , , , , , . (17) (18) (19) (20) (21) (22) (23)
Then the formulas calculating the relations 1, 1,
1, for lessons that are held weekly, take the following form (24) – (26): where ( ) – a relational operation of fetching tuples from a relation satisfying predicate .
To describe lessons that are held once every two weeks, we introduce an auxiliary relation ( ) with two tuples: = 1 and = 2 – an odd-numbered academic week and an evennumbered week. Then the formulas calculating the ratios 0, 0,
0, for classes that are held biweekly, take the following form (27) – (32): (24) (25) (26) (27) (28) (29) (30) (31) (32) 0 ← 0 ← , 0 ← , , , , ,
, , , , , ,
, 0 ← 0 × 0 ← 0 × 0 ← 0 × ( =0( ( =0( ( =0( )) )) )) where 0, 0, 0 are intermediate relational variables.
The relations , , contain a complete list of lessons that need to be scheduled. If we write this list of lessons in one relation , then it must contain all list of the attributes that are present in at least one of these relations: ( , of attributes is defined for all tuples of the relation . The remaining attributes are defined for some subsets of the tuples of this relation.
The relations 1, 1, 1, 0, 0, 0 make up the fuller space of possible states of the lesson schedule. This relations are sections of a given space. Dividing the common space into several sections is necessary to optimize the work of the class scheduling program.
If the space of possible states of the lesson schedule is described using one relation, then it should include all the attributes that are present in at least one of the 6 relations 1, 1, 1, 0, 0,
0, that is, the resulting relation have the following
set of attributes: , some specific numeric values for them. Both of these methods lead to complex predicates in the WHERE clause of the SELECT statement when fetching data from a relation. But for relation , the situation is more complicated, since among the set of attributes there are two keys that must uniquely identify the lesson that needs to be scheduled: , .
The union of a selection of data (SELECT … UNION SELECT …) from several relations with a simple structure and low cardinality is faster than a selection of data from one large table with several complex predicates in the WHERE clause. Thus, the representation of the space of possible states of the lessons schedule in the form of 6 sections for different types of lessons provides a simpler design of queries to the database, as well as faster execution of them.
The cardinality of the relations 1, 1, 1, 0, 0, 0 depends on the cardinality of the derived relations , , and .
The set of admissible study pairs for the lesson
is equal to the intersection of the set of admissible
study pairs of the group for which the classes are
held, the teacher who conducts the classes and the
classroom in which the classes are held. In
formulas (
If classrooms are used for class only and are available on any class, the is the Cartesian product of the list of classroom IDs by the list of study pair IDs. The relation can also be generated automatically if, for all academic groups, all study pairs of all days of the learning week are valid for classes. If for some groups there is a predetermined set of study pairs for which lessons cannot be assigned, this information should be specified as a source data. For example, on a given day of the week, the group is assigned duty in the laboratory, greenhouse, and the like.
The relation is usually formed from the wishes and requirements of teachers for their timetable. The easiest way to fill in the data is for the teachers to list the desired pairs for the entire learning week.
It is necessary to distinguish between the wishes and requirements of teachers. All teachers can put forward their wishes. Requirements can only be formulated by teachers with a sufficiently high rating.
If there are wishes and requirements of teachers, the space of all possible states of the lesson schedule is divided into two subspaces: the subspace of desired states (SDSLS) and the subspace of admissible states (SASLS).
Teachers can specify the desired and acceptable study pairs for classes not only in the form of a set of specific training pairs on specific days of the learning week, but also in the form of a range of possible values for the number of pairs during the day and the number of study days during the week. For example, the wishes and requirements of a teacher may look like this: no more than 3 study days a week, but preferably 2 days.
In this case, before the start of the scheduling of classes, all study pairs are considered desirable for the teacher. Therefore, all the lessons of a given teacher fall into the subset of the desired states of the lesson schedule, that is, they are tuples of relations 1, 1, 1, 0, 0, 0 – depending on the type of lesson.
Let us denote the relations of the subset of admissible states of the schedule of classes through 1, 1, 1, 0, 0, 0 – also depending on the type of lesson: streaming lecture weekly, a group lesson weekly, a subgroup lesson weekly, streaming lecture biweekly, a group lesson biweekly, a subgroup lesson biweekly.
For the example given above, with the teacher's wishes, after putting at least one study pair in the schedule of this teacher's lessons on any two days of the study week, all study pairs of all other days of the week move from the desired category to the acceptable category. That is, the tuples of relations 1, 1, 1, 0, 0, 0, corresponding to the lessons of this teacher on the remaining days of the study week, must be transferred to the relations 1, 1, 1, 0, 0, 0.
When placing each lesson in the schedule, the program first of all considers a subset of the desired states of the lesson schedule, that is, it selects from the relation 1, 1, 1, 0, 0 or 0 (depending on the type of lesson), tuples corresponding to the given lesson.
For each variant of placing a lesson in the schedule, the optimality of the position of this lesson in the space of the week's study pairs is calculated – a certain measure of the quality of this state of the schedule for the teacher and for the group (all groups in the case of a streaming lecture). This measure of quality can take into account many factors: the number of study pairs per day; number of study days per week; the appearance of a "window" in the schedule of a group or teacher; closing the "window" in the schedule of the group or teacher; the need for a group or teacher to move from one educational building to another to conduct a lesson; number of lectures during the study day; the number of laboratory lessons during the study day, and more. Particular factors affecting the quality of setting a lesson in the schedule are summed up in different weights using fuzzy logic methods [10].
The optimality of the location of this lesson in the space of study pairs related to the SASLS is also considered. If the quality measure for some option from this subset exceeds all quality measures of lessons from SDSLS, then this option is chosen.
For the example described above, with the teacher's wishes and requirements for their class schedule specified as a range of values, some states of the lessons schedule may go into a subset of inadmissible states. For this example, after assigning classes to a teacher on any 3 days of the study week, all schedule states with teacher's study pairs on the remaining days of the study week become inadmissible.
These scheduling states should not be considered in further sequential scheduling of classes. However, it is not necessary to remove the corresponding tuples from the relations 1, 1, 1, 0, 0, 0, since it may be necessary to change the lessons schedule to optimize it or if a deadlock occurs when scheduling. Therefore, all the corresponding tuples are transferred to the relations 1, 1, 1, 0, 0 or 0 – in the subspace of inadmissible states of the lesson schedule (SISLS). The relations 1, 1, 1, 0, 0, are not used in the planned scheduling of classes. 2.2.
Classes are placed in the schedule in turn, which is formed so that at each step the lesson with the least freedom of setting in the schedule is selected, or the teacher's lesson with the most dense work schedule is selected. The freedom to schedule classes and the density of the teacher's schedule are not constants calculated before the start of scheduling. These values are variables that are recalculated after each scheduled session.
The current freedom to schedule a lesson is determined by two values 1 and 2. 1 – the number of study pairs of the week for which a lesson can be scheduled. 2 – the number of places in two-dimensional space (study pair) (classroom) to which a lesson can be assigned.
The current density of the teacher's schedule is calculated using two values 3 and 4. 3 – the number of free teaching pairs of the teacher, to which at least one of his unallocated classes can be assigned. 4 – the number of still unallocated lessons of the teacher. The calculations use the relative density of the work schedule of the teacher 1 and the relative freedom of distribution of the lessons of the teacher 5 (33)– (34): 1 = 4 ∕ 3 (33) 5 = 3 − 4 (34)
The 1 and 2 values are calculated for each lesson not scheduled. The 3 and 4 values are calculated for each teacher who has unscheduled lessons.
Since all possible options for setting classes in the schedule are tuples of relations 1, 1, 1, 0, 0, 0 and 1, 1, 1, 0, 0, 0, the calculation of values is reduced to calculating the number of tuples in the specified relations with grouping either by class IDs or by teacher IDs.
From the variables 1, 2, 5, 1 a single value is not formed, according to which the remaining list of activities is sorted. A five-level sorting of the list of lessons is carried out: 1. Ascending 1, where 1 = 1, if 1 < 01, otherwise 1 = 01; 2. Ascending 2, where 2 = 2, if 2 < 02, otherwise 2 = 02; 3. Ascending 5, where 5 = 5, if 5 < 05, otherwise 5 = 05; 4. Descending , where = 1, if > 01, otherwise = 01; 5. Descending , where is the number of groups in the stream for which the lesson is held; for lessons in groups and subgroups = 1.
01, 02, 05, 01 are empirical coefficients, the values of which need to be determined in further practical calculations.
When any lesson is added to the schedule, it goes into the category of realized states of the lesson schedule, and the corresponding tuple from the relation 1, 1, 1, 0, 0 or 0 is transferred, respectively, to the relation 1, 1, 1, 0, 0 or 0 – to the subspace of the realized states of the lesson schedule (SRSLS). All other states of the same lesson – all tuples from the same section of the subspaces of desired, admissible and inadmissible states of lesson schedules (SDSLS, SASLS, SISLS) with an identical lesson key ( , or ( , )) are transferred to the subspace of unrealized lesson schedule states (SUSLS), that is into one of the relations 1, 1, 1, 0, 0 or 0 (depending on the type of lesson). If it is necessary to change the schedule, each tuple from SRSLS can be exchanged with a simple set of operations for any tuple with the same primary key of the lesson from the corresponding section of SUSLS.
It is also necessary to remove from the SDSLS, SASLS, SISLS those states of the lesson schedule that cannot be realized after the current lesson is added to the timetable according to the principle: any teacher cannot conduct more than one lesson at the same time; in any group (stream, subgroup) more than one lesson cannot be conducted at the same time; no classroom can have more than one lesson at a time. All tuples that violate this principle are transferred to the subspace of unrealizable states of the lesson schedule (SVSLS) – in the relations 1, 1, 1, 0, 0, 0. In this case, the search for unrealizable states of the lesson schedule is carried out in all sections of the SDSLS, SASLS, SISLS subspaces.
If the schedule is changed to replace a tuple from some SRSLS section with a tuple from the corresponding SVSLS section, a much more complex set of operations must be performed than when replacing this tuple with a tuple from the corresponding SUSLS section.
A mathematical model of the space of all possible states of the lesson schedule in HEIs has been developed. The model is developed in terms of relational algebra. The solution to the problem of automated scheduling of classes is found by means of a relational DBMS.
The initial solution to the problem is found using an iterative process, which at each step chooses the lesson with the least freedom to schedule or the teacher's lesson with the most tight schedule. Freedom of scheduling classes and the density of teachers' schedules are variables that are calculated at each iteration for a subset of classes not yet scheduled. The list of unscheduled lessons is ordered at each step using empirical coefficients, the values of which will need to be determined during a series of practical calculations. The selected lesson is scheduled in the optimal place in a three-dimensional state (day of the school week) - (number of the study pair) classroom. Optimality is determined by a set of criteria using fuzzy logic methods. An empirical weighting factor is assigned to each criterion. For each possible position of the lesson in the schedule, the criteria are summarized. The value of empirical weighting factors also needs to be determined in a series of practical calculations.
The efficiency of the algorithm based on the proposed model is determined by the developed database schema, which excludes transactions of high complexity.
Several factors contribute to reducing the complexity of transactions: 1. All join operations between database relations are performed prior to starting the scheduling process. 2. Different types of lessons refer to different relations, which allows replacing a data selection from one relationship with a complex structure and high cardinality with several simple selections (connected by the UNION operation) from relations of a simpler structure and lower cardinality; this eliminates NULL-valued attributes and complex predicates in the WHERE clause of the SELECT statement. 3. Storing all possible options for the schedule of classes in the form of physical database tables, and not in the form of their virtual representation – nested queries of various types – increases the volume of the database, but significantly reduces the number of operations required for setting each class in the schedule.
Storing all possible classroom scheduling options in physical database tables also makes it easy to compute characteristics that increase the likelihood of an optimal class schedule, such as the number of unallocated lessons that might "close the window" in a group’s or teacher’s schedule.
Storing unrealized options for placing a lesson in the schedule, as well as unrealizable options (options that are superimposed on already distributed activities) in the form of separate subspaces of the common space of all possible states of the lesson schedule allows you to adjust the schedule and optimize it if necessary.
In assessing the current state of the problem of automated scheduling of classes in the HEIs and its relevance, the analysis performed by R. A. Oude Vrielink, E. A. Jansen, E. W. Hans, J. van Hillegersberg turned out to be very useful [1].