Системный подход к построению онтологии для автоматизации составления расписания многоуровневого вуза

Полный текст

Introduction Methods and approaches of systems analysis form the basis of research methodology in various branches of the economy and scientific and technological development of society, ensuring the choice of the most universal methods, including the formulation and solution of optimization problems. The ontological model, as one of the tools for implementing the systems approach, is a structure of entities (concepts, notions, types of objects), their properties and rules for establishing relationships between them. In its most general form, a schedule is a tabular form of a graph containing instructions on the time, place, and sequence of execution of the required procedures necessary to determine the moment in time at which the management entities must be in certain positions. Schedules of many transport, production, and educational processes are organized with a certain frequency of repetitions in various time intervals. Scheduling theory, which studies the methods of their compilation and optimization, is one of the sections of discrete mathematics and operations research. The scientific direction of scheduling theory originates from the work of Henry Gantt (Gantt H.L.) [1]. At the same time, the compilation and optimization of the schedule of classes of universities, including those combining several levels of education (multi-level), refers to laborintensive multi-criteria problems of NP-complexity. As a traditional method for solving the probem of optimizing educational schedules, genetic algorithms (GA) are used, which became popular in the early 1970s thanks to the monograph by J.H. Holland “Adaptation in Natural and Artificial Systems” [2]. According to the definition of E. Virsanski, “Genetic algorithms are a family of search algorithms, the ideas of which are suggested by the principles of evolution in nature. By simulating the processes of natural selection and reproduction, genetic algorithms can find high-quality solutions to problems including search, optimization, and learning” [3]. The main advantages of GA are the ability to achieve a global optimum when solving complex multi-optimal problems, applicability to optimization algorithms without calculating the gradients of the objective function, and the ability to distribute processing and parallelize the calculations of the objective function (OF). At the same time, in [4-6] it is noted that the effectiveness of genetic algorithms significantly depends on the structure and method of coding the optimized data sets, the justification of which can be provided by methods of ontological modeling, including classes, connections, and rules for the relationship of objects. 1. Literature Review Ontology is a way of formalizing a subject area of knowledge using a conceptual scheme that includes a data structure containing classes of objects, their connections, and rules (relations) adopted in this area” [7-13]. According to E.M. Beniaminov, “Ontologies are specifications in a formal language that record the agreements of a group of specialists on what is called what in their area and what pro-perties it satisfies. Ontologies are usually built on a modular principle and should also be easy to understand for professionals and interpreted by systems when used” [14]. The publications of E.R. Gafarov, A.A. Lazarev, and others [15; 16] with minimax and additive criteria are devoted to the study of fundamental and applied problems of scheduling theory. The article [17] is devoted to the issues of applying scheduling theory directly to organizing the educational process in educational institutions. In [18-20], the rationale for the effectiveness of using the ontological approach to implementing situational management in some subject areas is presented. At the same time, the issues of using the ontological approach to solve problems of optimizing the preparation of educational schedules for a specific multilevel university combining subsystems of higher and secondary vocational education require further resolution [21; 22]. In the most general form, the ontology can be written as [23]: O = <К, R, F>, (1) where К is a set of domain concepts; R is a set of relationships between concepts; F is a set of interpretive functions. The constraints on the components of the ontology are the finiteness and non-emptiness of the set K, while R and F in special cases can also be empty. 2. Research Methods The construction of an ontological model of the academic schedule of a multi-level university was based on a systems approach that takes into account the main classes of the subject area under consideration. This study proposes an automated approach to constructing an ontological model of data used to solve the problems of compiling educational institution schedules, taking into account the structure of a multi-level university. The ontology of the subject area was built on the basis of concepts presented in the database [24]. For automated compilation of the ontology, specialized software was used that allows you to build ontologies using the OWL language. The program provides the ability to add objects, build a class hierarchy and assign roles between individuals. The UML diagram was developed based on the constructed ontology, it describes the structure of the future system, demonstrates its classes, attributes, methods and dependencies between structural blocks. 3. Results and Discussion It is necessary to justify the software platform for the automated construction of an ontological model, as well as identify the main problems that complicate the preparation of the curriculum of a multi-level university and possible directions for solving them. 3.1. Justification of a Software Platform for Automated Construction of an Ontological Model In order to substantiate the software platform used for automated construction of the ontological model, an analysis of known proprietary software tools implementing various stages of its construction was conducted. The results of the analysis are presented in Table 1. Table 1 Characteristics of software tools for automated ontology model building Program Characteristics URL 1. Protégé · Free and powerful ontology development tool, supports OWL, RDF · Suitable for designing complex technical and economic models https://protege.stanford.edu 2. WebProtégé A web-based version of Protégé that allows you to work with ontologies remotely and collaboratively https://webprotege.stanford.edu 3. TopBraid Composer A commercial tool for working with ontologies · Provides integration with various data sources and supports SPARQL https://www.topquadrant.com/ products/topbraid-composer/ 4. OntoUML A plugin for modeling ontologies based on the OntoUML language · Supports integration with other tools https://ontouml.org 5. RDF4J · A framework for working with RDF data and building ontologies · Supports SPARQL queries and database integration https://rdf4j.org 6. Fluent Editor · Ontology creation software with a simplified user interface · Suitable for simple projects http://www.fluenteditor.com 7. Neo4j · Ontology creation software with a simplified user interface · Suitable for simple projects https://neo4j.com 8. OWLGrEd · Visual ontology editor for working with OWL ontologies · Easy to use http://owlgred.lumii.lv 9. GraphDB A graph database optimized to handle ontologies and semantic data https://graphdb.ontotext.com S o u r c e: made by A.F. Rogachev Based on the set of functional capabilities, the Protégé software tool version 5.6.4 was chosen as a platform for developing the ontological model. This software tool supports the OWL and RDF modeling languages and provides integration with various data sources. 3.2. Analysis of the Main Problems of Drawing up the Curriculum of a Multi-Level University The University schedule is mostly organized in a periodic manner, with repetition every week or two. Such an organization allows to reduce planning costs. In the process of drawing up schedules, it is necessary to take into account many restrictions and requirements, such as the number of students in a group, the number of teachers, the size of classrooms, the availability of special equipment, legal regulations, etc. These restrictions can be divided by the degree of severity. Strict restrictions: - students may only be accommodated in a free classroom; - no teacher or student group may have more than one class at a time; - the classroom must have the required number of seats; - the classroom must be equipped with specialized equipment; - the student workload must be uniform. Soft restrictions: - teachers’ preferred class time; - teachers’ preferred classroom; - time and space restrictions for classes for student groups or teachers (for example, if the university has remote buildings). The compilation of a university schedule usually begins with the distribution of the teaching load of teachers based on approved curricula indicating the discipline, groups, number of people in a group and the number of classroom academic hours allocated for teaching the disciplines. The teaching load is compiled based on the regulations and approved procedures of the authorities (Sanitary Regulations and Norms, Federal Education and Science Supervision Service, Russian Federal State Agency for Health and Consumer Rights, Ministry of Education and Science). Some academic disciplines can be combined for several academic groups, for example, for general lectures in lecture halls, or, conversely, divided into subgroups, for example, for computer classes and laboratories in the event of an insufficient number of workstations. The structure of the automated construction of the academic schedule can be presented in the form of an IDEF0 diagram, shown in Figure 1. The schedule of classes is formed on the basis of the approved terms of the academic semester, and the number of academic weeks is also calculated. A class at a university, according to the order of the Ministry of Education and Science dated April 5, 2017 No. 301, is 2 academic hours (90 minutes) long. Each discipline of the curriculum has its own number of classroom academic hours. In order to find out how many classes need to be held in a particular semester, it is necessary to divide the total number of hours by 2, and then by the number of weeks specified in the academic schedule. Each educational institution has at its disposal a classroom fund, often located in separate buildings. Classrooms, like classes, have a specific purpose (laboratories, practical classes, gyms, lecture halls, etc.), a limited number of seats. Specialized classrooms are assigned to faculties and departments. Thus, we get 3 global data tuples: teachers, disciplines and classrooms. In addition, it is necessary to implement the fourth group of data - these are teachers’ preferences. The set of teachers’ preferences will contain wishes regarding the time and date of classes. This is due to the need to involve third-party teachers in the educational process, including production workers, whose employment depends on their main workplace. The listed data arrays must be distributed according to the schedule grid. There are quite a few manual and automated ways to perform this task. The disadvantages of manual distribution of classes are high labor intensity and complexity of coordination within multilevel universities, since it is necessary to establish communication between different faculties and departments. For example, there are disciplines whose teachers are involved in several faculties, mainly general education (mathematics, computer science, and similar). With this approach, the following problems may arise, reducing the quality of the compiled schedule: - simultaneous assignment of classrooms; - the presence of “gaps” for students and teachers; - local excess of the workload of teachers and students above standard values; - the preferences of teachers and “soft” restrictions for students are not taken into account. Figure 1. IDEF0-diagrams of the scheduling procedure S o u r c e: made by D.S. Zakharov There may be situations when the problem of a lack of free classrooms arises at the last stage of creating a schedule. In this case, the specialist must practically create a new schedule with a different distribution of teachers on the schedule grid, which greatly increases the amount of work, taking into account the preferences of teachers, which can change depending on their workload at their main place of work. Another problem with distributing disciplines on the schedule grid is the irregular distribution of hours in the curriculum, when the classroom hours of a discipline may not be multiple of the number of weeks in a semester. In this case, disciplines must be taught unevenly relative to the weekly schedule. In such cases, the university needs to introduce two- or three-week schedule, or set a limit on the number of weeks allocated to a small part of the discipline. A diagram of the consistency of classes within the future system was compiled. To construct the diagram, the following were studied: - the main limitations in drawing up schedules; - the structure of the schedule grid of academic disciplines; - the features of disciplines that require additional conditions, equipment, etc.; - the influence of the size of student groups on the educational process; - the possibility of taking into account the wishes of teachers, mainly working in several educational institutions; - legislative and legal acts regulating the process of drawing up university schedules. 4.3. Construction of an Ontological Model Particular cases of constructing ontologies (1) are the following. For the case when R = F = 0. Then the ontology O degenerates into a regular dictionary: Vc = <К, {}, {}>. (2) If only R = 0, then each concept of the ontology can be associated with some function f from the set F. К = Х1 U Х2, (3) where Х1 and Х2 - sets of correspondingly interpreted and interpreting terms. Taking into account the problems revealed by the above analysis, the ontological model oriented towards constructing the academic schedule of the university in question will include the following concepts: - Groups; - Classrooms; - Curricula; - Teachers; - Academic schedule; - Workload; - Schedule grid. Automation of the scheduling process includes the following steps: - Based on the curricula and the list of groups, the academic load and academic schedule are built; - A schedule grid is formed for student groups; - Subjects with teachers are randomly distributed across the schedule grid (without intersections); - Suitable rooms are assigned. The data structure table and the class interaction diagram within the future system are compiled using the given ontological model. This version of the diagram is intuitively understandable for subsequent creation of a schedule based on the genetic algorithm. Table 2 contains data for generating the zero generation of the genetic algorithm, including the names and types of data, their size, set “flags” and keys. Figure 2. The structure of the formed ontological model S o u r c e: made by D.S. Zakharov Table 2 Data structure of the automated scheduling system Class Flag Type Name Size Flag 1. Calendar id int 11 ai groups varchar 255 semestr1 int 11 semestr2 int 11 2. Breakdown id smallint 4 ai discipline_id smallint 3 igroup char 20 hours_lectures tinyint 3 hours_prak tinyint 3 hours_lab tinyint 3 teacher char 20 bond tinyint 2 3. Restricts id int 11 ai object varchar 255 type varchar 10 data varchar 10 4. Cabinets id int 11 ai build varchar 20 number varchar 20 types varchar 255 5. Cabinet_type id int 11 ai type_name varchar 255 6. Un_cabinets id int 11 ai name varchar 255 cab_id_lek varchar 255 cab_id_lab varchar 255 cab_id_prak varchar 255 7. Curricula id int 11 ai name varchar 255 semester varchar 255 groups varchar 255 type varchar 255 kafedra varchar 255 teacher varchar 255 hours_lek varchar 255 hours_prak varchar 255 hours_lab varchar 255 kafedra varchar 255 teacher varchar 255 hours_lek varchar 255 hours_prak varchar 255 hours_lab varchar 255 S o u r c e: made by D.S. Zakharov Figure 3. UML-diagram of classes of the developed software tool S o u r c e: made by D.S. Zakharov The ontology, including the main classes and constraints of the considered problem of automated scheduling, and the developed data structure of the system allow us to construct the class diagram shown in Figure 3. The class diagram, constructed on the basis of the ontology, was used to develop a software tool created to optimize the scheduling of university classes. MySQL DBMS is used to store the initial information. The described approach to designing the ontology of the subject area, the DB and the program for automated construction and optimization of the schedule was tested at the Sebryakovsky branch of the Volgograd State Technical University. Approaches based on the genetic algorithm were used, to develop the software tool modified taking into account the specifics of the problem being solved. This algorithm allows us to solve optimization problems and find the optimal solution to scheduling theory problems. The iterative approach of the genetic algorithm using pre-justified hyperparameters, the developed CF (fitness function in GA) of the population and the process stopping condition, uses the initial population of the structure generated randomly, and allows finding the optimized solution with sufficient accuracy. However, the numerical experiments conducted on the basis of the described approach to solving the problem of optimizing the educational schedule revealed the following shortcomings: - high costs of RAM and CPU loading time of the computer; - reduction of its efficiency at the stage of completion of the optimization algorithm; - achieving a global optimum is not always feasible, since classical variants of GA implementation allow iteratively achieving an optimum (global or one of the local ones), Elimination of the identified shortcomings required modification of the classical GA based on a system analysis of the possibility of adjusting hyperparameters, forming the initial population and genetic operators - selection, crossing and mutation. The modified algorithm of the GA for the task of creating schedules for a multi-level university is shown in Figure 4. YesYes Figure 4. A modified GA algorithm for scheduling problems of a multilevel university S o u r c e: made by D.S. Zakharov Thus, the use of the developed ontology for the automation of the construction of optimized educational schedules allows eliminating the shortcomings of the classical GA, reducing the time of work of educational methodologists in drawing up optimized versions of schedules, while it becomes possible to reduce the number of limi-tations of the mathematical model due to the flex-ible configuration of parameters and the mentioned modifications. Conclusion Based on the application of a systems approach to the automated compilation of a schedule of classes for a multi-level university, the main classes and limitations that must be taken into account when constructing and optimizing schedules of classes are identified. It is shown that the schedule of classes and metrics for assessing their quality should be considered as complex organizational and technical systems characterized by multi-factor integral criteria due to the specifics of educational systems of a multi-level university, the subsystems of which are partially intersecting components of higher and secondary education. The developed ontology allows one to construct a UML class diagram that implements the compilation and optimization of a schedule of classes using the example of specific conditions of a multi-level university. The operating algorithm and software tool developed on the basis of the constructed class diagram and using MySQL DBMS for storing the initial information ensure the construction of an effective schedule of classes for a multi-level university according to the integral criterion using penalty functions.

Об авторах

Алексей Фруминович Рогачев

Волгоградский государственный технический университет

Автор, ответственный за переписку.
Email: rafr@mail.ru
ORCID iD: 0000-0002-3077-6622
SPIN-код: 8413-5020

доктор технических наук, профессор кафедры информационных систем в экономике

Российская Федерация, 400005, г. Волгоград, пр-кт им. Ленина, 28

Дмитрий Сергеевич Захаров

Себряковский филиал Волгоградского государственного технического университета

Email: zakator@bk.ru
ORCID iD: 0009-0009-6665-510X

соискатель, старший преподаватель кафедры математических и естественнонаучных дисциплин

Российская Федерация, 403343, Волгоградская область, г. Михайловка, ул. Мичурина, 21

Список литературы

Дополнительные файлы