A Data-Driven Approach to Modeling and Solving Academic Teachers’ Competences Configuration Problem

Abstract

Before starting the subsequent academic year, the management staff from each organizational unit (faculty, department, research unit, etc.) must solve the university course timetabling problem (UCTP). UCTP belongs to the class of NP-difficult computational problems, thus its optimal solution becomes a challenge, even for small organizational units. Additionally, the process of searching for solutions is complicated by the need to take account of additional constraints resulting from local conditions, teachers’ and students’ preferences, etc. as well as held limited resources. For the management of a given organizational unit at the university, at the beginning of this process, it is important to find an answer to the question: are we able, given the held resources and existing constraints, to find any UCTP problem solution? Only in the next step we can consider finding an optimum solution according to the selected criterion. It seems that every missing resource can be supplemented (acquired, rented, modified etc.). It is a well-known fact from practice that the greatest problem is related to supplementing the missing competences of academic teachers. You can hire new teachers, already employed teachers can acquire new missing competences or you can manage the available set of competences in a different way. However, the solution to this problem (competences configuration) is key even before solving UCTP.

The article presents the data-driven based approach to modeling and solving the academic teachers’ competences configuration problem for the university’s organizational units of various sizes.

1 Introduction

The task of arranging the student and teacher course timetable in an optimal manner is not a simple or fast problem. Difficulties result, first of all, from using limited resources which are: the number of rooms and laboratories, number of teachers, or number of hours available in the given semester etc. Additionally, there is the need to take account of many competing interests reported by both the students and the teachers. Formally, the above problem is classified as University Course Timetabling Problem (UCTP) and recognized as a problem of operation research (OR). Owing to the computational complexity, UCTP belongs to NP-complete problems i.e. no effective algorithm for its solution is known. For this reason, artificial intelligence methods (AI), heuristics, hybrid methods etc. are very often applied for the solution UCTP. On the very general level, UCTP can be defined as the allocation of student groups and teachers to the courses and lecture halls/laboratories in certain time intervals (time-slots). Additionally, the received allocation needs to take account of the availability of each resource (lecture halls, teachers, equipment etc.) as well as fulfill a lot of various constraints. These are both resource – and time-related constraints, disjunctive constraints and additional constraints resulting from local conditions, university regulations and preferences of both teachers and students.

In many UCTP models presented in the subject literature (Sect. 2), it is assumed that the resources, though limited, are available and their number is known, allowing UCTP to be solved. This usually results from long-term practice of arranging the schedules, using last year’s data as well as support for this process from IT tools. It is also assumed that any possible obtained solution will be an acceptable solution and not the optimal one. If, despite that, it is not possible to find even an acceptable solution, and additionally the recruitment has been very successful (more candidates have been recruited than in the previous year), the solution seems obvious. Any missing resources should be obtained (expanded, bought, rented, etc.).

However, this is not always easy and possible to be achieved in such a short time (usually during the summer break); particularly, if lecturers with specific competences (specializations) are not available. An additional difficulty in this area is the fact that in many countries tertiary education has been changing in recent years. More flexible curricula and study forms appear. Many courses and specializations can be selected, which annually results in very variable demand for specific competences of lecturers.

In this context two major questions appear which the managers of the university’s organizational unit must answer. First: does our set of teachers’ competences guarantee finding an UCTP solution? Second, if our set of competences does not guarantee finding a solution to then: What competences are missing and in which quantity? In order to obtain an answer to this and other questions from this area, the teachers’ competences configuration problem and a model proposed for it have been formulated (Sect. 3 Appendix A). Its place and link to UCTP have been presented in Fig. 1.

Fig. 1.

Place of the competences configuration problem (in gray) in the context of UCTP

The main contribution of the presented research is to propose a new version of the proprietary competence configuration model and the use of a modified hybrid approach (data-driven approach) to solve it. The proposed model is a significant extension of the proprietary model from the first stage of research [1]. A significant innovation is that the model includes logical constraints (Sect. 3) and its implementation is possible using the data-driven approach in the proprietary framework (Sect. 4 Fig. 3). Finding a solution to this problem (obtaining answers to the above questions) may save time and result in appropriate actions being taken even before solving UCTP.

2 Literature Review

Timetabling problem was described in the subject literature for the first time in [2]. It was a relatively simple problem, under which only three data collections were considered: (i) classes (ii) teachers and (iii) timeslots. Since then, the timetabling problem has been the subject of interest of many researchers and practitioners [3]. Many options, classes and sub-classes of this problem have also been developed. One of them is UCTP (University Course Timetabling Problem). A fragment of timetabling problem classification has been presented in Fig. 2.

Fig. 2.

Part of the classification of timetabling problems.

Over the years, many methods, algorithms and approaches have been developed to modeling and solving variety of UCTPs.

The most important of them include: (a) operational research (OR) methods based on Integer/Mixed Integer Linear programming (IP/MILP), (b) metaheuristic methods, such as Evolutionary and Genetic Algorithms (E&GAs), Ant Colony Optimization (ACO), Case Base Reasoning method (CBR), Tabu Search Algorithm (TS), Partial Swarm Optimization (PSO), Simulated annealing (SA), Variable Neighborhood Search (VNS), etc., (c) methods and techniques of constraint programming (CP) and constraint logic programming (CLP), (d) multi-agent methods and (e) hybrid methods [4,5,6,7].

Practically, the academic teacher competences configuration problem has not been considered in any of the presented in literature approaches; it has been assumed that the set of academic teacher competences is definite and available prior to modeling and solving an UCTP or a similar problem. In the case of difficulties in finding solutions caused by constrained resources, in practice the number and availability of all resources increases. Such an action is often effective but this result in excessive resource involvement and increased costs.

3 Academic Teachers’ Competences Configuration Problem

After finishing the recruitment and the academic year, organization of the following academic year is planned, this includes division into student groups, specialties, determination of the teaching quotas (loads) for the teachers as well as an initial approach to UCTP. One of key elements of these actions is answer the question: Do we have the appropriate set of teachers with specific competences? This question applies to each organizational unit of the university. The answer is a solution of the specified problem which has been formulated as academic teachers’ competences configuration problem (ATCCP).

Formalization of this problem assumes that in the given organizational unit, academic teachers are employed T = {a₁, …, a_i, …, a_ZC} where ZC – number of academic teachers employed in the unit. Each of the academic teacher a has a certain teaching load allocated F_a i.e. the minimum number of hours to be realized in the given period (semester, academic year etc.). For instance, according to the valid law at Polish universities the teaching load is most often: 150, 240, or 360 h per academic year. In practice many academic teacher teach courses in the number of hours exceeding their teaching load. For this reason, W_a coefficient has been introduced. If W_a = 1, this means that academic teacher a agrees to teach classes in the number of hours exceeding the teaching load (otherwise W_a = 0). WSP coefficient has also been introduced, which determines by which percent an academic teacher’s teaching load can be exceeded without the need to obtain his or her consent (currently it is 15%). Certain types of courses are allocated to the given organizational unit (different forms for the given courses: lecturers, projects, laboratory classes etc.) C = {b₁,…, b_j, …, b_ZT} where ZT – number of types of classes in particular courses assigned to the organizational unit. Each type of courses b has a specified number of hours H_b in which it is realized. In addition, for all courses the number of student groups G_b is defined. Academic teacher of a given unit have certain qualifications (competences) to teach certain types of courses (coefficient Z_b,a = 1 means that academic teacher a, without any further training, courses or postgraduate studies, etc. may offer courses b, otherwise Z_b,a = 0).

The mathematical model for ATCCP has been formulated in the form of a MILP model (Appendix A). Table A2 presents the description of parameters, indexes and decision variables of the model. Table A1 presents the description of main constraints. The function minimizing the number of missing the academic teachers’ competences has been adopted as the objective function (A2).

An important element of the presented model is introducing logical constraints C_Log1, C_Log2 and C_Log3. The constraint C_Log1 formalized as (L1), (L2), (L3) specifies that teacher a should teach all student groups in course b or not teach it at all.

$$ {\text{X}}_{\text{b,a}} \,\ge {\text{ A}} \cdot {\text{ F}}_{\text{b,a}} \,\ge {\text{X}}_{\text{b,a}} $$

(L1)

$$ {\text{X}}_{\text{b,a}} = {\text{F}}_{\text{b,a}} \cdot {\text{h}}_{\text{b}} $$

(L2)

$$ {\text{F}}_{\text{b,a}} \in \{ 0,1\} $$

(L3)

The constraint C_Log2 (L4, L5, L6) forces the situation that if teacher a teaches course b1, then they must teach course b2.

$$ \begin{aligned} {\text{X}}_{\text{b,a}} \ge {\text{A}} \cdot {\text{F}}_{\text{b1,a}} \ge {\text{X}}_{\text{b1,a}} \hfill \\ {\text{X}}_{\text{b2,a}} \ge {\text{A}} \cdot {\text{F}}_{\text{b2,a}} \ge {\text{X}}_{\text{b2,a}} \hfill \\ \end{aligned} $$

(L4)

$$ {\text{F}}_{\text{b1,a}} = {\text{F}}_{\text{b2,a}} $$

(L5)

$$ {\text{F}}_{\text{b1,a}} \in \{ 0,1\} ;{\text{F}}_{\text{b2,a}} \in \{ 0,1\} $$

(L6)

The last of the logical constraints, C_Log3, formalized using (L7, L8, L9) determines the situation when, if the given course b is taught by teacher a1, it cannot be, even partially, taught by teacher a2. This, of course, does not prevent this course from being taught jointly by teacher a1 and another one (apart from a2).

$$ \begin{aligned} {\text{X}}_{\text{b,a1}} \ge {\text{A}} \cdot {\text{F}}_{\text{b,a1}} \ge {\text{X}}_{\text{b,a1}} \hfill \\ {\text{X}}_{\text{b,a2}} \ge {\text{A}} \cdot {\text{F}}_{\text{b,a2}} \ge {\text{X}}_{\text{b,a2}} \hfill \\ \end{aligned} $$

(L7)

$$ {\text{F}}_{\text{b,a1}} + {\text{F}}_{\text{b,a2}} \le 1 $$

(L8)

$$ {\text{F}}_{\text{b,a1}} \in \{ 0,1\} ;{\text{F}}_{\text{b,a2}} \in \{ 0,1\} $$

(L9)

The presented sample logical constraints result from situations existing in practice. They result from local, organizational and personal conditions. Of course, many more logical constraints may be introduced in a similar way, which will affect ATCCP.

4 Data-Driven Approach to Modeling and Solving ATCCP

Due to the great computational complexity of ATCCP (NP-complete) the author’s proprietary data-driven approach has been proposed for its implementation, which is a significant extension and generalization of the hybrid approach [8].

The idea of the hybrid approach consisted in the transformation of individual constraints and objective functions and was applied directly to a given model. Each new modeled problem required the development of a new dedicated method of transformation, which involved, among others, the need to modify predicates, facts, etc. The proposed data-driven approach is based on the generalized reduction algorithm and the data instances of the modeled problem. It is universal and can be used for any problem, regardless of its constraints, objective functions, etc.

The general scheme of the proposed data-driven approach has been presented in Fig. 3.

Fig. 3.

Proposed data-driven approach concept

It is based on problem data representation as facts [8, 9]. The structure of the data facts for ATCCP is shown in Fig. 4. The key element in the proposed approach is the reduction algorithm which transforms MILP model into MILP^R model. In simplified terms, this algorithm operates as follows. For each constraint, the model finds such data facts the attributes of which are a sub-set of the constraint attributes (parameters). If a row does not exist for the values of these attributes in the given data fact, this constraint is removed from the model. By analogy, the algorithm removes those variables from the constraints for which the parameter/coefficient values at the variables do not exist in the respective data facts. In other words, the algorithm, on the basis of a set of facts and MILP model, generates a new MILP^R model with a reduced number of constraints and decision variables. MILP^R model is solved by any MP-solver [10].

Fig. 4.

Structure of the scheme and relations between facts for ATCCP.

5 Computational Experiments and Results

The paper presents the problem concerning academic teacher’ competences configuration. A formal model with logical constraints has been proposed for this problem (A1..A10, L1..L9). The proposed model has been implemented using approaches based on mathematical programming (MILP model) and data-driven (MILP^R model) using data facts from Appendix B.

Computational experiments were carried out for both approaches for selected organizational units (chair, department, and faculty). Examples P1..P7 refer to the model with no logic constraints (A1..A10), while examples P1a..P7a to the logical constraint model (A1..A10, L1..L9). The solution of the two models provides information on the minimum number of the missing competences for particular academic teachers (U_b,a). In addition, we obtain the initial allocation (X_b,a) of the teachers to the classes which meets the constraints related to the teaching load for different academic teachers as well logical constraints. ATCCP solution significantly simplifies and accelerates UCTP solving by initial elimination of many allocations and determination of values for some decision variables. It is also useful for the university’s personnel-accounting services responsible for settlement of employees’ teaching loads. Analyzing the problem of computational outlays for solving ATCCP, it is clearly noticeable that the application of data-driven approach (Table 1) has shortened the calculation time by a tier for the model with no logical constraints and by two tiers for the model with logical constraints as compared to the application of MP-solver. For all experiments we used LINGO MP-solver [11] and a PC Intel core (TM2), 2.4 GHz, 4 GB RAM.

Table 1. Computational results for numerical examples

Table A1. Description of the constraints of the model for ATCCP

Table A2. The decision variables, indices and constraints of the model for ATCCP.

6 Conclusions

The paper presents a modified version of an ATCCP that takes into account logical constraints. The modified (data-driven) solving method has also been proposed, which is the development and generalization of the original hybrid approach [8]. With the proposed data-driven approach, it is possible to solve larger size problems in a shorter (acceptable) time. It is obvious that its application does not decrease computational complexity of the problem but reduces the model dimensions enough to keep it sufficient in practical applications. The ATCCP solution allows for optimal management of teachers’ competences and finding preliminary assignments of teachers to courses. What’s more, knowledge of these assignments will simplify the UTCP solution.

As part of further research is planned on modeling and solving UCTP integrated with the ATCCP model (Sect. 3, Appendix A). It is also planned to adapt this model to problems related to competences configuration from the production, logistics, vehicle routing problems and supply chain areas [12,13,14,15,16].

Appendices

Appendix A

$$ {\text{Fc}} = { \hbox{min} }\sum\limits_{{{\text{b}} \in {\text{C}}}} {\sum\limits_{{{\text{a}} \in {\text{T}}}} {{\text{U}}_{\text{b,a}} } } $$

(A1)

$$ {\text{X}}_{\text{b,a}} \le ({\text{Z}}_{\text{b,a}} + {\text{U}}_{\text{b,a}} ) \cdot {\text{ST}}\forall {\text{b}} \in {\text{C}},{\text{a}} \in {\text{T}} $$

(A2)

$$ \sum\limits_{{{\text{b}} \in {\text{C}}}} {{\text{X}}_{\text{b,a}} } = {\text{G}}_{\text{b}} \forall {\text{b}} \in {\text{C}} $$

(A3)

$$ \sum\limits_{{{\text{b}} \in {\text{C}}}} {{\text{H}}_{\text{b}} \cdot {\text{X}}_{\text{b,a}} } \ge {\text{F}}_{\text{a}} \forall {\text{a}} \in {\text{T}} $$

(A4)

$$ \begin{aligned} \sum\limits_{{{\text{b}} \in {\text{C}}}} {{\text{H}}_{\text{b}} \cdot {\text{X}}_{\text{b,a}} } \le {\text{WSP}} \cdot {\text{F}}_{\text{a}} \forall {\text{a}} \in {\text{T}}:{\text{W}}_{\text{a}} = 0 \hfill \\ \sum\limits_{{{\text{b}} \in {\text{C}}}} {{\text{H}}_{\text{b}} \cdot {\text{X}}_{\text{b,a}} } \le {\text{O}} \cdot {\text{F}}_{\text{a}} \forall {\text{a}} \in {\text{T}}:{\text{W}}_{\text{a}} = 1 \hfill \\ \end{aligned} $$

(A5)

$$ \sum\limits_{{{\text{b}} \in {\text{C}}}} {\sum\limits_{{a \in \text{T}}} {{\text{U}}_{\text{b,a}} } } \le {\text{L}} $$

(A6)

$$ {\text{U}}_{\text{b,a}} \le {\text{M}}_{\text{b,a}} \forall {\text{b}} \in {\text{C}},{\text{a}} \in {\text{T}} $$

(A7)

$$ {\text{U}}_{\text{b,a}} = 0\forall {\text{b}} \in {\text{C}},{\text{a}} \in {\text{T}}:{\text{Z}}_{\text{b,a}} = 0 $$

(A8)

$$ {\text{X}}_{\text{b,a}} \in {\text{C}}^{ + } \forall {\text{b}} \in {\text{C}},{\text{a}} \in {\text{T}} $$

(A9)

$$ {\text{U}}_{\text{b,a}} \in \{ 0,1\} \forall {\text{b}} \in {\text{C}},{\text{a}} \in {\text{T}} $$

(A10)

Appendix B Data for Examples P1 and P1a