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