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