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