org.cpsolver.coursett.constraint

• All Implemented Interfaces:

Departmental ballancing constraint.

The new implementation of the balancing times for departments works as follows: Initially, there is a histogram for each department computed. For each time slot, it says how many placements of all classes (of the department) include this time slot. Each such placement has the weight of 1 / number of placements of the class, so the total sum of all values in the histogram (i.e., for all time slots) is equal to the total sum of half-hours required by the given set of classes.

On the other hand, each class splits its number of half-hours (e.g., 2x50 has 4 half-hours, "4 points") into the time slots which it can occupy, according to the frequencies of the utilization of each time slots (i.e., number of placements containing the time slots divided by the number of all placements of the class).

For example, a histogram for department 1286:

1: [0.10,0.00,0.10,0.00,0.10] ← 7:30 [Mon, Tue, Wed, Thu, Fri]
2: [0.10,0.00,0.10,0.00,0.10] ← 8:00 [Mon, Tue, Wed, Thu, Fri]
3: [0.35,0.62,0.48,0.62,0.10] ... and so on
4: [0.35,0.62,0.48,0.62,0.10]
5: [1.35,1.12,1.48,0.12,1.10]
6: [1.35,1.12,1.48,0.12,1.10]
7: [0.35,0.62,0.48,1.63,0.10]
8: [0.35,0.62,0.48,1.63,0.10]
9: [0.35,0.12,0.48,0.12,0.10]
10:[0.35,0.12,0.48,0.12,0.10]
11:[0.35,0.12,0.48,0.12,0.10]
12:[0.35,0.12,0.48,0.12,0.10]
13:[0.35,0.12,0.48,1.12,0.10]
14:[0.35,0.12,0.48,1.12,0.10]
15:[0.35,0.12,0.48,0.12,0.10]
16:[0.35,0.12,0.48,0.12,0.10]
17:[0.35,0.12,0.48,0.12,0.10]
18:[0.35,0.12,0.48,0.12,0.10]
19:[0.10,0.00,0.10,0.00,0.10]
20:[0.10,0.00,0.10,0.00,0.10]
21:[0.00,0.00,0.00,0.00,0.00]

You can easily see, that the time slots which are prohibited for all of the classes of the department have zero values, also some time slots are used much often than the others. Note that there are no preferences involved in this computation, only prohibited / not used times are less involved.

The idea is to setup the initial limits for each of the time slots according to the above values. The reason for doing so is to take the requirements (time patterns, required/prohibited times) of all classes of the department into account. For instance, take two classes A and B of type MWF 2x100 with two available locations starting from 7:30 and 8:30. Note that the time slot Monday 8:30-9:00 will be always used by both of the classes and for instance the time slot Monday 7:30-8:00 (or Friday 9:30-10:00) can be used by none of them, only one of them or both of them. From the balancing point of the view, I believe it should be preferred to have one class starting from 7:30 and the other one from 8:30.

So, after the histogram is computed, its values are increased by the given percentage (same reason as before, to allow some space between the actual value and the limit, also not to make the limits for a department with 21 time slots less strict than a department with 20 time slots etc.). The initial limits are than computed as these values rounded upwards (1.90 results in 2).

Moreover, the value is increased only when the histogram value of a time slot is below the following value: spread factor * (number of used time slots / number of all time slots). Is assures a department of at least the given percentage more time slots than required, but does not provide an additional reward for above average use of time slots based on 'required' times.

For example, the department 1286 will have the following limits (histogram increased by 20% (i.e., each value is 20% higher) and rounded upwards):

1: [1,0,1,0,1]
2: [1,0,1,0,1]
3: [1,1,1,1,1]
4: [1,1,1,1,1]
5: [2,2,2,1,2]
6: [2,2,2,1,2]
7: [1,1,1,2,1]
8: [1,1,1,2,1]
9: [1,1,1,1,1]
10:[1,1,1,1,1]
11:[1,1,1,1,1]
12:[1,1,1,1,1]
13:[1,1,1,2,1]
14:[1,1,1,2,1]
15:[1,1,1,1,1]
16:[1,1,1,1,1]
17:[1,1,1,1,1]
18:[1,1,1,1,1]
19:[1,0,1,0,1]
20:[1,0,1,0,1]
21:[0,0,0,0,0]

The maximal penalty (i.e., the maximal number of half-hours which can be used above the pre-computed limits by a department) of a constraint is used. Initially, the maximal penalty is set to zero. It is increased by one after each time when the constraint causes the given number (e.g., 100) of un-assignments.

Also, the balancing penalty (the total number of half-hours over the initial limits) is computed and it can be minimized during the search (soft constraint).

Parameters:
Parameter Type Comment
DeptBalancing.SpreadFactor Double Initial allowance of the slots for a particular time (factor)
Allowed slots = ROUND(SpreadFactor * (number of requested slots / number of slots per day))
DeptBalancing.Unassignments2Weaken Integer Increase the initial allowance when it causes the given number of unassignments
Version:
CourseTT 1.3 (University Course Timetabling)
Copyright (C) 2006 - 2014 Tomáš Müller
muller@unitime.org
http://muller.unitime.org

This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library; if not see http://www.gnu.org/licenses/.