We consider an academic load distribution problem (ALD) in which training courses consist of separate units. Each of the units can be assigned just to one teacher. The minimum and maximum possible amounts of an academic load are set for each teacher. Integer linear programming (ILP) models for various formulations of this problem are proposed. One model takes into account interpersonal relationships when appointing teachers to one discipline. It is shown that nding a feasible solution of the ALD problem is NP-complete. In this paper, the research of the bicriteria ILP model of the ALD problem is continued. It is established that the cardinality of a complete set of alternatives for this problem is polynomial. An auxiliary problem is proposed to nd a feasible solution to the problem under study. A computational experiment with ILP models on random instances and on a real data instance is carried out.
Many problems taking place in the sphere of education are successfully solved by discrete optimization models and methods. They are the problems of scheduling [1], tests generation of academic performance rating [11], etc. Academic load distribution (ALD) for teachers is an important stage of the qualitative training process organization. It is di cult to formalize this problem. It becomes actual in a big and various department sta , quite a number of the courses, including the presence of the load in several groups or at several faculties, in the case of Copyright c by the paper's authors. Copying permitted for private and academic purposes. In: S. Belim et al. (eds.): OPTA-SCL 2018, Omsk, Russia, published at http://ceur-ws.org the changeable loading, when there are special requirements for the academic load distribution at a higher school. In particular, the works [3, 8] concentrate on the construction of mathematical models for the ALD problem.
The ALD problem, in which the average number of the training courses assigned to each teacher is minimized, is considered in [3]. The mathematical model o ered in the given work represents a special case of the transportation problem with the xed surcharges. The work shows that the mentioned problem is NP-hard, represents the equivalent combinatory formulation of this problem and o ers the branch-and-bound algorithm for its solving. However, in this case, it is not considered that each training course splits into the indivisible units corresponding to various kinds of the academic load, for example, lectures, seminars, laboratory works, tests, examinations, etc. As a result of the application of the model from [3], there may be obtained a solution wherein a unit of a training course is distributed among several teachers. It contradicts the existing practice at Russian higher schools.
The bicriteria formulation of the ALD problem in which the training courses consist of particular units each of which can be distributed just to one teacher is considered in [9]. The minimum and maximum possible amounts of academic load are preassigned for every teacher. In [9], ILP models for some formulations of this problem were proposed. The L-class enumeration algorithm [5, 10] which enables to solve problems of small dimension was suggested for one model.
In this article, we continue the study of the bicriteria model. According to it, one optimization criterion is to minimize the maximum number of courses assigned to teachers, and the other criterion is to maximize the total preferences of the "teacher{course" relations. In addition, a variant of the problem, considering interpersonal relations in the assignment of teachers to the same training course, is regarded. We show that the cardinality of the complete set of alternatives for this problem is polynomial.
We should note that in contrast to the problem from [3] nding a feasible solution of the investigated ALD problem is NP-complete. We construct an auxiliary ILP problem which can be used to organize the process of nding a solution to the investigated problem. Computational results obtained for random generated instances and for the real data of one department of Omsk State Technical University is described. 2
Formulations of Academic Load Distribution Problem and Mathematical Models Let I = f1; :::; mg be a set of teachers. The values ai, ci denote the maximum and minimum possible amounts of load speci ed for each teacher i, i 2 I. Normally ci di ers from ai by no more than 5%. Let J = f1; :::; ng be a set of training courses and let tj be a number of individual units of the course j. Denote a number of k hours for the k-th unit of the course j by bj , where k 2 Kj = f1; :::; tj g.
We denote by likj preference coe cients of the unit k of the course j by the teacher i for all i, j, k. Also, these values can be interpreted as the coe cients of e ciency under this assignment.
Let sj be a maximum number of units of one training course that are assigned to one teacher (sj tj ). We should note that if the values sj is not limited, it may lead to distributions in which the teachers have a narrow specialization.
It is necessary to distribute the training courses among the teachers "uniformly" in the number of courses taking into account their preferences. The condition of "uniformity" can be accounted for in di erent ways. Now we describe a mathematical model of the problem at issue when ai take the same value for all i.
We introduce Boolean variables xij and zikj , where i 2 I; j 2 J; k 2 Kj . Here xij = 1 if the teacher i gives the course j and xij = 0, otherwise; zikj = 1, if the teacher i gives the k-th unit of the course j and zikj = 0, otherwise. Let y be a non-negative integer variable.
Denote the vector of variables zikj by z. The ALD problem can be formulated
as a bicriteria ILP problem in this way:
(
ci xij minimize y
m n tj maximize L(z) = X X X likj zikj
i=1 j=1 k=1
Further we will call the problem (
In the problem M 1 the optimization criterion (
It is easy to see that nding a feasible solution to the model M 1 is NPcomplete. This follows from the fact that a well-known NP-complete bin packing problem [2] can be reduced to the mentioned problem. Here m is the number of containers with the volumes ai and Pj2J tj is the number of items with the volumes bikj which must be packed.
Consider the case when ai take di erent values. Let us denote amax =
maxi2I ai and let y be the number of courses assigned to the teacher with the
amount of the load amax. Then we o er to model the condition of "uniformity"
on the number of courses in the following way. The number of courses assigned
to the teacher i should not exceed the value which is proportional to y with
the factor pi = ai=amax. Then the conditions (
piy + q; i 2 I; where q 2 [0; 1] is a constant that controls the rounding of the values on the right side, for example, q = 0:5.
Now we will describe another variant of ALD problem. Let the maximum number of the courses ri assigned to the teacher i are given, i 2 I. The requirement of the diversity "uniformity" to the number of assigned courses can be also set explicitly n X xij j=1
ri; i 2 I:
Consider the problem M 2 which is obtained from the base model by adding
constraints taking into account interpersonal relationships among the teachers.
Let T = f(i1; i2) j i1; i2 2 Ig be the set that contains index pairs of teachers
who are undesirable to be assigned to one course for any reason because these
teachers have inconsistent relations [6]. Let us add appropriate restrictions
xi1;j + xi2;j
1; (i1; i2) 2 T; j 2 J:
(
Solving ALD Problem and Computational Experiment
Consider the bicriteria discrete optimization problem
minimize F (x) = (f1(x); f2(x))
(
x 2 X; where X is some nite set.
There are several approaches to solve this problem. One approach is nding all Pareto-optimal solutions or a part of this solutions. We denote the set of Pareto-optimal solutions by X~ , and a complete set of alternatives (CSA) by X0 (see, for example, [4, 7]). Let X be the set of feasible solutions of the problem. CSA is any set X0 (X0 X~ ) which has the minimal cardinality and F (X0) = F (X~ ), where F (X0) = fF (x) j x 2 X0g; X0 X. It is obvious that X0 ~ X
X:
We note that the cardinality of a complete set of alternatives for the constructed problems M 1 and M 2 is polynomial because the value of the second criterion does not exceed n.
To search for CSA, you can solve a series of the single-criterion problem
(
We introduce a non-negative variable v which can be interpreted as the maximum excess of values of ai, i 2 I, for some distribution of the units of the courses. Let us consider an auxiliary problem subject to
minimize v
and conditions (
If a feasible solution of the ALD problem exists, then the optimal value of the objective function of the auxiliary problem is equal to zero. We introduce additional restrictions y Y and L L and solve the auxiliary problem, where Y and L are some given values. Changing the values of Y and L, one can obtain a series of feasible solutions of the ALD problem or unfeasible solutions in which there is a small excess of some or all ai. Such solutions can also be used in practice.
We conducted a computational experiment to investigate the possibility of applying the proposed models.
We present the results of using model M 1 with restrictions (
The total amount of all types of the Department's load is 8571 hours. The number of di erent types of load including training courses is 103. The number of teachers equals 13. The total upper load is equal to 8590 hours.
In the rst stage, the personal load is assigned. This is the leadership of the department, the scienti c supervision of graduate students, undergraduates, etc. As a result in the second stage, it remains to distribute 5591 hours of 88 training courses among 11 teachers. The total number of the courses units equals 229. The number of units for every course is in the range from 1 to 6. The majority of courses (83%) consists of no more than three units. The upper bounds of the load for the teachers are given by the vector a = (557; 560; 601; 741; 591; 560; 625; 658; 360; 360; 68). The preference coe cients likj belong to the set f1; :::; 10g.
For nding Pareto-optimal solutions we construct single-criterion ILP
problem (
We compared our results with the actual load distribution in the department that was obtained without the use of mathematical models. In the actual load distribution, the total excess of the upper bounds of the teachers' load (ai) was 225 hours, and the total underperformance of lower bounds (ci) was 37 hours. Each teacher was assigned from 7 to 18 training courses.
Note that all our solutions satisfy the upper and lower bounds of the load of teachers. More "uniform" distributions on number of disciplines are obtained. For Y = 12 the number of courses for each teacher is proportional to the values of ai and varies from 6 to 12. In the actual distribution the number of courses varies from 7 to 18. In the mentioned solution, the total preference is decreased by 13% compared to the actual distribution. Note that it is not a valid solution for the M 1 problem. Extracurricular preparation of the teachers, i.e., the number of preparations for classes is decreased by 14%.
Brie y, we present the results of a computational experiments for model M 1
under restrictions (
The S2 series consists of tasks of large dimension with m = 22, n = 45, all tj 2 [2; 9], ai 2 [211; 1268] and likj 2 [1; 10]. These tasks are similar to practical tasks. The corresponding ILP model M 1 has 5962 variables and 2139 constraints. The computing time depends on the given values of Y and sj and varies from a few seconds to several hours. There are tasks for which no feasible solution has been found. In this case, we used the auxiliary problem AP. Changing the values of Y and L, we managed to obtain a series of feasible solutions in acceptable time. If a task does not have feasible solutions, then it is possible to obtain a load distribution with an insigni cant excess of the upper bounds ai.
A computational experiments with model M2 which taking into account the interpersonal relations among the teachers showed a signi cant increase of computing time. 4
Conclusion We propose some formulations of the ALD problem including the bicriteria model. It is shown that the cardinality of a complete set of alternatives is polynomial and nding a feasible solution of this problem is NP-hard. Computational experiments was carried out using the CPLEX solver and the GAMS solver for problems with random input data.
One of the constructed mathematical models was successfully applied to solve a practical problem. Distribution of the academic load of the department, depending on its size, usually takes from one to several weeks. The application of the constructed mathematical models signi cantly shortens this time.
The proposed models can be modi ed by additional requirements for load distribution, for example, when assigning no more than one new course to each teacher, uniform load distribution in semesters, etc. To solve problems of large dimension, it is advisable to develop heuristic algorithms.
The mathematical models of the mentioned problem can be used in the decision-making support systems for University management.
Acknowledgement. For the rst author the research was supported by RFBR grant 16-01-00740. For the second author the work was supported by the program of fundamental scienti c researches of the SB RAS { I.1.3., project { 0314-20160009.