001 package net.sf.cpsolver.coursett.criteria.additional; 002 003 import java.util.ArrayList; 004 import java.util.BitSet; 005 import java.util.Collection; 006 import java.util.HashMap; 007 import java.util.HashSet; 008 import java.util.List; 009 import java.util.Map; 010 import java.util.Set; 011 import java.util.TreeSet; 012 013 import net.sf.cpsolver.coursett.Constants; 014 import net.sf.cpsolver.coursett.constraint.InstructorConstraint; 015 import net.sf.cpsolver.coursett.model.Lecture; 016 import net.sf.cpsolver.coursett.model.Placement; 017 import net.sf.cpsolver.coursett.model.TimetableModel; 018 import net.sf.cpsolver.ifs.criteria.AbstractCriterion; 019 import net.sf.cpsolver.ifs.solver.Solver; 020 021 /** 022 * The class represents various criteria concerning compact timetables of 023 * instructors. The criteria are checked and updated when a variable is 024 * (un)assigned. 025 * <br> 026 * implemented criteria: lunch break 027 * <br> 028 * @version CourseTT 1.2 (University Course Timetabling)<br> 029 * Copyright (C) 2012 Matej Lukac<br> 030 * <br> 031 * This library is free software; you can redistribute it and/or modify 032 * it under the terms of the GNU Lesser General Public License as 033 * published by the Free Software Foundation; either version 3 of the 034 * License, or (at your option) any later version. <br> 035 * <br> 036 * This library is distributed in the hope that it will be useful, but 037 * WITHOUT ANY WARRANTY; without even the implied warranty of 038 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 039 * Lesser General Public License for more details. <br> 040 * <br> 041 * You should have received a copy of the GNU Lesser General Public 042 * License along with this library; if not see 043 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 044 */ 045 public class CompactTimetable extends AbstractCriterion<Lecture, Placement> { 046 // lunch attributes 047 private double iMultiplier, iLunchWeight; 048 private int iLunchStart, iLunchEnd, iLunchLength; 049 private boolean iCheckLunchBreak, iFullInfo; 050 private List<BitSet> iWeeks = null; 051 052 private Map<InstructorConstraint, CompactInfo> iCompactInfos = new HashMap<InstructorConstraint, CompactInfo>(); 053 054 public CompactTimetable() { 055 iValueUpdateType = ValueUpdateType.NoUpdate; 056 } 057 058 @Override 059 public boolean init(Solver<Lecture, Placement> solver) { 060 super.init(solver); 061 062 iWeight = solver.getProperties().getPropertyDouble("CompactTimetable.Weight", 1.0d); 063 064 // lunch parameters 065 iLunchStart = solver.getProperties().getPropertyInt("InstructorLunch.StartSlot", (11 * 60) / 5); 066 iLunchEnd = solver.getProperties().getPropertyInt("InstructorLunch.EndSlot", (13 * 60 + 30) / 5); 067 iLunchLength = solver.getProperties().getPropertyInt("InstructorLunch.Length", 30 / 5); 068 iMultiplier = solver.getProperties().getPropertyDouble("InstructorLunch.Multiplier", 1.35d); 069 iLunchWeight = solver.getProperties().getPropertyDouble("InstructorLunch.Weight", 0.3d); 070 iCheckLunchBreak = solver.getProperties().getPropertyBoolean("InstructorLunch.Enabled", true); 071 iFullInfo = solver.getProperties().getPropertyBoolean("InstructorLunch.InfoShowViolations", true); 072 073 return true; 074 } 075 076 /** 077 * Get compact info that is associated with an instructor constraint. 078 * Create a new one if none has been created yet. 079 */ 080 protected CompactInfo getCompactInfo(InstructorConstraint constraint) { 081 CompactInfo info = iCompactInfos.get(constraint); 082 if (info == null) { 083 info = new CompactInfo(); 084 iCompactInfos.put(constraint, info); 085 } 086 return info; 087 } 088 089 /** 090 * Update criterion after an assignment. 091 */ 092 @Override 093 public void afterAssigned(long iteration, Placement value) { 094 super.afterAssigned(iteration, value); 095 for (InstructorConstraint constraint: value.variable().getInstructorConstraints()) 096 updateCriterion(constraint, value); 097 } 098 099 /** 100 * Update criterion after an unassignment 101 */ 102 @Override 103 public void afterUnassigned(long iteration, Placement value) { 104 super.afterUnassigned(iteration, value); 105 for (InstructorConstraint constraint: value.variable().getInstructorConstraints()) 106 updateCriterion(constraint, value); 107 } 108 109 /** 110 * The method creates date patterns (bitsets) which represent the weeks of a 111 * semester. 112 * 113 * @param s 114 * default date pattern as combination of "0" and "1". 115 * @return a list of BitSets which represents the weeks of a semester. 116 */ 117 protected List<BitSet> getWeeks() { 118 if (iWeeks == null) { 119 String defaultDatePattern = ((TimetableModel)getModel()).getProperties().getProperty("DatePattern.Default"); 120 if (defaultDatePattern == null) return null; 121 // Create default date pattern 122 BitSet fullTerm = new BitSet(defaultDatePattern.length()); 123 for (int i = 0; i < defaultDatePattern.length(); i++) { 124 if (defaultDatePattern.charAt(i) == 49) { 125 fullTerm.set(i); 126 } 127 } 128 // Cut date pattern into weeks (every week contains 7 positive bits) 129 iWeeks = new ArrayList<BitSet>(); 130 int cnt = 0; 131 for (int i = 0; i < fullTerm.length(); i++) { 132 if (fullTerm.get(i)) { 133 int w = (cnt++) / 7; 134 if (iWeeks.size() == w) { 135 iWeeks.add(new BitSet(fullTerm.length())); 136 } 137 iWeeks.get(w).set(i); 138 } 139 } 140 } 141 return iWeeks; 142 } 143 144 /** 145 * Method updates number of violations in days (Mo, Tue, Wed,..) considering 146 * each week in the semester separately. The current number of violations 147 * for a day is stored in the CompactInfo.lunchDayViolations of the 148 * constraint, which must be set properly before the calling of the method. 149 * 150 * @param constraint 151 * the Instructor constraint of an instructor checked for a lunch 152 * break 153 * @param p 154 * placement of a lecture currently (un)assigned 155 */ 156 public void updateLunchPenalty(InstructorConstraint constraint, Placement p) { 157 // checks only placements in the lunch time 158 if (p.getTimeLocation().getStartSlot() <= iLunchEnd && p.getTimeLocation().getStartSlot() + p.getTimeLocation().getLength() > iLunchStart) { 159 CompactInfo compactInfo = getCompactInfo(constraint); 160 for (int i = 0; i < Constants.NR_DAYS; i++) { 161 // checks only days affected by the placement 162 if ((p.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0) { 163 int currentLunchStartSlot = Constants.SLOTS_PER_DAY * i + iLunchStart; 164 int currentLunchEndSlot = Constants.SLOTS_PER_DAY * i + iLunchEnd; 165 int semesterViolations = 0; 166 for (BitSet week : getWeeks()) { 167 int maxBreak = 0; 168 int currentBreak = 0; 169 for (int slot = currentLunchStartSlot; slot < currentLunchEndSlot; slot++) { 170 if (constraint.getPlacements(slot, week).isEmpty()) { 171 currentBreak++; 172 if (maxBreak < currentBreak) { 173 maxBreak = currentBreak; 174 } 175 } else { 176 currentBreak = 0; 177 } 178 } 179 if (maxBreak < iLunchLength) { 180 semesterViolations++; 181 } 182 } 183 // saving the result in the CompactInfo of the 184 // InstructorConstraint 185 compactInfo.getLunchDayViolations()[i] = semesterViolations; 186 } 187 } 188 } 189 } 190 191 /** 192 * Method checks or sets the CompactInfo of an InstructorConstraint. It 193 * updates the preference of chosen criteria. The update consists of 194 * decrementing the criterion value by previous preference, finding the 195 * current preference and incrementing the criterion value by the current 196 * preference. 197 * 198 * @param instructorConstraint 199 * the Instructor constraint of an instructor checked for 200 * criteria 201 * @param placement 202 * placement of a lecture currently (un)assigned 203 */ 204 public void updateCriterion(InstructorConstraint instructorConstraint, Placement placement) { 205 // manage lunch criterion 206 if (iCheckLunchBreak) { 207 iValue -= getLunchPreference(instructorConstraint) * iLunchWeight; 208 updateLunchPenalty(instructorConstraint, placement); 209 iValue += getLunchPreference(instructorConstraint) * iLunchWeight; 210 } 211 } 212 213 /** 214 * Method uses the CompactInfo of the InstructorConstraint and returns the 215 * lunch preference for this constraint. Calculation formula does not use 216 * linear function, the number of violations is multiplied by a power of 217 * iMultiplier. 218 * 219 * @param instructorConstraint 220 * the Instructor constraint of an instructor checked for a lunch 221 * break 222 * @return the lunch preference for this constraint 223 */ 224 private double getLunchPreference(InstructorConstraint instructorConstraint) { 225 double violations = 0d; 226 CompactInfo info = getCompactInfo(instructorConstraint); 227 for (int i = 0; i < Constants.NR_DAYS; i++) 228 violations += info.getLunchDayViolations()[i]; 229 return Math.pow(violations, iMultiplier); 230 } 231 232 @Override 233 public double getValue(Placement value, Set<Placement> conflicts) { 234 return iValue; 235 } 236 237 @Override 238 public double getWeightedValue(Placement value, Set<Placement> conflicts) { 239 return iValue * iWeight; 240 } 241 242 @Override 243 public double getValue(Collection<Lecture> variables) { 244 double lunchValue = 0.0d; 245 Set<InstructorConstraint> constraints = new HashSet<InstructorConstraint>(); 246 for (Lecture lecture : variables) { 247 constraints.addAll(lecture.getInstructorConstraints()); 248 } 249 for (InstructorConstraint instructor : constraints) { 250 lunchValue += getLunchPreference(instructor); 251 } 252 return lunchValue * iLunchWeight; 253 } 254 255 @Override 256 public double getWeightedValue(Collection<Lecture> variables) { 257 double lunchValue = 0.0d; 258 Set<InstructorConstraint> constraints = new HashSet<InstructorConstraint>(); 259 for (Lecture lecture : variables) { 260 constraints.addAll(lecture.getInstructorConstraints()); 261 } 262 for (InstructorConstraint instructor : constraints) { 263 lunchValue += getLunchPreference(instructor); 264 } 265 return lunchValue * iLunchWeight * iWeight; 266 } 267 268 @Override 269 public void getInfo(Map<String, String> info) { 270 Set<String> violatedLunchBreaks = new TreeSet<String>(); 271 int lunchViolations = 0; 272 for (InstructorConstraint c : ((TimetableModel)getModel()).getInstructorConstraints()) { 273 String days = ""; 274 CompactInfo compactInfo = getCompactInfo(c); 275 for (int i = 0; i < Constants.NR_DAYS; i++) { 276 if (compactInfo.getLunchDayViolations()[i] > 0) { 277 if (iFullInfo) 278 days += (days.isEmpty() ? "" : ", ") + compactInfo.getLunchDayViolations()[i] + " × " + Constants.DAY_NAMES_SHORT[i]; 279 lunchViolations += compactInfo.getLunchDayViolations()[i]; 280 } 281 } 282 if (iFullInfo && !days.isEmpty()) 283 violatedLunchBreaks.add(c.getName() + ": " + days); 284 } 285 if (lunchViolations > 0) { 286 info.put("Lunch breaks", getPerc(lunchViolations, 0, ((TimetableModel)getModel()).getInstructorConstraints().size() * Constants.NR_DAYS * getWeeks().size()) + "% (" + lunchViolations + ")"); 287 if (iFullInfo && !violatedLunchBreaks.isEmpty()) { 288 String message = ""; 289 for (String s: violatedLunchBreaks) 290 message += (message.isEmpty() ? "" : "<br>") + s; 291 info.put("Lunch break violations", message); 292 } 293 } 294 } 295 296 @Override 297 public void getInfo(Map<String, String> info, Collection<Lecture> variables) { 298 Set<InstructorConstraint> constraints = new HashSet<InstructorConstraint>(); 299 for (Lecture lecture : variables) { 300 for (InstructorConstraint c : lecture.getInstructorConstraints()) { 301 constraints.add(c); 302 } 303 } 304 Set<String> violatedLunchBreaks = new TreeSet<String>(); 305 int lunchViolations = 0; 306 for (InstructorConstraint c : constraints) { 307 String days = ""; 308 CompactInfo compactInfo = getCompactInfo(c); 309 for (int i = 0; i < Constants.NR_DAYS; i++) { 310 if (compactInfo.getLunchDayViolations()[i] > 0) { 311 if (iFullInfo) 312 days += (days.isEmpty() ? "" : ", ") + compactInfo.getLunchDayViolations()[i] + " × " + Constants.DAY_NAMES_SHORT[i]; 313 lunchViolations += compactInfo.getLunchDayViolations()[i]; 314 } 315 } 316 if (iFullInfo && !days.isEmpty()) 317 violatedLunchBreaks.add(c.getName() + ": " + days); 318 } 319 if (lunchViolations > 0) { 320 info.put("Lunch breaks", getPerc(lunchViolations, 0, constraints.size() * Constants.NR_DAYS * getWeeks().size()) + "% (" + lunchViolations + ")"); 321 if (iFullInfo && !violatedLunchBreaks.isEmpty()) { 322 String message = ""; 323 for (String s: violatedLunchBreaks) 324 message += (message.isEmpty() ? "" : "<br>") + s; 325 info.put("Lunch break violations", message); 326 } 327 } 328 } 329 330 /** 331 * The class is used as a container of information concerning compact 332 * timetables of instructors. It is designed as an attribute of an 333 * InstructorConstraint. 334 */ 335 public static class CompactInfo { 336 // lunch attributes 337 private int[] iLunchDayViolations = new int[Constants.NR_DAYS]; 338 339 public CompactInfo() { 340 } 341 342 public int[] getLunchDayViolations() { return iLunchDayViolations; } 343 } 344 }