001package net.sf.cpsolver.coursett.constraint; 002 003import net.sf.cpsolver.coursett.criteria.DepartmentBalancingPenalty; 004import net.sf.cpsolver.coursett.model.Lecture; 005import net.sf.cpsolver.coursett.model.Placement; 006import net.sf.cpsolver.ifs.criteria.Criterion; 007import 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 Tomáš Müller<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 155public 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}