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