Iterative optimization techniques using man–machine interaction for university timetabling problems

In this section, we show the numerical experiments with the actual data to examine
the performance of the proposed method. We used the timetabling data of Toyama Prefectural
University from the second semester of 2013 to the second semester of 2014. Here,
the decision of the classroom selection were excluded in this experiments in order
to reduce the model size described in “Mathematical programming models and makeup
class timetabling problem”. One staff of the educational affairs section in Toyama
Prefectural University scheduled a timetable by using our proposed method.

Problem specification

The problem specification we used is summarized as follows:

The second semester of 2013 (we call SS2013)

Number of students: 994,

Number of slots arranged for makeup classes: 34,

Number of classes requested by the lecturers: 257.

The first semester of 2014 (FS2014)

Number of students: 997,

Number of slots arranged for makeup classes: 36,

Number of classes requested by the lecturers: 280.

The second semester of 2014 (SS2014)

Number of students: 997,

Number of slots arranged for makeup classes: 34,

Number of classes requested by the lecturers: 257.

We used IBM ILOG CPLEX12 (IBM Corp 2011]) on a Core i5 (1.8GHz) computer for solving the integer programming model described
in “Mathematical programming models and
makeup class timetabling problem”. The branch-and-bound techniques are employed in
it. The scheduling staff was instructed that it is allowed to terminate the optimization
procedure by the computer after a dual gap, which is the difference between upper
and lower bounds of the objective values, is less than 1%. The values of the upper
and lower bounds can be found in the course of applying IBM ILOG CPLEX12. Figure 3 shows a screen shot of the implemented system.

Figure 3. A screen shot of the implemented system.

Results

The model specification and the scheduling results are summarized as follows:

SS2013

Number of variables: 41,472

Number of constraints: 45,259

Number of classes not operated in the period for the makeup classes: 8

Computational time (for each optimization by a computer): 1,088–5,384 s

Duplication of classes for the students [which is equal to in Eq. (9)]: 12

Number of feedback loops for generation and evaluation of the timetables : 240

FS2014

Number of variables: 50,288

Number of constraints: 53,782

Number of classes not operated in the period for the makeup classes: 4

Computational time (for each optimization by a computer): 0.03–6,064 s

Duplication of classes for the students [which is equal to in Eq. (9)]: 10

Number of feedback loops for generation and evaluation of the timetables : 382

SS2014

Number of variables: 43,153

Number of constraints: 46,876

Number of classes not operated in the period for the makeup classes: 1

Computational time (for each optimization by a computer): 0.00–41,324 s

Duplication of classes for the students: 35

Number of feedback loops for generation and evaluation of the timetables : 134

The results by the conventional scheduling techniques (i.e., hand working) are obtained
as a comparison from the hearing survey to the staff, and they are also summarized
as follows:

The first semester of 2013 (we call FS2013)

Number of students: 994,

Total period of a makeup classes: 6 days

Number of classes requested by the lecturers: 257

Number of classes not operated in the period for the makeup classes: 4

Duplication of classes for the students: 44

Figure 4 summarizes the operation time including both the operation by the staff and the computation
by the computer. Here, the operation time is divided into the time for data input
and for the parameter setting. In our all experiments, the modification of solution
by the operators was never occurred. On the other hand, the priority parameter , and were updated by the operators with referring to in the optimization loop.

Figure 4. Results: operation time (h).

Discussion

We conducted hearing surveys for the staffs after the experiments. We asked open-ended
questions on the workloads and the contents of operation. From the hearing surveys
and the results described in “Results”, the following points are observed:

The physical load for the staff was reduced to about a half of FS2013.

Timetables with a few duplication of classes were acquired in early iterations in
the optimization loop.

The model parameters such as , were modified by the operators in the optimization loop. On the other hand, the modification
step of Figure 1 was not necessary for almost every iteration.

Various timetables could be evaluated and compared by changing the model parameters.

The computational time of the branch-and bound techniques can vary significantly
depending on the model parameters corresponding to the implicit objective functions.

The requests from the lectures are different among the three data sets, and it provided
significant differences on the computation time of the branch-and-bound algorithm.

The staffs could attend some other duties during the optimization process by a computer.

Every acquired schedule was actually conducted in Toyama Prefectural University.