001 package net.sf.cpsolver.coursett.constraint;
002
003 import net.sf.cpsolver.ifs.util.DataProperties;
004
005
006 /**
007 * Departmental ballancing constraint.
008 * <br><br>
009 * The new implementation of the balancing times for departments works as follows: Initially, there is a histogram for
010 * each department computed. For each time slot, it says how many placements of all classes (of the department) include
011 * this time slot. Each such placement has the weight of 1 / number of placements of the class, so the total sum of all
012 * values in the histogram (i.e., for all time slots) is equal to the total sum of half-hours required by the given set
013 * of classes.
014 * <br><br>
015 * On the other hand, each class splits its number of half-hours (e.g., 2x50 has 4 half-hours, "4 points") into the
016 * time slots which it can occupy, according to the frequencies of the utilization of each time slots (i.e., number of
017 * placements containing the time slots divided by the number of all placements of the class).
018 * <br><br>
019 * For example, a histogram for department 1286:<code><br>
020 * 1: [0.10,0.00,0.10,0.00,0.10] <- 7:30 [Mon, Tue, Wed, Thu, Fri]<br>
021 * 2: [0.10,0.00,0.10,0.00,0.10] <- 8:00 [Mon, Tue, Wed, Thu, Fri]<br>
022 * 3: [0.35,0.62,0.48,0.62,0.10] ... and so on<br>
023 * 4: [0.35,0.62,0.48,0.62,0.10]<br>
024 * 5: [1.35,1.12,1.48,0.12,1.10]<br>
025 * 6: [1.35,1.12,1.48,0.12,1.10]<br>
026 * 7: [0.35,0.62,0.48,1.63,0.10]<br>
027 * 8: [0.35,0.62,0.48,1.63,0.10]<br>
028 * 9: [0.35,0.12,0.48,0.12,0.10]<br>
029 * 10:[0.35,0.12,0.48,0.12,0.10]<br>
030 * 11:[0.35,0.12,0.48,0.12,0.10]<br>
031 * 12:[0.35,0.12,0.48,0.12,0.10]<br>
032 * 13:[0.35,0.12,0.48,1.12,0.10]<br>
033 * 14:[0.35,0.12,0.48,1.12,0.10]<br>
034 * 15:[0.35,0.12,0.48,0.12,0.10]<br>
035 * 16:[0.35,0.12,0.48,0.12,0.10]<br>
036 * 17:[0.35,0.12,0.48,0.12,0.10]<br>
037 * 18:[0.35,0.12,0.48,0.12,0.10]<br>
038 * 19:[0.10,0.00,0.10,0.00,0.10]<br>
039 * 20:[0.10,0.00,0.10,0.00,0.10]<br>
040 * 21:[0.00,0.00,0.00,0.00,0.00]<br>
041 * </code><br>
042 * You can easily see, that the time slots which are prohibited for all of the classes of the department have zero
043 * values, also some time slots are used much often than the others. Note that there are no preferences involved in
044 * this computation, only prohibited / not used times are less involved.
045 * <br><br>
046 * The idea is to setup the initial limits for each of the time slots according to the above values. The reason for doing
047 * so is to take the requirements (time patterns, required/prohibited times) of all classes of the department into
048 * account. For instance, take two classes A and B of type MWF 2x100 with two available locations starting from 7:30
049 * 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
050 * 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.
051 * From the balancing point of the view, I believe it should be preferred to have one class starting from 7:30 and the
052 * other one from 8:30.
053 * <br><br>
054 * So, after the histogram is computed, its values are increased by the given percentage (same reason as before, to
055 * allow some space between the actual value and the limit, also not to make the limits for a department with 21 time
056 * slots less strict than a department with 20 time slots etc.). The initial limits are than computed as these values
057 * rounded upwards (1.90 results in 2).
058 * <br><br>
059 * Moreover, the value is increased only when the histogram value of a time slot is below the following value:
060 * spread factor * (number of used time slots / number of all time slots). Is assures a department of at least the
061 * given percentage more time slots than required, but does not provide an additional reward for above average
062 * use of time slots based on 'required' times.
063 * <br><br>
064 * For example, the department 1286 will have the following limits (histogram increased by 20% (i.e., each value is 20%
065 * higher) and rounded upwards):
066 * <code><br>
067 * 1: [1,0,1,0,1]<br>
068 * 2: [1,0,1,0,1]<br>
069 * 3: [1,1,1,1,1]<br>
070 * 4: [1,1,1,1,1]<br>
071 * 5: [2,2,2,1,2]<br>
072 * 6: [2,2,2,1,2]<br>
073 * 7: [1,1,1,2,1]<br>
074 * 8: [1,1,1,2,1]<br>
075 * 9: [1,1,1,1,1]<br>
076 * 10:[1,1,1,1,1]<br>
077 * 11:[1,1,1,1,1]<br>
078 * 12:[1,1,1,1,1]<br>
079 * 13:[1,1,1,2,1]<br>
080 * 14:[1,1,1,2,1]<br>
081 * 15:[1,1,1,1,1]<br>
082 * 16:[1,1,1,1,1]<br>
083 * 17:[1,1,1,1,1]<br>
084 * 18:[1,1,1,1,1]<br>
085 * 19:[1,0,1,0,1]<br>
086 * 20:[1,0,1,0,1]<br>
087 * 21:[0,0,0,0,0]<br>
088 * </code><br>
089 * The maximal penalty (i.e., the maximal number of half-hours which can be used above the pre-computed limits by a
090 * department) of a constraint is used. Initially, the maximal penalty is set to zero. It is increased by one after
091 * each time when the constraint causes the given number (e.g., 100) of un-assignments.
092 * <br><br>
093 * Also, the balancing penalty (the total number of half-hours over the initial limits) is computed and it can be
094 * minimized during the search (soft constraint).
095 * <br><br>
096 * Parameters:
097 * <table border='1'><tr><th>Parameter</th><th>Type</th><th>Comment</th></tr>
098 * <tr><td>DeptBalancing.SpreadFactor</td><td>{@link Double}</td><td>Initial allowance of the slots for a particular time (factor)<br>Allowed slots = ROUND(SpreadFactor * (number of requested slots / number of slots per day))</td></tr>
099 * <tr><td>DeptBalancing.Unassignments2Weaken</td><td>{@link Integer}</td><td>Increase the initial allowance when it causes the given number of unassignments</td></tr>
100 * </table>
101 *
102 * @version
103 * CourseTT 1.1 (University Course Timetabling)<br>
104 * Copyright (C) 2006 Tomáš Müller<br>
105 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
106 * Lazenska 391, 76314 Zlin, Czech Republic<br>
107 * <br>
108 * This library is free software; you can redistribute it and/or
109 * modify it under the terms of the GNU Lesser General Public
110 * License as published by the Free Software Foundation; either
111 * version 2.1 of the License, or (at your option) any later version.
112 * <br><br>
113 * This library is distributed in the hope that it will be useful,
114 * but WITHOUT ANY WARRANTY; without even the implied warranty of
115 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
116 * Lesser General Public License for more details.
117 * <br><br>
118 * You should have received a copy of the GNU Lesser General Public
119 * License along with this library; if not, write to the Free Software
120 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
121 */
122
123 public class DepartmentSpreadConstraint extends SpreadConstraint {
124 private Long iDepartment = null;
125
126 public DepartmentSpreadConstraint(DataProperties config, Long department, String name) {
127 super( name,
128 config.getPropertyDouble("DeptBalancing.SpreadFactor",1.20),
129 config.getPropertyInt("DeptBalancing.Unassignments2Weaken", 250),
130 config.getPropertyBoolean("General.InteractiveMode", false)
131 );
132 iDepartment = department;
133 }
134
135
136 public Long getDepartmentId() { return iDepartment; }
137
138 public String toString() {
139 return "Departmental Balancing for "+getName();
140 }
141 }