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 Tomas Muller<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 // 4-5. student quality 399 if (getModel().getStudentQuality() != null) { 400 double bestQuality = 0, currentQuality = 0; 401 for (StudentQuality.Type type: StudentQuality.Type.values()) { 402 for (int idx = 0; idx < current.length; idx++) { 403 if (best[idx] != null && best[idx].getAssignments() != null) { 404 bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[idx]); 405 for (int x = 0; x < idx; x++) { 406 if (best[x] != null && best[x].getAssignments() != null) 407 bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[x], best[idx]); 408 } 409 } 410 if (current[idx] != null && current[idx].getAssignments() != null) { 411 currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[idx]); 412 for (int x = 0; x < idx; x++) { 413 if (current[x] != null && current[x].getAssignments() != null) 414 currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[x], current[idx]); 415 } 416 } 417 } 418 } 419 if (currentQuality < bestQuality) 420 return -1; 421 if (bestQuality < currentQuality) 422 return 1; 423 } else { 424 // 4. avoid time overlaps 425 if (getModel().getTimeOverlaps() != null) { 426 int bestTimeOverlaps = 0, currentTimeOverlaps = 0; 427 for (int idx = 0; idx < current.length; idx++) { 428 if (best[idx] != null && best[idx].getAssignments() != null) { 429 for (int x = 0; x < idx; x++) { 430 if (best[x] != null && best[x].getAssignments() != null) 431 bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]); 432 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 433 bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), best[idx]); 434 } 435 for (int x = 0; x < idx; x++) { 436 if (current[x] != null && current[x].getAssignments() != null) 437 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]); 438 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 439 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), current[idx]); 440 } 441 } 442 } 443 for (int idx = 0; idx < current.length; idx++) { 444 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 445 bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]); 446 } 447 if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) { 448 currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]); 449 } 450 } 451 if (currentTimeOverlaps < bestTimeOverlaps) 452 return -1; 453 if (bestTimeOverlaps < currentTimeOverlaps) 454 return 1; 455 } 456 457 // 5. avoid distance conflicts 458 if (getModel().getDistanceConflict() != null) { 459 int bestDistanceConf = 0, currentDistanceConf = 0; 460 for (int idx = 0; idx < current.length; idx++) { 461 if (best[idx] != null && best[idx].getAssignments() != null) { 462 bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[idx]); 463 for (int x = 0; x < idx; x++) { 464 if (best[x] != null && best[x].getAssignments() != null) 465 bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]); 466 } 467 } 468 if (current[idx] != null && current[idx].getAssignments() != null) { 469 currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[idx]); 470 for (int x = 0; x < idx; x++) { 471 if (current[x] != null && current[x].getAssignments() != null) 472 currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x], current[idx]); 473 } 474 } 475 } 476 if (currentDistanceConf < bestDistanceConf) 477 return -1; 478 if (bestDistanceConf < currentDistanceConf) 479 return 1; 480 } 481 } 482 483 // 6. avoid no-time and online sections (no-time first, online second) 484 int bestNoTime = 0, currentNoTime = 0; 485 int bestOnline = 0, currentOnline = 0; 486 for (int idx = 0; idx < current.length; idx++) { 487 if (best[idx] != null && best[idx].getAssignments() != null) { 488 for (Section section : best[idx].getSections()) { 489 if (section.getTime() == null) 490 bestNoTime++; 491 if (section.isOnline()) 492 bestOnline++; 493 } 494 for (Section section : current[idx].getSections()) { 495 if (section.getTime() == null) 496 currentNoTime++; 497 if (section.isOnline()) 498 currentOnline++; 499 } 500 } 501 } 502 if (currentNoTime < bestNoTime) 503 return -1; 504 if (bestNoTime < currentNoTime) 505 return 1; 506 if (currentOnline < bestOnline) 507 return -1; 508 if (bestOnline < currentOnline) 509 return 1; 510 511 // 7. balance sections 512 double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0; 513 int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0; 514 for (int idx = 0; idx < current.length; idx++) { 515 if (best[idx] != null && best[idx].getAssignments() != null) { 516 for (Section section : best[idx].getSections()) { 517 Subpart subpart = section.getSubpart(); 518 // skip unlimited and single section subparts 519 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 520 continue; 521 // average size 522 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 523 // section is below average 524 if (section.getLimit() < averageSize) 525 bestUnavailableSize += (averageSize - section.getLimit()) / averageSize; 526 bestAltSectionsWithLimit++; 527 } 528 for (Section section : current[idx].getSections()) { 529 Subpart subpart = section.getSubpart(); 530 // skip unlimited and single section subparts 531 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 532 continue; 533 // average size 534 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 535 // section is below average 536 if (section.getLimit() < averageSize) 537 currentUnavailableSize += (averageSize - section.getLimit()) / averageSize; 538 currentAltSectionsWithLimit++; 539 } 540 } 541 } 542 double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit 543 : 0.0); 544 double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize 545 / currentAltSectionsWithLimit : 0.0); 546 if (currentUnavailableSizeFraction < bestUnavailableSizeFraction) 547 return -1; 548 if (bestUnavailableSizeFraction < currentUnavailableSizeFraction) 549 return 1; 550 551 // 8. average penalty sections 552 double bestPenalty = 0.0, currentPenalty = 0.0; 553 for (int idx = 0; idx < current.length; idx++) { 554 if (best[idx] != null && best[idx].getAssignments() != null) { 555 for (Section section : best[idx].getSections()) 556 bestPenalty += section.getPenalty() / best[idx].getSections().size(); 557 for (Section section : current[idx].getSections()) 558 currentPenalty += section.getPenalty() / current[idx].getSections().size(); 559 } 560 } 561 if (currentPenalty < bestPenalty) 562 return -1; 563 if (bestPenalty < currentPenalty) 564 return 1; 565 566 return 0; 567 } 568 569 @Override 570 public boolean canImprove(Assignment<Request, Enrollment> assignment, int maxIdx, Enrollment[] current, 571 Enrollment[] best) { 572 // 0. best priority & alternativity ignoring free time requests 573 int alt = 0; 574 boolean ft = false; 575 boolean res = false; 576 for (int idx = 0; idx < current.length; idx++) { 577 if (isFreeTime(idx)) { 578 ft = true; 579 continue; 580 } 581 Request request = getRequest(idx); 582 if (request instanceof CourseRequest && ((CourseRequest)request).hasReservations()) res = true; 583 if (idx < maxIdx) { 584 if (best[idx] != null) { 585 if (current[idx] == null) 586 return false; // higher priority request assigned 587 if (best[idx].getTruePriority() < current[idx].getTruePriority()) 588 return false; // less alternative request assigned 589 if (best[idx].getTruePriority() > current[idx].getTruePriority()) 590 return true; // less alternative request assigned 591 if (request.isAlternative()) 592 alt--; 593 } else { 594 if (current[idx] != null) 595 return true; // higher priority request assigned 596 if (!request.isAlternative()) 597 alt++; 598 } 599 } else { 600 if (best[idx] != null) { 601 if (best[idx].getTruePriority() > 0) 602 return true; // alternativity can be improved 603 } else { 604 if (!request.isAlternative() || alt > 0) 605 return true; // priority can be improved 606 } 607 } 608 } 609 610 // 0.1. allowed, but not available sections 611 int notAvailable = 0; 612 for (int idx = 0; idx < current.length; idx++) { 613 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].getRequest() instanceof CourseRequest && best[idx].getReservation() != null && best[idx].getReservation().canAssignOverLimit()) { 614 for (Section section: best[idx].getSections()) { 615 if (section.getLimit() == 0) 616 notAvailable ++; 617 } 618 } 619 if (idx < maxIdx && current[idx] != null && current[idx].getAssignments() != null && current[idx].getRequest() instanceof CourseRequest && current[idx].getReservation() != null && current[idx].getReservation().canAssignOverLimit()) { 620 for (Section section: current[idx].getSections()) { 621 if (section.getLimit() == 0) 622 notAvailable --; 623 } 624 } 625 } 626 if (notAvailable > 0) { 627 return true; 628 } 629 630 // 0.5. avoid course time overlaps & unavailability overlaps 631 if (getModel().getStudentQuality() != null) { 632 int bestTimeOverlaps = 0, currentTimeOverlaps = 0; 633 for (int idx = 0; idx < current.length; idx++) { 634 if (best[idx] != null && best[idx].getRequest() instanceof CourseRequest) { 635 for (int x = 0; x < idx; x++) { 636 if (best[x] != null && best[x].getRequest() instanceof CourseRequest) 637 bestTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.CourseTimeOverlap, best[x], best[idx]); 638 } 639 } 640 if (current[idx] != null && idx < maxIdx && current[idx].getRequest() instanceof CourseRequest) { 641 for (int x = 0; x < idx; x++) { 642 if (current[x] != null && current[x].getRequest() instanceof CourseRequest) 643 currentTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.CourseTimeOverlap, current[x], current[idx]); 644 } 645 } 646 } 647 for (int idx = 0; idx < current.length; idx++) { 648 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 649 bestTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, best[idx]); 650 } 651 if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) { 652 currentTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, current[idx]); 653 } 654 } 655 if (currentTimeOverlaps < bestTimeOverlaps) 656 return true; 657 if (bestTimeOverlaps < currentTimeOverlaps) 658 return false; 659 } else if (getModel().getTimeOverlaps() != null) { 660 int bestTimeOverlaps = 0, currentTimeOverlaps = 0; 661 for (int idx = 0; idx < current.length; idx++) { 662 if (best[idx] != null && best[idx].getRequest() instanceof CourseRequest) { 663 for (int x = 0; x < idx; x++) { 664 if (best[x] != null && best[x].getRequest() instanceof CourseRequest) 665 bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]); 666 } 667 } 668 if (current[idx] != null && idx < maxIdx && current[idx].getRequest() instanceof CourseRequest) { 669 for (int x = 0; x < idx; x++) { 670 if (current[x] != null && current[x].getRequest() instanceof CourseRequest) 671 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]); 672 } 673 } 674 } 675 for (int idx = 0; idx < current.length; idx++) { 676 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 677 bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]); 678 } 679 if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) { 680 currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]); 681 } 682 } 683 if (currentTimeOverlaps < bestTimeOverlaps) 684 return true; 685 if (bestTimeOverlaps < currentTimeOverlaps) 686 return false; 687 } 688 689 // 1. maximize number of penalties 690 double bestPenalties = 0, currentPenalties = 0; 691 for (int idx = 0; idx < current.length; idx++) { 692 if (best[idx] != null) { 693 for (Section section : best[idx].getSections()) 694 bestPenalties += getModel().getOverExpected(assignment, best, idx, section, best[idx].getRequest()); 695 } 696 if (current[idx] != null && idx < maxIdx) { 697 for (Section section : current[idx].getSections()) 698 currentPenalties += getModel().getOverExpected(assignment, current, idx, section, current[idx].getRequest()); 699 } 700 } 701 if (currentPenalties < bestPenalties) 702 return true; 703 if (bestPenalties < currentPenalties) 704 return false; 705 706 // 2. best priority & alternativity including free times 707 if (ft) { 708 alt = 0; 709 for (int idx = 0; idx < current.length; idx++) { 710 Request request = getStudent().getRequests().get(idx); 711 if (idx < maxIdx) { 712 if (best[idx] != null) { 713 if (current[idx] == null) 714 return false; // higher priority request assigned 715 if (best[idx].getTruePriority() < current[idx].getTruePriority()) 716 return false; // less alternative request assigned 717 if (best[idx].getTruePriority() > current[idx].getTruePriority()) 718 return true; // less alternative request assigned 719 if (request.isAlternative()) 720 alt--; 721 } else { 722 if (current[idx] != null) 723 return true; // higher priority request assigned 724 if (request instanceof CourseRequest && !request.isAlternative()) 725 alt++; 726 } 727 } else { 728 if (best[idx] != null) { 729 if (best[idx].getTruePriority() > 0) 730 return true; // alternativity can be improved 731 } else { 732 if (!request.isAlternative() || alt > 0) 733 return true; // priority can be improved 734 } 735 } 736 } 737 } 738 739 // 3. maximize selection 740 int bestSelected = 0, currentSelected = 0; 741 for (int idx = 0; idx < current.length; idx++) { 742 if (best[idx] != null && best[idx].isCourseRequest()) { 743 Set<Section> preferred = getPreferredSections(best[idx].getRequest()); 744 if (preferred != null && !preferred.isEmpty()) { 745 for (Section section : best[idx].getSections()) 746 if (preferred.contains(section)) { 747 if (idx < maxIdx) 748 bestSelected++; 749 } else if (idx >= maxIdx) 750 bestSelected--; 751 } 752 } 753 if (current[idx] != null && idx < maxIdx && current[idx].isCourseRequest()) { 754 Set<Section> preferred = getPreferredSections(current[idx].getRequest()); 755 if (preferred != null && !preferred.isEmpty()) { 756 for (Section section : current[idx].getSections()) 757 if (preferred.contains(section)) 758 currentSelected++; 759 } 760 } 761 } 762 if (currentSelected > bestSelected) 763 return true; 764 if (bestSelected > currentSelected) 765 return false; 766 767 // 3.5 maximize preferences 768 double bestSelectedConfigs = 0, currentSelectedConfigs = 0; 769 double bestSelectedSections = 0, currentSelectedSections = 0; 770 for (int idx = 0; idx < current.length; idx++) { 771 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 772 bestSelectedSections += best[idx].percentSelectedSameSection(); 773 bestSelectedConfigs += best[idx].percentSelectedSameConfig(); 774 if (idx >= maxIdx) { 775 bestSelectedSections -= 1.0; 776 bestSelectedConfigs -= 1.0; 777 } 778 } 779 if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) { 780 currentSelectedSections += current[idx].percentSelectedSameSection(); 781 currentSelectedConfigs += current[idx].percentSelectedSameConfig(); 782 } 783 } 784 if (0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections > 0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections) return true; 785 if (0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections > 0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections) return false; 786 787 // 3.9 maximize selection with penalization for not followed reservations 788 if (res) { 789 alt = 0; 790 for (int idx = 0; idx < current.length; idx++) { 791 Request request = getStudent().getRequests().get(idx); 792 if (idx < maxIdx) { 793 if (best[idx] != null) { 794 if (current[idx] == null) 795 return false; // higher priority request assigned 796 if (best[idx].getAdjustedPriority() < current[idx].getAdjustedPriority()) 797 return false; // less alternative request assigned 798 if (best[idx].getAdjustedPriority() > current[idx].getAdjustedPriority()) 799 return true; // less alternative request assigned 800 if (request.isAlternative()) 801 alt--; 802 } else { 803 if (current[idx] != null) 804 return true; // higher priority request assigned 805 if (request instanceof CourseRequest && !request.isAlternative()) 806 alt++; 807 } 808 } else { 809 if (best[idx] != null) { 810 if (best[idx].getTruePriority() > 0) 811 return true; // alternativity can be improved 812 } else { 813 if (!request.isAlternative() || alt > 0) 814 return true; // priority can be improved 815 } 816 } 817 } 818 } 819 820 // 4-5. student quality 821 if (getModel().getStudentQuality() != null) { 822 double bestQuality = 0, currentQuality = 0; 823 for (StudentQuality.Type type: StudentQuality.Type.values()) { 824 for (int idx = 0; idx < current.length; idx++) { 825 if (best[idx] != null) { 826 bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[idx]); 827 for (int x = 0; x < idx; x++) { 828 if (best[x] != null) 829 bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[x], best[idx]); 830 } 831 } 832 if (current[idx] != null && idx < maxIdx) { 833 currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[idx]); 834 for (int x = 0; x < idx; x++) { 835 if (current[x] != null) 836 currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[x], current[idx]); 837 } 838 } 839 } 840 } 841 if (currentQuality < bestQuality) 842 return true; 843 if (bestQuality < currentQuality) 844 return false; 845 } else { 846 // 4. avoid time overlaps 847 if (getModel().getTimeOverlaps() != null) { 848 int bestTimeOverlaps = 0, currentTimeOverlaps = 0; 849 for (int idx = 0; idx < current.length; idx++) { 850 if (best[idx] != null) { 851 for (int x = 0; x < idx; x++) { 852 if (best[x] != null) 853 bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]); 854 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 855 bestTimeOverlaps += getModel().getTimeOverlaps() 856 .nrConflicts( 857 ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), 858 best[idx]); 859 } 860 } 861 if (current[idx] != null && idx < maxIdx) { 862 for (int x = 0; x < idx; x++) { 863 if (current[x] != null) 864 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]); 865 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 866 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts( 867 ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), 868 current[idx]); 869 } 870 } 871 } 872 for (int idx = 0; idx < current.length; idx++) { 873 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 874 bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]); 875 } 876 if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) { 877 currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]); 878 } 879 } 880 if (currentTimeOverlaps < bestTimeOverlaps) 881 return true; 882 if (bestTimeOverlaps < currentTimeOverlaps) 883 return false; 884 } 885 886 // 5. avoid distance conflicts 887 if (getModel().getDistanceConflict() != null) { 888 int bestDistanceConf = 0, currentDistanceConf = 0; 889 for (int idx = 0; idx < current.length; idx++) { 890 if (best[idx] != null) { 891 bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[idx]); 892 for (int x = 0; x < idx; x++) { 893 if (best[x] != null) 894 bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]); 895 } 896 } 897 if (current[idx] != null && idx < maxIdx) { 898 currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[idx]); 899 for (int x = 0; x < idx; x++) { 900 if (current[x] != null) 901 currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x], 902 current[idx]); 903 } 904 } 905 } 906 if (currentDistanceConf < bestDistanceConf) 907 return true; 908 if (bestDistanceConf < currentDistanceConf) 909 return false; 910 } 911 } 912 913 // 6. avoid no-time and online sections (no-time first, online second) 914 int bestNoTime = 0, currentNoTime = 0; 915 int bestOnline = 0, currentOnline = 0; 916 for (int idx = 0; idx < current.length; idx++) { 917 if (best[idx] != null) { 918 for (Section section : best[idx].getSections()) { 919 if (section.getTime() == null) 920 bestNoTime++; 921 if (section.isOnline()) 922 bestOnline++; 923 } 924 } 925 if (current[idx] != null && idx < maxIdx) { 926 for (Section section : current[idx].getSections()) { 927 if (section.getTime() == null) 928 currentNoTime++; 929 if (section.isOnline()) 930 currentOnline++; 931 } 932 } 933 } 934 if (currentNoTime < bestNoTime) 935 return true; 936 if (bestNoTime < currentNoTime) 937 return false; 938 if (currentOnline < bestOnline) 939 return true; 940 if (bestOnline < currentOnline) 941 return false; 942 943 // 7. balance sections 944 double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0; 945 int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0; 946 for (int idx = 0; idx < current.length; idx++) { 947 if (best[idx] != null) { 948 for (Section section : best[idx].getSections()) { 949 Subpart subpart = section.getSubpart(); 950 // skip unlimited and single section subparts 951 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 952 continue; 953 // average size 954 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 955 // section is below average 956 if (section.getLimit() < averageSize) 957 bestUnavailableSize += (averageSize - section.getLimit()) / averageSize; 958 bestAltSectionsWithLimit++; 959 } 960 } 961 if (current[idx] != null && idx < maxIdx) { 962 for (Section section : current[idx].getSections()) { 963 Subpart subpart = section.getSubpart(); 964 // skip unlimited and single section subparts 965 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 966 continue; 967 // average size 968 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 969 // section is below average 970 if (section.getLimit() < averageSize) 971 currentUnavailableSize += (averageSize - section.getLimit()) / averageSize; 972 currentAltSectionsWithLimit++; 973 } 974 } 975 } 976 double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit 977 : 0.0); 978 double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize 979 / currentAltSectionsWithLimit : 0.0); 980 if (currentUnavailableSizeFraction < bestUnavailableSizeFraction) 981 return true; 982 if (bestUnavailableSizeFraction < currentUnavailableSizeFraction) 983 return false; 984 985 // 8. average penalty sections 986 double bestPenalty = 0.0, currentPenalty = 0.0; 987 for (int idx = 0; idx < current.length; idx++) { 988 if (best[idx] != null) { 989 for (Section section : best[idx].getSections()) 990 bestPenalty += section.getPenalty() / best[idx].getSections().size(); 991 if (idx >= maxIdx && best[idx].isCourseRequest()) 992 bestPenalty -= ((CourseRequest) best[idx].getRequest()).getMinPenalty(); 993 } 994 if (current[idx] != null && idx < maxIdx) { 995 for (Section section : current[idx].getSections()) 996 currentPenalty += section.getPenalty() / current[idx].getSections().size(); 997 } 998 } 999 if (currentPenalty < bestPenalty) 1000 return true; 1001 if (bestPenalty < currentPenalty) 1002 return false; 1003 1004 return true; 1005 } 1006 1007 @Override 1008 public double getTotalWeight(Assignment<Request, Enrollment> assignment, Enrollment[] enrollemnts) { 1009 if (enrollemnts == null) 1010 return 0.0; 1011 double value = 0.0; 1012 for (int idx = 0; idx < enrollemnts.length; idx++) { 1013 if (enrollemnts[idx] != null) 1014 if (getModel().getStudentQuality() != null) { 1015 value += getWeight(assignment, enrollemnts[idx], getStudentQualityConflicts(enrollemnts, idx)); 1016 } else { 1017 value += getWeight(assignment, enrollemnts[idx], getDistanceConflicts(enrollemnts, idx), getTimeOverlappingConflicts(enrollemnts, idx)); 1018 } 1019 } 1020 return value; 1021 } 1022 1023 @Override 1024 public int compare(Assignment<Request, Enrollment> assignment, Enrollment e1, Enrollment e2) { 1025 // 1. alternativity 1026 if (e1.getTruePriority() < e2.getTruePriority()) 1027 return -1; 1028 if (e1.getTruePriority() > e2.getTruePriority()) 1029 return 1; 1030 1031 // 1.5 not available sections 1032 int na1 = 0, na2 = 0; 1033 for (Section section: e1.getSections()) 1034 if (section.getLimit() == 0) na1++; 1035 for (Section section: e2.getSections()) 1036 if (section.getLimit() == 0) na2++; 1037 if (na1 < na2) return -1; 1038 if (na1 > na2) return 1; 1039 1040 // 2. maximize number of penalties 1041 double p1 = 0, p2 = 0; 1042 for (Section section : e1.getSections()) 1043 p1 += getModel().getOverExpected(assignment, section, e1.getRequest()); 1044 for (Section section : e2.getSections()) 1045 p2 += getModel().getOverExpected(assignment, section, e2.getRequest()); 1046 if (p1 < p2) 1047 return -1; 1048 if (p2 < p1) 1049 return 1; 1050 1051 // 3. maximize selection 1052 if (e1.isCourseRequest()) { 1053 Set<Section> preferred = getPreferredSections(e1.getRequest()); 1054 if (preferred != null && !preferred.isEmpty()) { 1055 int s1 = 0, s2 = 0; 1056 for (Section section : e1.getSections()) 1057 if (preferred.contains(section)) 1058 s1++; 1059 for (Section section : e2.getSections()) 1060 if (preferred.contains(section)) 1061 s2++; 1062 if (s2 > s1) 1063 return -1; 1064 if (s1 > s2) 1065 return 1; 1066 } 1067 } 1068 1069 // 3.5 maximize preferences 1070 if (e1.isCourseRequest()) { 1071 double s1 = 0.3 * e1.percentSelectedSameConfig() + 0.7 * e1.percentSelectedSameSection(); 1072 double s2 = 0.3 * e2.percentSelectedSameConfig() + 0.7 * e2.percentSelectedSameSection(); 1073 if (s1 > s2) return -1; 1074 if (s2 > s1) return 1; 1075 } 1076 1077 // 3.9 maximize selection with penalization for not followed reservations 1078 if (e1.getAdjustedPriority() < e2.getAdjustedPriority()) 1079 return -1; 1080 if (e1.getAdjustedPriority() > e2.getAdjustedPriority()) 1081 return 1; 1082 1083 // 4. avoid time overlaps 1084 if (getTimesToAvoid() == null) { 1085 if (getModel().getStudentQuality() != null) { 1086 int o1 = getModel().getStudentQuality().penalty(StudentQuality.Type.FreeTimeOverlap, e1) + getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, e1); 1087 int o2 = getModel().getStudentQuality().penalty(StudentQuality.Type.FreeTimeOverlap, e2) + getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, e2); 1088 if (o1 < o2) 1089 return -1; 1090 if (o2 < o1) 1091 return 1; 1092 } else if (getModel().getTimeOverlaps() != null) { 1093 int o1 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e1) + getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(e1); 1094 int o2 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e2) + getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(e2); 1095 if (o1 < o2) 1096 return -1; 1097 if (o2 < o1) 1098 return 1; 1099 } 1100 } else { 1101 if (e1.getRequest().equals(e2.getRequest()) && e1.isCourseRequest()) { 1102 double o1 = 0.0, o2 = 0.0; 1103 for (Section s : e1.getSections()) { 1104 if (s.getTime() != null) 1105 for (TimeToAvoid avoid : getTimesToAvoid()) { 1106 if (avoid.priority() > e1.getRequest().getPriority()) 1107 o1 += avoid.overlap(s.getTime()); 1108 } 1109 } 1110 for (Section s : e2.getSections()) { 1111 if (s.getTime() != null) 1112 for (TimeToAvoid avoid : getTimesToAvoid()) { 1113 if (avoid.priority() > e2.getRequest().getPriority()) 1114 o2 += avoid.overlap(s.getTime()); 1115 } 1116 } 1117 if (o1 < o2) 1118 return -1; 1119 if (o2 < o1) 1120 return 1; 1121 } 1122 } 1123 1124 // 5. avoid distance conflicts 1125 if (getModel().getDistanceConflict() != null) { 1126 int c1 = getModel().getDistanceConflict().nrConflicts(e1); 1127 int c2 = getModel().getDistanceConflict().nrConflicts(e2); 1128 if (c1 < c2) 1129 return -1; 1130 if (c2 < c1) 1131 return 1; 1132 } 1133 1134 // 6. avoid no-time and online sections (no-time first, online second) 1135 int n1 = 0, n2 = 0; 1136 int o1 = 0, o2 = 0; 1137 for (Section section : e1.getSections()) { 1138 if (section.getTime() == null) 1139 n1++; 1140 if (section.isOnline()) 1141 o1++; 1142 } 1143 for (Section section : e2.getSections()) { 1144 if (section.getTime() == null) 1145 n2++; 1146 if (section.isOnline()) 1147 o2++; 1148 } 1149 if (n1 < n2) 1150 return -1; 1151 if (n2 < n1) 1152 return 1; 1153 if (o1 < o2) 1154 return -1; 1155 if (o2 < o1) 1156 return 1; 1157 1158 // 7. balance sections 1159 double u1 = 0.0, u2 = 0.0; 1160 int a1 = 0, a2 = 0; 1161 for (Section section : e1.getSections()) { 1162 Subpart subpart = section.getSubpart(); 1163 // skip unlimited and single section subparts 1164 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 1165 continue; 1166 // average size 1167 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 1168 // section is below average 1169 if (section.getLimit() < averageSize) 1170 u1 += (averageSize - section.getLimit()) / averageSize; 1171 a1++; 1172 } 1173 for (Section section : e2.getSections()) { 1174 Subpart subpart = section.getSubpart(); 1175 // skip unlimited and single section subparts 1176 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 1177 continue; 1178 // average size 1179 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 1180 // section is below average 1181 if (section.getLimit() < averageSize) 1182 u2 += (averageSize - section.getLimit()) / averageSize; 1183 a2++; 1184 } 1185 double f1 = (u1 > 0 ? u1 / a1 : 0.0); 1186 double f2 = (u2 > 0 ? u2 / a2 : 0.0); 1187 if (f1 < f2) 1188 return -1; 1189 if (f2 < f1) 1190 return 1; 1191 1192 // 8. average penalty sections 1193 double x1 = 0.0, x2 = 0.0; 1194 for (Section section : e1.getSections()) 1195 x1 += section.getPenalty() / e1.getSections().size(); 1196 for (Section section : e2.getSections()) 1197 x2 += section.getPenalty() / e2.getSections().size(); 1198 if (x1 < x2) 1199 return -1; 1200 if (x2 < x1) 1201 return 1; 1202 1203 return 0; 1204 } 1205 1206 /** 1207 * Time to be avoided. 1208 */ 1209 public static class TimeToAvoid { 1210 private TimeLocation iTime; 1211 private double iPenalty; 1212 private int iPriority; 1213 1214 public TimeToAvoid(TimeLocation time, int penalty, int priority) { 1215 iTime = time; 1216 iPenalty = penalty; 1217 iPriority = priority; 1218 } 1219 1220 public int priority() { 1221 return iPriority; 1222 } 1223 1224 public double overlap(TimeLocation time) { 1225 if (time.hasIntersection(iTime)) { 1226 return iPenalty * (time.nrSharedDays(iTime) * time.nrSharedHours(iTime)) 1227 / (iTime.getNrMeetings() * iTime.getLength()); 1228 } else { 1229 return 0.0; 1230 } 1231 } 1232 1233 @Override 1234 public String toString() { 1235 return iTime.getLongName(true) + " (" + iPriority + "/" + iPenalty + ")"; 1236 } 1237 } 1238}