Mathematical Model and Efficiency of Courses Timetable Creation Process

Mathematical Model and Efficiency of Courses Timetable Creation Process

Oleksii Yuriy SakaliukFedir Anatoly Trishyn

Department of Technological Processes Automation and Robotic Systems, Odessa National Academy of Food Technologies, Odessa 65039, Ukraine

Corresponding Author Email: 
sakaliuk@cloud.onaft.edu.ua
Page: 
377-385
|
DOI: 
https://doi.org/10.18280/mmep.080306
Received: 
6 April 2021
|
Revised: 
7 May 2021
|
Accepted: 
18 May 2021
|
Available online: 
24 June 2021
| Citation

© 2021 IIETA. This article is published by IIETA and is licensed under the CC BY 4.0 license (http://creativecommons.org/licenses/by/4.0/).

OPEN ACCESS

Abstract: 

The object of the study is the courses timetable creation process. A complex of problems has been solved, which are related to the mathematical description of the control object. The main purpose of the paper is development of a complex of mathematical models, which are describing the courses timetable creation process and a set of criteria for assessing the quality of a class schedule in higher education. The observation method was used researching of the courses timetable creation process. The research of the process was conducted on the basis of the timetable department of the Odessa National Academy of Food Technologies using the information system "Rozklad". The observer was included in the process creation of the courses timetabling as a participant. Observation is controlled by degree of formalization and conducted in real conditions. Regularity is not systematic namely participants in the process (researcher and staff) deal with unplanned phenomena and unexpected situations. The method of formalization and analysis was used to describe the mathematical model of the courses timetable creation process. The result of the paper is the obtained mathematical models of constraints that are imposed on the timetable and a description of the efficiency criteria of the resulting schedule. The prospects for further research may include the development of the logical control system for the courses timetable creation process, experimental research and optimization of the proposed criteria with fulfilling all the proposed conditions for conducting the process.

Keywords: 

automation, automated control system, control object, identification, optimality criterion, Pareto compromise, scheduling

1. Introduction

The task of scheduling classes is an integral part of the work of any educational institution, including higher education institutions. From the point of view of formalization in the theory of the schedule, the schedule of classes is the determination on the time scale of the place of the discipline with the fulfilment of the requirements set for them. In order to develop an effective automation control system of the courses timetable creation process, it is necessary to define all the requirements and connections between them [1]. One of the steps in developing a process control automation system is a mathematical description of the control object. The need for research is to determine the impact of parameters and limitations of the process of the courses timetable creation process. That is, obtaining a mathematical model that describes the properties and characteristics of the control object.

The relevance of the work for automation and planning is due to the fact that most of the work on this subject are outdated, or are incomplete reviews of the tasks of creating an effective schedule of classes and automation of scheduling, they address only certain aspects of the problem.

For more than half a century, the time schedule problems have attracted the attention of scientists around the world. One of the typical problems of planning is the courses timetable creation. The problem of scheduling is to schedule a set of meetings between teachers and students over a period of time that requires certain resources and meets some additional requirements. In the university schedule, which is the subject of this study, the assignment of classes to teachers, and then the distribution of these classes over time is an important administrative task that must be performed each semester. An important feature of this schedule is that it can be adjusted during the semester and the curriculum for the semester must be followed.

There is a wide variety of works describing a wide range of educational methods of scheduling. A review of its literature is contained in ref. [2]. The variety of methods and approaches to solving the problem of planning suggests that there is still no universal solution. Common to all researchers is the finding of different heuristics that reduce the number of complete search operations. Each of the researchers offers his approach to solving the problem of scheduling. Examples of such methods are mathematical and integer programming, constraint-based methods, the Hungarian method, methods based on graph theory, genetic algorithm, TABU-search, neural networks and evolutionary methods.

We will note that courses timetable creation process depends on the result of the decision of other tasks which need to be solved at the organization of the educational process. The organization of the educational process is based on the Laws of Ukraine "On Education", "On Higher Education", "On Scientific and Scientific-Technical Activity", normative legal acts of the Verkhovna Rada of Ukraine, the Cabinet of Ministers of Ukraine, the Ministry of Education and Science, the National Quality Assurance Agency higher education, standards of educational activity and standards of higher education and other normative documents [1].

The formation of mandatory and desirable requirements and determining the importance of these requirements is the initial stage of formalizing the task of forming a schedule of classes. A lot of scientists have been engaged in this task [3-6]. The main mandatory requirements, non-compliance with which will lead to non-compliance with the curriculum, were described. Researchers have described the desired requirements, but these requirements are not universal for all educational institutions. The main hard and soft constraints are described. Lytvynenko et al. [7] provides a mathematical model of the classes scheduling problem in higher education and considers the algorithm for solving the problem. In the work of A.S. Hasuhadzhiev [8] formed a set of requirements for the selection of an acceptable version of the schedule and selected estimates of the importance of indicators for each group of requirements.

The object of study is the courses timetable creation process.

The courses timetable creation process is a labor-intensive, tedious process that requires a significant amount of human resources and time. Therefore, to increase the creation timetable speed and the quality of the developed schedule, you need to automate the process. The first stage of automation is the identification and description of mathematical models.

The subject of study is a mathematical model of the courses timetable creation process: a mathematical description of process variables, soft and hard constraints, efficiency criteria of the schedule and its target function.

The purpose of the work is to describe the mathematical model and description of the efficiency criteria of the resulting schedule.

Now we give a formalized statement of the courses timetable creation problem, the main condition of which is to implement the curriculum. It is necessary to develop such a mathematical model of courses timetable creation process, which will describe the schedule with all hard constraints, as well as minimize non-compliance with all soft constraints, having only data on the audiences, the list of disciplines taught in higher education, the list of participants educational process (teachers) and students, and set time intervals in which classes can take place. In addition to the courses timetable creation, it is necessary to provide for the possibility of prompt adjustment of the schedule in real-time.

The following task follows from the above.

Let the given sets that are ordered by index:

-audiences, $A=\left\{A_{i}, i=\overline{1, N_{a}}\right\}$;

-disciplines, $D=\left\{D_{i}, i=\overline{1, N_{d}}\right\}$;

-teachers, $P=\left\{P_{i}, i=\overline{1, N_{p}}\right\}$;

-students, $S=\left\{S_{i}, i=\overline{1, N_{s}}\right\}$;

-timeslots, $T=\left\{T_{i}, i=\overline{1, N_{t}}\right\}$.

It is necessary to find such a set $L=\left\{L_{i}, i=\overline{1, N_{l}}\right\}$, for all items Li, where: $F=\sum_{i=1}^{K} \lambda_{i} \cdot \phi_{i} \rightarrow \max$.

Moreover, the schedule is subject to hard constraints, violation of which is unacceptable when creating the schedule of courses.

2. Determining Process Variables

Let's build a mathematical model of courses timetabling creation process, identifying variables and constraints.

L– the set of lessons, $L=\left\{L_{i}, i=\overline{1, N_{l}}\right\}$, where Nl – the number of lessons. Each of them is characterized by the following parameters: academic discipline, audience, participant in the educational process (teacher), student [9].

Lessons are formed for each discipline and student group. The set of lessons can be represented as a combination of two subsets: $L=L_{T S T} \cup L_{F S T}$.

LTST– the set of lessons with special requirements for audience, $L_{T S T}=\left\{L_{T S T i^{\prime}} i=\overline{1, N_{l t s t}}\right\}$, where Nltst – the number of lessons with special requirements for audiences.

LFST – the set of lessons without special requirements for audience, $L_{F S T}=\left\{L_{F S T i}, i=\overline{1, N_{l f s t}}\right\}$, where Nlfst – the number of lessons without special requirements for audiences.

Let's enter a set of time slots $T=\left\{T_{i}, i=\overline{1, N_{t}}\right\}$ – the time intervals when lessons take place, where Nt – the total number of time intervals of the timetable. Usually, the schedule of lessons is made for one semester. The number of weeks, days and pairs per day is known. Each element of the set of time slots is a triple type of tuple: $T_{i}=T(T^{i}_(week),T^{i}_(day),T^{i}_(pair))$, where $T_{\text {week }}{i}=\overline{1, N_{\text {week }}}$ – the number of the week, $\Gamma_{\text {day }}^{i}=\left\{T_{i}, i=\overline{1, N_{\text {day }}}\right\}$ – the number of the day, where $T_{\text {pair }}^{i}=\overline{1, N_{\text {pair }}}$ – the pair number during the day. $N_{\text {week }^{\prime}} N_{\text {day }^{\prime}} N_{\text {pair }}$ – the number of weeks, days and pairs in one semester [10].

D– the set of disciplines $D=\left\{D_{i}, i=\overline{1, N_{d}}\right\}$, where Nd – the number of disciplines. The discipline can be represented as a function of parameters: name of the discipline $D_{n}^{i}$  and lesson duration in hours $D_{t}^{i}: D_{i}=D\left(D_{n}^{i}, D_{t}^{i}\right)$.

A – the set of audiences $A=\left\{A_{i}, i=\overline{1, N_{a}}\right\}$, where Na – the number of audiences of the educational institution. The set of the audiences can be represented as a combination of two subsets: $A=A_{T S T} \cup A_{F S T}$.

Figure 1. The hierarchical structure of the set “Audiences”

ATST – the set of specialized audiences, $A_{T S T}=\left\{A_{T S T i}, i=\overline{1, N_{a t s t}}\right\}$, where Natst – the number of specialized audiences. Specialized audiences are the set of laboratories and audiences with special equipment $A_{T S T l}=\left\{A_{\text {TSTl }_{i}}, i=\overline{1, N_{\text {atstl }}}\right\}$, where Natstl – the number of laboratories and audiences with special equipment.

AFST – the set of non-dedicated audiences, $A_{F S T}=\left\{A_{F S T_{i}}, i=\overline{1, N_{a f s t}}\right\}$, where Nafst – the number of non-dedicated audiences. Non-dedicated audiences are the set of large audiences for students streams $A_{F S T l}=\left\{A_{F S T l_{i}}, i=\overline{1, N_{a f s t l}}\right\}$, where Nafstl – the number of large audiences for students streams; the set medium audiences for groups $A_{F S T m}=\left\{A_{F S T m_{i}}, i=1, N_{a f s t m}\right\}$, where Nafstm – the number of medium audiences for groups; the set of small audiences for subgroups $A_{F S T s}=\left\{A_{F S T s_{i}}, i=\overline{1, N_{a f s t s}}\right\}$, where Nafsts – the number of small audiences for subgroups.

Figure 1 shows the hierarchical structure of audiences set. Non-specialized audiences are audiences without special equipment, such as lecture halls. Specialized audiences include laboratories in which laboratory and practical work takes place using special equipment, devices or individual conditions.

The audiences can be represented as a function of parameters: audience volume $A_{v}^{i}$, audience type $A_{t}^{i}=\{0 ; 1\}$, if $A_{t}^{i}=1$, than the audience is specialized, otherwise without special purpose and the educational building in which the audience is located $A_{b}^{i}: A_{i}=A\left(A_{w}^{i}, A_{t}^{i}, A_{b}^{i}\right)$.

P – the set of participants in the educational process $P=\left\{P_{i}, i=\overline{1, N_{p}}\right\}$, where Np – the number of participants in the educational process.

$S-$ the set of students, $S=\left\{S_{i}, i=\overline{1, N_{s}}\right\}$, where $N_{s}-$ the number of students. Students united in $N_{s g}$ subgroups, forming a set of subgroups $S g$, which looks like: $S g=\left\{S g_{i}, i=\right.$ $\left.\overline{1, N_{s g}}\right\}$, where $N_{s g}-$ the number of subgroups. Subgroups united in $N_{g}$ groups, forming a set of groups $G$, which looks like: $G=\left\{G_{i}, i=\overline{1, N_{g}}\right\}$, where $N_{g}-$ the number of groups. $N_{g}$ groups united in $N_{t s}$ students streams, where $N_{t s}-$ the number of students streams. The set of students streams looks like: $T s=\left\{T s_{i}, i=\overline{1, N_{t s}}\right\}$

Thus, a specific lesson can be represented as a function of the parameters of the discipline, time slot, participant in the educational process and the student: $L_{i}=$ $L\left(D_{d}^{i}, T_{t}^{i}, P_{p}^{i}, S_{s}^{i}, A_{a}^{i}, L_{p}^{i}, L_{s}^{i}, L_{k i n d}^{i}\right)$ where $D_{d} \in D, T_{t} \in T, P_{p} \in$$P, S_{s} \in S, A_{a} \in A, L_{k i n d}^{i}-$ type of lesson and binary variables: $L_{p}^{i}=\{0 ; 1\}, L_{s}^{i}=\{0 ; 1\} .$ The meaning of these variables is as follows. If $L_{p}^{i}=1$, then the teacher $P$ in the time interval $T$ must be in the audience $A .$ At $L_{p}^{i}=0$ this statement is incorrect. If $L_{s}^{i}=1$, then it means that the student $S$ in the time interval $T$ must be in the audience $A$. At $L_{s}^{i}=0$ this statement is incorrect.

3. Hard Constraints Description

All the requirements for the courses timetable will be divided into two groups: mandatory (hard parameters) and desirable (soft parameters).

As part of the courses timetabling creation, we highlight the task of forming an acceptable timetable (not necessarily optimal), which satisfies all the mandatory requirements. Failure to comply with any of the hard constraints means that the courses timetable is not working. This means that there are no situations in the schedule when one teacher can conduct more than one lesson at a time, one audience holds more than one lesson at a time, one student visits more than one audience at a time, the number of students in the audience exceeds the volume of the audience.

The task of courses timetabling creation is to determine the time interval for each audience, taking into account the implementation of hard objective constraints and to provide the required number of cases of simultaneous student formation (students groups, groups, subgroups) and the teacher in one of the possible audiences (laboratories) [7].

1) One teacher can conduct no more than one lesson at a time:

$\begin{align}  & \forall \left( {{P}_{p}},{{T}_{t}} \right):{{P}_{p}}\in P;{{T}_{t}}\in T; \\ & \sum\limits_{i\in {{L}^{{{P}_{p}}}}\cap {{L}^{{{T}_{t}}}}}{L_{p}^{i}\le 1} \\\end{align}$     (1)

$L^{P p}-$ the set of lessons, which involved teacher $P_{p} . L^{T_{t}}-$ the set of lessons that take place in the time interval $T_{t}$. Thus, in the equation (1) the amount $L_{p}^{i}$ from the set $L^{P_{p}} \cap L^{T_{t}}$ not more than 1 . This means that during this pair, the teacher conducts this lesson, or he is free.

2) No more than one lesson can be held in one audience at a time:

$\begin{align}  & \forall \left( {{A}_{a}},{{T}_{t}} \right):{{A}_{a}}\in A;{{T}_{t}}\in T; \\ & \left( \exists !{{L}_{i}}:\left( {{A}_{i}}={{A}_{a}} \right)\wedge \left( {{L}_{i}}={{L}^{{{T}_{t}}}} \right) \right)\vee  \\ & \vee \left( \neg \exists !{{L}_{i}}:\left( {{A}_{i}}={{A}_{a}} \right)\wedge \left( {{L}_{i}}={{L}^{{{T}_{t}}}} \right) \right) \\\end{align}$     (2)

$L^{T_{t}}$ – the set of lessons that take place in the time interval Tt. Expression (2) means that there is a single cycle of lessons, which is assigned a given audience and time interval, or such a cycle does not exist and the audience is free.

3) No more than one lesson can be held per student at a time:

$\begin{align}  & \forall \left( {{S}_{s}},{{T}_{t}} \right):{{S}_{s}}\in S;{{T}_{t}}\in T; \\ & \left( \exists !{{L}_{i}}:\left( S_{i}^{*}={{S}_{s}} \right)\wedge \left( {{L}_{i}}={{L}^{{{T}_{t}}}} \right) \right)\vee  \\ & \vee \left( \neg \exists !{{L}_{i}}:\left( S_{i}^{*}={{S}_{s}} \right)\wedge \left( {{L}_{i}}={{L}^{{{T}_{t}}}} \right) \right) \\\end{align}$     (3)

$L^{T_{t}}$ – the set of lessons that take place in the time interval Tt. The expression (3) means that there is a single cycle of lessons where a subset of students (student formation) are on the lesson, or such a cycle does not exist and student formation is free.

4) The number of students in the audience must not exceed the volume of the audience:

$\begin{align}  & \forall \left( {{A}_{a}},{{S}_{s}},{{T}_{t}} \right):{{A}_{a}}\in A;{{S}_{s}}\in S;{{T}_{t}}\in T; \\ & \sum\limits_{i\in {{L}^{{{A}_{a}}}}\cap {{L}^{{{S}_{s}}}}\cap {{L}^{{{T}_{t}}}}}{S_{s}^{i}\le A_{v}^{a}} \\\end{align}$      (4)

$L^{S_{S}}-$ the set of lessons, which are held for set of the students $S_{s} . L^{A_{a}}-$ the set of lessons, which are held in the audience $A_{a}$. $L^{T_{t}}-$ the set of lessons that take place in the time interval $T_{t}$. Thus, in the Eq. (1) the amount $S_{s}^{i}$ from the set $L^{A a} \cap L^{S_{s}} \cap L^{T_{t}}$ no more than the volume of the relevant audience $A_{v}^{a}$. This means that in this time interval the number of students does not exceed the volume of the audience, or the audience is empty.

4. Soft Constraints Description

The task of courses timetabling creation puts forward increased demands on machine resources. Solving the problem by a complete search and the ratio of all options for the schedule of courses is almost impossible. In addition to the task of creation an acceptable schedule, we highlight the task of improving the existing schedule by fulfilling the desired requirements [11].

1) Lack of "windows" (this is a term used by the supervisors of the educational department, which means a free time interval between classes is longer than a break [1]) for students. Fewer "windows" in the schedule will improve the quality of the schedule, because classes will be placed more densely and the student will not have to wait for the next class more than a break time:

$\begin{align}  & \forall \left( {{S}_{s}},T_{t}^{day} \right):{{S}_{s}}\in S;T_{t}^{day}\in T\left( {{T}_{day}} \right); \\ & \sum\limits_{i\in {{L}^{{{S}_{s}}}}\cap {{L}^{{{T}_{t}}\left( {{T}_{day}} \right)}}}{L_{s}^{i}}=\left( {{i}_{\max }}-{{i}_{\min }} \right)+1 \\\end{align}$     (5)

$L^{S_{s}}-$ the set of lessons, which are held for student $S_{s}$. $L^{T_{t}\left(T_{\text {day }}\right)}-$ the set of lessons that take place in the time interval $T_{t}\left(T_{d a y}\right)$. ${{i}_{\max }}$ – the serial number of the last lesson, $i_{\min }-$ the serial number of the first lesson. Thus, in the Eq. (5) the amount $L_{s}^{i}$ from the set $L^{S_{s}} \cap L^{T_{t}\left(T_{\text {day }}\right)}$ is equal to the expression $\left(\operatorname{imin}_{\max +1}\right)$ if the number of "windows" is 0 .

2) The lessons number of students per day should not exceed the allowable number of lessons per day:

$\begin{align}  & \forall \left( {{S}_{s}},T_{t}^{day} \right):{{S}_{s}}\in S;T_{t}^{day}\in T\left( {{T}_{day}} \right); \\ & \sum\limits_{i\in {{L}^{{{S}_{s}}}}\cap {{L}^{{{T}_{t}}\left( {{T}_{day}} \right)}}}{L_{s}^{i}}\le {{N}_{ld}} \\\end{align}$     (6)

$L^{S_{s}}-$ the set of lessons, which are held for student $S_{s}$ $L^{T_{t}\left(T_{\text {day }}\right)}-$ the set of lessons that take place in the time interval $T_{t}\left(T_{\text {day }}\right)$. Thus, in the Eq. (6) the amount $L_{s}^{i}$ from the set $L^{S_{s}} \cap$ $L^{T_{t}\left(T_{\text {day }}\right)}$ no more than the allowable number of lessons for a student per day $N_{l d}$.

3) Correspondence of the type of audience to the type of lesson:

$\begin{align}  & \forall \left( {{A}_{a}} \right):{{A}_{a}}\in A; \\ & \exists !{{L}_{i}}:\left( L_{kind}^{i}=A_{t}^{a} \right) \\\end{align}$    (7)

The expression (7) means that there is a single cycle of lessons in which the type of audience is assigned to the audience of the appropriate type.

4) The limits of hours per day do not exceed the specified number of study hours:

$\begin{align}  & \forall \left( {{S}_{s}},T_{t}^{day} \right):{{S}_{s}}\in S;T_{t}^{day}\in T\left( {{T}_{day}} \right); \\ & \sum\limits_{i\in {{L}^{{{S}_{s}}}}\cap {{L}^{{{T}_{t}}\left( {{T}_{day}} \right)}}}{2L_{s}^{i}}\le {{N}_{hd}} \\\end{align}$     (8)

$L^{S_{s}}-$ the set of lessons, which are held for student $S_{s}$. $L^{T_{t}\left(T_{\text {day }}\right)}-$ the set of lessons that take place in the time interval $T_{t}\left(T_{\text {day }}\right)$. Thus, in the Eq. (8) the amount $2 L_{s}^{i}$ from the set $L^{S_{s}} \cap L^{T_{t}\left(T_{\text {day }}\right)}$ no more than a specified number of hours per day for students $N_{h d}$.

5) Lectures preferably carried out in the first, second lessons:

$\begin{align}  & \forall \left( T_{t}^{pair} \right):T_{t}^{pair}\in {{T}_{pair}}; \\ & \exists !{{L}_{i}}:\left( \left( L_{kind}^{i}=lecture \right)\wedge \left( T_{t}^{pair}\le 2 \right) \right) \\\end{align}$     (9)

The expression (9) means that there is a single cycle of lessons in which type of class is a lecture and the order of its placement in the time slot is not higher than the second lesson.

6) The number of lectures should not exceed two per day:

$\begin{align}  & \forall \left( {{S}_{s}},T_{t}^{day} \right):{{S}_{s}}\in S;T_{t}^{day}\in T\left( {{T}_{day}} \right); \\ & \sum\limits_{i\in {{L}^{lectures}}\cap {{L}^{{{T}_{t}}\left( {{T}_{day}} \right)}}}{L_{s}^{i}}\le 2 \\\end{align}$     (10)

$L^{\text {lectures }}-$ the set of classes such as "lecture". $L^{T_{t}\left(T_{\text {day }}\right)}-$ the set of lessons that take place in the time interval $T_{t}\left(T_{d a y}\right)$. Thus, in the Eq. (10) the amount $L_{s}^{i}$ from the set $L^{\text {lectures }} \cap L^{T_{t}\left(T_{\text {day }}\right)}$ no more than 2.

7) Some wishes of teachers:

To formulate this requirement, a teachers' wishes matrix Mdesires is considered.

$\begin{align}  & \forall \left( {{P}_{p}},{{T}_{t}} \right):{{P}_{p}}\in P;{{T}_{t}}\in T; \\ & \left( \exists !{{L}_{i}}:\left( P_{i}^{*}={{P}_{p}} \right)\wedge \left( {{L}_{i}}={{L}^{{{T}_{t}}}} \right)\wedge \left( {{m}_{p,t}}=1 \right) \right)\vee  \\ & \vee \left( \neg \exists !{{L}_{i}}:\left( P_{i}^{*}={{P}_{p}} \right)\wedge \left( {{L}_{i}}={{L}^{{{T}_{t}}}} \right)\wedge \left( {{m}_{p,t}}=0 \right) \right) \\\end{align}$     (11)



$M_{\text {desires }}=\left(m_{p, t}\right)_{p=1, t=1}^{N_{p}, N_{t}}$, where mp,t=1, if there is a ban on the lesson for the p-th teacher during the t-th lesson, and mp,t=0, if there is no ban.

$L^{T_{t}}$ – the set of lessons that take place in the time interval Tt. The expression (11) means that there is a single cycle of lessons where the participant of the educational process conducts lessons in a given time interval, if there is no ban on lessons, or such a cycle does not exist and in this time interval lessons are not held. If the teacher's desire leads to non-fulfillment of hard constraints, the desire will not be fulfilled, or there will be another decision that does not violate hard constraints.

8) Minimizing teachers’ transitions between buildings:

$\begin{align}  & \forall \left( {{P}_{p}},T_{t}^{day} \right):{{P}_{p}}\in P;T_{t}^{day}\in T\left( {{T}_{day}} \right); \\ & \sum\limits_{i\in {{L}^{{{p}_{p}}}}\cap {{L}^{{{T}_{t}}\left( {{T}_{day}} \right)}}}{A_{i}^{b}}={{N}_{ab}}; \\ & \left( \exists !{{L}_{i}}:\left( P_{i}^{*}={{P}_{p}} \right)\wedge \left( {{L}_{i}}={{L}^{{{T}_{t}}}} \right)\wedge \left( {{N}_{ab}}\le 2 \right) \right)\vee  \\ & \vee \left( \neg \exists !{{L}_{i}}:\left( P_{i}^{*}={{P}_{p}} \right)\wedge \left( {{L}_{i}}={{L}^{{{T}_{t}}}} \right)\wedge \left( {{N}_{ab}}\le 2 \right) \right) \\\end{align}$     (12)

$L^{T_{t}}$ – the set of lessons that take place in the time interval Tt. The expression (12) means that there is a single cycle of lessons when the participant of the educational process conducts lessons, where the number of educational buildings in which the audiences are located is not more than 2, or such a cycle does not exist.

9) Minimizing students’ transitions between buildings:

$\begin{align}  & \forall \left( {{S}_{s}},T_{t}^{day} \right):{{S}_{s}}\in S;T_{t}^{day}\in T\left( {{T}_{day}} \right); \\ & \sum\limits_{i\in {{L}^{{{S}_{S}}}}\cap {{L}^{{{T}_{t}}\left( {{T}_{day}} \right)}}}{A_{i}^{b}}={{N}_{ab}}; \\ & \left( \exists !{{L}_{i}}:\left( S_{i}^{*}={{S}_{p}} \right)\wedge \left( {{L}_{i}}={{L}^{{{T}_{t}}}} \right)\wedge \left( {{N}_{ab}}\le 2 \right) \right)\vee  \\ & \vee \left( \neg \exists !{{L}_{i}}:\left( S_{i}^{*}={{S}_{p}} \right)\wedge \left( {{L}_{i}}={{L}^{{{T}_{t}}}} \right)\wedge \left( {{N}_{ab}}\le 2 \right) \right) \\\end{align}$     (13)

$L^{T_{t}}$ – the set of lessons that take place in the time interval Tt. The expression (13) means that there is a single cycle of lessons when the student has lessons, where the number of buildings in which the audiences are located is not more than 2, or such a cycle does not exist.

5. Courses Timetabling Creation Process Target Function

The schedule of courses should be as convenient as possible for both students and participants in the learning process [7]. It is difficult to choose one criterion by which to assess the quality and effectiveness of the schedule of courses. In section “Soft Constraints Description” a list of criteria that will be used in the work to optimize the schedule of courses sessions was proposed.

Let's assume that $\phi_{i}: X \rightarrow R^{1}, i=\overline{1, K}$ – functions, each of which optimizes one criterion for assessing the schedule of training sessions, where K – this is the total number of criteria. Then the criterion of efficiency in the courses timetabling creation task will be:

$F=\sum\limits_{i=1}^{K}{{{\lambda }_{i}}\cdot {{\phi }_{i}}}\to \max $     (14)

λi – a "weighting factor" that determines the significance of the i-th criterion. The "weighting factor" is determined by the operator, before creating a schedule based on their own considerations about the importance of each efficiency criteria. The difference between the current and the "ideal" schedule is an integral assessment of the schedule by all criteria.

The efficiency of schedule by constraint (5) – ϕw is determined for each student and it takes value $\phi_{w} \in[0 ; 1]$. The minimum possible number of “windows” is $C_{w}^{\min }$, and the maximum possible number of “windows” is $C_{w}^{\max _{s}\left(\left(T_{\text {pair }}^{i}\right)_{\max } 0\right)}$, where $\left(T_{\text {pair }}^{i}\right)_{\max }$ – the maximum possible number of lessons per day. Then ϕw (15) is the ratio of the difference between the maximum possible number of "windows" $C_{w}^{\max }$ and the actual number of "windows" Cw to the maximum possible number of "windows" $C_{w}^{\max }$. From this statement it follows that the greater the value KW, the higher the efficiency of the created schedule of courses, because the number of "windows" is less.

${{\phi }_{w}}=1-\frac{{{C}_{w}}}{C_{w}^{\max }}\to \max $      (15)

The efficiency of schedule by constraint (6) –ϕld is determined for each student and it takes value $\phi_{l d} \in[0 ; 1]$. The minimum possible number of exceedances of the number of lessons per allowable number per day is equal $C_{l d}^{\min }$, and the maximum possible number of excesses is $C_{l d}^{max \sum_{i=1}^{N_{s} \frac{N l d}{i}}{l d^{+1}}}$, where $N_{i}^{l d}$ – the number of classes for each student according to the plan, ${{N}_{ld}}$ – the permissible number of classes for a student per day. Then ϕld (16) is the ratio of the difference between the maximum possible number of exceedances of the number of lessons for the allowable number $C_{l d}^{\max }$ and the actual number of exceedances of the number of lessons for the allowable number Cld to the maximum possible number of exceedances of the number of lessons for the allowable number $C_{l d}^{\max }$. From this statement it follows that the greater the value ϕld, the higher the efficiency of the created schedule of courses, because the less the number of exceedances of the allowable number of lessons per day.

${{\phi }_{ld}}=1-\frac{{{C}_{ld}}}{C_{ld}^{\max }}\to \max $      (16)

The efficiency of schedule by constraint (7) – ϕat is determined for each lesson and it takes value $\phi_{a t} \in[0 ; 1]$. The minimum possible number of discrepancies in the type of audiences is equal $C_{a t}^{\min }$, and the maximum possible number of discrepancies in the type of audiences is $C_{a t}^{\max _{l}}$. Then ϕat (17) is the ratio of the difference between the maximum possible number of discrepancies between the type of audience and the type of lessons $C_{a t}^{\max }$ and the actual number of discrepancies between the type of audience and the type of lessons $C_{a t}$ to the maximum possible number of discrepancies between the type of audience and the type of lessons $C_{a t}^{\max }$. From this statement it follows that the greater the value ϕat, the higher the efficiency of the created schedule of courses, because the number of audiences that do not correspond to the type of lessons is less.

 ${{\phi }_{at}}=1-\frac{{{C}_{at}}}{C_{at}^{\max }}\to \max $      (17)

The efficiency of schedule by constraint (8) – ϕhd is determined for each student and it takes value $\phi_{h d} \in[0 ; 1]$. The minimum possible number of exceedances of study hours per day for the allowable number of study hours per day is equal $C_{h d}^{\min }$, and the maximum possible number of excesses is $C_{h d}^{\max _{s} d a y}$. Then ϕhd (18) is the ratio of the difference between the maximum possible number of exceedances of study hours per day for the allowable number of study hours per day $C_{h d}^{\max }$ and the actual number of exceedances of study hours per day for the allowable number of study hours per day Chd to the maximum possible number of exceedances of study hours per day for the allowable number of study hours per day $C_{h d}^{\max }$. From this statement it follows that the greater the value ϕhd, the higher the efficiency of the created schedule of courses, because the number of exceedances of the allowable number of study hours per day is less.

${{\phi }_{hd}}=1-\frac{{{C}_{hd}}}{C_{hd}^{\max }}\to \max $      (18)

The efficiency of schedule by constraint (9) – ϕnl is determined for each student and it takes value $\phi_{n l} \in[0 ; 1]$. The minimum possible number of lectures held after the second lesson for each student is equal $C_{n l}^{\min }$, and the maximum possible number of lectures held after the second lesson for each student is $C_{n l}^{\max _{s} d a y}$. Then ϕnl (19) is the ratio of the difference between the maximum number of lectures given after the second lesson for each student $C_{n l}^{\max }$ and the actual number of lectures given after the second lesson for each student Cnl to the maximum possible number of lectures held after the second lesson for each student $C_{n l}^{\max }$. From this statement it follows that the greater the value ϕnl, the higher the efficiency of the created schedule of courses, because the number of lectures after the second lesson is less.

${{\phi }_{nl}}=1-\frac{{{C}_{nl}}}{C_{nl}^{\max }}\to \max $      (19)

The efficiency of schedule by constraint (10) – ϕal is determined for each student and it takes value $\phi_{a l} \in[0 ; 1]$. The minimum possible number of days where more than two lectures for each student is $C_{a l}^{\min }$, and the maximum possible number of days where more than two lectures for each student is $C_{a l}^{m a x_{s} d a y}$. Then ϕal (20) is the ratio of the difference of the maximum number of days where the lectures are more than two for each student $C_{a l}^{\max }$ and the actual number of days where there are more than two lectures for each student Cal to the maximum possible number of days, where there are more than two lectures for each student $C_{a l}^{\max }$. From this statement it follows that the greater the value ϕal, the higher the efficiency of the created schedule of courses, because the number of days where the number of lectures is more than two is less.

${{\phi }_{al}}=1-\frac{{{C}_{al}}}{C_{al}^{\max }}\to \max $      (20)

The efficiency of schedule by constraint (11) – ϕd is determined for each teacher and it takes value $\phi_{d} \in[0 ; 1]$. The minimum possible number of non-fulfillment of teachers' wishes is equal $C_{d}^{\min }$, and the maximum possible number of non-fulfillment of teachers' wishes is $C_{d}^{\max \sum_{i=1}^{N_{p}} N_{\text {desires }}^{i}}$, where $N_{\text {desires }}^{i}$ – the number of wishes of the i-th teacher. Then ϕd (21) is the ratio of the difference between the maximum number of non-fulfillment of teachers' wishes $C_{d}^{\max }$ and the actual number of non-fulfillment of teachers' wishes Cd to the maximum possible number of non-fulfillment of teachers' wishes $C_{d}^{\max }$. From this statement it follows that the greater the value ϕd, the higher the efficiency of the created schedule of courses, because the number of unfulfilled wishes of teachers is less.

${{\phi }_{d}}=1-\frac{{{C}_{d}}}{C_{d}^{\max }}\to \max $      (21)

The efficiency of schedule by constraint (12) – ϕpd is determined for each teacher and it takes value $\phi_{p d} \in[0 ; 1]$. The minimum possible number of transitions for teachers between buildings is $C_{p d}^{\min }$, and the maximum number of transitions between buildings equal $C_{p d}^{\max \sum_{i \in L}^{\Sigma} P_{p_{\cap L}}T_{t}\left(T_{d a y}\right)^{\left(i_{\max } \mathrm{()}\right)}}$, where imax – this is the ordinal number of the last lesson of the teacher on a particular day. Then ϕpd (22) is the ratio of the difference between the maximum number of transitions of teachers between buildings $C_{p d}^{\max }$ and the actual number of teachers transitions between buildings Cpd to the maximum possible number of transitions of teachers between buildings $C_{p d}^{\max }$. From this statement it follows that the greater the value ϕpd, the higher the efficiency of the created schedule of courses, because the number of transitions of teachers between buildings is less.

${{\phi }_{pd}}=1-\frac{{{C}_{pd}}}{C_{pd}^{\max }}\to \max $      (22)

The efficiency of schedule by constraint (13) – ϕsd is determined for each student and it takes value $\phi_{s d} \in[0 ; 1]$. The minimum possible number of transitions for students between buildings is $C_{s d}^{\min }$, and the maximum number of transitions between buildings equal $C_{s d}^{$\max \sum_{i \in L^{S} \cap L}^{\Sigma} T_{t}\left(T_{d a y}\right)^{\left(i_{\max } ()\right)}$}$, where imax – this is the ordinal number of the last lesson of the student on a particular day. Then ϕsd (23) is the ratio of the difference between the maximum number of transitions of students between buildings $C_{s d}^{\max }$  and the actual number of students transitions between buildings Csd to the maximum possible number of transitions of students between buildings $C_{s d}^{\max }$. From this statement it follows that the greater the value ϕsd, the higher the efficiency of the created schedule of courses, because the number of transitions of students between buildings is less.

 ${{\phi }_{sd}}=1-\frac{{{C}_{sd}}}{C_{sd}^{\max }}\to \max $      (23)

This approach is not the only one. The number of constraints may increase, but this will increase the complexity and flexibility of the system. There may be problems with the solution of large systems, namely: lack of computer memory, loss of accuracy, the way to improve results will be very difficult and long.

6. Efficiency and Finding a Compromise Between the Criteria

Analysis of the criteria for optimality of schedule does not allow to identify the most important of them, assuming that others are insignificant [12]. In cases where the efficiency indicator cannot be represented as one indicator and one optimality criterion, the problem is called multicriteria. In the case of a multicriteria problem, the optimization problem is considered as a problem of finding a compromise between the criteria [13]. These criteria may reflect assessments of the different qualities of the object or process about which the decision is made [14].

One type of compromise is the Pareto compromise. In this case, we get not one solution, but the solution area of the optimization problem. Defining the area of compromises Qx is to select from a set of acceptable solutions Q a subset having the property that each solution $q \in Q_{x}$, cannot be improved without deteriorating at least one of the criteria. [15].

On the set of variants of change of the schedule, at its optimization, the set of Pareto-optimal variants is defined, i.e. options where the integrated estimate of the schedule is close to zero, i.e. the estimate of the "ideal" and the actual schedule are equal, or almost equal, in other words, a schedule that does not deteriorate compared to the original schedule. Such decisions include those where deterioration by one criterion does not result in a weakening by any other criterion.

Ideally, the task of forming a schedule of courses can be considered as a task of finding such $x \in Q$, at which the maximum of all private criteria is reached, where x – allowable schedule, Q – the set of all possible allowable schedules [16]:

$\left\{ \begin{align}  & {{\phi }_{i}}(x)\to \max  \\ & x\in Q \\\end{align} \right.$      (24)

In practice, a solution in which the maximum of all private criteria is achieved simultaneously exists as an exception. This is often due to various contradictions between the subjects of the schedule. Therefore, the solution of such problems should be sought in the set of Pareto-optimal solutions $Q_{x} \subset Q$. Then choose the resulting schedule from the set Qx could be performed by an expert, however, the power of the set Qx for problem (24) can be large, which makes its analysis by an expert difficult and tedious. Therefore, it is better to reduce the number of criteria for evaluating schedules. The problem of determining the set Qx takes the form:

$\left\{ \begin{align}  & {{F}_{k}}\left( x \right)\to \max ,k=1,2 \\ & {{F}_{1}}\left( x \right)=\sum\limits_{i=1}^{K}{{{\lambda }_{i}}\cdot {{\phi }_{i}}\left( x \right)} \\ & {{F}_{2}}\left( x \right)=\underset{i=1...K}{\mathop{\min }}\,\left( {{\lambda }_{i}}\cdot {{\phi }_{i}}\left( x \right) \right) \\ & x\in Q \\\end{align} \right.$      (25)

where, Fk(x), k=1, 2 – private criteria indicators of the problem, F1(x) – general assessment of the schedule of courses x; F2(x) – minimum (worst) individual assessment of the schedule x.

In general, to maximize indicators F1(x) and F2(x) is contradictory. For example, changes in some schedule x, increasing the indicator F1(x), can lead to serious disturbances in the schedule of a subject that will lead to increased indicator F2(x), this is especially evident in problems of medium and large size with a large number of requirements for the schedule.

Figure 2 shows a diagram for calculating the effectiveness of the schedule and checking for compliance with hard constraints.

From the output of the "Schedule Creator" block, a ready-made schedule is sent to the input of the "Hard Constraints Check (HCC)" block, which is checked for compliance with hard constraints. If at the outputs of the "Hard Constraints Check (HCC)" block all values are equal to 1, then all constraints are met and the quality of the schedule can be calculated. The input of the "Schedule Efficiency" block receives the schedule and the response that all the prerequisites are met. The block "Schedule Efficiency" calculates private estimates of the effectiveness of the schedule and the general estimate of the schedule. The results of several experiments are listed in Table 1.

Figure 2. Simulink scheme for calculating schedule efficiency indicators

Table 1. The results of experiments

F(x)

φw

φld

φat

φhd

φnl

φal

φd

φpd

φsd

1.

7.74

0.85

0.82

0.91

0.86

0.88

0.9

0.63

0.99

0.9

2.

8.04

0.96

0.82

0.99

0.95

0.85

0.86

0.7

0.95

0.96

3.

8.08

0.93

0.97

0.94

0.83

0.9

0.79

0.94

0.86

0.92

4.

8.41

0.96

0.81

0.97

0.95

0.99

0.92

0.99

0.93

0.89

5.

8.54

0.96

0.87

0.95

0.99

0.99

0.96

1

0.94

0.88

Notes: 1. The number of checked schedules is 5. 2. Minimum individual grades are in bold and italicized.

Analyzing the results obtained for the first experiment, we are looking for a private estimate with the lowest value. By optimizing the schedule by increasing the value of the minimum estimate, we observe the value of the total estimate of the schedule. We see that in the third variant, by increasing the previous estimate of the schedule, another partial estimate decreased. By increasing this estimate, another particular estimate worsens. By the Pareto principle, we are looking for a compromise between the schedule estimate and the worst private estimate.

7. Conclusions

The paper describes a mathematical model of courses timetable creation process. During this, in the first stage, all process variables were identified, namely lessons, disciplines, teachers, students, audiences and timeslots. The next step, using the described variables, was a description of hard and soft constraints. The importance of describing them is that non-compliance with hard constraints will result in the student not fully fulfilling the curriculum, and soft constraints are needed to improve the efficiency and quality of the courses schedule. Therefore, a number of performance criteria were described, according to which the evaluation of the obtained schedule will be performed. But due to the fact that in practice the schedule in which the maximums of all criteria are reached exists as an exception, due to the contradictions of the subjects. Therefore, the number of criteria was reduced to two. The solution of such problems should be sought in the set of Pareto-optimal solutions.

The obtained results will be used in the description of the algorithm and the development of an automated control system for the courses timetable creation process.

Nomenclature

A

set of audiences

D

set of disciplines

F

process target function

K

total number of criteria

L

set of lessons

M

teachers' wishes matrix

N

number of the elements in the set

P

set of participants in the educational process

Q

set of all possible allowable schedules

S

set of students

T

set of timeslots

x

schedule of courses

Greek symbols

λ

weighting factor that determines the degree of importance of the criterion

φ

assessment that determines non-compliance with the desired requirement or soft constraints

  References

[1] Sakaliuk, O., Trishyn, F. (2019). Analysis of process creation of the courses timetabling. Automation of Technological and Business Processes, 11(2): 30-35. https://doi.org/10.15673/atbp.v11i2.1370

[2] Petrovic, S., Burke, E. (2004). University timetabling. Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Chapter 45: 1-34.

[3] Adewumi, A., Sawyerr, B., Montaz Ali, M. (2009). A heuristic solution to the university timetabling problem. Engineering Computations, 26(8): 972-984. https://doi.org/10.1108/02644400910996853

[4] Lih, B.C., Nah, S.S., Bolhassan, N.A. (2015). A study on heuristic timetabling method for faculty course timetable problem. 2015 9th International Conference on IT in Asia (CITA), pp. 1-3. https://doi.org/10.1109/cita.2015.7349832

[5] Hooshmand, S., Behshameh, M., Hamidi, O. (2013). A tabu search algorithm with efficient diversification strategy for high school timetabling problem. International Journal of Computer Science and Information Technology, 5(4): 21-34. https://doi.org/10.5121/ijcsit.2013.5402

[6] Khonggamnerd, P., Innet, S. (2009). On improvement of effectiveness in automatic university timetabling arrangement with applied genetic algorithm. 2009 Fourth International Conference on Computer Sciences and Convergence Information Technology, pp. 1266-1270. https://doi.org/10.1109/iccit.2009.202

[7] Lytvynenko, O., Kralina, H., Stopushkina, O. (2004). Matematychna model zadachi skladannia rozkladu navchalnykh zaniat. Proceedings of National Aviation University. 9(1): 180-186. https://doi.org/10.18372/2306-1472.19.992

[8] Hasuhadzhiev, A.S. (2017). Formirovanie sistemy pokazatelej dlja avtomatizacii uchebnogo raspisanija tipovogo vuza. Vestnik AGTU. Serija: Upravlenie, vychislitel'naja tehnika i informatika, 117-127. https://doi.org/10.24143/2072-9502-2017-3-117-127

[9] Khabipov, R. (2018). Avtomatizatsiya postroyeniya raspisaniya zanyatiy v vuze: matematicheskaya model i metody realizatsii. Elektronnyee biblioteki, 21(5): 461-470. https://elbib.ru/article/view/480/559, accessed on Nov. 11, 2019

[10] Kabalnov, Yu., Shekhtman, L., Nizamova, G. Zemchenkova, N. (2006). Kompozitsionnyy geneticheskiy algoritm sostavleniya raspisaniya uchebnykh zanyatiy. Vestnik UGATU. 7(2): 99-107. http://journal.ugatu.ac.ru/index.php/Vestnik/article/view/1354, accessed on Nov. 11, 2019.

[11] Verevkin, V., Ismagilova, O., Atavin, T. (2009). Avtomatizirovannoye sostavlenyee raspisaniya uchebnykh zanyatiy vuza s uchetom trudnosti distsiplin i utomyeyaemosti studentov. Doklady TUSUR. 1(19): 221-225. https://cyberleninka.ru/article/n/avtomatizirovannoe-sostavlenie-raspisaniya-uchebnyh-zanyatiy-vuza-s-uchetom-trudnosti-distsiplin-i-utomlyaemosti-studentov, accessed on Jan. 15, 2020.

[12] Klevanskiy, N.N., Puzanov A.A., Rubtsov, O.G. (2006). Modeli i metody mnogokriterialnoy optimizatsii raspisaniy vuza. Vestnik Saratovskogo gosudarstvennogo tekhnicheskogo universiteta, 17(2): 77-83. http://oldlib.sstu.ru/open/vestniki/2006/04_17_-2006.pdf, accessed on Feb. 9, 2021.

[13] Khobin, V.A. (2008). Sistemy garantiruyushchego upravleniya tekhnologicheskimi agregatami: Osnovy teorii, praktika primeneniya. Odessa: Odesskaya natsionalnaya akademiya pishchevykh tekhnologiy, 1-308.

[14] Chybisov, Y.V., Shulha, Y.S. (2014). Zastosuvannia metodiv bahatokryterialnoi optymizatsii dlia vyrishennia zadachi rozpodilu vahoniv po vantazhnym frontam. Transportni Systemy Ta Tekhnolohii Perevezen, 7(1): 65-72. https://doi.org/10.15802/tstt2014/35994

[15] Kostenko, A.N. (2000). Opredeleniye oblasti kompromissov pri reshenii zadach optimizatsii v mnogokriterialnoy postanovke. Sistemi Obrobki Іnformatsії 2(8): 52-56 http://www.hups.mil.gov.ua/periodic-app/article/13004, accessed on Feb. 15, 2021.

[16] Bezginov, A., Tregubov, S. (2011). Mnogokriterialnyy podkhod k otsenke raspisaniya zanyatiy na osnove nechetkoy logiki. Problemy upravleniya, 2: 52-59. https://cyberleninka.ru/article/n/mnogokriterialnyy-podhod-k-otsenke-raspisaniya-zanyatiy-na-osnove-nechyotkoy-logiki, accessed on Feb. 9, 2021.