Advances in Mathematical
Sciences and Applications
Vol. 26, No.1 (2017), pp. 109–118

GAKKOTOSHOTOKYO JAPANTHE CLASS/TEACHER ASSIGNMENT PROBLEM:A CASE STUDY IN A BRAZILIAN UNIVERSITY

Robinson S. V. Hoto
Mathematics Department
State University of Londrina - Brazil(E-mail: hoto@uel.br)andGlaucia M. Bressan
Mathematics Department
Federal University of Technology of Parana - Brazil(E-mail: glauciabressan@utfpr.edu.br)

Abstract.
In this work, a mathematical model to assign classes to professors is
proposed, aiming at a maximization of a convex function depending on their preferences
and skills. The mathematical model consists of an integer binary linear program, whose
objective allows for both satisfaction and productivity optimizations, which is considereda more rational use of their skills. The method applied was a case study exploratory
research. The data used to assess the goodness of the mathematical model were collectedon the Mathematics Department to which the first author are affiliated.

Communicated by Editors; Received May 12, 2017.
This work is supported by CNPq (National Council for Scientific and Technological Development) andFICO optimization (industry).
AMS Subject Classification: 65C99, 65K05, 90B35, 90C10,90C27.
Keywords: Timetabling, Application, Integer programming, Simulation.

109

110

1

Introduction

University timetabling represents a difficult optimization problem and finding a highquality timetable is a challenging task. With a large number of events involved andvarious hard constraints to be considered, finding an optimal timetable is time consuming[1]. According to [14], timetabling problems are a specific type of scheduling problem andare mainly concerned with the assignment of events to timeslots subject to constraints
with the resultant solution constituting a timetable.
The courses given at undergraduate level in Brazilian universities are mostly designed
for one semester or one academic year periods. The subjects to be offered are associatedwith a timetable and group of professors, usually in a complex way. In this paper, westart from the assumption that the timetabling is given, and we set a integer binary
linear program to make the distributions of subjects to each of the professors, according
to their skills and availabilities. The contracts weekly hours also vary, ranging from 8
to 16 hours in classes. The problem may be stated as follows: how to perform the
distribution efficiently, meeting the team expectations?
Some working hypotheses will be designed. First of all, every subject must be assigned
to at least one professor, but, in some cases, a subject may be assigned to up to threeprofessors.
It is also common that some professors are lecturing in more than one institution,
therefore needing some time to commute form one place to another. Further, some professors make requirements not to be assigned to certain times due to other pre-scheduled
appointments.
Some professors may have prerogatives over subjects and timetable, as well as there
are preferences among courses. Professors preferences may be also associated with a classsize and shifts (usually the night shift has less preference).
Some departments give privileges to more experienced professors, with active researchor with higher degrees, but an egalitarian approach can also be followed.
When considered altogether, or partly, these conditions lead, more frequently thannot, to some gaps in the timetable assignment. We propose to attack this problem fromthe Operations Research perspective.
We shall use as case study the Maths Department of the State University of Londrina(Universidade Estadual de Londrina – UEL – PR – Brazil), which has a fairly complex
assignment problem. Presently, the department has to serve around 10 undergraduate and5 graduate courses. About 10 of its 40 professors are temporary, mostly having other duties
besides the contract with the University. The model we devise seek to encompass on topof that some restrictions in abilities to lecture very specific subjects. This present study
was motivated by real experimented situations on this cited Mathematics Department,
since professors have preferences to develop a specific activity or subject, but they do nothave the required skill for that. From these detected situations, the idea is to propose amathematical model that consider not only to maximize the professors satisfaction, butalso their skills. Thus, this model must be able to harmonize satisfaction and efficiencyof the team, by considering the skills of the professors. In this sense, the contribution ofthis paper is to propose an alternative model which is able to consider the satisfaction of
professors and to assign tasks so that the team be more efficient.

111
Briefly, the mathematical model is based on a integer linear program, adjusting someparameters according to the conditions we described. We simulated various assignment
scenarios which may be applied in our case study and adapted to others.
In Section 2 we present a brief review of the literature on the subject. In Section 3,
we state the mathematical model and explain its parameters. In Section 4 we describe
graphical results of the simulations and end up with our conclusions in Section 5.

2

Literature review

There are several approaches in the assignment problem, concerning the various aspects,
as professor, class and rooms. In recent years, interest in meta-heuristic approaches suchas Simulated Annealing, Tabu Search and Genetic Algorithms, for university timetabling,has increased since these approaches generate better solutions than those generated fromsequential heuristics alone. We briefly review some of these approaches.
Colorni, Dorigo and Maniezzo [5] uses the technique of Simulated Annealing, with
Tabu Search and Genetic Algorithms, in the assignment of teachers in Italian schools,
concluding that the first technique had the worst performance. The authors compared
the simulated results with made manually assignments. Cowling et. al. [6] also investigated a genetic algorithm based hyperheuristic (hyper-GA) for scheduling geographically
distributed training staff and courses. The aim of the hyper-GA was to evolve a goodquality heuristic for each given instance of the problem and use this to find a solution by
applying a suitable ordering from a set of low-level heuristics.
Carter and Laporte [4] have developed a computerized examination timetabling system called examine. Several algorithmic strategies for this problem are investigated andcompared. Results are reported on some real problems. Considering the examination timetabling problem, Nuitjen et al. [11] applied a general constraint satisfaction techniqueto this problem at the Eindhoven University of Technology.
An approach to the student-scheduling problem is presented by [7]. Students satisfaction with regard to individually specified preferences for various aspects of the schedulingare used as the objective which yields a multi-criteria decision problem. The resulting
mixed-integer programme is then modeled.
Kingston [9] built an object oriented software, based on the internet, known as KTS.
The author developed it working with Australian teaching data and claimed his software
is very efficient.
About applying hybrid approaches, White and Zhang [12] aim that the sequential use
of a constraint logic program whose output was used to start the Tabu Search produced
the best timetables of all in a time that was much longer than that of the logic program
alone but shorter than that of the Tabu Search used alone. Merlot et al. [10] implemented
a hybrid algorithm for examination timetabling, consisting of three phases: a constraint
programming phase to develop an initial solution, a simulated annealing phase to improve
the quality of solution, and a hill climbing phase for further improvement. The hybrid
method was compared to established methods on the publicly available data sets, andfound to perform well in comparison.
Burke et al. [3] present an investigation of a simple generic hyper-heuristic appro-112
ach upon a set of widely used graph coloring heuristics in timetabling. A Tabu Search
approach is employed to search for permutations of graph heuristics which are used forconstructing timetables in exam and course timetabling problems. The approach represents a significantly more generally applicable approach than the current literature.
Avella et al. [2] proposed a two phase method. Firstly the use Simulated Annealing,
and on the second phase, they made a local search, using random descent. The authors
based their work on the method of Very Large-Scale Neighborhood to solve timetableproblem.
The research [1] aims to build upon the state of the art in search methodologies foruniversity timetabling. It focuses on both examination and course timetabling problems.
The research first highlights an initial investigation into a very large scale neighbourhood
search for examination timetabling problem. Computational results based on standard
university benchmark instances are reported to demonstrate the effectiveness of the approaches studied.
Wilke and Ostler [13] used Branch-and-Bound method, Tabu Search, Simulated Annealing and Genetic Algorithm, reporting that the best solutions were obtained with Tabu
Search.
Irene, Deris and Hashim [8] combined Particle Swarm Optimization (PSO) with local
search techniques to solve the timetable problem. The authors compared the performanceof PSO solution with their combined method, concluding that the combined approachprovides better solutions.
The extensive diversity of approaches to the timetable problem stands for its relevanceand current interest. We will next show our proposed formulation of a binary linear
program model for the timetable problem designed from actual offered courses data of
the Mathematics Department at University of Londrina.

3

Proposed Mathematical Model

3.1

Description of the DMAT/UEL Scenario

In DMAT/UEL there are 40 professors and about 130 subjects to be assigned whoseschedules are pre-defined. Consequently, some auxiliary sets are considered, identified as
I, J, T and K. The first one, I = {1, 2, · · · , m}, represents professors, the second one,J = {1, 2, · · · , n}, represents subjects. The third set, T = {1, 2, · · · , 150}, identifies thelesson times and differentiates the semesters, where each lesson time of each semester isnamed period (15 periods distributed in 5 week days; each day is divided in first andsecond semester). Finally, the set K = {1, 2, · · · , 16} is applied to organize the subjects
in categories by syllabus affinities.
The highest weekly workload for classes’ distribution, in each semester of each professor, is obtained after administrative charges, undergraduate advising charges (like traineeships, scientific initiation and final paper) and graduate charges (classes and advising)are considered. After that, it is checked if there is space to assign undergraduate classes
according to the contract of each professor (20 or 40 hours per week), so that a group of
professors whose contracts have already exceeded the workload is discriminated, for whom
no more than 4 hours are assigned. The highest weekly workload for classes’ distribution

113
of other professors is calculated proportionally, so that the final spreadsheet of each professor is extrapolated equally. Mathematically, these pieces of information are organizedin cmaxis which is the highest weekly workload of each professor, i ∈ I, in the first or in
the second semester (s = 1 or s = 2). The professors also inform their available schedule,
in which dit = 1 if teacher i ∈ I is available in period t ∈ T and dit = 0 otherwise.
Each professor has to fill a spreadsheet indicating their preferences and skills in the 16
categories of subjects. Preferences (pij , i ∈ I and j ∈ J) and skills (hij , j ∈ J and j ∈ J)
vary among: none (weight 0), low (weight 1), medium (weight 2) and high (weight 3).
In addition to the above information, the schedule of subjects under DMAT/ UEL’s
responsibility is known, mathematically represented by cjt = 1 if the subject j ∈ J is
located in period t ∈ T and, cjt = 0 otherwise. Furthermore, gjk = 1 if subject j ∈ Jbelongs to category k ∈ K and gjk = 0 otherwise. Finally, aj represents the forecast of
the number of students in subject j ∈ J.

3.2

Mathematical Model

The proposed model to perform the professor/subject assignment is a binary linear mathematical model, which intends to maximize preferences and skills of DMAT/UEL professors.
Since the final decision must answer which professor will perform which subject, adecision variable must represents the professor/subject assignment, that is, xij = 1 if professor i ∈ I is assigned to subject j ∈ J and xij = 0 otherwise. Another required decisionvariable consists of defining which professors will perform in which subject categories,that is, yik = 1 if professor i ∈ I has received a subject from category k ∈ K, and yik = 0
otherwise.
Considering these conditions, the proposed mathematical model is described as follows.
Maximizez=XX(λhij + (1 − λ)pij )xij ,i∈I j∈J(1)

114
subject to:(dit − cjt )xij ≥ 0, i ∈ I, j ∈ J, and t ∈ TXaj xij ≤ amax , i ∈ I

(2)
(3)

j∈J

XX

cjt xij ≤ cmaxis , i ∈ I and s ∈ {1, 2}(4)i∈I t∈TX

pij xij ≥ pmin , i ∈ I(5)

hij xij ≥ hmin , i ∈ I(6)xij = 1, j ∈ J(7)xij ≥ 1, i ∈ I(8)cjt xij ≤ 1, i ∈ I and t ∈ T(9)gjk xij ≤ µyik , i ∈ I and k ∈ K(10)yik ≤ ymax , i ∈ I(11)

xij ∈ {0, 1}, i ∈ I, j ∈ J
yik ∈ {0, 1}, i ∈ I, k ∈ K

(12)
(13)

j∈J

X
j∈J

X
i∈I

X
j∈J

X
j∈J

X
j∈J

X
k∈K

The objective function (1) is composed of a convex combination between skills andpreferences, with λ ∈ [0, 1]. It corresponds to maximize the summation of i ∈ I (professor)
and j ∈ J (subject of the category k ∈ K ), where pij assumes the value of the preference
that professor i assign to subject j. The element hij assumes the value of the skill thatprofessor i assign to subject j. The higher the λ value, function (1) maximizes the skillsof the professor; the lower the λ value, function (1) maximizes the preferences of theprofessor.
Inequality (2) guarantees that each professor not be assigned to subjects whose classes
are located in periods in which the professor is not available. Restriction (3) has been
imposed in order to not burden teachers, in relation to correct home works and exams,
limiting with amax the total number of students to be attended per professor. Restriction(4) guarantees that professors have respected their limit of weekly workload. Restrictions(5) and (6) define a minimum level of preference and skill, respectively, for each professor.
The pij element assumes the weight of the interest of the professor i in relation to subject
j. A minimum level of the preference (pmin ) for any professor is given by (5) and aminimum level of their skill (hmin ) is given by (6).
Restriction (7) defines that each subject will be attended by only one teacher. Inequalities (8) and (9) guarantee that each professor will be assigned to at least one subject
and each professor will not be assigned to more than one subject in the same period.

115
Inequalities (10) and (11) limit the number of categories that each professor will perform,
where µ and ymax are pre-defined parameters. Finally, (12) and (13) define the domain
where solutions are searched.

4

Simulations

The mathematical model presented in the Section 3 was solved by using solver XpressMP 7.1 (Xpress-IVE 2.21.02 - Xpress Mosel 3.2.0 - Xpress Optimizer 21.01.00), which has
found a solution to the model in few seconds.
The data used to develop this paper correspond to the reality of the mathematics
department in study and do not present great annual variability. For the tests, the valuesof the model parameters were fitted according to DMAT/UEL necessities. Parameterspmin , hmin and µ were fitted using the value 4; on the other hand, the maximum numberof students amax assigned to each professor was set to 150 and the maximum numberof categories assigned to each professor is ymax = 3. The maximum number of subjects
assigned to each professor is dmax = 4.
These tests were performed to fit the parameter λ which belongs to the objectivefunction, in order to evaluate the most relevant weight to be assigned to preference andskill.
In order to do this evaluation, results obtained from mathematical model of Section
3 were compared with the manually assignment which is performed by leaders of the
DMAT/UEL. In this perform was used a preference index, a skill index and a medium
index in each assignment. The preference individual index of professor i ∈ I is defined byPj∈J pij xij(14)
Ip (i) = P
j∈J 3xij
It should be noted that Ip (i) is the ratio of the sum of the subjects weights assigned toprofessor and the maximum weight if subjects assigned to professor were those of his/her
preference majority. This index is between 0 and 1. Unitary index indicates that classes
assigned to professor are those of his/her preference. The index is null in an extreme
case, in which only classes not chosen by the professor are assigned to him, however, theseclasses fit well in professor schedule. The average provides overall preference satisfaction:
m

1 X
Ip =
Ip (i) .
m i=1
The skill index is defined byPj∈J hij xij
Ih (i) = P
j∈J 3xij
with average
m

1 X
Ih =
Ih (i) .
m i=1

(15)

116
Fig. 1 and Fig. 2 illustrate, respectively, results about preferences and skills in 11
scenarios.

Fig. 1. Professors’ average preference by simulating several values of λ.

Fig. 2. Professors’ average skill by simulating several values of λ.
As expected, average skill is a non-decreasing function of λ but surprisingly mean
attended preferences is not non-increasing, showing a maximum for positive λ, λ = 0.2 inour simulations.
Various approaches are possible to qualify the best solution. First, the maximumof either average preferences or average skills. However, it seems natural to consider thebest product of average preferences and average skills, which occur in the parameter range[0.2, 0.3].
For λ = 0, 0.1, 0.2, 0.3, 0.4 and 0.9, the number of professors whose preferences were
improved was 27. For λ = 0.6, 0.7 and 0.8, the number of professors whose preferenceswere improved was 26. For λ = 0.5, 24 professors had their preferences improved and, for
λ = 1, 16 professors had their preferences improved. In the range in which there was thehighest number of professors’ preferences improvements, notice that λ = 0.9 provides thehighest level of average skill (between 0.96 e 0.97). For λ ∈ [0, 0.4] the level of average skill
is between 0.94 and 0.95. With a view to increasing average preference, for λ ∈ [0.1, 0.3],
it is higher than 0.91, and for λ = 0.9, it is between 0.88 and 0.89.

117
From this information, the most relevant values to the DMAT/UEL are λ ∈ [0.1, 0.3],
where 27 professors had their preferences improved, the average index of professors’ preferences Ip is higher than 0.93 and the average index of professors’ skills Ih is 0.94.

5Concluding Remarks

This work presented a case study of the timetable problem with data from the Mathematics Department at University of Londrina, aiming at the efficiency of the class-professor
assignment and satisfaction of the majority of professors.
The mathematical model was performed with preferences and skills entering the objective function. The simulations conducted indicate that the model fulfill its purposes,
and can be successfully adapted to other scenarios. A parameter conveniently switches
preferences/skills objectives: for λ = 0 the model maximize preferences, whereas for λ = 1
the model maximize skills alone.
Scenarios as the one described in this paper are very difficult to be solved satisfactorily
using only the human experience of a manager, because these situations involve people
satisfaction and, on the other hand, the demand must be answered. In the university, there
are general rules which must be obeyed by employees and which require an ethical posturefrom the manager. In problems like that, the help from Mathematics and Operational
Research makes work easier and difficult tasks more manageable. In this way, the manager
only has to fit a solution that, almost every time, is the most adequate one.
At the moment, the mathematics department, where the research described in this paper has been conducted, has enjoyed the simulations described in Section 4 as a support
in decision making in relation to the workloads distributions. Since the results obtained
and presented here are promising, the department has required the development of a prototype based on java to be available in an online management platform. For that purpose,
we are developing a heuristic procedure that will be able to solve the mathematical model
presented in this paper. For future papers, we propose an improvement in the objectivefunction so that the excessive workload be equally distributed among professors.

References[1] Abdullah, S.: HEURISTIC APPROACHES FOR UNIVERSITY TIMETABLING
PROBLEMS. PhD Thesis University of Nottingham Malaysia (2006)[2] Avella, P., D’Auria, B., Salerno, S., Vasil’ev, I.: A computational study of local
search algorithms for italian high-school timetabling. Journal Heuristics 13(6), 543–
556 (2007). DOI 10.1007/s10732-007-9025-3[3] Burke, E.K., McCollumb, B., Meiselsc, A., Petrovica, S., Qu, R.: A graph - based
hyper-heuristic for educational timetabling problems. European Journal of Operational Research 176(1), 177–192 (2007). DOI 10.1016/j.ejor.2005.08.012

118[4] Carter, M.W., Laporte, G., Lee., S.: Examination timetabling: Algorithmic strategies and applications. Journal of the Operational Research Society 47(3), 373–383(1996)[5] Colorni, A., Dorigo, M., Maniezzo, V.: Metaheuristics for high school timetabling.
Computational Optimization and Applications 9, 275–298 (1998)[6] Cowling, P., Kendall, G., Han, L.:
An investigation of a hyperheuristic genetic algorithm applied to a trainer scheduling problem.
http://www.cs.nott.ac.uk/ gxk/papers/cec2002lxh.pdf (2002)[7] Heitmann, H., Bruggemann, W.: Preference-based assignment of university students
to multiple teaching groups. OR Spectrum 36(3), 607–629 (2014)[8] Irene, S., Deris, S., Hashim, S.: A combination of pso and local search in university
course tmetabling problem. Proceedings of International Conference on Computer
Engineering and Technology (2009)[9] Kingston, J.: The KTS high school timetabling system. International Conference on
the Practice and Theory of Automated Timetabling, PATAT (2006)[10] Merlot, L.T.G., Boland, N., Hughes, B.D., Stuckey, P.J.: A hybrid algorithm for theexamination timetabling problem. The Practice and Theory of Automated Timetabling IV: Selected Papers from 4th International Conference on the Practice andTheory of Automated Timetabling (PATAT IV) pp. 207–231 (2003)[11] Nuitjen, W.P.M., Kunnen, G.M., Aarts, E.L.H., Dignum, F.P.M.: Examination timetabling: A case study for constraint satisfaction. The Proceedings of the ECAI
Workshop on Constraint Satisfaction Issues Raised by Practical Applications pp.
11–19 (1994)[12] White, G.M., Zhang, J.: Generating complete university timetables by combining
tabu search with constraint logic. The Practice and Theory of Automated Timetabling II: Selected Papers from 2nd International Conference on the Practice andTheory of Automated Timetabling (PATAT II) pp. 187–198 (1998)[13] Wilke, P., Ostler, J.: Solving the school timetabling problem using tabu search, simulated annealing, genetic and branch and bound algorithms. International Conference
on the Practice and Theory of Automated Timetabling, PATAT (2008)[14] Wren, A.: Scheduling, timetabling and rostering: A special relationship? The Practice and Theory of Automated Timetabling I: Selected Papers from 1st International
Conference on the Practice and Theory of Automated Timetabling (PATAT I) pp.
46–75 (1996)