001package org.cpsolver.studentsct.online.selection; 002 003import java.util.ArrayList; 004import java.util.HashSet; 005import java.util.Hashtable; 006import java.util.List; 007import java.util.Set; 008 009import org.cpsolver.coursett.model.TimeLocation; 010import org.cpsolver.ifs.assignment.Assignment; 011import org.cpsolver.studentsct.extension.DistanceConflict; 012import org.cpsolver.studentsct.extension.StudentQuality; 013import org.cpsolver.studentsct.extension.TimeOverlapsCounter; 014import org.cpsolver.studentsct.model.CourseRequest; 015import org.cpsolver.studentsct.model.Enrollment; 016import org.cpsolver.studentsct.model.FreeTimeRequest; 017import org.cpsolver.studentsct.model.Request; 018import org.cpsolver.studentsct.model.Section; 019import org.cpsolver.studentsct.model.Student; 020import org.cpsolver.studentsct.model.Subpart; 021import org.cpsolver.studentsct.model.Unavailability; 022import org.cpsolver.studentsct.online.OnlineSectioningModel; 023import org.cpsolver.studentsct.online.selection.MultiCriteriaBranchAndBoundSelection.SelectionCriterion; 024import org.cpsolver.studentsct.weights.StudentWeights; 025 026/** 027* Multi-criteria selection criterion. This provides a lexicographical order of solutions using the 028* following criteria: 029* <ul> 030* <li>best priority & alternativity ignoring free time requests (a better solution has a higher priority course assigned or does not use alternative request if possible) 031* <li>avoid or minimize course time overlaps 032* <li>minimise use of over-expected classes (this prevents students of getting into classes that we know will be needed later in the process) 033* <li>best priority & alternativity including free time requests (this is to prevent students of gaming the system by adding free time requests) 034* <li>maximise selection (preferred sections) 035* <li>avoid or minimise time overlaps (for classes that are allowed to overlap and for free time requests) 036* <li>avoid or minimise distance conflicts 037* <li>avoid classes that have no time assignment (arranged hours) 038* <li>balance sections 039* <li>minimise class penalties (expressing how much a class is over-expected) 040* </ul> 041* 042* @version StudentSct 1.3 (Student Sectioning)<br> 043* Copyright (C) 2014 Tomáš Müller<br> 044* <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 045* <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 046* <br> 047* This library is free software; you can redistribute it and/or modify 048* it under the terms of the GNU Lesser General Public License as 049* published by the Free Software Foundation; either version 3 of the 050* License, or (at your option) any later version. <br> 051* <br> 052* This library is distributed in the hope that it will be useful, but 053* WITHOUT ANY WARRANTY; without even the implied warranty of 054* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 055* Lesser General Public License for more details. <br> 056* <br> 057* You should have received a copy of the GNU Lesser General Public 058* License along with this library; if not see <a 059* href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>. 060* 061*/ 062public class OnlineSectioningCriterion implements SelectionCriterion { 063 private Hashtable<CourseRequest, Set<Section>> iPreferredSections = null; 064 private List<TimeToAvoid> iTimesToAvoid = null; 065 private OnlineSectioningModel iModel; 066 private Student iStudent; 067 protected double[] iQalityWeights; 068 069 /** 070 * Constructor 071 * @param student current student 072 * @param model online student sectioning model 073 * @param assignment current assignment 074 * @param preferredSections preferred sections 075 */ 076 public OnlineSectioningCriterion(Student student, OnlineSectioningModel model, 077 Assignment<Request, Enrollment> assignment, Hashtable<CourseRequest, Set<Section>> preferredSections) { 078 iStudent = student; 079 iModel = model; 080 iPreferredSections = preferredSections; 081 if (model.getProperties().getPropertyBoolean("OnlineStudentSectioning.TimesToAvoidHeuristics", true)) { 082 iTimesToAvoid = new ArrayList<TimeToAvoid>(); 083 for (Request r : iStudent.getRequests()) { 084 if (r instanceof CourseRequest) { 085 List<Enrollment> enrollments = ((CourseRequest) r).getAvaiableEnrollmentsSkipSameTime(assignment); 086 if (enrollments.size() <= 5) { 087 int penalty = (7 - enrollments.size()) * (r.isAlternative() ? 1 : 7 - enrollments.size()); 088 for (Enrollment enrollment : enrollments) 089 for (Section section : enrollment.getSections()) 090 if (section.getTime() != null) 091 iTimesToAvoid.add(new TimeToAvoid(section.getTime(), penalty, r.getPriority())); 092 } 093 } else if (r instanceof FreeTimeRequest) { 094 iTimesToAvoid.add(new TimeToAvoid(((FreeTimeRequest) r).getTime(), 1, Integer.MAX_VALUE)); 095 } 096 } 097 for (Unavailability unavailability: iStudent.getUnavailabilities()) 098 if (unavailability.getTime() != null) 099 iTimesToAvoid.add(new TimeToAvoid(unavailability.getTime(), 1, Integer.MAX_VALUE)); 100 } 101 iQalityWeights = new double[StudentQuality.Type.values().length]; 102 for (StudentQuality.Type type: StudentQuality.Type.values()) { 103 iQalityWeights[type.ordinal()] = model.getProperties().getPropertyDouble(type.getWeightName(), type.getWeightDefault()); 104 } 105 } 106 107 protected OnlineSectioningModel getModel() { 108 return iModel; 109 } 110 111 protected Student getStudent() { 112 return iStudent; 113 } 114 115 protected Set<Section> getPreferredSections(Request request) { 116 return iPreferredSections.get(request); 117 } 118 119 protected List<TimeToAvoid> getTimesToAvoid() { 120 return iTimesToAvoid; 121 } 122 123 /** 124 * Distance conflicts of idx-th assignment of the current schedule 125 */ 126 public Set<DistanceConflict.Conflict> getDistanceConflicts(Enrollment[] assignment, int idx) { 127 if (getModel().getDistanceConflict() == null || assignment[idx] == null) 128 return null; 129 Set<DistanceConflict.Conflict> dist = getModel().getDistanceConflict().conflicts(assignment[idx]); 130 for (int x = 0; x < idx; x++) 131 if (assignment[x] != null) 132 dist.addAll(getModel().getDistanceConflict().conflicts(assignment[x], assignment[idx])); 133 return dist; 134 } 135 136 /** 137 * Time overlapping conflicts of idx-th assignment of the current schedule 138 */ 139 public Set<TimeOverlapsCounter.Conflict> getTimeOverlappingConflicts(Enrollment[] assignment, int idx) { 140 if (getModel().getTimeOverlaps() == null || assignment[idx] == null) 141 return null; 142 Set<TimeOverlapsCounter.Conflict> overlaps = new HashSet<TimeOverlapsCounter.Conflict>(); 143 for (int x = 0; x < idx; x++) 144 if (assignment[x] != null) { 145 overlaps.addAll(getModel().getTimeOverlaps().conflicts(assignment[x], assignment[idx])); 146 } else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 147 overlaps.addAll(getModel().getTimeOverlaps().conflicts( 148 ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), assignment[idx])); 149 overlaps.addAll(getModel().getTimeOverlaps().notAvailableTimeConflicts(assignment[idx])); 150 return overlaps; 151 } 152 153 public Set<StudentQuality.Conflict> getStudentQualityConflicts(Enrollment[] assignment, int idx) { 154 if (getModel().getStudentQuality() == null || assignment[idx] == null) 155 return null; 156 Set<StudentQuality.Conflict> conflicts = new HashSet<StudentQuality.Conflict>(); 157 for (StudentQuality.Type t: StudentQuality.Type.values()) { 158 for (int x = 0; x < idx; x++) 159 if (assignment[x] != null) 160 conflicts.addAll(getModel().getStudentQuality().conflicts(t, assignment[x], assignment[idx])); 161 conflicts.addAll(getModel().getStudentQuality().conflicts(t, assignment[idx])); 162 } 163 return conflicts; 164 } 165 166 /** 167 * Weight of an assignment. Unlike 168 * {@link StudentWeights#getWeight(Assignment, Enrollment, Set, Set)}, only count this 169 * side of distance conflicts and time overlaps. 170 **/ 171 @Deprecated 172 protected double getWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment, 173 Set<DistanceConflict.Conflict> distanceConflicts, Set<TimeOverlapsCounter.Conflict> timeOverlappingConflicts) { 174 double weight = -getModel().getStudentWeights().getWeight(assignment, enrollment); 175 if (distanceConflicts != null) 176 for (DistanceConflict.Conflict c : distanceConflicts) { 177 Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1()); 178 if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority()) 179 weight += getModel().getStudentWeights().getDistanceConflictWeight(assignment, c); 180 } 181 if (timeOverlappingConflicts != null) 182 for (TimeOverlapsCounter.Conflict c : timeOverlappingConflicts) { 183 weight += getModel().getStudentWeights().getTimeOverlapConflictWeight(assignment, enrollment, c); 184 } 185 return enrollment.getRequest().getWeight() * weight; 186 } 187 188 protected double getWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment, Set<StudentQuality.Conflict> conflicts) { 189 double weight = -getModel().getStudentWeights().getWeight(assignment, enrollment); 190 if (conflicts != null) 191 for (StudentQuality.Conflict c : conflicts) { 192 weight += getModel().getStudentWeights().getStudentQualityConflictWeight(assignment, enrollment, c); 193 } 194 return enrollment.getRequest().getWeight() * weight; 195 } 196 197 public Request getRequest(int index) { 198 return (index < 0 || index >= getStudent().getRequests().size() ? null : getStudent().getRequests().get(index)); 199 } 200 201 public boolean isFreeTime(int index) { 202 Request r = getRequest(index); 203 return r != null && r instanceof FreeTimeRequest; 204 } 205 206 @Override 207 public int compare(Assignment<Request, Enrollment> assignment, Enrollment[] current, Enrollment[] best) { 208 if (best == null) 209 return -1; 210 211 // 0. best priority & alternativity ignoring free time requests 212 boolean ft = false; 213 boolean res = false; 214 for (int idx = 0; idx < current.length; idx++) { 215 if (isFreeTime(idx)) { 216 ft = true; 217 continue; 218 } 219 Request request = getRequest(idx); 220 if (request instanceof CourseRequest && ((CourseRequest)request).hasReservations()) res = true; 221 if (best[idx] != null && best[idx].getAssignments() != null) { 222 if (current[idx] == null || current[idx].getSections() == null) 223 return 1; // higher priority request assigned 224 if (best[idx].getTruePriority() < current[idx].getTruePriority()) 225 return 1; // less alternative request assigned 226 if (best[idx].getTruePriority() > current[idx].getTruePriority()) 227 return -1; // less alternative request assigned 228 } else { 229 if (current[idx] != null && current[idx].getAssignments() != null) 230 return -1; // higher priority request assigned 231 } 232 } 233 234 // 0.1. allowed, but not available sections 235 int bestNotAvailable = 0, currentNotAvailable = 0; 236 for (int idx = 0; idx < current.length; idx++) { 237 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].getRequest() instanceof CourseRequest && best[idx].getReservation() != null && best[idx].getReservation().canAssignOverLimit()) { 238 for (Section section: best[idx].getSections()) { 239 if (section.getLimit() == 0) 240 bestNotAvailable ++; 241 } 242 } 243 if (current[idx] != null && current[idx].getAssignments() != null && current[idx].getRequest() instanceof CourseRequest && current[idx].getReservation() != null && current[idx].getReservation().canAssignOverLimit()) { 244 for (Section section: current[idx].getSections()) { 245 if (section.getLimit() == 0) 246 currentNotAvailable ++; 247 } 248 } 249 } 250 if (bestNotAvailable > currentNotAvailable) return -1; 251 if (bestNotAvailable < currentNotAvailable) return 1; 252 253 // 0.5. avoid course time overlaps & unavailabilities 254 if (getModel().getStudentQuality() != null) { 255 int bestTimeOverlaps = 0, currentTimeOverlaps = 0; 256 for (int idx = 0; idx < current.length; idx++) { 257 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].getRequest() instanceof CourseRequest) { 258 for (int x = 0; x < idx; x++) { 259 if (best[x] != null && best[x].getAssignments() != null && best[x].getRequest() instanceof CourseRequest) 260 bestTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.CourseTimeOverlap, best[x], best[idx]); 261 } 262 } 263 if (current[idx] != null && current[idx].getAssignments() != null && current[idx].getRequest() instanceof CourseRequest) { 264 for (int x = 0; x < idx; x++) { 265 if (current[x] != null && current[x].getAssignments() != null && current[x].getRequest() instanceof CourseRequest) 266 currentTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.CourseTimeOverlap, current[x], current[idx]); 267 } 268 } 269 } 270 for (int idx = 0; idx < current.length; idx++) { 271 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 272 bestTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, best[idx]); 273 } 274 if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) { 275 currentTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, current[idx]); 276 } 277 } 278 if (currentTimeOverlaps < bestTimeOverlaps) 279 return -1; 280 if (bestTimeOverlaps < currentTimeOverlaps) 281 return 1; 282 } else if (getModel().getTimeOverlaps() != null) { 283 int bestTimeOverlaps = 0, currentTimeOverlaps = 0; 284 for (int idx = 0; idx < current.length; idx++) { 285 if (best[idx] != null && best[idx].getAssignments() != null 286 && best[idx].getRequest() instanceof CourseRequest) { 287 for (int x = 0; x < idx; x++) { 288 if (best[x] != null && best[x].getAssignments() != null 289 && best[x].getRequest() instanceof CourseRequest) 290 bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]); 291 } 292 for (int x = 0; x < idx; x++) { 293 if (current[x] != null && current[x].getAssignments() != null 294 && current[x].getRequest() instanceof CourseRequest) 295 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]); 296 } 297 } 298 } 299 for (int idx = 0; idx < current.length; idx++) { 300 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 301 bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]); 302 } 303 if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) { 304 currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]); 305 } 306 } 307 if (currentTimeOverlaps < bestTimeOverlaps) 308 return -1; 309 if (bestTimeOverlaps < currentTimeOverlaps) 310 return 1; 311 } 312 313 // 1. minimize number of penalties 314 double bestPenalties = 0, currentPenalties = 0; 315 for (int idx = 0; idx < current.length; idx++) { 316 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 317 for (Section section : best[idx].getSections()) 318 bestPenalties += getModel().getOverExpected(assignment, best, idx, section, best[idx].getRequest()); 319 for (Section section : current[idx].getSections()) 320 currentPenalties += getModel().getOverExpected(assignment, current, idx, section, current[idx].getRequest()); 321 } 322 } 323 if (currentPenalties < bestPenalties) 324 return -1; 325 if (bestPenalties < currentPenalties) 326 return 1; 327 328 // 2. best priority & alternativity including free time requests 329 if (ft) { 330 for (int idx = 0; idx < current.length; idx++) { 331 if (best[idx] != null && best[idx].getAssignments() != null) { 332 if (current[idx] == null || current[idx].getSections() == null) 333 return 1; // higher priority request assigned 334 if (best[idx].getTruePriority() < current[idx].getTruePriority()) 335 return 1; // less alternative request assigned 336 if (best[idx].getTruePriority() > current[idx].getTruePriority()) 337 return -1; // less alternative request assigned 338 } else { 339 if (current[idx] != null && current[idx].getAssignments() != null) 340 return -1; // higher priority request assigned 341 } 342 } 343 } 344 345 // 3. maximize selection 346 int bestSelected = 0, currentSelected = 0; 347 for (int idx = 0; idx < current.length; idx++) { 348 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 349 Set<Section> preferred = getPreferredSections(best[idx].getRequest()); 350 if (preferred != null && !preferred.isEmpty()) { 351 for (Section section : best[idx].getSections()) 352 if (preferred.contains(section)) 353 bestSelected++; 354 for (Section section : current[idx].getSections()) 355 if (preferred.contains(section)) 356 currentSelected++; 357 } 358 } 359 } 360 if (currentSelected > bestSelected) 361 return -1; 362 if (bestSelected > currentSelected) 363 return 1; 364 365 // 3.5 maximize preferences 366 double bestSelectedConfigs = 0, currentSelectedConfigs = 0; 367 double bestSelectedSections = 0, currentSelectedSections = 0; 368 for (int idx = 0; idx < current.length; idx++) { 369 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 370 bestSelectedSections += best[idx].percentSelectedSameSection(); 371 bestSelectedConfigs += best[idx].percentSelectedSameConfig(); 372 } 373 if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) { 374 currentSelectedSections += current[idx].percentSelectedSameSection(); 375 currentSelectedConfigs += current[idx].percentSelectedSameConfig(); 376 } 377 } 378 if (0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections > 0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections) return -1; 379 if (0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections > 0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections) return 1; 380 381 // 3.9 maximize selection with penalization for not followed reservations 382 if (res) { 383 for (int idx = 0; idx < current.length; idx++) { 384 if (best[idx] != null && best[idx].getAssignments() != null) { 385 if (current[idx] == null || current[idx].getSections() == null) 386 return 1; // higher priority request assigned 387 if (best[idx].getAdjustedPriority() < current[idx].getAdjustedPriority()) 388 return 1; // less alternative request assigned 389 if (best[idx].getAdjustedPriority() > current[idx].getAdjustedPriority()) 390 return -1; // less alternative request assigned 391 } else { 392 if (current[idx] != null && current[idx].getAssignments() != null) 393 return -1; // higher priority request assigned 394 } 395 } 396 } 397 398 // 3.95 avoid past sections 399 double bestPast = 0.0, currentPast = 0.0; 400 for (int idx = 0; idx < current.length; idx++) { 401 if (best[idx] != null && best[idx].getAssignments() != null) { 402 for (Section section : best[idx].getSections()) { 403 if (section.isPast()) 404 bestPast += 1.0 / best[idx].getSections().size(); 405 } 406 } 407 if (current[idx] != null && current[idx].getAssignments() != null) { 408 for (Section section : current[idx].getSections()) { 409 if (section.isPast()) 410 currentPast += 1.0 / current[idx].getSections().size(); 411 } 412 } 413 } 414 if (Math.abs(currentPast - bestPast) > 0.0001) { 415 if (currentPast < bestPast) 416 return -1; 417 if (bestPast < currentPast) 418 return 1; 419 } 420 421 // 4-5. student quality 422 if (getModel().getStudentQuality() != null) { 423 double bestQuality = 0, currentQuality = 0; 424 for (StudentQuality.Type type: StudentQuality.Type.values()) { 425 for (int idx = 0; idx < current.length; idx++) { 426 if (best[idx] != null && best[idx].getAssignments() != null) { 427 bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[idx]); 428 for (int x = 0; x < idx; x++) { 429 if (best[x] != null && best[x].getAssignments() != null) 430 bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[x], best[idx]); 431 } 432 } 433 if (current[idx] != null && current[idx].getAssignments() != null) { 434 currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[idx]); 435 for (int x = 0; x < idx; x++) { 436 if (current[x] != null && current[x].getAssignments() != null) 437 currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[x], current[idx]); 438 } 439 } 440 } 441 } 442 if (currentQuality < bestQuality) 443 return -1; 444 if (bestQuality < currentQuality) 445 return 1; 446 } else { 447 // 4. avoid time overlaps 448 if (getModel().getTimeOverlaps() != null) { 449 int bestTimeOverlaps = 0, currentTimeOverlaps = 0; 450 for (int idx = 0; idx < current.length; idx++) { 451 if (best[idx] != null && best[idx].getAssignments() != null) { 452 for (int x = 0; x < idx; x++) { 453 if (best[x] != null && best[x].getAssignments() != null) 454 bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]); 455 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 456 bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), best[idx]); 457 } 458 for (int x = 0; x < idx; x++) { 459 if (current[x] != null && current[x].getAssignments() != null) 460 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]); 461 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 462 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), current[idx]); 463 } 464 } 465 } 466 for (int idx = 0; idx < current.length; idx++) { 467 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 468 bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]); 469 } 470 if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) { 471 currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]); 472 } 473 } 474 if (currentTimeOverlaps < bestTimeOverlaps) 475 return -1; 476 if (bestTimeOverlaps < currentTimeOverlaps) 477 return 1; 478 } 479 480 // 5. avoid distance conflicts 481 if (getModel().getDistanceConflict() != null) { 482 int bestDistanceConf = 0, currentDistanceConf = 0; 483 for (int idx = 0; idx < current.length; idx++) { 484 if (best[idx] != null && best[idx].getAssignments() != null) { 485 bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[idx]); 486 for (int x = 0; x < idx; x++) { 487 if (best[x] != null && best[x].getAssignments() != null) 488 bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]); 489 } 490 } 491 if (current[idx] != null && current[idx].getAssignments() != null) { 492 currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[idx]); 493 for (int x = 0; x < idx; x++) { 494 if (current[x] != null && current[x].getAssignments() != null) 495 currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x], current[idx]); 496 } 497 } 498 } 499 if (currentDistanceConf < bestDistanceConf) 500 return -1; 501 if (bestDistanceConf < currentDistanceConf) 502 return 1; 503 } 504 } 505 506 // 6. avoid no-time and online sections (no-time first, online second) 507 int bestNoTime = 0, currentNoTime = 0; 508 int bestOnline = 0, currentOnline = 0; 509 for (int idx = 0; idx < current.length; idx++) { 510 if (best[idx] != null && best[idx].getAssignments() != null) { 511 for (Section section : best[idx].getSections()) { 512 if (!section.hasTime()) 513 bestNoTime++; 514 if (section.isOnline()) 515 bestOnline++; 516 } 517 for (Section section : current[idx].getSections()) { 518 if (!section.hasTime()) 519 currentNoTime++; 520 if (section.isOnline()) 521 currentOnline++; 522 } 523 } 524 } 525 if (currentNoTime < bestNoTime) 526 return -1; 527 if (bestNoTime < currentNoTime) 528 return 1; 529 if (currentOnline < bestOnline) 530 return -1; 531 if (bestOnline < currentOnline) 532 return 1; 533 534 // 7. balance sections 535 double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0; 536 int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0; 537 for (int idx = 0; idx < current.length; idx++) { 538 if (best[idx] != null && best[idx].getAssignments() != null) { 539 for (Section section : best[idx].getSections()) { 540 Subpart subpart = section.getSubpart(); 541 // skip unlimited and single section subparts 542 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 543 continue; 544 // average size 545 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 546 // section is below average 547 if (section.getLimit() < averageSize) 548 bestUnavailableSize += (averageSize - section.getLimit()) / averageSize; 549 bestAltSectionsWithLimit++; 550 } 551 for (Section section : current[idx].getSections()) { 552 Subpart subpart = section.getSubpart(); 553 // skip unlimited and single section subparts 554 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 555 continue; 556 // average size 557 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 558 // section is below average 559 if (section.getLimit() < averageSize) 560 currentUnavailableSize += (averageSize - section.getLimit()) / averageSize; 561 currentAltSectionsWithLimit++; 562 } 563 } 564 } 565 double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit 566 : 0.0); 567 double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize 568 / currentAltSectionsWithLimit : 0.0); 569 if (currentUnavailableSizeFraction < bestUnavailableSizeFraction) 570 return -1; 571 if (bestUnavailableSizeFraction < currentUnavailableSizeFraction) 572 return 1; 573 574 // 8. average penalty sections 575 double bestPenalty = 0.0, currentPenalty = 0.0; 576 for (int idx = 0; idx < current.length; idx++) { 577 if (best[idx] != null && best[idx].getAssignments() != null) { 578 for (Section section : best[idx].getSections()) 579 bestPenalty += section.getPenalty() / best[idx].getSections().size(); 580 for (Section section : current[idx].getSections()) 581 currentPenalty += section.getPenalty() / current[idx].getSections().size(); 582 } 583 } 584 if (currentPenalty < bestPenalty) 585 return -1; 586 if (bestPenalty < currentPenalty) 587 return 1; 588 589 return 0; 590 } 591 592 @Override 593 public boolean canImprove(Assignment<Request, Enrollment> assignment, int maxIdx, Enrollment[] current, 594 Enrollment[] best) { 595 // 0. best priority & alternativity ignoring free time requests 596 int alt = 0; 597 boolean ft = false; 598 boolean res = false; 599 for (int idx = 0; idx < current.length; idx++) { 600 if (isFreeTime(idx)) { 601 ft = true; 602 continue; 603 } 604 Request request = getRequest(idx); 605 if (request instanceof CourseRequest && ((CourseRequest)request).hasReservations()) res = true; 606 if (idx < maxIdx) { 607 if (best[idx] != null) { 608 if (current[idx] == null) 609 return false; // higher priority request assigned 610 if (best[idx].getTruePriority() < current[idx].getTruePriority()) 611 return false; // less alternative request assigned 612 if (best[idx].getTruePriority() > current[idx].getTruePriority()) 613 return true; // less alternative request assigned 614 if (request.isAlternative()) 615 alt--; 616 } else { 617 if (current[idx] != null) 618 return true; // higher priority request assigned 619 if (!request.isAlternative()) 620 alt++; 621 } 622 } else { 623 if (best[idx] != null) { 624 if (best[idx].getTruePriority() > 0) 625 return true; // alternativity can be improved 626 } else { 627 if (!request.isAlternative() || alt > 0) 628 return true; // priority can be improved 629 } 630 } 631 } 632 633 // 0.1. allowed, but not available sections 634 int notAvailable = 0; 635 for (int idx = 0; idx < current.length; idx++) { 636 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].getRequest() instanceof CourseRequest && best[idx].getReservation() != null && best[idx].getReservation().canAssignOverLimit()) { 637 for (Section section: best[idx].getSections()) { 638 if (section.getLimit() == 0) 639 notAvailable ++; 640 } 641 } 642 if (idx < maxIdx && current[idx] != null && current[idx].getAssignments() != null && current[idx].getRequest() instanceof CourseRequest && current[idx].getReservation() != null && current[idx].getReservation().canAssignOverLimit()) { 643 for (Section section: current[idx].getSections()) { 644 if (section.getLimit() == 0) 645 notAvailable --; 646 } 647 } 648 } 649 if (notAvailable > 0) { 650 return true; 651 } 652 653 // 0.5. avoid course time overlaps & unavailability overlaps 654 if (getModel().getStudentQuality() != null) { 655 int bestTimeOverlaps = 0, currentTimeOverlaps = 0; 656 for (int idx = 0; idx < current.length; idx++) { 657 if (best[idx] != null && best[idx].getRequest() instanceof CourseRequest) { 658 for (int x = 0; x < idx; x++) { 659 if (best[x] != null && best[x].getRequest() instanceof CourseRequest) 660 bestTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.CourseTimeOverlap, best[x], best[idx]); 661 } 662 } 663 if (current[idx] != null && idx < maxIdx && current[idx].getRequest() instanceof CourseRequest) { 664 for (int x = 0; x < idx; x++) { 665 if (current[x] != null && current[x].getRequest() instanceof CourseRequest) 666 currentTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.CourseTimeOverlap, current[x], current[idx]); 667 } 668 } 669 } 670 for (int idx = 0; idx < current.length; idx++) { 671 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 672 bestTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, best[idx]); 673 } 674 if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) { 675 currentTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, current[idx]); 676 } 677 } 678 if (currentTimeOverlaps < bestTimeOverlaps) 679 return true; 680 if (bestTimeOverlaps < currentTimeOverlaps) 681 return false; 682 } else if (getModel().getTimeOverlaps() != null) { 683 int bestTimeOverlaps = 0, currentTimeOverlaps = 0; 684 for (int idx = 0; idx < current.length; idx++) { 685 if (best[idx] != null && best[idx].getRequest() instanceof CourseRequest) { 686 for (int x = 0; x < idx; x++) { 687 if (best[x] != null && best[x].getRequest() instanceof CourseRequest) 688 bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]); 689 } 690 } 691 if (current[idx] != null && idx < maxIdx && current[idx].getRequest() instanceof CourseRequest) { 692 for (int x = 0; x < idx; x++) { 693 if (current[x] != null && current[x].getRequest() instanceof CourseRequest) 694 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]); 695 } 696 } 697 } 698 for (int idx = 0; idx < current.length; idx++) { 699 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 700 bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]); 701 } 702 if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) { 703 currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]); 704 } 705 } 706 if (currentTimeOverlaps < bestTimeOverlaps) 707 return true; 708 if (bestTimeOverlaps < currentTimeOverlaps) 709 return false; 710 } 711 712 // 1. maximize number of penalties 713 double bestPenalties = 0, currentPenalties = 0; 714 for (int idx = 0; idx < current.length; idx++) { 715 if (best[idx] != null) { 716 for (Section section : best[idx].getSections()) 717 bestPenalties += getModel().getOverExpected(assignment, best, idx, section, best[idx].getRequest()); 718 } 719 if (current[idx] != null && idx < maxIdx) { 720 for (Section section : current[idx].getSections()) 721 currentPenalties += getModel().getOverExpected(assignment, current, idx, section, current[idx].getRequest()); 722 } 723 } 724 if (currentPenalties < bestPenalties) 725 return true; 726 if (bestPenalties < currentPenalties) 727 return false; 728 729 // 2. best priority & alternativity including free times 730 if (ft) { 731 alt = 0; 732 for (int idx = 0; idx < current.length; idx++) { 733 Request request = getStudent().getRequests().get(idx); 734 if (idx < maxIdx) { 735 if (best[idx] != null) { 736 if (current[idx] == null) 737 return false; // higher priority request assigned 738 if (best[idx].getTruePriority() < current[idx].getTruePriority()) 739 return false; // less alternative request assigned 740 if (best[idx].getTruePriority() > current[idx].getTruePriority()) 741 return true; // less alternative request assigned 742 if (request.isAlternative()) 743 alt--; 744 } else { 745 if (current[idx] != null) 746 return true; // higher priority request assigned 747 if (request instanceof CourseRequest && !request.isAlternative()) 748 alt++; 749 } 750 } else { 751 if (best[idx] != null) { 752 if (best[idx].getTruePriority() > 0) 753 return true; // alternativity can be improved 754 } else { 755 if (!request.isAlternative() || alt > 0) 756 return true; // priority can be improved 757 } 758 } 759 } 760 } 761 762 // 3. maximize selection 763 int bestSelected = 0, currentSelected = 0; 764 for (int idx = 0; idx < current.length; idx++) { 765 if (best[idx] != null && best[idx].isCourseRequest()) { 766 Set<Section> preferred = getPreferredSections(best[idx].getRequest()); 767 if (preferred != null && !preferred.isEmpty()) { 768 for (Section section : best[idx].getSections()) 769 if (preferred.contains(section)) { 770 if (idx < maxIdx) 771 bestSelected++; 772 } else if (idx >= maxIdx) 773 bestSelected--; 774 } 775 } 776 if (current[idx] != null && idx < maxIdx && current[idx].isCourseRequest()) { 777 Set<Section> preferred = getPreferredSections(current[idx].getRequest()); 778 if (preferred != null && !preferred.isEmpty()) { 779 for (Section section : current[idx].getSections()) 780 if (preferred.contains(section)) 781 currentSelected++; 782 } 783 } 784 } 785 if (currentSelected > bestSelected) 786 return true; 787 if (bestSelected > currentSelected) 788 return false; 789 790 // 3.5 maximize preferences 791 double bestSelectedConfigs = 0, currentSelectedConfigs = 0; 792 double bestSelectedSections = 0, currentSelectedSections = 0; 793 for (int idx = 0; idx < current.length; idx++) { 794 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 795 bestSelectedSections += best[idx].percentSelectedSameSection(); 796 bestSelectedConfigs += best[idx].percentSelectedSameConfig(); 797 if (idx >= maxIdx) { 798 bestSelectedSections -= 1.0; 799 bestSelectedConfigs -= 1.0; 800 } 801 } 802 if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) { 803 currentSelectedSections += current[idx].percentSelectedSameSection(); 804 currentSelectedConfigs += current[idx].percentSelectedSameConfig(); 805 } 806 } 807 if (0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections > 0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections) return true; 808 if (0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections > 0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections) return false; 809 810 // 3.9 maximize selection with penalization for not followed reservations 811 if (res) { 812 alt = 0; 813 for (int idx = 0; idx < current.length; idx++) { 814 Request request = getStudent().getRequests().get(idx); 815 if (idx < maxIdx) { 816 if (best[idx] != null) { 817 if (current[idx] == null) 818 return false; // higher priority request assigned 819 if (best[idx].getAdjustedPriority() < current[idx].getAdjustedPriority()) 820 return false; // less alternative request assigned 821 if (best[idx].getAdjustedPriority() > current[idx].getAdjustedPriority()) 822 return true; // less alternative request assigned 823 if (request.isAlternative()) 824 alt--; 825 } else { 826 if (current[idx] != null) 827 return true; // higher priority request assigned 828 if (request instanceof CourseRequest && !request.isAlternative()) 829 alt++; 830 } 831 } else { 832 if (best[idx] != null) { 833 if (best[idx].getTruePriority() > 0) 834 return true; // alternativity can be improved 835 } else { 836 if (!request.isAlternative() || alt > 0) 837 return true; // priority can be improved 838 } 839 } 840 } 841 } 842 843 // 3.95 avoid past sections 844 double bestPast = 0.0, currentPast = 0.0; 845 for (int idx = 0; idx < current.length; idx++) { 846 if (best[idx] != null && best[idx].getAssignments() != null) { 847 for (Section section : best[idx].getSections()) { 848 if (section.isPast()) 849 bestPast += 1.0 / best[idx].getSections().size(); 850 } 851 } 852 if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null) { 853 for (Section section : current[idx].getSections()) { 854 if (section.isPast()) 855 currentPast += 1.0 / current[idx].getSections().size(); 856 } 857 } 858 } 859 if (Math.abs(currentPast - bestPast) > 0.0001) { 860 if (currentPast < bestPast) 861 return true; 862 if (bestPast < currentPast) 863 return false; 864 } 865 866 // 4-5. student quality 867 if (getModel().getStudentQuality() != null) { 868 double bestQuality = 0, currentQuality = 0; 869 for (StudentQuality.Type type: StudentQuality.Type.values()) { 870 for (int idx = 0; idx < current.length; idx++) { 871 if (best[idx] != null) { 872 bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[idx]); 873 for (int x = 0; x < idx; x++) { 874 if (best[x] != null) 875 bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[x], best[idx]); 876 } 877 } 878 if (current[idx] != null && idx < maxIdx) { 879 currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[idx]); 880 for (int x = 0; x < idx; x++) { 881 if (current[x] != null) 882 currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[x], current[idx]); 883 } 884 } 885 } 886 } 887 if (currentQuality < bestQuality) 888 return true; 889 if (bestQuality < currentQuality) 890 return false; 891 } else { 892 // 4. avoid time overlaps 893 if (getModel().getTimeOverlaps() != null) { 894 int bestTimeOverlaps = 0, currentTimeOverlaps = 0; 895 for (int idx = 0; idx < current.length; idx++) { 896 if (best[idx] != null) { 897 for (int x = 0; x < idx; x++) { 898 if (best[x] != null) 899 bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]); 900 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 901 bestTimeOverlaps += getModel().getTimeOverlaps() 902 .nrConflicts( 903 ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), 904 best[idx]); 905 } 906 } 907 if (current[idx] != null && idx < maxIdx) { 908 for (int x = 0; x < idx; x++) { 909 if (current[x] != null) 910 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]); 911 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 912 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts( 913 ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), 914 current[idx]); 915 } 916 } 917 } 918 for (int idx = 0; idx < current.length; idx++) { 919 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 920 bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]); 921 } 922 if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) { 923 currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]); 924 } 925 } 926 if (currentTimeOverlaps < bestTimeOverlaps) 927 return true; 928 if (bestTimeOverlaps < currentTimeOverlaps) 929 return false; 930 } 931 932 // 5. avoid distance conflicts 933 if (getModel().getDistanceConflict() != null) { 934 int bestDistanceConf = 0, currentDistanceConf = 0; 935 for (int idx = 0; idx < current.length; idx++) { 936 if (best[idx] != null) { 937 bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[idx]); 938 for (int x = 0; x < idx; x++) { 939 if (best[x] != null) 940 bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]); 941 } 942 } 943 if (current[idx] != null && idx < maxIdx) { 944 currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[idx]); 945 for (int x = 0; x < idx; x++) { 946 if (current[x] != null) 947 currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x], 948 current[idx]); 949 } 950 } 951 } 952 if (currentDistanceConf < bestDistanceConf) 953 return true; 954 if (bestDistanceConf < currentDistanceConf) 955 return false; 956 } 957 } 958 959 // 6. avoid no-time and online sections (no-time first, online second) 960 int bestNoTime = 0, currentNoTime = 0; 961 int bestOnline = 0, currentOnline = 0; 962 for (int idx = 0; idx < current.length; idx++) { 963 if (best[idx] != null) { 964 for (Section section : best[idx].getSections()) { 965 if (!section.hasTime()) 966 bestNoTime++; 967 if (section.isOnline()) 968 bestOnline++; 969 } 970 } 971 if (current[idx] != null && idx < maxIdx) { 972 for (Section section : current[idx].getSections()) { 973 if (!section.hasTime()) 974 currentNoTime++; 975 if (section.isOnline()) 976 currentOnline++; 977 } 978 } 979 } 980 if (currentNoTime < bestNoTime) 981 return true; 982 if (bestNoTime < currentNoTime) 983 return false; 984 if (currentOnline < bestOnline) 985 return true; 986 if (bestOnline < currentOnline) 987 return false; 988 989 // 7. balance sections 990 double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0; 991 int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0; 992 for (int idx = 0; idx < current.length; idx++) { 993 if (best[idx] != null) { 994 for (Section section : best[idx].getSections()) { 995 Subpart subpart = section.getSubpart(); 996 // skip unlimited and single section subparts 997 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 998 continue; 999 // average size 1000 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 1001 // section is below average 1002 if (section.getLimit() < averageSize) 1003 bestUnavailableSize += (averageSize - section.getLimit()) / averageSize; 1004 bestAltSectionsWithLimit++; 1005 } 1006 } 1007 if (current[idx] != null && idx < maxIdx) { 1008 for (Section section : current[idx].getSections()) { 1009 Subpart subpart = section.getSubpart(); 1010 // skip unlimited and single section subparts 1011 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 1012 continue; 1013 // average size 1014 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 1015 // section is below average 1016 if (section.getLimit() < averageSize) 1017 currentUnavailableSize += (averageSize - section.getLimit()) / averageSize; 1018 currentAltSectionsWithLimit++; 1019 } 1020 } 1021 } 1022 double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit 1023 : 0.0); 1024 double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize 1025 / currentAltSectionsWithLimit : 0.0); 1026 if (currentUnavailableSizeFraction < bestUnavailableSizeFraction) 1027 return true; 1028 if (bestUnavailableSizeFraction < currentUnavailableSizeFraction) 1029 return false; 1030 1031 // 8. average penalty sections 1032 double bestPenalty = 0.0, currentPenalty = 0.0; 1033 for (int idx = 0; idx < current.length; idx++) { 1034 if (best[idx] != null) { 1035 for (Section section : best[idx].getSections()) 1036 bestPenalty += section.getPenalty() / best[idx].getSections().size(); 1037 if (idx >= maxIdx && best[idx].isCourseRequest()) 1038 bestPenalty -= ((CourseRequest) best[idx].getRequest()).getMinPenalty(); 1039 } 1040 if (current[idx] != null && idx < maxIdx) { 1041 for (Section section : current[idx].getSections()) 1042 currentPenalty += section.getPenalty() / current[idx].getSections().size(); 1043 } 1044 } 1045 if (currentPenalty < bestPenalty) 1046 return true; 1047 if (bestPenalty < currentPenalty) 1048 return false; 1049 1050 return true; 1051 } 1052 1053 @Override 1054 public double getTotalWeight(Assignment<Request, Enrollment> assignment, Enrollment[] enrollemnts) { 1055 if (enrollemnts == null) 1056 return 0.0; 1057 double value = 0.0; 1058 for (int idx = 0; idx < enrollemnts.length; idx++) { 1059 if (enrollemnts[idx] != null) 1060 if (getModel().getStudentQuality() != null) { 1061 value += getWeight(assignment, enrollemnts[idx], getStudentQualityConflicts(enrollemnts, idx)); 1062 } else { 1063 value += getWeight(assignment, enrollemnts[idx], getDistanceConflicts(enrollemnts, idx), getTimeOverlappingConflicts(enrollemnts, idx)); 1064 } 1065 } 1066 return value; 1067 } 1068 1069 @Override 1070 public int compare(Assignment<Request, Enrollment> assignment, Enrollment e1, Enrollment e2) { 1071 // 1. alternativity 1072 if (e1.getTruePriority() < e2.getTruePriority()) 1073 return -1; 1074 if (e1.getTruePriority() > e2.getTruePriority()) 1075 return 1; 1076 1077 // 1.5 not available sections 1078 int na1 = 0, na2 = 0; 1079 for (Section section: e1.getSections()) 1080 if (section.getLimit() == 0) na1++; 1081 for (Section section: e2.getSections()) 1082 if (section.getLimit() == 0) na2++; 1083 if (na1 < na2) return -1; 1084 if (na1 > na2) return 1; 1085 1086 // 2. maximize number of penalties 1087 double p1 = 0, p2 = 0; 1088 for (Section section : e1.getSections()) 1089 p1 += getModel().getOverExpected(assignment, section, e1.getRequest()); 1090 for (Section section : e2.getSections()) 1091 p2 += getModel().getOverExpected(assignment, section, e2.getRequest()); 1092 if (p1 < p2) 1093 return -1; 1094 if (p2 < p1) 1095 return 1; 1096 1097 // 3. maximize selection 1098 if (e1.isCourseRequest()) { 1099 Set<Section> preferred = getPreferredSections(e1.getRequest()); 1100 if (preferred != null && !preferred.isEmpty()) { 1101 int s1 = 0, s2 = 0; 1102 for (Section section : e1.getSections()) 1103 if (preferred.contains(section)) 1104 s1++; 1105 for (Section section : e2.getSections()) 1106 if (preferred.contains(section)) 1107 s2++; 1108 if (s2 > s1) 1109 return -1; 1110 if (s1 > s2) 1111 return 1; 1112 } 1113 } 1114 1115 // 3.5 maximize preferences 1116 if (e1.isCourseRequest()) { 1117 double s1 = 0.3 * e1.percentSelectedSameConfig() + 0.7 * e1.percentSelectedSameSection(); 1118 double s2 = 0.3 * e2.percentSelectedSameConfig() + 0.7 * e2.percentSelectedSameSection(); 1119 if (s1 > s2) return -1; 1120 if (s2 > s1) return 1; 1121 } 1122 1123 // 3.9 maximize selection with penalization for not followed reservations 1124 if (e1.getAdjustedPriority() < e2.getAdjustedPriority()) 1125 return -1; 1126 if (e1.getAdjustedPriority() > e2.getAdjustedPriority()) 1127 return 1; 1128 1129 // 3.95 avoid past sections 1130 double w1 = 0, w2 = 0; 1131 for (Section section : e1.getSections()) { 1132 if (section.isPast()) 1133 w1 += 1.0 / e1.getSections().size(); 1134 } 1135 for (Section section : e2.getSections()) { 1136 if (section.isPast()) 1137 w2 += 1.0 / e2.getSections().size(); 1138 } 1139 if (Math.abs(w1 - w2) > 0.0001) { 1140 if (w1 < w2) 1141 return -1; 1142 if (w2 < w1) 1143 return 1; 1144 } 1145 1146 // 4. avoid time overlaps 1147 if (getTimesToAvoid() == null) { 1148 if (getModel().getStudentQuality() != null) { 1149 int o1 = getModel().getStudentQuality().penalty(StudentQuality.Type.FreeTimeOverlap, e1) + getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, e1); 1150 int o2 = getModel().getStudentQuality().penalty(StudentQuality.Type.FreeTimeOverlap, e2) + getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, e2); 1151 if (o1 < o2) 1152 return -1; 1153 if (o2 < o1) 1154 return 1; 1155 } else if (getModel().getTimeOverlaps() != null) { 1156 int o1 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e1) + getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(e1); 1157 int o2 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e2) + getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(e2); 1158 if (o1 < o2) 1159 return -1; 1160 if (o2 < o1) 1161 return 1; 1162 } 1163 } else { 1164 if (e1.getRequest().equals(e2.getRequest()) && e1.isCourseRequest()) { 1165 double o1 = 0.0, o2 = 0.0; 1166 for (Section s : e1.getSections()) { 1167 if (s.getTime() != null) 1168 for (TimeToAvoid avoid : getTimesToAvoid()) { 1169 if (avoid.priority() > e1.getRequest().getPriority()) 1170 o1 += avoid.overlap(s.getTime()); 1171 } 1172 } 1173 for (Section s : e2.getSections()) { 1174 if (s.getTime() != null) 1175 for (TimeToAvoid avoid : getTimesToAvoid()) { 1176 if (avoid.priority() > e2.getRequest().getPriority()) 1177 o2 += avoid.overlap(s.getTime()); 1178 } 1179 } 1180 if (o1 < o2) 1181 return -1; 1182 if (o2 < o1) 1183 return 1; 1184 } 1185 } 1186 1187 // 5. avoid distance conflicts 1188 if (getModel().getDistanceConflict() != null) { 1189 int c1 = getModel().getDistanceConflict().nrConflicts(e1); 1190 int c2 = getModel().getDistanceConflict().nrConflicts(e2); 1191 if (c1 < c2) 1192 return -1; 1193 if (c2 < c1) 1194 return 1; 1195 } 1196 1197 // 6. avoid no-time and online sections (no-time first, online second) 1198 int n1 = 0, n2 = 0; 1199 int o1 = 0, o2 = 0; 1200 for (Section section : e1.getSections()) { 1201 if (!section.hasTime()) 1202 n1++; 1203 if (section.isOnline()) 1204 o1++; 1205 } 1206 for (Section section : e2.getSections()) { 1207 if (!section.hasTime()) 1208 n2++; 1209 if (section.isOnline()) 1210 o2++; 1211 } 1212 if (n1 < n2) 1213 return -1; 1214 if (n2 < n1) 1215 return 1; 1216 if (o1 < o2) 1217 return -1; 1218 if (o2 < o1) 1219 return 1; 1220 1221 // 7. balance sections 1222 double u1 = 0.0, u2 = 0.0; 1223 int a1 = 0, a2 = 0; 1224 for (Section section : e1.getSections()) { 1225 Subpart subpart = section.getSubpart(); 1226 // skip unlimited and single section subparts 1227 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 1228 continue; 1229 // average size 1230 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 1231 // section is below average 1232 if (section.getLimit() < averageSize) 1233 u1 += (averageSize - section.getLimit()) / averageSize; 1234 a1++; 1235 } 1236 for (Section section : e2.getSections()) { 1237 Subpart subpart = section.getSubpart(); 1238 // skip unlimited and single section subparts 1239 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 1240 continue; 1241 // average size 1242 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 1243 // section is below average 1244 if (section.getLimit() < averageSize) 1245 u2 += (averageSize - section.getLimit()) / averageSize; 1246 a2++; 1247 } 1248 double f1 = (u1 > 0 ? u1 / a1 : 0.0); 1249 double f2 = (u2 > 0 ? u2 / a2 : 0.0); 1250 if (f1 < f2) 1251 return -1; 1252 if (f2 < f1) 1253 return 1; 1254 1255 // 8. average penalty sections 1256 double x1 = 0.0, x2 = 0.0; 1257 for (Section section : e1.getSections()) 1258 x1 += section.getPenalty() / e1.getSections().size(); 1259 for (Section section : e2.getSections()) 1260 x2 += section.getPenalty() / e2.getSections().size(); 1261 if (x1 < x2) 1262 return -1; 1263 if (x2 < x1) 1264 return 1; 1265 1266 return 0; 1267 } 1268 1269 /** 1270 * Time to be avoided. 1271 */ 1272 public static class TimeToAvoid { 1273 private TimeLocation iTime; 1274 private double iPenalty; 1275 private int iPriority; 1276 1277 public TimeToAvoid(TimeLocation time, int penalty, int priority) { 1278 iTime = time; 1279 iPenalty = penalty; 1280 iPriority = priority; 1281 } 1282 1283 public int priority() { 1284 return iPriority; 1285 } 1286 1287 public double overlap(TimeLocation time) { 1288 if (time.hasIntersection(iTime)) { 1289 return iPenalty * (time.nrSharedDays(iTime) * time.nrSharedHours(iTime)) 1290 / (iTime.getNrMeetings() * iTime.getLength()); 1291 } else { 1292 return 0.0; 1293 } 1294 } 1295 1296 @Override 1297 public String toString() { 1298 return iTime.getLongName(true) + " (" + iPriority + "/" + iPenalty + ")"; 1299 } 1300 } 1301}