When making schedule of a large educational institution, we have to work with big data, which requires a special organization of the software and hardware infrastructure: usage of special data structures and indexing, organization of data marts and analytical services, development of new data manipulation algorithms. The paper examines certain aspects of the software and hardware infrastructure for business process of training schedule formation in North Caucasus Federal University.
Copyright c by the paper's authors. Copying permitted for private and academic purposes. but as a rule the main way of compiling is a manual method. In this case, known information systems have the following limitations: require considerable time to prepare the initial data in the form of the department's study load; poorly adapted to the processes of continuous change of the initial data in the study load or do not support the temporality of the initial data; do not allow to make a schedule in the presence of individual learning paths for each student, including the limitations when working with large data; not convenient system of parallel access of a large number of employees, who making the schedule (next { schedule maker), to shared resources (classrooms, training groups, teachers) using the classical query model of data manipulation.
The software and hardware infrastructure of training schedule formation of the North Caucasus Federal University is considered, which allows solve these problems. 2
The North Caucasus Federal University (NCFU) is the largest university in the North Caucasus, formed in 2012. Currently, more than 25,000 students study at more than 400 educational programs in the NCFU. To ensure the main business processes of educational, scienti c and educational activities, the University uses the integrated automated management system (IASY VUZ). In the database IASY VUZ, since 1994, information about more than 500,000 students have been gathered. The total size of the managed dataexceeds 1TB.
Relational OLTP-database IASY VUZ contains more than 1000 tables and indexes based on B+trees. As a result of the normalization, the metadata schema is represented by a tree: the root of the tree is the table kartapromat with students, which accumulates data on the features of each lesson and schedule, assessments, attendance, etc.; the table contains more than 2 billion records; a subtree with educational programs is represented by tables with the description of educational programs, schedules of the educational process, educational disciplines, lists of classes; a subtree with students is represented by tables with personal data of people, training groups, information about students; a subtree with employees is represented by tables with the structure of educational institutions, states, information about employees.
The presented scheme supports the individualization of the learning process of each student, associated with the presence of elective disciplines in the curriculum, the availability of several alternative educational programs, the ability of the federal university to create new own educational standards. The curriculums for di erent education level and form contain from 2000 to 4000 separate lessons with an average of 1000 lessons per year. As a result, it is required every year to schedule for p = 25000 1000 = 25000000 records. With the modern development of computer technology with such a large amount of initial data, the task of automatically or manually compiling a timetable for an acceptable time seems di cult.
Heuristics are required, which can signi cantly narrow the area of data to be processed. The main approach is based on the formation of student learning streams in accordance with the constraints imposed on the academic disciplines, activities, classrooms used. The learning ow is a virtual aggregation of individual lessons of students that can be held together when the conditions for the coincidence of the restrictions accepted in the educational institution are met. Examples of such restrictions are: the coincidence of the name or content of the discipline; complete or partial coincidence of the calendar plans of the educational process; restrictions on the maximum number of students in the stream, for example, because of safety requirements; restrictions on the maximum number of students in the stream due to limitations of the classrooms.
The business process of preparing the study schedule can be conditionally divided into the following stages: 1. The formation of an educational program; 2. Formation of a contingent of students on the educational program; 3. The distribution of students in elective disciplines; 4. Calculation of training streams; 5. The distribution of compulsory resources for educational streams: teachers; 6. Updating the data mart with the study load; 7. Distribution of shared resources by educational ows: classrooms, time; 8. Mapping of the timetable to individual learning trajectories and the formation of individual schedules for students and teachers. 1. In the initial calculation mode, current regulations and restrictions are taken into account when forming the stream. The main tasks at this stage: to minimize the number of streams within the limits of current restrictions; as much as possible to reduce the number of student permutations between di erent streams to avoid unnecessary checks of individual overlays in the schedule for each student. 2. In the regime of continuous updating of streams, changes in educational programs and movement of students are taken into account. The main tasks at this stage: if possible, to preserve the initial set of streams when students are added and removed during the year, including possibly with violation of certain restrictions; when distributing new students through the streams, rst of all, only information about the stream should be taken into account, but not the norms of its formation. At this stage, the study streams have already been checked by specialists and accepted for processing.
The owchart for calculating the study streams is shown in Figure 2. The algorithm for calculating the study streams is a modi ed version of the greedy algorithm, which makes it possible to signi cantly reduce the range of enumeration of all possible combinations of student pooling into streams, but on the other hand does not guarantee global optimization of the formation of streams. At each step of the algorithm, the problem of local optimization is solved by comparing each new occupation of each student with the already formed streams, sequentially checking from the smallest streams to the largest ones. If a suitable ow is found, the student is added to it, otherwise a new stream is created from one person.
The algorithm can be e ectively paralleled when partitioning the sorted list in step 2. At the same time, sectioning should be carried out in such a way as to ensure that all the activities of one student and all potential for the organization of students stream into one section fall into place. Examples of such sections may be institutes or faculties in situations where interfaculty streams are not used in an educational institution. When using the software and hardware infrastructure of the NCFU, the parallel implementation of the presented algorithm takes 8 hours if 15-20 processes are organized. In order to perform analytical services and organize automated workplaces for schedule makers, a data mart with study streams organized in the database. The main implemented analytical services are: calculation of the load of basic resources: classrooms, teachers, training groups; calculation of hourly pay for teachers; optimization and load balancing of students and teachers; calculation of the e ciency of the use of scienti c equipment and laboratories; optimization of the work of auxiliary services: food, security; optimization of the use of water, electricity, etc.
The data mart contains pre-processed aggregated data on study streams and their properties and is designed to update the multidimensional cubes of the OLAP-module of the information system built according to the MOLAP scheme with the update period { one time per day. The main measure is the number of students in the subgroups, combined into a stream. The measurements are: educational programs, groups of students and study streams.
The structure of the fragment of the data mart with a table of measures and tables for storing information about the study streams and groups of students is shown in Figure 3.
The data mart does not store information about individual trajectories of students learning. In order for the information system to track the overlays for each student, the data mart is supplemented with a table 0matchF lows0 (kodpot1, kodpot2) to store the symmetric binary relation of the prohibited overlays in the schedule. Each entry in the table contains all pairs of a binary relation, while only kodpot1 < kodpot2 pairs are stored with symmetry taken into account. To ll the table 0matchF lows0, you need to match all the pairs of lessons of students to each other, i.e. perform Cp2 = C225000000 comparisons. The computational complexity of pairwise comparisons is described by a polynomial of the second degree. To reduce the computational complexity, the list of activities can be compared to itself using a merge join, i.e. doublepass the sorted list. In this case, the computational complexity corresponds to twice the length of the list, but you will also need to sort the list and hash the result to obtain unique pairs of threads with shared students. Script in SQL to ll the table 0matchF lows0:
t h e temporary t a b l e #temp maps t o each f l o w k o d p o t a l i s t o f i t s s t u d e n t s k o d c o n t
t h e t a b l e dbo . k a rt a p r o m a t c o n t a i n s a l i s t o f a l l a c t i v i t i e s f o r a l l s t u d e n t s s e l e c t d i s t i n c t s l 1 . kod pot , k1 . k o d c o n t into #temp from sch . s c h e d u l e L o g s l 1 inner join dbo . kartapromat k1
on k1 . kod ng=s l 1 . i d S c h e d u l e time s e n s i t i v e r e c o r d s where g e t d a t e ( ) between s l 1 . dateBegin and s l 1 . dateEnd and k1 . pr=1 a s i g n o f e l e c t i v e c o u r s e s f o r s t u d e n t s
b u i l d B + t r e e CREATE INDEX I X k o d c o n t ON #temp ( kod cont , kod pot ) ON [PRIMARY] d e t e r m i n e t h e f l o w s i n which t h e r e i s a t l e a s t one common s t u d e n t i n s e r t matchFlows ( kod pot1 , kod pot2 ) s e l e c t d i s t i n c t t1 . kod pot , t2 . kod pot from #temp t1 ( n o l o c k ) inner join #temp t2 ( n o l o c k )
on t1 . k o d c o n t=t2 . k o d c o n t and t1 . kod pot<t2 . kod pot drop table #temp
Figure 4 shows the plan of the last query in the script. When performing a merge join, the connection can be parallelized into several processes by cutting each of the two sorted copies of the student list. The architecture of the program module used by the sta of the university for scheduling classes consists of three main components, represented in Figure 5.
The server part of the software module (Services) is the intermediary between the database and client applications. Its tasks are: transparent access of clients to the database, ensuring the simultaneous operation of all schedule makers and synchronization and data exchange between clients. 1. Database
Client part allows: calculate con icts, arrange classes and view the load of classrooms, teachers, departments.
The architecture of the software module is designed in such a way that all schedule makers work in a single information space. Changes made by one schedule maker are instantly visible to all other schedule makers. To avoid creating con ict situations in the schedule grid (for example, when the teacher at the same time is engaged in several groups), the software module has a subsystem for calculating the con icts. With any changes to the schedule grid, the con icts are automatically recalculated for all clients.
According to this approach, the dispatchers that make up the schedule can track changes in real time and see any kinds of overlays.
The client part consists of the following subsystems:
The subsystem for calculating the con icts is a module designed to account for con icts in the schedule. The following types of con icts are possible: (a) the con ict by the teacher: the teacher conducts the lesson at the same time for several groups; (b) the con ict by classroom: in the classroom in one lesson, several groups are put; (c) the con ict by the number of seats in the classroom: the number of students exceeds the number of seats in the classroom. 2. Storage subsystem
Calculation of con icts requires storing all data associated with the open schedule grid on the client and updating con icts, when changing data, by other schedule makers.
The database contains all records of student movements (transfer to the course, enrollment). In order for schedule makers to have exibility in scheduling, they can selectively make some changes made in database. This process is called acceptance of updates.
Some updates can make changes to the already arranged schedule. In order not to make changes to the schedule already created, they can selectively receive updates.
The procedure of accepting updates is changing the eld that stores the date when updates were last received. Figure 6 shows a section of the database schema.
The update is considered accepted if the lastU pdate entry is less than versionDate.
V ersionDate is the version in which the schedule is running. To accept the update, you must change the lastU pdate entry to the current date, which is always greater than versionDate.
After accepting updates, all changed records are automatically transferred to all clients.
The developed software module is a unique solution at the moment, which allows to make a schedule, take into account overlays, view the load of classrooms, teachers and departments; form various reports; view the schedule through the Internet.
The schedule is available on the Educational portal NCFU http://eCampus.ncfu.ru in the section "Schedule" [9]. Unauthorized users have access to a schedule of streaming lessons, including the schedule of groups of students, teachers, classrooms (Figure 7). After authorization, the user is granted access to a personalized individual schedule.
The client part of the software module allows to create a schedule using the usual gestures drag'n'drop. To add a lesson to the schedule grid, schedule maker needs to drag the lesson from the left side of the application to the schedule grid. To add a classroom to the lesson, schedule maker needs to drag the lesson from the right part to the lesson on the schedule grid. Some classes are assigned to the classroom, and when dragging these classes to the grid, the classroom will automatically be added to them.
The appearance of the program module is shown in Figure 8. 7
The paper presents an approach and describes the software and hardware infrastructure of the big data processing NCFU in the task of calculating the study load and scheduling lessons. Taking into account individual trajectories of training, it is necessary to process several tens of millions of records per year. To solve this problem, special algorithms have been developed for narrowing the area of processed data, forming study streams, calculating overlays in the schedule. To work with a limited set of study stream records and provide analytical services, a data mart has been developed and updated.
At the nal stage, the opposite task is solved: the timetable is mapped on individual trajectory of training, which allows to form an individual schedule for each student and teacher. [6] Automated information system for scheduling classes in ==www:tolgas:ru=orgstructura=kaf iis=nauka=project=raspisanie= educational institutions.
http : [7] BIT.VUZ. Schedule. http://www.pulsar.ru/progs/1904/ [8] Express schedule School Mini. http : ==pbprog:ru=products=programs:php?ELEM EN TI D = 365 [9] Educational portal of NCFU. http : ==eCampus:ncf u:ru