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