001package org.cpsolver.coursett.constraint; 002 003import java.util.Enumeration; 004import java.util.HashSet; 005import java.util.Iterator; 006import java.util.List; 007import java.util.Set; 008 009import org.cpsolver.coursett.Constants; 010import org.cpsolver.coursett.criteria.SameSubpartBalancingPenalty; 011import org.cpsolver.coursett.model.Lecture; 012import org.cpsolver.coursett.model.Placement; 013import org.cpsolver.ifs.assignment.Assignment; 014import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext; 015import org.cpsolver.ifs.assignment.context.ConstraintWithContext; 016import org.cpsolver.ifs.criteria.Criterion; 017import org.cpsolver.ifs.model.WeakeningConstraint; 018import org.cpsolver.ifs.util.DataProperties; 019import org.cpsolver.ifs.util.ToolBox; 020 021 022/** 023 * Spread given set of classes in time as much as possible. See 024 * {@link DepartmentSpreadConstraint} for more details. 025 * 026 * @version CourseTT 1.3 (University Course Timetabling)<br> 027 * Copyright (C) 2006 - 2014 Tomas Muller<br> 028 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 029 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><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 046public class SpreadConstraint extends ConstraintWithContext<Lecture, Placement, SpreadConstraint.SpreadConstraintContext> implements WeakeningConstraint<Lecture, Placement> { 047 private boolean iInteractive = false; 048 private double iSpreadFactor = 1.20; 049 private int iUnassignmentsToWeaken = 250; 050 private String iName = null; 051 private int iFirstDaySlot, iLastDaySlot, iFirstWorkDay, iLastWorkDay; 052 053 public static boolean USE_MOST_IMPROVEMENT_ADEPTS = false; 054 055 public SpreadConstraint(String name, double spreadFactor, int unassignmentsToWeaken, boolean interactiveMode, int firstDaySlot, int lastDaySlot, int firstWorkDay, int lastWorkDay) { 056 iName = name; 057 iSpreadFactor = spreadFactor; 058 iUnassignmentsToWeaken = unassignmentsToWeaken; 059 iInteractive = interactiveMode; 060 iFirstDaySlot = firstDaySlot; 061 iLastDaySlot = lastDaySlot; 062 iFirstWorkDay = firstWorkDay; 063 iLastWorkDay = lastWorkDay; 064 } 065 066 public SpreadConstraint(DataProperties config, String name) { 067 this(name, 068 config.getPropertyDouble("Spread.SpreadFactor", 1.20), 069 config.getPropertyInt("Spread.Unassignments2Weaken", 250), 070 config.getPropertyBoolean("General.InteractiveMode", false), 071 config.getPropertyInt("General.FirstDaySlot", Constants.DAY_SLOTS_FIRST), 072 config.getPropertyInt("General.LastDaySlot", Constants.DAY_SLOTS_LAST), 073 config.getPropertyInt("General.FirstWorkDay", 0), 074 config.getPropertyInt("General.LastWorkDay", Constants.NR_DAYS_WEEK - 1) 075 ); 076 } 077 078 079 protected Criterion<Lecture, Placement> getCriterion() { 080 return getModel().getCriterion(SameSubpartBalancingPenalty.class); 081 } 082 083 public Placement getAdept(Assignment<Lecture, Placement> assignment, Placement placement, int[][] nrCourses, Set<Placement> conflicts) { 084 Placement adept = null; 085 int improvement = 0; 086 087 // take uncommitted placements first 088 for (Lecture lect : variables()) { 089 if (lect.isCommitted()) 090 continue; 091 Placement plac = assignment.getValue(lect); 092 if (plac == null || plac.equals(placement) || placement.variable().equals(plac.variable()) 093 || conflicts.contains(plac)) 094 continue; 095 int imp = getPenaltyIfUnassigned(assignment, plac, nrCourses); 096 if (imp == 0) 097 continue; 098 if (adept == null || imp > improvement) { 099 adept = plac; 100 improvement = imp; 101 } 102 } 103 if (adept != null) 104 return adept; 105 106 // no uncommitted placement found -- take committed one 107 for (Lecture lect : variables()) { 108 if (!lect.isCommitted()) 109 continue; 110 Placement plac = assignment.getValue(lect); 111 if (plac == null || plac.equals(placement) || conflicts.contains(plac)) 112 continue; 113 int imp = getPenaltyIfUnassigned(assignment, plac, nrCourses); 114 if (imp == 0) 115 continue; 116 if (adept == null || imp > improvement) { 117 adept = plac; 118 improvement = imp; 119 } 120 } 121 122 return adept; 123 } 124 125 @SuppressWarnings("unchecked") 126 private Set<Placement>[] getAdepts(Assignment<Lecture, Placement> assignment, Placement placement, int[][] nrCourses, Set<Placement> conflicts) { 127 SpreadConstraintContext context = getContext(assignment); 128 int firstSlot = placement.getTimeLocation().getStartSlot(); 129 if (firstSlot > iLastDaySlot) 130 return null; 131 int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1; 132 if (endSlot < iFirstDaySlot) 133 return null; 134 HashSet<Placement> adepts[] = new HashSet[] { new HashSet<Placement>(), new HashSet<Placement>() }; 135 for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) { 136 for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) { 137 int dayCode = Constants.DAY_CODES[j]; 138 if ((dayCode & placement.getTimeLocation().getDayCode()) != 0 && nrCourses[i - iFirstDaySlot][j - iFirstWorkDay] >= context.getMaxCourses(i, j)) { 139 for (Placement p : context.getCourses(i, j)) { 140 if (conflicts.contains(p)) 141 continue; 142 if (p.equals(placement)) 143 continue; 144 if (p.variable().equals(placement.variable())) 145 continue; 146 adepts[(p.variable()).isCommitted() ? 1 : 0].add(p); 147 } 148 } 149 } 150 } 151 return adepts; 152 // sLogger.debug(" -- adept "+adept+" selected, penalty will be decreased by "+improvement); 153 } 154 155 private int getPenaltyIfUnassigned(Assignment<Lecture, Placement> assignment, Placement placement, int[][] nrCourses) { 156 SpreadConstraintContext context = getContext(assignment); 157 int firstSlot = placement.getTimeLocation().getStartSlot(); 158 if (firstSlot > iLastDaySlot) 159 return 0; 160 int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1; 161 if (endSlot < iFirstDaySlot) 162 return 0; 163 int penalty = 0; 164 for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) { 165 for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) { 166 int dayCode = Constants.DAY_CODES[j]; 167 if ((dayCode & placement.getTimeLocation().getDayCode()) != 0 && nrCourses[i - iFirstDaySlot][j - iFirstWorkDay] > context.getMaxCourses(i, j)) 168 penalty++; 169 } 170 } 171 return penalty; 172 } 173 174 private int tryUnassign(Assignment<Lecture, Placement> assignment, Placement placement, int[][] nrCourses) { 175 SpreadConstraintContext context = getContext(assignment); 176 // sLogger.debug(" -- trying to unassign "+placement); 177 int firstSlot = placement.getTimeLocation().getStartSlot(); 178 if (firstSlot > iLastDaySlot) 179 return 0; 180 int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1; 181 if (endSlot < iFirstDaySlot) 182 return 0; 183 int improvement = 0; 184 for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) { 185 for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) { 186 int dayCode = Constants.DAY_CODES[j]; 187 if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) { 188 if (nrCourses[i - iFirstDaySlot][j - iFirstWorkDay] > context.getMaxCourses(i, j)) 189 improvement++; 190 nrCourses[i - iFirstDaySlot][j - iFirstWorkDay]--; 191 } 192 } 193 } 194 // sLogger.debug(" -- penalty is decreased by "+improvement); 195 return improvement; 196 } 197 198 private int tryAssign(Assignment<Lecture, Placement> assignment, Placement placement, int[][] nrCourses) { 199 SpreadConstraintContext context = getContext(assignment); 200 // sLogger.debug(" -- trying to assign "+placement); 201 int firstSlot = placement.getTimeLocation().getStartSlot(); 202 if (firstSlot > iLastDaySlot) 203 return 0; 204 int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1; 205 if (endSlot < iFirstDaySlot) 206 return 0; 207 int penalty = 0; 208 for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) { 209 for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) { 210 int dayCode = Constants.DAY_CODES[j]; 211 if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) { 212 nrCourses[i - iFirstDaySlot][j - iFirstWorkDay]++; 213 if (nrCourses[i - iFirstDaySlot][j - iFirstWorkDay] > context.getMaxCourses(i, j)) 214 penalty++; 215 } 216 } 217 } 218 // sLogger.debug(" -- penalty is incremented by "+penalty); 219 return penalty; 220 } 221 222 @Override 223 public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement placement, Set<Placement> conflicts) { 224 SpreadConstraintContext context = getContext(assignment); 225 if (context.getUnassignmentsToWeaken() == 0) 226 return; 227 int penalty = context.getCurrentPenalty() + getPenalty(assignment, placement); 228 if (penalty <= context.getMaxAllowedPenalty()) 229 return; 230 int firstSlot = placement.getTimeLocation().getStartSlot(); 231 if (firstSlot > iLastDaySlot) 232 return; 233 int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1; 234 if (endSlot < iFirstDaySlot) 235 return; 236 // sLogger.debug("-- computing conflict for value "+value+" ... (penalty="+iCurrentPenalty+", penalty with the value="+penalty+", max="+iMaxAllowedPenalty+")"); 237 int[][] nrCourses = new int[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1]; 238 for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++) 239 for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) 240 nrCourses[i][j] = context.getNrCourses(i + iFirstDaySlot, j + iFirstWorkDay, placement); 241 tryAssign(assignment, placement, nrCourses); 242 // sLogger.debug(" -- nrCurses="+fmt(nrCourses)); 243 for (Lecture lect : variables()) { 244 if (lect.equals(placement.variable())) continue; 245 if (conflicts.contains(lect)) { 246 penalty -= tryUnassign(assignment, assignment.getValue(lect), nrCourses); 247 } 248 if (penalty <= context.getMaxAllowedPenalty()) 249 return; 250 } 251 if (USE_MOST_IMPROVEMENT_ADEPTS) { 252 while (penalty > context.getMaxAllowedPenalty()) { 253 Placement plac = getAdept(assignment, placement, nrCourses, conflicts); 254 if (plac == null) 255 break; 256 conflicts.add(plac); 257 penalty -= tryUnassign(assignment, plac, nrCourses); 258 } 259 } else { 260 if (penalty > context.getMaxAllowedPenalty()) { 261 Set<Placement> adepts[] = getAdepts(assignment, placement, nrCourses, conflicts); 262 for (int i = 0; penalty > context.getMaxAllowedPenalty() && i < adepts.length; i++) { 263 while (!adepts[i].isEmpty() && penalty > context.getMaxAllowedPenalty()) { 264 Placement plac = ToolBox.random(adepts[i]); 265 adepts[i].remove(plac); 266 conflicts.add(plac); 267 // sLogger.debug(" -- conflict "+lect.getAssignment()+" added"); 268 penalty -= tryUnassign(assignment, plac, nrCourses); 269 } 270 } 271 } 272 } 273 } 274 275 @Override 276 public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement placement) { 277 SpreadConstraintContext context = getContext(assignment); 278 if (context.getUnassignmentsToWeaken() == 0) return false; 279 return getPenalty(assignment, placement) + context.getCurrentPenalty() > context.getMaxAllowedPenalty(); 280 } 281 282 @Override 283 public void weaken(Assignment<Lecture, Placement> assignment) { 284 getContext(assignment).weaken(); 285 } 286 287 @Override 288 public String getName() { 289 return iName; 290 } 291 292 @Override 293 public String toString() { 294 StringBuffer sb = new StringBuffer(); 295 sb.append("Time Spread between "); 296 for (Iterator<Lecture> e = variables().iterator(); e.hasNext();) { 297 Lecture v = e.next(); 298 sb.append(v.getName()); 299 if (e.hasNext()) 300 sb.append(", "); 301 } 302 return sb.toString(); 303 } 304 305 /** Department balancing penalty for this department 306 * @param assignment current assignment 307 * @return current penalty 308 **/ 309 public int getPenalty(Assignment<Lecture, Placement> assignment) { 310 return getContext(assignment).getCurrentPenalty(); 311 } 312 313 public int getPenaltyEstimate(Assignment<Lecture, Placement> assignment) { 314 double histogramPerDay[][] = new double[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1]; 315 int maxCourses[][] = new int[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1]; 316 int nrCourses[][] = new int[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1]; 317 for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++) 318 for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) 319 histogramPerDay[i][j] = 0.0; 320 int totalUsedSlots = 0; 321 for (Lecture lecture : variables()) { 322 List<Placement> values = lecture.values(assignment); 323 Placement firstPlacement = (values.isEmpty() ? null : values.get(0)); 324 if (firstPlacement != null) { 325 totalUsedSlots += firstPlacement.getTimeLocation().getNrSlotsPerMeeting() 326 * firstPlacement.getTimeLocation().getNrMeetings(); 327 } 328 for (Placement p : values) { 329 int firstSlot = p.getTimeLocation().getStartSlot(); 330 if (firstSlot > iLastDaySlot) 331 continue; 332 int endSlot = firstSlot + p.getTimeLocation().getNrSlotsPerMeeting() - 1; 333 if (endSlot < iFirstDaySlot) 334 continue; 335 for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) { 336 int dayCode = p.getTimeLocation().getDayCode(); 337 for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) { 338 if ((dayCode & Constants.DAY_CODES[j]) != 0) { 339 histogramPerDay[i - iFirstDaySlot][j - iFirstWorkDay] += 1.0 / values.size(); 340 } 341 } 342 } 343 } 344 } 345 double threshold = iSpreadFactor * ((double) totalUsedSlots / ((iLastWorkDay - iFirstWorkDay + 1) * (iLastDaySlot - iFirstDaySlot + 1))); 346 for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++) { 347 for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) { 348 nrCourses[i][j] = 0; 349 maxCourses[i][j] = (int) (0.999 + (histogramPerDay[i][j] <= threshold ? iSpreadFactor * histogramPerDay[i][j] : histogramPerDay[i][j])); 350 } 351 } 352 int currentPenalty = 0; 353 for (Lecture lecture : variables()) { 354 Placement placement = assignment.getValue(lecture); 355 if (placement == null) 356 continue; 357 int firstSlot = placement.getTimeLocation().getStartSlot(); 358 if (firstSlot > iLastDaySlot) 359 continue; 360 int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1; 361 if (endSlot < iFirstDaySlot) 362 continue; 363 for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) { 364 for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) { 365 int dayCode = Constants.DAY_CODES[j]; 366 if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) { 367 nrCourses[i - iFirstDaySlot][j - iFirstWorkDay]++; 368 } 369 } 370 } 371 } 372 for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++) { 373 for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) { 374 currentPenalty += Math.max(0, nrCourses[i][j] - maxCourses[i][j]); 375 } 376 } 377 return currentPenalty; 378 } 379 380 public int getMaxPenalty(Assignment<Lecture, Placement> assignment, Placement placement) { 381 SpreadConstraintContext context = getContext(assignment); 382 int penalty = 0; 383 for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) { 384 int slot = e.nextElement(); 385 int day = slot / Constants.SLOTS_PER_DAY; 386 int time = slot % Constants.SLOTS_PER_DAY; 387 if (time < iFirstDaySlot || time > iLastDaySlot) 388 continue; 389 if (day < iFirstWorkDay || day > iLastWorkDay) 390 continue; 391 int dif = 1 + context.getNrCourses(time, day, placement) - context.getMaxCourses(time, day); 392 if (dif > penalty) 393 penalty = dif; 394 } 395 return penalty; 396 } 397 398 /** Department balancing penalty of the given placement 399 * @param assignment current assignment 400 * @param placement a placement that is being considered 401 * @return change in the penalty if assigned 402 **/ 403 public int getPenalty(Assignment<Lecture, Placement> assignment, Placement placement) { 404 SpreadConstraintContext context = getContext(assignment); 405 int firstSlot = placement.getTimeLocation().getStartSlot(); 406 if (firstSlot > iLastDaySlot) 407 return 0; 408 int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1; 409 if (endSlot < iFirstDaySlot) 410 return 0; 411 int penalty = 0; 412 int min = Math.max(firstSlot, iFirstDaySlot); 413 int max = Math.min(endSlot, iLastDaySlot); 414 for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) { 415 int dayCode = Constants.DAY_CODES[j]; 416 if ((dayCode & placement.getTimeLocation().getDayCode()) == 0) 417 continue; 418 for (int i = min; i <= max; i++) { 419 if (context.getNrCourses(i, j, placement) >= context.getMaxCourses(i, j)) 420 penalty++; 421 } 422 } 423 return penalty; 424 } 425 426 @Override 427 public void addVariable(Lecture lecture) { 428 if (lecture.canShareRoom()) { 429 for (GroupConstraint gc : lecture.groupConstraints()) { 430 if (gc.getType() == GroupConstraint.ConstraintType.MEET_WITH) { 431 if (gc.variables().indexOf(lecture) > 0) 432 return; 433 } 434 } 435 } 436 super.addVariable(lecture); 437 } 438 439 @Override 440 public void weaken(Assignment<Lecture, Placement> assignment, Placement value) { 441 while (inConflict(assignment, value)) 442 getContext(assignment).weaken(getContext(assignment).getCurrentPenalty() + getPenalty(assignment, value)); 443 } 444 445 @Override 446 public SpreadConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) { 447 return new SpreadConstraintContext(assignment); 448 } 449 450 public class SpreadConstraintContext implements AssignmentConstraintContext<Lecture, Placement> { 451 private int iMaxAllowedPenalty = 0; 452 private long iUnassignment = 0; 453 private Set<Placement>[][] iCourses = null; 454 private int iMaxCourses[][] = null; 455 private int iCurrentPenalty = 0; 456 457 @SuppressWarnings("unchecked") 458 public SpreadConstraintContext(Assignment<Lecture, Placement> assignment) { 459 iCourses = new Set[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1]; 460 if (iInteractive) 461 iUnassignmentsToWeaken = 0; 462 for (int i = 0; i < iCourses.length; i++) { 463 for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) { 464 iCourses[i][j] = new HashSet<Placement>(10); 465 } 466 } 467 double histogramPerDay[][] = new double[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1]; 468 iMaxCourses = new int[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1]; 469 for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++) 470 for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) 471 histogramPerDay[i][j] = 0.0; 472 int totalUsedSlots = 0; 473 for (Lecture lecture : variables()) { 474 List<Placement> values = lecture.values(assignment); 475 Placement firstPlacement = (values.isEmpty() ? null : values.get(0)); 476 if (firstPlacement != null) { 477 totalUsedSlots += firstPlacement.getTimeLocation().getNrSlotsPerMeeting() * firstPlacement.getTimeLocation().getNrMeetings(); 478 } 479 for (Placement p : values) { 480 int firstSlot = p.getTimeLocation().getStartSlot(); 481 if (firstSlot > iLastDaySlot) 482 continue; 483 int endSlot = firstSlot + p.getTimeLocation().getNrSlotsPerMeeting() - 1; 484 if (endSlot < iFirstDaySlot) 485 continue; 486 for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) { 487 int dayCode = p.getTimeLocation().getDayCode(); 488 for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) { 489 if ((dayCode & Constants.DAY_CODES[j]) != 0) { 490 histogramPerDay[i - iFirstDaySlot][j - iFirstWorkDay] += 1.0 / values.size(); 491 } 492 } 493 } 494 } 495 } 496 // System.out.println("Histogram for department "+iDepartment+":"); 497 double threshold = iSpreadFactor * ((double) totalUsedSlots / ((iLastWorkDay - iFirstWorkDay + 1) * (iLastDaySlot - iFirstDaySlot + 1))); 498 // System.out.println("Threshold["+iDepartment+"] = "+threshold); 499 for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++) { 500 // System.out.println(" "+fmt(i+1)+": "+fmt(histogramPerDay[i])); 501 for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) { 502 iMaxCourses[i][j] = (int) (0.999 + (histogramPerDay[i][j] <= threshold ? iSpreadFactor * histogramPerDay[i][j] : histogramPerDay[i][j])); 503 } 504 } 505 for (Lecture lecture : variables()) { 506 Placement placement = assignment.getValue(lecture); 507 if (placement == null) 508 continue; 509 int firstSlot = placement.getTimeLocation().getStartSlot(); 510 if (firstSlot > iLastDaySlot) 511 continue; 512 int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1; 513 if (endSlot < iFirstDaySlot) 514 continue; 515 for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) { 516 for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) { 517 int dayCode = Constants.DAY_CODES[j]; 518 if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) { 519 iCourses[i - iFirstDaySlot][j - iFirstWorkDay].add(placement); 520 } 521 } 522 } 523 } 524 iCurrentPenalty = 0; 525 for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++) { 526 for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) { 527 iCurrentPenalty += Math.max(0, iCourses[i][j].size() - iMaxCourses[i][j]); 528 } 529 } 530 iMaxAllowedPenalty = iCurrentPenalty; 531 getCriterion().inc(assignment, iCurrentPenalty); 532 } 533 534 535 @Override 536 public void assigned(Assignment<Lecture, Placement> assignment, Placement placement) { 537 int firstSlot = placement.getTimeLocation().getStartSlot(); 538 if (firstSlot > iLastDaySlot) 539 return; 540 int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1; 541 if (endSlot < iFirstDaySlot) 542 return; 543 getCriterion().inc(assignment, -iCurrentPenalty); 544 for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) { 545 for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) { 546 int dayCode = Constants.DAY_CODES[j]; 547 if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) { 548 iCourses[i - iFirstDaySlot][j - iFirstWorkDay].add(placement); 549 if (iCourses[i - iFirstDaySlot][j - iFirstWorkDay].size() > iMaxCourses[i - iFirstDaySlot][j - iFirstWorkDay]) 550 iCurrentPenalty++; 551 } 552 } 553 } 554 getCriterion().inc(assignment, iCurrentPenalty); 555 } 556 557 @Override 558 public void unassigned(Assignment<Lecture, Placement> assignment, Placement placement) { 559 int firstSlot = placement.getTimeLocation().getStartSlot(); 560 if (firstSlot > iLastDaySlot) 561 return; 562 int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1; 563 if (endSlot < iFirstDaySlot) 564 return; 565 getCriterion().inc(assignment, -iCurrentPenalty); 566 for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) { 567 for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) { 568 int dayCode = Constants.DAY_CODES[j]; 569 if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) { 570 if (iCourses[i - iFirstDaySlot][j - iFirstWorkDay].size() > iMaxCourses[i - iFirstDaySlot][j - iFirstWorkDay]) 571 iCurrentPenalty--; 572 iCourses[i - iFirstDaySlot][j - iFirstWorkDay].remove(placement); 573 } 574 } 575 } 576 getCriterion().inc(assignment, iCurrentPenalty); 577 } 578 579 public int[][] getMaxCourses() { 580 return iMaxCourses; 581 } 582 583 public int getMaxCourses(int time, int day) { 584 return iMaxCourses[time - iFirstDaySlot][day - iFirstWorkDay]; 585 } 586 587 public int getNrCourses(int time, int day, Placement placement) { 588 if (placement == null) return getCourses(time, day).size(); 589 int nrCourses = 0; 590 for (Placement p: getCourses(time, day)) 591 if (!p.variable().equals(placement.variable())) 592 nrCourses ++; 593 return nrCourses; 594 } 595 596 public Set<Placement> getCourses(int time, int day) { 597 return iCourses[time - iFirstDaySlot][day - iFirstWorkDay]; 598 } 599 600 public int getUnassignmentsToWeaken() { 601 return iUnassignmentsToWeaken; 602 } 603 604 public int getCurrentPenalty() { 605 return iCurrentPenalty; 606 } 607 608 public int getMaxAllowedPenalty() { 609 return iMaxAllowedPenalty; 610 } 611 612 public void weaken() { 613 if (iUnassignmentsToWeaken == 0) return; 614 iUnassignment++; 615 if (iUnassignment % iUnassignmentsToWeaken == 0) 616 iMaxAllowedPenalty++; 617 } 618 619 public void weaken(int penalty) { 620 if (penalty > iMaxAllowedPenalty) 621 iMaxAllowedPenalty = penalty; 622 } 623 624 } 625}