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