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.