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 Tomáš Müller<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 Placement p = assignment.getValue(lect); 247 if (p != null && conflicts.contains(p)) { 248 penalty -= tryUnassign(assignment, p, nrCourses); 249 } 250 if (penalty <= context.getMaxAllowedPenalty()) 251 return; 252 } 253 if (USE_MOST_IMPROVEMENT_ADEPTS) { 254 while (penalty > context.getMaxAllowedPenalty()) { 255 Placement plac = getAdept(assignment, placement, nrCourses, conflicts); 256 if (plac == null) 257 break; 258 conflicts.add(plac); 259 penalty -= tryUnassign(assignment, plac, nrCourses); 260 } 261 } else { 262 if (penalty > context.getMaxAllowedPenalty()) { 263 Set<Placement> adepts[] = getAdepts(assignment, placement, nrCourses, conflicts); 264 for (int i = 0; penalty > context.getMaxAllowedPenalty() && i < adepts.length; i++) { 265 while (!adepts[i].isEmpty() && penalty > context.getMaxAllowedPenalty()) { 266 Placement plac = ToolBox.random(adepts[i]); 267 adepts[i].remove(plac); 268 conflicts.add(plac); 269 // sLogger.debug(" -- conflict "+lect.getAssignment()+" added"); 270 penalty -= tryUnassign(assignment, plac, nrCourses); 271 } 272 } 273 } 274 } 275 } 276 277 @Override 278 public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement placement) { 279 SpreadConstraintContext context = getContext(assignment); 280 if (context.getUnassignmentsToWeaken() == 0) return false; 281 return getPenalty(assignment, placement) + context.getCurrentPenalty() > context.getMaxAllowedPenalty(); 282 } 283 284 @Override 285 public void weaken(Assignment<Lecture, Placement> assignment) { 286 getContext(assignment).weaken(); 287 } 288 289 @Override 290 public String getName() { 291 return iName; 292 } 293 294 @Override 295 public String toString() { 296 StringBuffer sb = new StringBuffer(); 297 sb.append("Time Spread between "); 298 for (Iterator<Lecture> e = variables().iterator(); e.hasNext();) { 299 Lecture v = e.next(); 300 sb.append(v.getName()); 301 if (e.hasNext()) 302 sb.append(", "); 303 } 304 return sb.toString(); 305 } 306 307 /** Department balancing penalty for this department 308 * @param assignment current assignment 309 * @return current penalty 310 **/ 311 public int getPenalty(Assignment<Lecture, Placement> assignment) { 312 return getContext(assignment).getCurrentPenalty(); 313 } 314 315 public int getPenaltyEstimate(Assignment<Lecture, Placement> assignment) { 316 double histogramPerDay[][] = new double[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1]; 317 int maxCourses[][] = new int[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1]; 318 int nrCourses[][] = new int[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1]; 319 for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++) 320 for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) 321 histogramPerDay[i][j] = 0.0; 322 int totalUsedSlots = 0; 323 for (Lecture lecture : variables()) { 324 List<Placement> values = lecture.values(assignment); 325 Placement firstPlacement = (values.isEmpty() ? null : values.get(0)); 326 if (firstPlacement != null) { 327 totalUsedSlots += firstPlacement.getTimeLocation().getNrSlotsPerMeeting() 328 * firstPlacement.getTimeLocation().getNrMeetings(); 329 } 330 for (Placement p : values) { 331 int firstSlot = p.getTimeLocation().getStartSlot(); 332 if (firstSlot > iLastDaySlot) 333 continue; 334 int endSlot = firstSlot + p.getTimeLocation().getNrSlotsPerMeeting() - 1; 335 if (endSlot < iFirstDaySlot) 336 continue; 337 for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) { 338 int dayCode = p.getTimeLocation().getDayCode(); 339 for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) { 340 if ((dayCode & Constants.DAY_CODES[j % 7]) != 0) { 341 histogramPerDay[i - iFirstDaySlot][j - iFirstWorkDay] += 1.0 / values.size(); 342 } 343 } 344 } 345 } 346 } 347 double threshold = iSpreadFactor * ((double) totalUsedSlots / ((iLastWorkDay - iFirstWorkDay + 1) * (iLastDaySlot - iFirstDaySlot + 1))); 348 for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++) { 349 for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) { 350 nrCourses[i][j] = 0; 351 maxCourses[i][j] = (int) (0.999 + (histogramPerDay[i][j] <= threshold ? iSpreadFactor * histogramPerDay[i][j] : histogramPerDay[i][j])); 352 } 353 } 354 int currentPenalty = 0; 355 for (Lecture lecture : variables()) { 356 Placement placement = assignment.getValue(lecture); 357 if (placement == null) 358 continue; 359 int firstSlot = placement.getTimeLocation().getStartSlot(); 360 if (firstSlot > iLastDaySlot) 361 continue; 362 int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1; 363 if (endSlot < iFirstDaySlot) 364 continue; 365 for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) { 366 for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) { 367 int dayCode = Constants.DAY_CODES[j % 7]; 368 if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) { 369 nrCourses[i - iFirstDaySlot][j - iFirstWorkDay]++; 370 } 371 } 372 } 373 } 374 for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++) { 375 for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) { 376 currentPenalty += Math.max(0, nrCourses[i][j] - maxCourses[i][j]); 377 } 378 } 379 return currentPenalty; 380 } 381 382 public int getMaxPenalty(Assignment<Lecture, Placement> assignment, Placement placement) { 383 SpreadConstraintContext context = getContext(assignment); 384 int penalty = 0; 385 for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) { 386 int slot = e.nextElement(); 387 int day = slot / Constants.SLOTS_PER_DAY; 388 int time = slot % Constants.SLOTS_PER_DAY; 389 if (time < iFirstDaySlot || time > iLastDaySlot) 390 continue; 391 if (iLastWorkDay < 7) { 392 if (day < iFirstWorkDay || day > iLastWorkDay) 393 continue; 394 } else { 395 if (day < iFirstWorkDay && day > iLastWorkDay - 7) 396 continue; 397 if (day < iFirstWorkDay) day += 7; 398 } 399 int dif = 1 + context.getNrCourses(time, day, placement) - context.getMaxCourses(time, day); 400 if (dif > penalty) 401 penalty = dif; 402 } 403 return penalty; 404 } 405 406 /** Department balancing penalty of the given placement 407 * @param assignment current assignment 408 * @param placement a placement that is being considered 409 * @return change in the penalty if assigned 410 **/ 411 public int getPenalty(Assignment<Lecture, Placement> assignment, Placement placement) { 412 SpreadConstraintContext context = getContext(assignment); 413 int firstSlot = placement.getTimeLocation().getStartSlot(); 414 if (firstSlot > iLastDaySlot) 415 return 0; 416 int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1; 417 if (endSlot < iFirstDaySlot) 418 return 0; 419 int penalty = 0; 420 int min = Math.max(firstSlot, iFirstDaySlot); 421 int max = Math.min(endSlot, iLastDaySlot); 422 for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) { 423 int dayCode = Constants.DAY_CODES[j % 7]; 424 if ((dayCode & placement.getTimeLocation().getDayCode()) == 0) 425 continue; 426 for (int i = min; i <= max; i++) { 427 if (context.getNrCourses(i, j, placement) >= context.getMaxCourses(i, j)) 428 penalty++; 429 } 430 } 431 return penalty; 432 } 433 434 @Override 435 public void addVariable(Lecture lecture) { 436 if (lecture.canShareRoom()) { 437 for (GroupConstraint gc : lecture.groupConstraints()) { 438 if (gc.getType() == GroupConstraint.ConstraintType.MEET_WITH) { 439 if (gc.variables().indexOf(lecture) > 0) 440 return; 441 } 442 } 443 } 444 super.addVariable(lecture); 445 } 446 447 @Override 448 public void weaken(Assignment<Lecture, Placement> assignment, Placement value) { 449 while (inConflict(assignment, value)) 450 getContext(assignment).weaken(getContext(assignment).getCurrentPenalty() + getPenalty(assignment, value)); 451 } 452 453 @Override 454 public SpreadConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) { 455 return new SpreadConstraintContext(assignment); 456 } 457 458 public class SpreadConstraintContext implements AssignmentConstraintContext<Lecture, Placement> { 459 private int iMaxAllowedPenalty = 0; 460 private long iUnassignment = 0; 461 private Set<Placement>[][] iCourses = null; 462 private int iMaxCourses[][] = null; 463 private int iCurrentPenalty = 0; 464 465 @SuppressWarnings("unchecked") 466 public SpreadConstraintContext(Assignment<Lecture, Placement> assignment) { 467 iCourses = new Set[iLastDaySlot - iFirstDaySlot + 1][(iLastWorkDay - iFirstWorkDay + 1) % 7]; 468 if (iInteractive) 469 iUnassignmentsToWeaken = 0; 470 for (int i = 0; i < iCourses.length; i++) { 471 for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) { 472 iCourses[i][j] = new HashSet<Placement>(10); 473 } 474 } 475 double histogramPerDay[][] = new double[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1]; 476 iMaxCourses = new int[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1]; 477 for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++) 478 for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) 479 histogramPerDay[i][j] = 0.0; 480 int totalUsedSlots = 0; 481 for (Lecture lecture : variables()) { 482 List<Placement> values = lecture.values(assignment); 483 Placement firstPlacement = (values.isEmpty() ? null : values.get(0)); 484 if (firstPlacement != null) { 485 totalUsedSlots += firstPlacement.getTimeLocation().getNrSlotsPerMeeting() * firstPlacement.getTimeLocation().getNrMeetings(); 486 } 487 for (Placement p : values) { 488 int firstSlot = p.getTimeLocation().getStartSlot(); 489 if (firstSlot > iLastDaySlot) 490 continue; 491 int endSlot = firstSlot + p.getTimeLocation().getNrSlotsPerMeeting() - 1; 492 if (endSlot < iFirstDaySlot) 493 continue; 494 for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) { 495 int dayCode = p.getTimeLocation().getDayCode(); 496 for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) { 497 if ((dayCode & Constants.DAY_CODES[j % 7]) != 0) { 498 histogramPerDay[i - iFirstDaySlot][j - iFirstWorkDay] += 1.0 / values.size(); 499 } 500 } 501 } 502 } 503 } 504 // System.out.println("Histogram for department "+iDepartment+":"); 505 double threshold = iSpreadFactor * ((double) totalUsedSlots / ((iLastWorkDay - iFirstWorkDay + 1) * (iLastDaySlot - iFirstDaySlot + 1))); 506 // System.out.println("Threshold["+iDepartment+"] = "+threshold); 507 for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++) { 508 // System.out.println(" "+fmt(i+1)+": "+fmt(histogramPerDay[i])); 509 for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) { 510 iMaxCourses[i][j] = (int) (0.999 + (histogramPerDay[i][j] <= threshold ? iSpreadFactor * histogramPerDay[i][j] : histogramPerDay[i][j])); 511 } 512 } 513 for (Lecture lecture : variables()) { 514 Placement placement = assignment.getValue(lecture); 515 if (placement == null) 516 continue; 517 int firstSlot = placement.getTimeLocation().getStartSlot(); 518 if (firstSlot > iLastDaySlot) 519 continue; 520 int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1; 521 if (endSlot < iFirstDaySlot) 522 continue; 523 for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) { 524 for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) { 525 int dayCode = Constants.DAY_CODES[j % 7]; 526 if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) { 527 iCourses[i - iFirstDaySlot][j - iFirstWorkDay].add(placement); 528 } 529 } 530 } 531 } 532 iCurrentPenalty = 0; 533 for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++) { 534 for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) { 535 iCurrentPenalty += Math.max(0, iCourses[i][j].size() - iMaxCourses[i][j]); 536 } 537 } 538 iMaxAllowedPenalty = iCurrentPenalty; 539 getCriterion().inc(assignment, iCurrentPenalty); 540 } 541 542 543 @Override 544 public void assigned(Assignment<Lecture, Placement> assignment, Placement placement) { 545 int firstSlot = placement.getTimeLocation().getStartSlot(); 546 if (firstSlot > iLastDaySlot) 547 return; 548 int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1; 549 if (endSlot < iFirstDaySlot) 550 return; 551 getCriterion().inc(assignment, -iCurrentPenalty); 552 for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) { 553 for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) { 554 int dayCode = Constants.DAY_CODES[j % 7]; 555 if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) { 556 iCourses[i - iFirstDaySlot][j - iFirstWorkDay].add(placement); 557 if (iCourses[i - iFirstDaySlot][j - iFirstWorkDay].size() > iMaxCourses[i - iFirstDaySlot][j - iFirstWorkDay]) 558 iCurrentPenalty++; 559 } 560 } 561 } 562 getCriterion().inc(assignment, iCurrentPenalty); 563 } 564 565 @Override 566 public void unassigned(Assignment<Lecture, Placement> assignment, Placement placement) { 567 int firstSlot = placement.getTimeLocation().getStartSlot(); 568 if (firstSlot > iLastDaySlot) 569 return; 570 int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1; 571 if (endSlot < iFirstDaySlot) 572 return; 573 getCriterion().inc(assignment, -iCurrentPenalty); 574 for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) { 575 for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) { 576 int dayCode = Constants.DAY_CODES[j % 7]; 577 if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) { 578 if (iCourses[i - iFirstDaySlot][j - iFirstWorkDay].size() > iMaxCourses[i - iFirstDaySlot][j - iFirstWorkDay]) 579 iCurrentPenalty--; 580 iCourses[i - iFirstDaySlot][j - iFirstWorkDay].remove(placement); 581 } 582 } 583 } 584 getCriterion().inc(assignment, iCurrentPenalty); 585 } 586 587 public int[][] getMaxCourses() { 588 return iMaxCourses; 589 } 590 591 public int getMaxCourses(int time, int day) { 592 return iMaxCourses[time - iFirstDaySlot][day - iFirstWorkDay]; 593 } 594 595 public int getNrCourses(int time, int day, Placement placement) { 596 if (placement == null) return getCourses(time, day).size(); 597 int nrCourses = 0; 598 for (Placement p: getCourses(time, day)) 599 if (!p.variable().equals(placement.variable())) 600 nrCourses ++; 601 return nrCourses; 602 } 603 604 public Set<Placement> getCourses(int time, int day) { 605 return iCourses[time - iFirstDaySlot][day - iFirstWorkDay]; 606 } 607 608 public int getUnassignmentsToWeaken() { 609 return iUnassignmentsToWeaken; 610 } 611 612 public int getCurrentPenalty() { 613 return iCurrentPenalty; 614 } 615 616 public int getMaxAllowedPenalty() { 617 return iMaxAllowedPenalty; 618 } 619 620 public void weaken() { 621 if (iUnassignmentsToWeaken == 0) return; 622 iUnassignment++; 623 if (iUnassignment % iUnassignmentsToWeaken == 0) 624 iMaxAllowedPenalty++; 625 } 626 627 public void weaken(int penalty) { 628 if (penalty > iMaxAllowedPenalty) 629 iMaxAllowedPenalty = penalty; 630 } 631 632 } 633}