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