001package org.cpsolver.studentsct.extension; 002 003import java.util.ArrayList; 004import java.util.BitSet; 005import java.util.Collection; 006import java.util.HashMap; 007import java.util.HashSet; 008import java.util.Iterator; 009import java.util.List; 010import java.util.Map; 011import java.util.Set; 012 013import org.apache.log4j.Logger; 014import org.cpsolver.coursett.Constants; 015import org.cpsolver.coursett.model.Placement; 016import org.cpsolver.coursett.model.RoomLocation; 017import org.cpsolver.coursett.model.TimeLocation; 018import org.cpsolver.ifs.assignment.Assignment; 019import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext; 020import org.cpsolver.ifs.assignment.context.CanInheritContext; 021import org.cpsolver.ifs.assignment.context.ExtensionWithContext; 022import org.cpsolver.ifs.model.InfoProvider; 023import org.cpsolver.ifs.model.ModelListener; 024import org.cpsolver.ifs.solver.Solver; 025import org.cpsolver.ifs.util.DataProperties; 026import org.cpsolver.ifs.util.DistanceMetric; 027import org.cpsolver.studentsct.StudentSectioningModel; 028import org.cpsolver.studentsct.StudentSectioningModel.StudentSectioningModelContext; 029import org.cpsolver.studentsct.model.CourseRequest; 030import org.cpsolver.studentsct.model.Enrollment; 031import org.cpsolver.studentsct.model.FreeTimeRequest; 032import org.cpsolver.studentsct.model.Request; 033import org.cpsolver.studentsct.model.SctAssignment; 034import org.cpsolver.studentsct.model.Section; 035import org.cpsolver.studentsct.model.Student; 036import org.cpsolver.studentsct.model.Unavailability; 037 038/** 039 * This extension computes student schedule quality using various matrices. 040 * It replaces {@link TimeOverlapsCounter} and {@link DistanceConflict} extensions. 041 * Besides of time and distance conflicts, it also counts cases when a student 042 * has a lunch break conflict, travel time during the day, it can prefer 043 * or discourage student class back-to-backm and cases when a student has more than 044 * a given number of hours between the first and the last class on a day. 045 * See {@link StudentQuality.Type} for more details. 046 * 047 * <br> 048 * <br> 049 * 050 * @version StudentSct 1.3 (Student Sectioning)<br> 051 * Copyright (C) 2007 - 2014 Tomáš Müller<br> 052 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 053 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 054 * <br> 055 * This library is free software; you can redistribute it and/or modify 056 * it under the terms of the GNU Lesser General Public License as 057 * published by the Free Software Foundation; either version 3 of the 058 * License, or (at your option) any later version. <br> 059 * <br> 060 * This library is distributed in the hope that it will be useful, but 061 * WITHOUT ANY WARRANTY; without even the implied warranty of 062 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 063 * Lesser General Public License for more details. <br> 064 * <br> 065 * You should have received a copy of the GNU Lesser General Public 066 * License along with this library; if not see 067 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 068 */ 069 070public class StudentQuality extends ExtensionWithContext<Request, Enrollment, StudentQuality.StudentQualityContext> implements ModelListener<Request, Enrollment>, CanInheritContext<Request, Enrollment, StudentQuality.StudentQualityContext>, InfoProvider<Request, Enrollment> { 071 private static Logger sLog = Logger.getLogger(StudentQuality.class); 072 private Context iContext; 073 074 /** 075 * Constructor 076 * @param solver student scheduling solver 077 * @param properties solver configuration 078 */ 079 public StudentQuality(Solver<Request, Enrollment> solver, DataProperties properties) { 080 super(solver, properties); 081 if (solver != null) { 082 StudentSectioningModel model = (StudentSectioningModel) solver.currentSolution().getModel(); 083 iContext = new Context(model.getDistanceMetric(), properties); 084 model.setStudentQuality(this, false); 085 } else { 086 iContext = new Context(null, properties); 087 } 088 } 089 090 /** 091 * Constructor 092 * @param metrics distance metric 093 * @param properties solver configuration 094 */ 095 public StudentQuality(DistanceMetric metrics, DataProperties properties) { 096 super(null, properties); 097 iContext = new Context(metrics, properties); 098 } 099 100 /** 101 * Current distance metric 102 * @return distance metric 103 */ 104 public DistanceMetric getDistanceMetric() { 105 return iContext.getDistanceMetric(); 106 } 107 108 /** 109 * Is debugging enabled 110 * @return true when StudentQuality.Debug is true 111 */ 112 public boolean isDebug() { 113 return iContext.isDebug(); 114 } 115 116 /** 117 * Student quality context 118 */ 119 public Context getStudentQualityContext() { 120 return iContext; 121 } 122 123 /** 124 * Weighting types 125 */ 126 public static enum WeightType { 127 /** Penalty is incurred on the request with higher priority */ 128 HIGHER, 129 /** Penalty is incurred on the request with lower priority */ 130 LOWER, 131 /** Penalty is incurred on both requests */ 132 BOTH, 133 /** Penalty is incurred on the course request (for conflicts between course request and a free time) */ 134 REQUEST, 135 ; 136 } 137 138 /** 139 * Measured student qualities 140 * 141 */ 142 public static enum Type { 143 /** 144 * Time conflicts between two classes that is allowed. Time conflicts are penalized as shared time 145 * between two course requests proportional to the time of each, capped at one half of the time. 146 * This criterion is weighted by StudentWeights.TimeOverlapFactor, defaulting to 0.5. 147 */ 148 CourseTimeOverlap(WeightType.BOTH, "StudentWeights.TimeOverlapFactor", 0.5000, new Quality(){ 149 @Override 150 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 151 return r1 instanceof CourseRequest && r2 instanceof CourseRequest; 152 } 153 154 @Override 155 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { 156 if (a1.getTime() == null || a2.getTime() == null) return false; 157 if (((Section)a1).isToIgnoreStudentConflictsWith(a2.getId())) return false; 158 return a1.getTime().hasIntersection(a2.getTime()); 159 } 160 161 @Override 162 public int penalty(Context cx, SctAssignment a1, SctAssignment a2) { 163 if (!inConflict(cx, a1, a2)) return 0; 164 return a1.getTime().nrSharedDays(a2.getTime()) * a1.getTime().nrSharedHours(a2.getTime()); 165 } 166 167 @Override 168 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 169 return new Nothing(); 170 } 171 172 @Override 173 public double getWeight(Context cx, Conflict c, Enrollment e) { 174 return Math.min(cx.getTimeOverlapMaxLimit() * c.getPenalty() / e.getNrSlots(), cx.getTimeOverlapMaxLimit()); 175 } 176 }), 177 /** 178 * Time conflict between class and a free time request. Free time conflicts are penalized as the time 179 * of a course request overlapping with a free time proportional to the time of the request, capped at one half 180 * of the time. This criterion is weighted by StudentWeights.TimeOverlapFactor, defaulting to 0.5. 181 */ 182 FreeTimeOverlap(WeightType.REQUEST, "StudentWeights.TimeOverlapFactor", 0.5000, new Quality(){ 183 @Override 184 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 185 return false; 186 } 187 188 @Override 189 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { 190 if (a1.getTime() == null || a2.getTime() == null) return false; 191 return a1.getTime().hasIntersection(a2.getTime()); 192 } 193 194 @Override 195 public int penalty(Context cx, SctAssignment a1, SctAssignment a2) { 196 if (!inConflict(cx, a1, a2)) return 0; 197 return a1.getTime().nrSharedDays(a2.getTime()) * a1.getTime().nrSharedHours(a2.getTime()); 198 } 199 200 @Override 201 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 202 return (e.isCourseRequest() ? new FreeTimes(e.getStudent()) : new Nothing()); 203 } 204 205 @Override 206 public double getWeight(Context cx, Conflict c, Enrollment e) { 207 return Math.min(cx.getTimeOverlapMaxLimit() * c.getPenalty() / c.getE1().getNrSlots(), cx.getTimeOverlapMaxLimit()); 208 } 209 }), 210 /** 211 * Student unavailability conflict. Time conflict between a class that the student is taking and a class that the student 212 * is teaching (if time conflicts are allowed). Unavailability conflicts are penalized as the time 213 * of a course request overlapping with an unavailability proportional to the time of the request, capped at one half 214 * of the time. This criterion is weighted by StudentWeights.TimeOverlapFactor, defaulting to 0.5. 215 */ 216 Unavailability(WeightType.REQUEST, "StudentWeights.TimeOverlapFactor", 0.5000, new Quality(){ 217 @Override 218 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 219 return false; 220 } 221 222 @Override 223 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { 224 if (a1.getTime() == null || a2.getTime() == null) return false; 225 return a1.getTime().hasIntersection(a2.getTime()); 226 } 227 228 @Override 229 public int penalty(Context cx, SctAssignment a1, SctAssignment a2) { 230 if (!inConflict(cx, a1, a2)) return 0; 231 return a1.getTime().nrSharedDays(a2.getTime()) * a1.getTime().nrSharedHours(a2.getTime()); 232 } 233 234 @Override 235 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 236 return (e.isCourseRequest() ? new Unavailabilities(e.getStudent()) : new Nothing()); 237 } 238 239 @Override 240 public double getWeight(Context cx, Conflict c, Enrollment e) { 241 return Math.min(cx.getTimeOverlapMaxLimit() * c.getPenalty() / c.getE1().getNrSlots(), cx.getTimeOverlapMaxLimit()); 242 } 243 }), 244 /** 245 * Distance conflict. When Distances.ComputeDistanceConflictsBetweenNonBTBClasses is set to false, 246 * distance conflicts are only considered between back-to-back classes (break time of the first 247 * class is shorter than the distance in minutes between the two classes). When 248 * Distances.ComputeDistanceConflictsBetweenNonBTBClasses is set to true, the distance between the 249 * two classes is also considered. 250 * This criterion is weighted by StudentWeights.DistanceConflict, defaulting to 0.01. 251 */ 252 Distance(WeightType.LOWER, "StudentWeights.DistanceConflict", 0.0100, new Quality(){ 253 @Override 254 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 255 return r1 instanceof CourseRequest && r2 instanceof CourseRequest; 256 } 257 258 @Override 259 public boolean inConflict(Context cx, SctAssignment sa1, SctAssignment sa2) { 260 Section s1 = (Section) sa1; 261 Section s2 = (Section) sa2; 262 if (s1.getPlacement() == null || s2.getPlacement() == null) 263 return false; 264 TimeLocation t1 = s1.getTime(); 265 TimeLocation t2 = s2.getTime(); 266 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) 267 return false; 268 int a1 = t1.getStartSlot(), a2 = t2.getStartSlot(); 269 if (cx.getDistanceMetric().doComputeDistanceConflictsBetweenNonBTBClasses()) { 270 if (a1 + t1.getNrSlotsPerMeeting() <= a2) { 271 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 272 if (dist > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength())) 273 return true; 274 } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) { 275 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 276 if (dist > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength())) 277 return true; 278 } 279 } else { 280 if (a1 + t1.getNrSlotsPerMeeting() == a2) { 281 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 282 if (dist > t1.getBreakTime()) 283 return true; 284 } else if (a2 + t2.getNrSlotsPerMeeting() == a1) { 285 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 286 if (dist > t2.getBreakTime()) 287 return true; 288 } 289 } 290 return false; 291 } 292 293 @Override 294 public int penalty(Context cx, SctAssignment a1, SctAssignment a2) { 295 return inConflict(cx, a1, a2) ? 1 : 0; 296 } 297 298 @Override 299 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 300 return new Nothing(); 301 } 302 303 @Override 304 public double getWeight(Context cx, Conflict c, Enrollment e) { 305 return c.getPenalty(); 306 } 307 }), 308 /** 309 * Short distance conflict. Similar to distance conflicts but for students that require short 310 * distances. When Distances.ComputeDistanceConflictsBetweenNonBTBClasses is set to false, 311 * distance conflicts are only considered between back-to-back classes (travel time between the 312 * two classes is more than zero minutes). When 313 * Distances.ComputeDistanceConflictsBetweenNonBTBClasses is set to true, the distance between the 314 * two classes is also considered (break time is also ignored). 315 * This criterion is weighted by StudentWeights.ShortDistanceConflict, defaulting to 0.1. 316 */ 317 ShortDistance(WeightType.LOWER, "StudentWeights.ShortDistanceConflict", 0.1000, new Quality(){ 318 @Override 319 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 320 return student.isNeedShortDistances() && r1 instanceof CourseRequest && r2 instanceof CourseRequest; 321 } 322 323 @Override 324 public boolean inConflict(Context cx, SctAssignment sa1, SctAssignment sa2) { 325 Section s1 = (Section) sa1; 326 Section s2 = (Section) sa2; 327 if (s1.getPlacement() == null || s2.getPlacement() == null) 328 return false; 329 TimeLocation t1 = s1.getTime(); 330 TimeLocation t2 = s2.getTime(); 331 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) 332 return false; 333 int a1 = t1.getStartSlot(), a2 = t2.getStartSlot(); 334 if (cx.getDistanceMetric().doComputeDistanceConflictsBetweenNonBTBClasses()) { 335 if (a1 + t1.getNrSlotsPerMeeting() <= a2) { 336 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 337 if (dist > Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength())) 338 return true; 339 } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) { 340 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 341 if (dist > Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength())) 342 return true; 343 } 344 } else { 345 if (a1 + t1.getNrSlotsPerMeeting() == a2) { 346 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 347 if (dist > 0) return true; 348 } else if (a2 + t2.getNrSlotsPerMeeting() == a1) { 349 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 350 if (dist > 0) return true; 351 } 352 } 353 return false; 354 } 355 356 @Override 357 public int penalty(Context cx, SctAssignment a1, SctAssignment a2) { 358 return inConflict(cx, a1, a2) ? 1 : 0; 359 } 360 361 @Override 362 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 363 return new Nothing(); 364 } 365 366 @Override 367 public double getWeight(Context cx, Conflict c, Enrollment e) { 368 return c.getPenalty(); 369 } 370 }), 371 /** 372 * Naive, yet effective approach for modeling student lunch breaks. It creates a conflict whenever there are 373 * two classes (of a student) overlapping with the lunch time which are one after the other with a break in 374 * between smaller than the requested lunch break. Lunch time is defined by StudentLunch.StartSlot and 375 * StudentLunch.EndStart properties (default is 11:00 am - 1:30 pm), with lunch break of at least 376 * StudentLunch.Length slots (default is 30 minutes). Such a conflict is weighted 377 * by StudentWeights.LunchBreakFactor, which defaults to 0.005. 378 */ 379 LunchBreak(WeightType.BOTH, "StudentWeights.LunchBreakFactor", 0.0050, new Quality() { 380 @Override 381 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 382 return r1 instanceof CourseRequest && r2 instanceof CourseRequest && !student.isDummy(); 383 } 384 385 @Override 386 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { 387 if (a1.getTime() == null || a2.getTime() == null) return false; 388 if (((Section)a1).isToIgnoreStudentConflictsWith(a2.getId())) return false; 389 if (a1.getTime().hasIntersection(a2.getTime())) return false; 390 TimeLocation t1 = a1.getTime(), t2 = a2.getTime(); 391 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) return false; 392 int s1 = t1.getStartSlot(), s2 = t2.getStartSlot(); 393 int e1 = t1.getStartSlot() + t1.getNrSlotsPerMeeting(), e2 = t2.getStartSlot() + t2.getNrSlotsPerMeeting(); 394 if (e1 + cx.getLunchLength() > s2 && e2 + cx.getLunchLength() > s1 && e1 > cx.getLunchStart() && cx.getLunchEnd() > s1 && e2 > cx.getLunchStart() && cx.getLunchEnd() > s2) 395 return true; 396 return false; 397 } 398 399 @Override 400 public int penalty(Context cx, SctAssignment a1, SctAssignment a2) { 401 if (!inConflict(cx, a1, a2)) return 0; 402 return a1.getTime().nrSharedDays(a2.getTime()); 403 } 404 405 @Override 406 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 407 return new Nothing(); 408 } 409 410 @Override 411 public double getWeight(Context cx, Conflict c, Enrollment e) { 412 return c.getPenalty(); 413 } 414 }), 415 /** 416 * Naive, yet effective approach for modeling travel times. A conflict with the penalty 417 * equal to the distance in minutes occurs when two classes are less than TravelTime.MaxTravelGap 418 * time slots a part (defaults 1 hour), or when they are less then twice as long apart 419 * and the travel time is longer than the break time of the first class. 420 * Such a conflict is weighted by StudentWeights.TravelTimeFactor, which defaults to 0.001. 421 */ 422 TravelTime(WeightType.BOTH, "StudentWeights.TravelTimeFactor", 0.0010, new Quality() { 423 @Override 424 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 425 return r1 instanceof CourseRequest && r2 instanceof CourseRequest && !student.isDummy(); 426 } 427 428 @Override 429 public boolean inConflict(Context cx, SctAssignment sa1, SctAssignment sa2) { 430 Section s1 = (Section) sa1; 431 Section s2 = (Section) sa2; 432 if (s1.getPlacement() == null || s2.getPlacement() == null) 433 return false; 434 TimeLocation t1 = s1.getTime(); 435 TimeLocation t2 = s2.getTime(); 436 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) 437 return false; 438 int a1 = t1.getStartSlot(), a2 = t2.getStartSlot(); 439 if (a1 + t1.getNrSlotsPerMeeting() <= a2) { 440 int gap = a2 - (a1 + t1.getNrSlotsPerMeeting()); 441 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 442 return (gap < cx.getMaxTravelGap() && dist > 0) || (gap < 2 * cx.getMaxTravelGap() && dist > t1.getBreakTime()); 443 } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) { 444 int gap = a1 - (a2 + t2.getNrSlotsPerMeeting()); 445 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 446 return (gap < cx.getMaxTravelGap() && dist > 0) || (gap < 2 * cx.getMaxTravelGap() && dist > t2.getBreakTime()); 447 } 448 return false; 449 } 450 451 @Override 452 public int penalty(Context cx, SctAssignment sa1, SctAssignment sa2) { 453 Section s1 = (Section) sa1; 454 Section s2 = (Section) sa2; 455 if (s1.getPlacement() == null || s2.getPlacement() == null) return 0; 456 TimeLocation t1 = s1.getTime(); 457 TimeLocation t2 = s2.getTime(); 458 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) return 0; 459 int a1 = t1.getStartSlot(), a2 = t2.getStartSlot(); 460 if (a1 + t1.getNrSlotsPerMeeting() <= a2) { 461 int gap = a2 - (a1 + t1.getNrSlotsPerMeeting()); 462 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 463 if ((gap < cx.getMaxTravelGap() && dist > 0) || (gap < 2 * cx.getMaxTravelGap() && dist > t1.getBreakTime())) 464 return dist; 465 } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) { 466 int gap = a1 - (a2 + t2.getNrSlotsPerMeeting()); 467 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 468 if ((gap < cx.getMaxTravelGap() && dist > 0) || (gap < 2 * cx.getMaxTravelGap() && dist > t2.getBreakTime())) 469 return dist; 470 } 471 return 0; 472 } 473 474 @Override 475 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 476 return new Nothing(); 477 } 478 479 @Override 480 public double getWeight(Context cx, Conflict c, Enrollment e) { 481 return c.getPenalty(); 482 } 483 }), 484 /** 485 * A back-to-back conflict is there every time when a student has two classes that are 486 * back-to-back or less than StudentWeights.BackToBackDistance time slots apart (defaults to 30 minutes). 487 * Such a conflict is weighted by StudentWeights.BackToBackFactor, which 488 * defaults to -0.0001 (these conflicts are preferred by default, trying to avoid schedule gaps). 489 */ 490 BackToBack(WeightType.BOTH, "StudentWeights.BackToBackFactor", -0.0001, new Quality() { 491 @Override 492 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 493 return r1 instanceof CourseRequest && r2 instanceof CourseRequest && !student.isDummy(); 494 } 495 496 @Override 497 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { 498 TimeLocation t1 = a1.getTime(); 499 TimeLocation t2 = a2.getTime(); 500 if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return false; 501 if (t1.getStartSlot() + t1.getNrSlotsPerMeeting() <= t2.getStartSlot()) { 502 int dist = t2.getStartSlot() - (t1.getStartSlot() + t1.getNrSlotsPerMeeting()); 503 return dist <= cx.getBackToBackDistance(); 504 } else if (t2.getStartSlot() + t2.getNrSlotsPerMeeting() <= t1.getStartSlot()) { 505 int dist = t1.getStartSlot() - (t2.getStartSlot() + t2.getNrSlotsPerMeeting()); 506 return dist <= cx.getBackToBackDistance(); 507 } 508 return false; 509 } 510 511 @Override 512 public int penalty(Context cx, SctAssignment a1, SctAssignment a2) { 513 if (!inConflict(cx, a1, a2)) return 0; 514 return a1.getTime().nrSharedDays(a2.getTime()); 515 } 516 517 @Override 518 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 519 return new Nothing(); 520 } 521 522 @Override 523 public double getWeight(Context cx, Conflict c, Enrollment e) { 524 return c.getPenalty(); 525 } 526 }), 527 /** 528 * A work-day conflict is there every time when a student has two classes that are too 529 * far apart. This means that the time between the start of the first class and the end 530 * of the last class is more than WorkDay.WorkDayLimit (defaults to 6 hours). A penalty 531 * of one is incurred for every hour started over this limit. 532 * Such a conflict is weighted by StudentWeights.WorkDayFactor, which defaults to 0.01. 533 */ 534 WorkDay(WeightType.BOTH, "StudentWeights.WorkDayFactor", 0.0100, new Quality() { 535 @Override 536 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 537 return r1 instanceof CourseRequest && r2 instanceof CourseRequest && !student.isDummy(); 538 } 539 540 @Override 541 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { 542 TimeLocation t1 = a1.getTime(); 543 TimeLocation t2 = a2.getTime(); 544 if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return false; 545 int dist = Math.max(t1.getStartSlot() + t1.getLength(), t2.getStartSlot() + t2.getLength()) - Math.min(t1.getStartSlot(), t2.getStartSlot()); 546 return dist > cx.getWorkDayLimit(); 547 } 548 549 @Override 550 public int penalty(Context cx, SctAssignment a1, SctAssignment a2) { 551 TimeLocation t1 = a1.getTime(); 552 TimeLocation t2 = a2.getTime(); 553 if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return 0; 554 int dist = Math.max(t1.getStartSlot() + t1.getLength(), t2.getStartSlot() + t2.getLength()) - Math.min(t1.getStartSlot(), t2.getStartSlot()); 555 if (dist > cx.getWorkDayLimit()) 556 return a1.getTime().nrSharedDays(a2.getTime()) * (dist - cx.getWorkDayLimit()); 557 else 558 return 0; 559 } 560 561 @Override 562 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 563 return new Nothing(); 564 } 565 566 @Override 567 public double getWeight(Context cx, Conflict c, Enrollment e) { 568 return c.getPenalty() / 12.0; 569 } 570 }), 571 TooEarly(WeightType.REQUEST, "StudentWeights.TooEarlyFactor", 0.0500, new Quality(){ 572 @Override 573 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 574 return false; 575 } 576 577 @Override 578 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { 579 if (a1.getTime() == null || a2.getTime() == null) return false; 580 return a1.getTime().shareDays(a2.getTime()) && a1.getTime().shareHours(a2.getTime()); 581 } 582 583 @Override 584 public int penalty(Context cx, SctAssignment a1, SctAssignment a2) { 585 if (!inConflict(cx, a1, a2)) return 0; 586 return a1.getTime().nrSharedDays(a2.getTime()) * a1.getTime().nrSharedHours(a2.getTime()); 587 } 588 589 @Override 590 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 591 return (e.isCourseRequest() ? new SingleTimeIterable(0, cx.getEarlySlot()) : new Nothing()); 592 } 593 594 @Override 595 public double getWeight(Context cx, Conflict c, Enrollment e) { 596 return Math.min(cx.getTimeOverlapMaxLimit() * c.getPenalty() / c.getE1().getNrSlots(), cx.getTimeOverlapMaxLimit()); 597 } 598 }), 599 TooLate(WeightType.REQUEST, "StudentWeights.TooLateFactor", 0.0250, new Quality(){ 600 @Override 601 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 602 return false; 603 } 604 605 @Override 606 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { 607 if (a1.getTime() == null || a2.getTime() == null) return false; 608 return a1.getTime().shareDays(a2.getTime()) && a1.getTime().shareHours(a2.getTime()); 609 } 610 611 @Override 612 public int penalty(Context cx, SctAssignment a1, SctAssignment a2) { 613 if (!inConflict(cx, a1, a2)) return 0; 614 return a1.getTime().nrSharedDays(a2.getTime()) * a1.getTime().nrSharedHours(a2.getTime()); 615 } 616 617 @Override 618 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 619 return (e.isCourseRequest() ? new SingleTimeIterable(cx.getLateSlot(), 288) : new Nothing()); 620 } 621 622 @Override 623 public double getWeight(Context cx, Conflict c, Enrollment e) { 624 return Math.min(cx.getTimeOverlapMaxLimit() * c.getPenalty() / c.getE1().getNrSlots(), cx.getTimeOverlapMaxLimit()); 625 } 626 }), 627 /** 628 * DRC: Time conflict between class and a free time request (for students with FT accommodation). 629 * Free time conflicts are penalized as the time of a course request overlapping with a free time 630 * proportional to the time of the request, capped at one half of the time. 631 * This criterion is weighted by Accommodations.FreeTimeOverlapFactor, defaulting to 0.5. 632 */ 633 AccFreeTimeOverlap(WeightType.REQUEST, "Accommodations.FreeTimeOverlapFactor", 0.5000, new Quality(){ 634 @Override 635 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 636 return false; 637 } 638 639 @Override 640 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { 641 if (a1.getTime() == null || a2.getTime() == null) return false; 642 return a1.getTime().hasIntersection(a2.getTime()); 643 } 644 645 @Override 646 public int penalty(Context cx, SctAssignment a1, SctAssignment a2) { 647 if (!inConflict(cx, a1, a2)) return 0; 648 return a1.getTime().nrSharedDays(a2.getTime()) * a1.getTime().nrSharedHours(a2.getTime()); 649 } 650 651 @Override 652 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 653 if (!e.getStudent().hasAccommodation(cx.getFreeTimeAccommodation())) return new Nothing(); 654 return (e.isCourseRequest() ? new FreeTimes(e.getStudent()) : new Nothing()); 655 } 656 657 @Override 658 public double getWeight(Context cx, Conflict c, Enrollment e) { 659 return Math.min(cx.getTimeOverlapMaxLimit() * c.getPenalty() / c.getE1().getNrSlots(), cx.getTimeOverlapMaxLimit()); 660 } 661 }), 662 /** 663 * DRC: A back-to-back conflict (for students with BTB accommodation) is there every time when a student has two classes that are NOT 664 * back-to-back or less than Accommodations.BackToBackDistance time slots apart (defaults to 30 minutes). 665 * Such a conflict is weighted by Accommodations.BackToBackFactor, which defaults to 0.001 666 */ 667 AccBackToBack(WeightType.BOTH, "Accommodations.BackToBackFactor", 0.001, new Quality() { 668 @Override 669 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 670 return r1 instanceof CourseRequest && r2 instanceof CourseRequest && !student.isDummy() && student.hasAccommodation(cx.getBackToBackAccommodation()); 671 } 672 673 @Override 674 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { 675 TimeLocation t1 = a1.getTime(); 676 TimeLocation t2 = a2.getTime(); 677 if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return false; 678 if (t1.getStartSlot() + t1.getNrSlotsPerMeeting() <= t2.getStartSlot()) { 679 int dist = t2.getStartSlot() - (t1.getStartSlot() + t1.getNrSlotsPerMeeting()); 680 return dist > cx.getBackToBackDistance(); 681 } else if (t2.getStartSlot() + t2.getNrSlotsPerMeeting() <= t1.getStartSlot()) { 682 int dist = t1.getStartSlot() - (t2.getStartSlot() + t2.getNrSlotsPerMeeting()); 683 return dist > cx.getBackToBackDistance(); 684 } 685 return false; 686 } 687 688 @Override 689 public int penalty(Context cx, SctAssignment a1, SctAssignment a2) { 690 if (!inConflict(cx, a1, a2)) return 0; 691 return a1.getTime().nrSharedDays(a2.getTime()); 692 } 693 694 @Override 695 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 696 return new Nothing(); 697 } 698 699 @Override 700 public double getWeight(Context cx, Conflict c, Enrollment e) { 701 return c.getPenalty(); 702 } 703 }), 704 /** 705 * DRC: A not back-to-back conflict (for students with BBC accommodation) is there every time when a student has two classes that are 706 * back-to-back or less than Accommodations.BackToBackDistance time slots apart (defaults to 30 minutes). 707 * Such a conflict is weighted by Accommodations.BreaksBetweenClassesFactor, which defaults to 0.001. 708 */ 709 AccBreaksBetweenClasses(WeightType.BOTH, "Accommodations.BreaksBetweenClassesFactor", 0.001, new Quality() { 710 @Override 711 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 712 return r1 instanceof CourseRequest && r2 instanceof CourseRequest && !student.isDummy() && student.hasAccommodation(cx.getBreakBetweenClassesAccommodation()); 713 } 714 715 @Override 716 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { 717 TimeLocation t1 = a1.getTime(); 718 TimeLocation t2 = a2.getTime(); 719 if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return false; 720 if (t1.getStartSlot() + t1.getNrSlotsPerMeeting() <= t2.getStartSlot()) { 721 int dist = t2.getStartSlot() - (t1.getStartSlot() + t1.getNrSlotsPerMeeting()); 722 return dist <= cx.getBackToBackDistance(); 723 } else if (t2.getStartSlot() + t2.getNrSlotsPerMeeting() <= t1.getStartSlot()) { 724 int dist = t1.getStartSlot() - (t2.getStartSlot() + t2.getNrSlotsPerMeeting()); 725 return dist <= cx.getBackToBackDistance(); 726 } 727 return false; 728 } 729 730 @Override 731 public int penalty(Context cx, SctAssignment a1, SctAssignment a2) { 732 if (!inConflict(cx, a1, a2)) return 0; 733 return a1.getTime().nrSharedDays(a2.getTime()); 734 } 735 736 @Override 737 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 738 return new Nothing(); 739 } 740 741 @Override 742 public double getWeight(Context cx, Conflict c, Enrollment e) { 743 return c.getPenalty(); 744 } 745 }), 746 ; 747 748 private WeightType iType; 749 private Quality iQuality; 750 private String iWeightName; 751 private double iWeightDefault; 752 Type(WeightType type, String weightName, double weightDefault, Quality quality) { 753 iQuality = quality; 754 iType = type; 755 iWeightName = weightName; 756 iWeightDefault = weightDefault; 757 } 758 759 760 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { return iQuality.isApplicable(cx, student, r1, r2); } 761 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { return iQuality.inConflict(cx, a1, a2); } 762 public int penalty(Context cx, SctAssignment a1, SctAssignment a2) { return iQuality.penalty(cx, a1, a2); } 763 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { return iQuality.other(cx, e); } 764 public double getWeight(Context cx, Conflict c, Enrollment e) { return iQuality.getWeight(cx, c, e); } 765 public String getName() { return name().replaceAll("(?<=[^A-Z0-9])([A-Z0-9])"," $1"); } 766 public String getAbbv() { return getName().replaceAll("[a-z ]",""); } 767 public WeightType getType() { return iType; } 768 public String getWeightName() { return iWeightName; } 769 public double getWeightDefault() { return iWeightDefault; } 770 } 771 772 /** 773 * Schedule quality interface 774 */ 775 public static interface Quality { 776 /** 777 * Check if the metric is applicable for the given student, between the given two requests 778 */ 779 public boolean isApplicable(Context cx, Student student, Request r1, Request r2); 780 /** 781 * When applicable, is there a conflict between two sections 782 */ 783 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2); 784 /** 785 * When in conflict, what is the penalisation 786 */ 787 public int penalty(Context cx, SctAssignment a1, SctAssignment a2); 788 /** 789 * Enumerate other section assignments applicable for the given enrollment (e.g., student unavailabilities) 790 */ 791 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e); 792 /** 793 * Base weight of the given conflict and enrollment. Typically based on the {@link Conflict#getPenalty()}, but 794 * change to be between 0.0 and 1.0. For example, for time conflicts, a percentage of share is used. 795 */ 796 public double getWeight(Context cx, Conflict c, Enrollment e); 797 } 798 799 /** 800 * Penalisation of the given type between two enrollments of a student. 801 */ 802 public int penalty(Type type, Enrollment e1, Enrollment e2) { 803 if (!e1.getStudent().equals(e2.getStudent()) || !type.isApplicable(iContext, e1.getStudent(), e1.getRequest(), e2.getRequest())) return 0; 804 int cnt = 0; 805 for (SctAssignment s1 : e1.getAssignments()) { 806 for (SctAssignment s2 : e2.getAssignments()) { 807 cnt += type.penalty(iContext, s1, s2); 808 } 809 } 810 return cnt; 811 } 812 813 /** 814 * Conflicss of the given type between two enrollments of a student. 815 */ 816 public Set<Conflict> conflicts(Type type, Enrollment e1, Enrollment e2) { 817 Set<Conflict> ret = new HashSet<Conflict>(); 818 if (!e1.getStudent().equals(e2.getStudent()) || !type.isApplicable(iContext, e1.getStudent(), e1.getRequest(), e2.getRequest())) return ret; 819 for (SctAssignment s1 : e1.getAssignments()) { 820 for (SctAssignment s2 : e2.getAssignments()) { 821 int penalty = type.penalty(iContext, s1, s2); 822 if (penalty > 0) 823 ret.add(new Conflict(e1.getStudent(), type, penalty, e1, s1, e2, s2)); 824 } 825 } 826 return ret; 827 } 828 829 /** 830 * Conflicts of any type between two enrollments of a student. 831 */ 832 public Set<Conflict> conflicts(Enrollment e1, Enrollment e2) { 833 Set<Conflict> ret = new HashSet<Conflict>(); 834 for (Type type: iContext.getTypes()) { 835 if (!e1.getStudent().equals(e2.getStudent()) || !type.isApplicable(iContext, e1.getStudent(), e1.getRequest(), e2.getRequest())) continue; 836 for (SctAssignment s1 : e1.getAssignments()) { 837 for (SctAssignment s2 : e2.getAssignments()) { 838 int penalty = type.penalty(iContext, s1, s2); 839 if (penalty > 0) 840 ret.add(new Conflict(e1.getStudent(), type, penalty, e1, s1, e2, s2)); 841 } 842 } 843 } 844 return ret; 845 } 846 847 /** 848 * Conflicts of the given type between classes of a single enrollment (or with free times, unavailabilities, etc.) 849 */ 850 public Set<Conflict> conflicts(Type type, Enrollment e1) { 851 Set<Conflict> ret = new HashSet<Conflict>(); 852 boolean applicable = type.isApplicable(iContext, e1.getStudent(), e1.getRequest(), e1.getRequest()); 853 for (SctAssignment s1 : e1.getAssignments()) { 854 if (applicable) { 855 for (SctAssignment s2 : e1.getAssignments()) { 856 if (s1.getId() < s2.getId()) { 857 int penalty = type.penalty(iContext, s1, s2); 858 if (penalty > 0) 859 ret.add(new Conflict(e1.getStudent(), type, penalty, e1, s1, e1, s2)); 860 } 861 } 862 } 863 for (SctAssignment s2: type.other(iContext, e1)) { 864 int penalty = type.penalty(iContext, s1, s2); 865 if (penalty > 0) 866 ret.add(new Conflict(e1.getStudent(), type, penalty, e1, s1, s2)); 867 } 868 } 869 return ret; 870 } 871 872 /** 873 * Conflicts of any type between classes of a single enrollment (or with free times, unavailabilities, etc.) 874 */ 875 public Set<Conflict> conflicts(Enrollment e1) { 876 Set<Conflict> ret = new HashSet<Conflict>(); 877 for (Type type: iContext.getTypes()) { 878 boolean applicable = type.isApplicable(iContext, e1.getStudent(), e1.getRequest(), e1.getRequest()); 879 for (SctAssignment s1 : e1.getAssignments()) { 880 if (applicable) { 881 for (SctAssignment s2 : e1.getAssignments()) { 882 if (s1.getId() < s2.getId()) { 883 int penalty = type.penalty(iContext, s1, s2); 884 if (penalty > 0) 885 ret.add(new Conflict(e1.getStudent(), type, penalty, e1, s1, e1, s2)); 886 } 887 } 888 } 889 for (SctAssignment s2: type.other(iContext, e1)) { 890 int penalty = type.penalty(iContext, s1, s2); 891 if (penalty > 0) 892 ret.add(new Conflict(e1.getStudent(), type, penalty, e1, s1, s2)); 893 } 894 } 895 } 896 return ret; 897 } 898 899 /** 900 * Penalty of given type between classes of a single enrollment (or with free times, unavailabilities, etc.) 901 */ 902 public int penalty(Type type, Enrollment e1) { 903 int penalty = 0; 904 boolean applicable = type.isApplicable(iContext, e1.getStudent(), e1.getRequest(), e1.getRequest()); 905 for (SctAssignment s1 : e1.getAssignments()) { 906 if (applicable) { 907 for (SctAssignment s2 : e1.getAssignments()) { 908 if (s1.getId() < s2.getId()) { 909 penalty += type.penalty(iContext, s1, s2); 910 } 911 } 912 } 913 for (SctAssignment s2: type.other(iContext, e1)) { 914 penalty += type.penalty(iContext, s1, s2); 915 } 916 } 917 return penalty; 918 } 919 920 /** 921 * Check whether the given type is applicable for the student and the two requests. 922 */ 923 public boolean isApplicable(Type type, Student student, Request r1, Request r2) { 924 return type.isApplicable(iContext, student, r1, r2); 925 } 926 927 /** 928 * Total penalisation of given type 929 */ 930 public int getTotalPenalty(Type type, Assignment<Request, Enrollment> assignment) { 931 return getContext(assignment).getTotalPenalty(type); 932 } 933 934 /** 935 * Total penalisation of given types 936 */ 937 public int getTotalPenalty(Assignment<Request, Enrollment> assignment, Type... types) { 938 int ret = 0; 939 for (Type type: types) 940 ret += getContext(assignment).getTotalPenalty(type); 941 return ret; 942 } 943 944 /** 945 * Re-check total penalization for the given assignment 946 */ 947 public void checkTotalPenalty(Assignment<Request, Enrollment> assignment) { 948 for (Type type: iContext.getTypes()) 949 checkTotalPenalty(type, assignment); 950 } 951 952 /** 953 * Re-check total penalization for the given assignment and conflict type 954 */ 955 public void checkTotalPenalty(Type type, Assignment<Request, Enrollment> assignment) { 956 getContext(assignment).checkTotalPenalty(type, assignment); 957 } 958 959 /** 960 * All conflicts of the given type for the given assignment 961 */ 962 public Set<Conflict> getAllConflicts(Type type, Assignment<Request, Enrollment> assignment) { 963 return getContext(assignment).getAllConflicts(type); 964 } 965 966 /** 967 * All conflicts of the any type for the enrollment (including conflicts with other enrollments of the student) 968 */ 969 public Set<Conflict> allConflicts(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 970 Set<Conflict> conflicts = new HashSet<Conflict>(); 971 for (Type t: iContext.getTypes()) { 972 conflicts.addAll(conflicts(t, enrollment)); 973 for (Request request : enrollment.getStudent().getRequests()) { 974 if (request.equals(enrollment.getRequest()) || assignment.getValue(request) == null) continue; 975 conflicts.addAll(conflicts(t, enrollment, assignment.getValue(request))); 976 } 977 } 978 return conflicts; 979 } 980 981 @Override 982 public void beforeAssigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) { 983 getContext(assignment).beforeAssigned(assignment, iteration, value); 984 } 985 986 @Override 987 public void afterAssigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) { 988 getContext(assignment).afterAssigned(assignment, iteration, value); 989 } 990 991 @Override 992 public void afterUnassigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) { 993 getContext(assignment).afterUnassigned(assignment, iteration, value); 994 } 995 996 /** A representation of a time overlapping conflict */ 997 public class Conflict { 998 private Type iType; 999 private int iPenalty; 1000 private Student iStudent; 1001 private SctAssignment iA1, iA2; 1002 private Enrollment iE1, iE2; 1003 private int iHashCode; 1004 1005 /** 1006 * Constructor 1007 * 1008 * @param student related student 1009 * @param type conflict type 1010 * @param penalty conflict penalization, e.g., the number of slots in common between the two conflicting sections 1011 * @param e1 first enrollment 1012 * @param a1 first conflicting section 1013 * @param e2 second enrollment 1014 * @param a2 second conflicting section 1015 */ 1016 public Conflict(Student student, Type type, int penalty, Enrollment e1, SctAssignment a1, Enrollment e2, SctAssignment a2) { 1017 iStudent = student; 1018 if (a1.compareById(a2) < 0 ) { 1019 iA1 = a1; 1020 iA2 = a2; 1021 iE1 = e1; 1022 iE2 = e2; 1023 } else { 1024 iA1 = a2; 1025 iA2 = a1; 1026 iE1 = e2; 1027 iE2 = e1; 1028 } 1029 iHashCode = (iStudent.getId() + ":" + iA1.getId() + ":" + iA2.getId()).hashCode(); 1030 iType = type; 1031 iPenalty = penalty; 1032 } 1033 1034 public Conflict(Student student, Type type, int penalty, Enrollment e1, SctAssignment a1, SctAssignment a2) { 1035 this(student, type, penalty, e1, a1, a2 instanceof FreeTimeRequest ? ((FreeTimeRequest)a2).createEnrollment() : a2 instanceof Unavailability ? ((Unavailability)a2).createEnrollment() : e1, a2); 1036 1037 } 1038 1039 /** Related student 1040 * @return student 1041 **/ 1042 public Student getStudent() { 1043 return iStudent; 1044 } 1045 1046 /** First section 1047 * @return first section 1048 **/ 1049 public SctAssignment getS1() { 1050 return iA1; 1051 } 1052 1053 /** Second section 1054 * @return second section 1055 **/ 1056 public SctAssignment getS2() { 1057 return iA2; 1058 } 1059 1060 /** First request 1061 * @return first request 1062 **/ 1063 public Request getR1() { 1064 return iE1.getRequest(); 1065 } 1066 1067 /** First request weight 1068 * @return first request weight 1069 **/ 1070 public double getR1Weight() { 1071 return (iE1.getRequest() == null ? 0.0 : iE1.getRequest().getWeight()); 1072 } 1073 1074 /** Second request weight 1075 * @return second request weight 1076 **/ 1077 public double getR2Weight() { 1078 return (iE2.getRequest() == null ? 0.0 : iE2.getRequest().getWeight()); 1079 } 1080 1081 /** Second request 1082 * @return second request 1083 **/ 1084 public Request getR2() { 1085 return iE2.getRequest(); 1086 } 1087 1088 /** First enrollment 1089 * @return first enrollment 1090 **/ 1091 public Enrollment getE1() { 1092 return iE1; 1093 } 1094 1095 /** Second enrollment 1096 * @return second enrollment 1097 **/ 1098 public Enrollment getE2() { 1099 return iE2; 1100 } 1101 1102 @Override 1103 public int hashCode() { 1104 return iHashCode; 1105 } 1106 1107 /** Conflict penalty, e.g., the number of overlapping slots against the number of slots of the smallest section 1108 * @return conflict penalty 1109 **/ 1110 public int getPenalty() { 1111 return iPenalty; 1112 } 1113 1114 /** Other enrollment of the conflict */ 1115 public Enrollment getOther(Enrollment enrollment) { 1116 return (getE1().getRequest().equals(enrollment.getRequest()) ? getE2() : getE1()); 1117 } 1118 1119 /** Weight of the conflict on the given enrollment */ 1120 public double getWeight(Enrollment e) { 1121 return iType.getWeight(iContext, this, e); 1122 } 1123 1124 /** Weight of the conflict on both enrollment (sum) */ 1125 public double getWeight() { 1126 return (iType.getWeight(iContext, this, iE1) + iType.getWeight(iContext, this, iE2)) / 2.0; 1127 } 1128 1129 /** Conflict type 1130 * @return conflict type; 1131 */ 1132 public Type getType() { 1133 return iType; 1134 } 1135 1136 @Override 1137 public boolean equals(Object o) { 1138 if (o == null || !(o instanceof Conflict)) return false; 1139 Conflict c = (Conflict) o; 1140 return getType() == c.getType() && getStudent().equals(c.getStudent()) && getS1().equals(c.getS1()) && getS2().equals(c.getS2()); 1141 } 1142 1143 @Override 1144 public String toString() { 1145 return getStudent() + ": (" + getType() + ", p:" + getPenalty() + ") " + getS1() + " -- " + getS2(); 1146 } 1147 } 1148 1149 /** 1150 * Context holding parameters and distance cache. See {@link Type} for the list of available parameters. 1151 */ 1152 public static class Context { 1153 private List<Type> iTypes = null; 1154 private DistanceMetric iDistanceMetric = null; 1155 private boolean iDebug = false; 1156 protected double iTimeOverlapMaxLimit = 0.5000; 1157 private int iLunchStart, iLunchEnd, iLunchLength, iMaxTravelGap, iWorkDayLimit, iBackToBackDistance, iEarlySlot, iLateSlot, iAccBackToBackDistance; 1158 private String iFreeTimeAccommodation = "FT", iBackToBackAccommodation = "BTB", iBreakBetweenClassesAccommodation = "BBC"; 1159 1160 public Context(DistanceMetric dm, DataProperties config) { 1161 iDistanceMetric = (dm == null ? new DistanceMetric(config) : dm); 1162 iDebug = config.getPropertyBoolean("StudentQuality.Debug", false); 1163 iTimeOverlapMaxLimit = config.getPropertyDouble("StudentWeights.TimeOverlapMaxLimit", iTimeOverlapMaxLimit); 1164 iLunchStart = config.getPropertyInt("StudentLunch.StartSlot", (11 * 60) / 5); 1165 iLunchEnd = config.getPropertyInt("StudentLunch.EndStart", (13 * 60) / 5); 1166 iLunchLength = config.getPropertyInt("StudentLunch.Length", 30 / 5); 1167 iMaxTravelGap = config.getPropertyInt("TravelTime.MaxTravelGap", 12); 1168 iWorkDayLimit = config.getPropertyInt("WorkDay.WorkDayLimit", 6 * 12); 1169 iBackToBackDistance = config.getPropertyInt("StudentWeights.BackToBackDistance", 6); 1170 iAccBackToBackDistance = config.getPropertyInt("Accommodations.BackToBackDistance", 6); 1171 iEarlySlot = config.getPropertyInt("WorkDay.EarlySlot", 102); 1172 iLateSlot = config.getPropertyInt("WorkDay.LateSlot", 210); 1173 iFreeTimeAccommodation = config.getProperty("Accommodations.FreeTimeReference", iFreeTimeAccommodation); 1174 iBackToBackAccommodation = config.getProperty("Accommodations.BackToBackReference", iBackToBackAccommodation); 1175 iBreakBetweenClassesAccommodation = config.getProperty("Accommodations.BreakBetweenClassesReference", iBreakBetweenClassesAccommodation); 1176 iTypes = new ArrayList<Type>(); 1177 for (Type t: Type.values()) 1178 if (config.getPropertyDouble(t.getWeightName(), t.getWeightDefault()) != 0.0) 1179 iTypes.add(t); 1180 } 1181 1182 public DistanceMetric getDistanceMetric() { 1183 return iDistanceMetric; 1184 } 1185 1186 public boolean isDebug() { return iDebug; } 1187 1188 public double getTimeOverlapMaxLimit() { return iTimeOverlapMaxLimit; } 1189 public int getLunchStart() { return iLunchStart; } 1190 public int getLunchEnd() { return iLunchEnd; } 1191 public int getLunchLength() { return iLunchLength; } 1192 public int getMaxTravelGap() { return iMaxTravelGap; } 1193 public int getWorkDayLimit() { return iWorkDayLimit; } 1194 public int getBackToBackDistance() { return iBackToBackDistance; } 1195 public int getAccBackToBackDistance() { return iAccBackToBackDistance; } 1196 public int getEarlySlot() { return iEarlySlot; } 1197 public int getLateSlot() { return iLateSlot; } 1198 public String getFreeTimeAccommodation() { return iFreeTimeAccommodation; } 1199 public String getBackToBackAccommodation() { return iBackToBackAccommodation; } 1200 public String getBreakBetweenClassesAccommodation() { return iBreakBetweenClassesAccommodation; } 1201 public List<Type> getTypes() { return iTypes; } 1202 1203 private Map<Long, Map<Long, Integer>> iDistanceCache = new HashMap<Long, Map<Long,Integer>>(); 1204 protected synchronized int getDistanceInMinutes(RoomLocation r1, RoomLocation r2) { 1205 if (r1.getId().compareTo(r2.getId()) > 0) return getDistanceInMinutes(r2, r1); 1206 if (r1.getId().equals(r2.getId()) || r1.getIgnoreTooFar() || r2.getIgnoreTooFar()) 1207 return 0; 1208 if (r1.getPosX() == null || r1.getPosY() == null || r2.getPosX() == null || r2.getPosY() == null) 1209 return iDistanceMetric.getMaxTravelDistanceInMinutes(); 1210 Map<Long, Integer> other2distance = iDistanceCache.get(r1.getId()); 1211 if (other2distance == null) { 1212 other2distance = new HashMap<Long, Integer>(); 1213 iDistanceCache.put(r1.getId(), other2distance); 1214 } 1215 Integer distance = other2distance.get(r2.getId()); 1216 if (distance == null) { 1217 distance = iDistanceMetric.getDistanceInMinutes(r1.getId(), r1.getPosX(), r1.getPosY(), r2.getId(), r2.getPosX(), r2.getPosY()); 1218 other2distance.put(r2.getId(), distance); 1219 } 1220 return distance; 1221 } 1222 1223 public int getDistanceInMinutes(Placement p1, Placement p2) { 1224 if (p1.isMultiRoom()) { 1225 if (p2.isMultiRoom()) { 1226 int dist = 0; 1227 for (RoomLocation r1 : p1.getRoomLocations()) { 1228 for (RoomLocation r2 : p2.getRoomLocations()) { 1229 dist = Math.max(dist, getDistanceInMinutes(r1, r2)); 1230 } 1231 } 1232 return dist; 1233 } else { 1234 if (p2.getRoomLocation() == null) 1235 return 0; 1236 int dist = 0; 1237 for (RoomLocation r1 : p1.getRoomLocations()) { 1238 dist = Math.max(dist, getDistanceInMinutes(r1, p2.getRoomLocation())); 1239 } 1240 return dist; 1241 } 1242 } else if (p2.isMultiRoom()) { 1243 if (p1.getRoomLocation() == null) 1244 return 0; 1245 int dist = 0; 1246 for (RoomLocation r2 : p2.getRoomLocations()) { 1247 dist = Math.max(dist, getDistanceInMinutes(p1.getRoomLocation(), r2)); 1248 } 1249 return dist; 1250 } else { 1251 if (p1.getRoomLocation() == null || p2.getRoomLocation() == null) 1252 return 0; 1253 return getDistanceInMinutes(p1.getRoomLocation(), p2.getRoomLocation()); 1254 } 1255 } 1256 } 1257 1258 /** 1259 * Assignment context 1260 */ 1261 public class StudentQualityContext implements AssignmentConstraintContext<Request, Enrollment> { 1262 private int[] iTotalPenalty = null; 1263 private Set<Conflict>[] iAllConflicts = null; 1264 private Request iOldVariable = null; 1265 private Enrollment iUnassignedValue = null; 1266 1267 @SuppressWarnings("unchecked") 1268 public StudentQualityContext(Assignment<Request, Enrollment> assignment) { 1269 iTotalPenalty = new int[Type.values().length]; 1270 for (Type t: iContext.getTypes()) 1271 iTotalPenalty[t.ordinal()] = countTotalPenalty(t, assignment); 1272 if (iContext.isDebug()) { 1273 iAllConflicts = new Set[Type.values().length]; 1274 for (Type t: iContext.getTypes()) 1275 iAllConflicts[t.ordinal()] = computeAllConflicts(t, assignment); 1276 } 1277 StudentSectioningModelContext cx = ((StudentSectioningModel)getModel()).getContext(assignment); 1278 for (Type t: iContext.getTypes()) 1279 for (Conflict c: computeAllConflicts(t, assignment)) cx.add(assignment, c); 1280 } 1281 1282 @SuppressWarnings("unchecked") 1283 public StudentQualityContext(StudentQualityContext parent) { 1284 iTotalPenalty = new int[Type.values().length]; 1285 for (Type t: iContext.getTypes()) 1286 iTotalPenalty[t.ordinal()] = parent.iTotalPenalty[t.ordinal()]; 1287 if (iContext.isDebug()) { 1288 iAllConflicts = new Set[Type.values().length]; 1289 for (Type t: iContext.getTypes()) 1290 iAllConflicts[t.ordinal()] = new HashSet<Conflict>(parent.iAllConflicts[t.ordinal()]); 1291 } 1292 } 1293 1294 @Override 1295 public void assigned(Assignment<Request, Enrollment> assignment, Enrollment value) { 1296 StudentSectioningModelContext cx = ((StudentSectioningModel)getModel()).getContext(assignment); 1297 for (Type type: iContext.getTypes()) { 1298 iTotalPenalty[type.ordinal()] += allPenalty(type, assignment, value); 1299 for (Conflict c: allConflicts(type, assignment, value)) 1300 cx.add(assignment, c); 1301 } 1302 if (iContext.isDebug()) { 1303 sLog.debug("A:" + value.variable() + " := " + value); 1304 for (Type type: iContext.getTypes()) { 1305 int inc = allPenalty(type, assignment, value); 1306 if (inc != 0) { 1307 sLog.debug("-- " + type + " +" + inc + " A: " + value.variable() + " := " + value); 1308 for (Conflict c: allConflicts(type, assignment, value)) { 1309 sLog.debug(" -- " + c); 1310 iAllConflicts[type.ordinal()].add(c); 1311 inc -= c.getPenalty(); 1312 } 1313 if (inc != 0) { 1314 sLog.error(type + ": Different penalty for the assigned value (difference: " + inc + ")!"); 1315 } 1316 } 1317 } 1318 } 1319 } 1320 1321 /** 1322 * Called when a value is unassigned from a variable. Internal number of 1323 * time overlapping conflicts is updated, see 1324 * {@link TimeOverlapsCounter#getTotalNrConflicts(Assignment)}. 1325 */ 1326 @Override 1327 public void unassigned(Assignment<Request, Enrollment> assignment, Enrollment value) { 1328 StudentSectioningModelContext cx = ((StudentSectioningModel)getModel()).getContext(assignment); 1329 for (Type type: iContext.getTypes()) { 1330 iTotalPenalty[type.ordinal()] -= allPenalty(type, assignment, value); 1331 for (Conflict c: allConflicts(type, assignment, value)) 1332 cx.remove(assignment, c); 1333 } 1334 if (iContext.isDebug()) { 1335 sLog.debug("U:" + value.variable() + " := " + value); 1336 for (Type type: iContext.getTypes()) { 1337 int dec = allPenalty(type, assignment, value); 1338 if (dec != 0) { 1339 sLog.debug("-- " + type + " -" + dec + " U: " + value.variable() + " := " + value); 1340 for (Conflict c: allConflicts(type, assignment, value)) { 1341 sLog.debug(" -- " + c); 1342 iAllConflicts[type.ordinal()].remove(c); 1343 dec -= c.getPenalty(); 1344 } 1345 if (dec != 0) { 1346 sLog.error(type + ":Different penalty for the unassigned value (difference: " + dec + ")!"); 1347 } 1348 } 1349 } 1350 } 1351 } 1352 1353 /** 1354 * Called before a value is assigned to a variable. 1355 * @param assignment current assignment 1356 * @param iteration current iteration 1357 * @param value value to be assigned 1358 */ 1359 public void beforeAssigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) { 1360 if (value != null) { 1361 Enrollment old = assignment.getValue(value.variable()); 1362 if (old != null) { 1363 iUnassignedValue = old; 1364 unassigned(assignment, old); 1365 } 1366 iOldVariable = value.variable(); 1367 } 1368 } 1369 1370 /** 1371 * Called after a value is assigned to a variable. 1372 * @param assignment current assignment 1373 * @param iteration current iteration 1374 * @param value value that was assigned 1375 */ 1376 public void afterAssigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) { 1377 iOldVariable = null; 1378 iUnassignedValue = null; 1379 if (value != null) { 1380 assigned(assignment, value); 1381 } 1382 } 1383 1384 /** 1385 * Called after a value is unassigned from a variable. 1386 * @param assignment current assignment 1387 * @param iteration current iteration 1388 * @param value value that was unassigned 1389 */ 1390 public void afterUnassigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) { 1391 if (value != null && !value.equals(iUnassignedValue)) { 1392 unassigned(assignment, value); 1393 } 1394 } 1395 1396 public Set<Conflict> getAllConflicts(Type type) { 1397 return iAllConflicts[type.ordinal()]; 1398 } 1399 1400 public int getTotalPenalty(Type type) { 1401 return iTotalPenalty[type.ordinal()]; 1402 } 1403 1404 public void checkTotalPenalty(Type type, Assignment<Request, Enrollment> assignment) { 1405 int total = countTotalPenalty(type, assignment); 1406 if (total != iTotalPenalty[type.ordinal()]) { 1407 sLog.error(type + " penalty does not match for (actual: " + total + ", count: " + iTotalPenalty[type.ordinal()] + ")!"); 1408 iTotalPenalty[type.ordinal()] = total; 1409 if (iContext.isDebug()) { 1410 Set<Conflict> conflicts = computeAllConflicts(type, assignment); 1411 for (Conflict c: conflicts) { 1412 if (!iAllConflicts[type.ordinal()].contains(c)) 1413 sLog.debug(" +add+ " + c); 1414 } 1415 for (Conflict c: iAllConflicts[type.ordinal()]) { 1416 if (!conflicts.contains(c)) 1417 sLog.debug(" -rem- " + c); 1418 } 1419 for (Conflict c: conflicts) { 1420 for (Conflict d: iAllConflicts[type.ordinal()]) { 1421 if (c.equals(d) && c.getPenalty() != d.getPenalty()) { 1422 sLog.debug(" -dif- " + c + " (other: " + d.getPenalty() + ")"); 1423 } 1424 } 1425 } 1426 iAllConflicts[type.ordinal()] = conflicts; 1427 } 1428 } 1429 } 1430 1431 public int countTotalPenalty(Type type, Assignment<Request, Enrollment> assignment) { 1432 int total = 0; 1433 for (Request r1 : getModel().variables()) { 1434 Enrollment e1 = assignment.getValue(r1); 1435 if (e1 == null || r1.equals(iOldVariable)) continue; 1436 for (Request r2 : r1.getStudent().getRequests()) { 1437 Enrollment e2 = assignment.getValue(r2); 1438 if (e2 != null && r1.getId() < r2.getId() && !r2.equals(iOldVariable)) { 1439 if (type.isApplicable(iContext, r1.getStudent(), r1, r2)) 1440 total += penalty(type, e1, e2); 1441 } 1442 } 1443 total += penalty(type, e1); 1444 } 1445 return total; 1446 } 1447 1448 public Set<Conflict> computeAllConflicts(Type type, Assignment<Request, Enrollment> assignment) { 1449 Set<Conflict> ret = new HashSet<Conflict>(); 1450 for (Request r1 : getModel().variables()) { 1451 Enrollment e1 = assignment.getValue(r1); 1452 if (e1 == null || r1.equals(iOldVariable)) continue; 1453 for (Request r2 : r1.getStudent().getRequests()) { 1454 Enrollment e2 = assignment.getValue(r2); 1455 if (e2 != null && r1.getId() < r2.getId() && !r2.equals(iOldVariable)) { 1456 if (type.isApplicable(iContext, r1.getStudent(), r1, r2)) 1457 ret.addAll(conflicts(type, e1, e2)); 1458 } 1459 } 1460 ret.addAll(conflicts(type, e1)); 1461 } 1462 return ret; 1463 } 1464 1465 public Set<Conflict> allConflicts(Type type, Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 1466 Set<Conflict> ret = new HashSet<Conflict>(); 1467 for (Request request : enrollment.getStudent().getRequests()) { 1468 if (request.equals(enrollment.getRequest())) continue; 1469 if (assignment.getValue(request) != null && !request.equals(iOldVariable)) { 1470 ret.addAll(conflicts(type, enrollment, assignment.getValue(request))); 1471 } 1472 } 1473 ret.addAll(conflicts(type, enrollment)); 1474 return ret; 1475 } 1476 1477 public int allPenalty(Type type, Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 1478 int penalty = 0; 1479 for (Request request : enrollment.getStudent().getRequests()) { 1480 if (request.equals(enrollment.getRequest())) continue; 1481 if (assignment.getValue(request) != null && !request.equals(iOldVariable)) { 1482 if (type.isApplicable(iContext, enrollment.getStudent(), enrollment.variable(), request)) 1483 penalty += penalty(type, enrollment, assignment.getValue(request)); 1484 } 1485 } 1486 penalty += penalty(type, enrollment); 1487 return penalty; 1488 } 1489 } 1490 1491 @Override 1492 public StudentQualityContext createAssignmentContext(Assignment<Request, Enrollment> assignment) { 1493 return new StudentQualityContext(assignment); 1494 } 1495 1496 @Override 1497 public StudentQualityContext inheritAssignmentContext(Assignment<Request, Enrollment> assignment, StudentQualityContext parentContext) { 1498 return new StudentQualityContext(parentContext); 1499 } 1500 1501 /** Empty iterator */ 1502 public static class Nothing implements Iterable<SctAssignment> { 1503 @Override 1504 public Iterator<SctAssignment> iterator() { 1505 return new Iterator<SctAssignment>() { 1506 @Override 1507 public SctAssignment next() { return null; } 1508 @Override 1509 public boolean hasNext() { return false; } 1510 @Override 1511 public void remove() { throw new UnsupportedOperationException(); } 1512 }; 1513 } 1514 } 1515 1516 /** Unavailabilities of a student */ 1517 public static class Unavailabilities implements Iterable<Unavailability> { 1518 private Student iStudent; 1519 public Unavailabilities(Student student) { iStudent = student; } 1520 @Override 1521 public Iterator<Unavailability> iterator() { return iStudent.getUnavailabilities().iterator(); } 1522 } 1523 1524 private static class SingleTime implements SctAssignment { 1525 private TimeLocation iTime = null; 1526 1527 public SingleTime(int start, int end) { 1528 iTime = new TimeLocation(0x7f, start, end-start, 0, 0.0, 0, null, null, new BitSet(), 0); 1529 } 1530 1531 @Override 1532 public TimeLocation getTime() { return iTime; } 1533 @Override 1534 public List<RoomLocation> getRooms() { return null; } 1535 @Override 1536 public int getNrRooms() { return 0; } 1537 @Override 1538 public void assigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {} 1539 @Override 1540 public void unassigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {} 1541 @Override 1542 public Set<Enrollment> getEnrollments(Assignment<Request, Enrollment> assignment) { return null; } 1543 @Override 1544 public boolean isAllowOverlap() { return false; } 1545 @Override 1546 public long getId() { return -1;} 1547 @Override 1548 public int compareById(SctAssignment a) { return 0; } 1549 1550 @Override 1551 public boolean isOverlapping(SctAssignment assignment) { 1552 return assignment.getTime() != null && getTime().shareDays(assignment.getTime()) && getTime().shareHours(assignment.getTime()); 1553 } 1554 1555 @Override 1556 public boolean isOverlapping(Set<? extends SctAssignment> assignments) { 1557 for (SctAssignment assignment : assignments) { 1558 if (isOverlapping(assignment)) return true; 1559 } 1560 return false; 1561 } 1562 } 1563 1564 /** Early/late time */ 1565 public static class SingleTimeIterable implements Iterable<SingleTime> { 1566 private SingleTime iTime = null; 1567 public SingleTimeIterable(int start, int end) { 1568 if (start < end) 1569 iTime = new SingleTime(start, end); 1570 1571 } 1572 @Override 1573 public Iterator<SingleTime> iterator() { 1574 return new Iterator<SingleTime>() { 1575 @Override 1576 public SingleTime next() { 1577 SingleTime ret = iTime; iTime = null; return ret; 1578 } 1579 @Override 1580 public boolean hasNext() { return iTime != null; } 1581 @Override 1582 public void remove() { throw new UnsupportedOperationException(); } 1583 }; 1584 } 1585 } 1586 1587 /** Free times of a student */ 1588 public static class FreeTimes implements Iterable<FreeTimeRequest> { 1589 private Student iStudent; 1590 public FreeTimes(Student student) { 1591 iStudent = student; 1592 } 1593 1594 @Override 1595 public Iterator<FreeTimeRequest> iterator() { 1596 return new Iterator<FreeTimeRequest>() { 1597 Iterator<Request> i = iStudent.getRequests().iterator(); 1598 FreeTimeRequest next = null; 1599 boolean hasNext = nextFreeTime(); 1600 1601 private boolean nextFreeTime() { 1602 while (i.hasNext()) { 1603 Request r = i.next(); 1604 if (r instanceof FreeTimeRequest) { 1605 next = (FreeTimeRequest)r; 1606 return true; 1607 } 1608 } 1609 return false; 1610 } 1611 1612 @Override 1613 public FreeTimeRequest next() { 1614 try { 1615 return next; 1616 } finally { 1617 hasNext = nextFreeTime(); 1618 } 1619 } 1620 @Override 1621 public boolean hasNext() { return hasNext; } 1622 @Override 1623 public void remove() { throw new UnsupportedOperationException(); } 1624 }; 1625 } 1626 } 1627 1628 @Override 1629 public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info) { 1630 StudentQualityContext cx = getContext(assignment); 1631 if (iContext.isDebug()) 1632 for (Type type: iContext.getTypes()) 1633 info.put("[Schedule Quality] " + type.getName(), String.valueOf(cx.getTotalPenalty(type))); 1634 } 1635 1636 @Override 1637 public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info, Collection<Request> variables) { 1638 } 1639 1640 public String toString(Assignment<Request, Enrollment> assignment) { 1641 String ret = ""; 1642 StudentQualityContext cx = getContext(assignment); 1643 for (Type type: iContext.getTypes()) { 1644 int p = cx.getTotalPenalty(type); 1645 if (p != 0) { 1646 ret += (ret.isEmpty() ? "" : ", ") + type.getAbbv() + ": " + p; 1647 } 1648 } 1649 return ret; 1650 } 1651 1652 public boolean hasDistanceConflict(Student student, Section s1, Section s2) { 1653 if (student.isNeedShortDistances()) 1654 return Type.ShortDistance.inConflict(iContext, s1, s2); 1655 else 1656 return Type.Distance.inConflict(iContext, s1, s2); 1657 } 1658}