001package net.sf.cpsolver.coursett.model; 002 003import java.util.ArrayList; 004import java.util.Collection; 005import java.util.HashSet; 006import java.util.HashMap; 007import java.util.Iterator; 008import java.util.List; 009 010import net.sf.cpsolver.ifs.util.Progress; 011 012/** 013 * Student initial sectioning (before a solver is started). <br> 014 * <br> 015 * Many course offerings consist of multiple classes, with students enrolled in 016 * the course divided among them. These classes are often linked by a set of 017 * constraints, namely: 018 * <ul> 019 * <li>Each class has a limit stating the maximum number of students who can be 020 * enrolled in it. 021 * <li>A student must be enrolled in exactly one class for each subpart of a 022 * course. 023 * <li>If two subparts of a course have a parent-child relationship, a student 024 * enrolled in the parent class must also be enrolled in one of the child 025 * classes. 026 * </ul> 027 * Moreover, some of the classes of an offering may be required or prohibited 028 * for certain students, based on reservations that can be set on an offering, a 029 * configuration, or a class. <br> 030 * Before implementing the solver, an initial sectioning of students into 031 * classes is processed. This sectioning is based on Carter's homogeneous 032 * sectioning and is intended to minimize future student conflicts. However, it 033 * is still possible to improve on the number of student conflicts in the 034 * solution. This can be accomplished by moving students between alternative 035 * classes of the same course during or after the search (see 036 * {@link FinalSectioning}). 037 * 038 * @version CourseTT 1.2 (University Course Timetabling)<br> 039 * Copyright (C) 2006 - 2010 Tomáš Müller<br> 040 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 041 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 042 * <br> 043 * This library is free software; you can redistribute it and/or modify 044 * it under the terms of the GNU Lesser General Public License as 045 * published by the Free Software Foundation; either version 3 of the 046 * License, or (at your option) any later version. <br> 047 * <br> 048 * This library is distributed in the hope that it will be useful, but 049 * WITHOUT ANY WARRANTY; without even the implied warranty of 050 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 051 * Lesser General Public License for more details. <br> 052 * <br> 053 * You should have received a copy of the GNU Lesser General Public 054 * License along with this library; if not see 055 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 056 */ 057public class InitialSectioning { 058 protected Collection<Student> iStudents = null; 059 protected Group[] iGroups = null; 060 protected Long iOfferingId = null; 061 protected Progress iProgress = null; 062 063 public InitialSectioning(Progress progress, Long offeringId, Collection<?> lectureOrConfigurations, 064 Collection<Student> students) { 065 iOfferingId = offeringId; 066 iStudents = new HashSet<Student>(students); 067 iProgress = progress; 068 069 iGroups = new Group[lectureOrConfigurations.size()]; 070 071 int idx = 0; 072 double total = 0; 073 for (Iterator<?> i = lectureOrConfigurations.iterator(); i.hasNext(); idx++) { 074 Object lectureOrConfiguration = i.next(); 075 if (lectureOrConfiguration instanceof Lecture) { 076 Lecture lecture = (Lecture) lectureOrConfiguration; 077 iGroups[idx] = new Group(lecture); 078 } else { 079 Configuration configuration = (Configuration) lectureOrConfiguration; 080 iGroups[idx] = new Group(configuration); 081 } 082 total += iGroups[idx].getMaxSize(); 083 } 084 085 tweakSizes(total); 086 087 progress.trace("Initial sectioning:"); 088 progress.trace(" going to section " + iStudents.size() + " into " + total + " seats"); 089 for (idx = 0; idx < iGroups.length; idx++) 090 progress.trace(" " + (idx + 1) + ". group can accomodate <" + iGroups[idx].getMinSize() + "," 091 + iGroups[idx].getMaxSize() + "> students"); 092 } 093 094 protected void tweakSizes(double total) { 095 if (total == 0) { 096 for (int idx = 0; idx < iGroups.length; idx++) { 097 iGroups[idx].setMaxSize(1); 098 total++; 099 } 100 } 101 102 double studentsWeight = 0; 103 for (Student s : iStudents) { 104 studentsWeight += s.getOfferingWeight(iOfferingId); 105 } 106 107 double factor = studentsWeight / total; 108 for (int idx = 0; idx < iGroups.length; idx++) { 109 iGroups[idx].setMaxSize(factor * iGroups[idx].getMaxSize()); 110 iGroups[idx].setMinSize(Math.min(iGroups[idx].getMinSize(), 0.9 * iGroups[idx].getMaxSize())); 111 } 112 } 113 114 public void addStudent(Student student) { 115 iStudents.add(student); 116 } 117 118 private boolean moveAwayOneStudent(Group group) { 119 Group newGroup = null; 120 Student movingStudent = null; 121 double curDist = 0, newDist = 0; 122 123 for (Student student : group.getStudents()) { 124 if (group.isEnrolled(student)) 125 continue; 126 double cd = group.getDistance(student); 127 for (int x = 0; x < iGroups.length; x++) { 128 if (group.equals(iGroups[x])) 129 continue; 130 if (iGroups[x].size() > iGroups[x].getMaxSize()) 131 continue; 132 if (!iGroups[x].canEnroll(student)) 133 continue; 134 double nd = iGroups[x].getDistance(student); 135 if (newGroup == null || newDist - curDist < nd - cd) { 136 newGroup = iGroups[x]; 137 movingStudent = student; 138 curDist = cd; 139 newDist = nd; 140 if (newDist - curDist < 0.01) 141 break; 142 } 143 } 144 } 145 146 if (newGroup != null) { 147 group.removeStudent(movingStudent); 148 newGroup.addStudent(movingStudent); 149 return true; 150 } 151 152 return false; 153 } 154 155 public boolean moveIntoOneStudent(Group group) { 156 Group oldGroup = null; 157 Student movingStudent = null; 158 double curDist = 0, newDist = 0; 159 160 for (int x = 0; x < iGroups.length; x++) { 161 if (group.equals(iGroups[x])) 162 continue; 163 if (iGroups[x].size() <= iGroups[x].getMinSize()) 164 continue; 165 for (Student student : iGroups[x].getStudents()) { 166 if (!group.canEnroll(student)) 167 continue; 168 if (iGroups[x].isEnrolled(student)) 169 continue; 170 double cd = iGroups[x].getDistance(student); 171 double nd = group.getDistance(student); 172 if (oldGroup == null || newDist - curDist < nd - cd) { 173 oldGroup = iGroups[x]; 174 movingStudent = student; 175 curDist = cd; 176 newDist = nd; 177 if (newDist - curDist < 0.01) 178 break; 179 } 180 } 181 } 182 183 if (oldGroup != null) { 184 oldGroup.removeStudent(movingStudent); 185 group.addStudent(movingStudent); 186 return true; 187 } 188 189 return false; 190 } 191 192 public Group[] getGroups() { 193 double minDist = 1.0 / iGroups.length; 194 195 for (Iterator<Student> i = iStudents.iterator(); i.hasNext();) { 196 Student student = i.next(); 197 Group group = null; 198 for (int idx = 0; idx < iGroups.length; idx++) { 199 if (iGroups[idx].isEnrolled(student)) { 200 group = iGroups[idx]; 201 break; 202 } 203 } 204 if (group != null) { 205 group.addStudent(student); 206 i.remove(); 207 } 208 } 209 210 for (Student student : iStudents) { 211 double studentWeight = student.getOfferingWeight(iOfferingId); 212 213 Group group = null; 214 double dist = 0.0; 215 for (int idx = 0; idx < iGroups.length; idx++) { 216 Group g = iGroups[idx]; 217 if (!g.canEnroll(student)) 218 continue; 219 if (g.size() + studentWeight > g.getMaxSize()) 220 continue; 221 double d = g.getDistance(student); 222 if (group == null || d < dist) { 223 group = g; 224 dist = d; 225 if (d < minDist) 226 break; 227 } 228 } 229 230 if (group != null) { 231 group.addStudent(student); 232 continue; 233 } 234 235 // disobey max size, but prefer sections with smallest excess 236 int excess = 0; 237 for (int idx = 0; idx < iGroups.length; idx++) { 238 Group g = iGroups[idx]; 239 if (!g.canEnroll(student)) 240 continue; 241 double d = g.getDistance(student); 242 int ex = (int)Math.round(g.size() + studentWeight - g.getMaxSize()); 243 if (group == null || ex < excess || (ex == excess && d < dist)) { 244 group = g; 245 dist = d; 246 excess = ex; 247 } 248 } 249 250 if (group != null) { 251 group.addStudent(student); 252 continue; 253 } 254 255 // disobey max size & can enroll 256 for (int idx = 0; idx < iGroups.length; idx++) { 257 Group g = iGroups[idx]; 258 double d = g.getDistance(student); 259 if (group == null || d < dist) { 260 group = g; 261 dist = d; 262 } 263 } 264 265 iProgress.debug("Unable to find a valid section for student " 266 + student.getId() 267 + ", enrolling to " 268 + (group.getLecture() != null ? group.getLecture().getName() : group.getConfiguration() 269 .getConfigId().toString())); 270 271 group.addStudent(student); 272 } 273 274 for (int idx = 0; idx < iGroups.length; idx++) { 275 Group group = iGroups[idx]; 276 277 while (group.size() > group.getMaxSize()) { 278 if (!moveAwayOneStudent(group)) 279 break; 280 } 281 282 while (group.size() > group.getMaxSize()) { 283 284 Group newGroup = null; 285 Student movingStudent = null; 286 287 for (Student student : group.getStudents()) { 288 if (group.isEnrolled(student)) 289 continue; 290 for (int x = 0; x < iGroups.length; x++) { 291 if (idx == x) 292 continue; 293 if (!iGroups[x].canEnroll(student)) 294 continue; 295 while (iGroups[x].size() + student.getOfferingWeight(iOfferingId) > iGroups[x].getMaxSize()) { 296 if (!moveAwayOneStudent(iGroups[x])) 297 break; 298 } 299 if (iGroups[x].size() + student.getOfferingWeight(iOfferingId) > iGroups[x].getMaxSize()) 300 continue; 301 newGroup = iGroups[x]; 302 movingStudent = student; 303 break; 304 } 305 if (newGroup != null) 306 break; 307 } 308 309 if (newGroup != null) { 310 group.removeStudent(movingStudent); 311 newGroup.addStudent(movingStudent); 312 } else { 313 break; 314 } 315 } 316 317 while (group.size() < group.getMinSize()) { 318 if (!moveIntoOneStudent(group)) 319 break; 320 } 321 } 322 323 return iGroups; 324 } 325 326 public class Group { 327 private ArrayList<Student> iStudents = new ArrayList<Student>(); 328 private Lecture iLecture = null; 329 private Configuration iConfiguration = null; 330 private Double iDist = null; 331 private double iMinSize = 0, iMaxSize = 0; 332 private HashMap<Student, Double> iDistCache = new HashMap<Student, Double>(); 333 private double iSize = 0.0; 334 335 public Group(Lecture lecture) { 336 iLecture = lecture; 337 iMinSize = lecture.minClassLimit(); 338 iMaxSize = lecture.maxAchievableClassLimit(); 339 } 340 341 public Group(Configuration configuration) { 342 iConfiguration = configuration; 343 iMinSize = iMaxSize = iConfiguration.getLimit(); 344 } 345 346 public Configuration getConfiguration() { 347 return iConfiguration; 348 } 349 350 public Lecture getLecture() { 351 return iLecture; 352 } 353 354 public double getMinSize() { 355 return iMinSize; 356 } 357 358 public double getMaxSize() { 359 return iMaxSize; 360 } 361 362 public void setMinSize(double minSize) { 363 iMinSize = minSize; 364 } 365 366 public void setMaxSize(double maxSize) { 367 iMaxSize = maxSize; 368 } 369 370 public double getDistance() { 371 if (iDist == null) { 372 double dist = 0.0; 373 double prob = 10.0 / iStudents.size(); 374 int cnt = 0; 375 for (Student s1 : iStudents) { 376 if (Math.random() < prob) { 377 for (Student s2 : iStudents) { 378 if (s1.getId().compareTo(s2.getId()) <= 0) 379 continue; 380 if (Math.random() < prob) { 381 dist += s1.getDistance(s2); 382 cnt++; 383 } 384 } 385 } 386 } 387 iDist = new Double(dist / cnt); 388 } 389 return iDist.doubleValue(); 390 } 391 392 public double getDistance(Student student) { 393 Double cachedDist = iDistCache.get(student); 394 if (cachedDist != null) 395 return cachedDist.doubleValue(); 396 double dist = 0.0; 397 double prob = 10.0 / iStudents.size(); 398 int cnt = 0; 399 for (Student s : iStudents) { 400 if (prob >= 1.0 || Math.random() < prob) { 401 dist += s.getDistance(student); 402 cnt++; 403 } 404 } 405 iDistCache.put(student, new Double(dist / cnt)); 406 return dist / cnt; 407 } 408 409 public void addStudent(Student student) { 410 iStudents.add(student); 411 iSize += student.getOfferingWeight(iOfferingId); 412 iDist = null; 413 iDistCache.clear(); 414 } 415 416 public void removeStudent(Student student) { 417 iStudents.remove(student); 418 iSize -= student.getOfferingWeight(iOfferingId); 419 iDist = null; 420 iDistCache.clear(); 421 } 422 423 public List<Student> getStudents() { 424 return iStudents; 425 } 426 427 public double size() { 428 return iSize; 429 } 430 431 @Override 432 public String toString() { 433 return "{" + size() + "-" + getDistance() + "/" + getStudents() + "}"; 434 } 435 436 public boolean canEnroll(Student student) { 437 if (getLecture() != null) { 438 return student.canEnroll(getLecture()); 439 } else { 440 for (Long subpartId: getConfiguration().getTopSubpartIds()) { 441 boolean canEnrollThisSubpart = false; 442 for (Lecture lecture : getConfiguration().getTopLectures(subpartId)) { 443 if (student.canEnroll(lecture)) { 444 canEnrollThisSubpart = true; 445 break; 446 } 447 } 448 if (!canEnrollThisSubpart) 449 return false; 450 } 451 return true; 452 } 453 } 454 455 public boolean isEnrolled(Student student) { 456 if (getLecture() != null) { 457 return student.getLectures().contains(getLecture()); 458 } else { 459 for (Lecture lect : student.getLectures()) { 460 if (lect.getConfiguration().equals(getConfiguration())) 461 return true; 462 } 463 return false; 464 } 465 466 } 467 } 468 469 public static void initialSectioningCfg(Progress p, Long offeringId, String courseName, Collection<Student> students, 470 List<Configuration> configurations) { 471 if (students == null || students.isEmpty()) 472 return; 473 if (configurations == null || configurations.isEmpty()) 474 return; 475 if (configurations.size() == 1) { 476 Configuration cfg = configurations.get(0); 477 for (Student st : students) { 478 st.addConfiguration(cfg); 479 } 480 for (Long subpartId: cfg.getTopSubpartIds()) { 481 initialSectioning(p, offeringId, courseName, students, cfg.getTopLectures(subpartId)); 482 } 483 } else { 484 p.trace("sectioning " + students.size() + " students of course " + courseName + " into " 485 + configurations.size() + " configurations"); 486 InitialSectioning sect = new InitialSectioning(p, offeringId, configurations, students); 487 Group[] studentsPerSection = sect.getGroups(); 488 for (int i = 0; i < configurations.size(); i++) { 489 Group group = studentsPerSection[i]; 490 p.trace((i + 1) + ". configuration got " + group.getStudents().size() + " students (weighted=" 491 + group.size() + ", cfgLimit=" + group.getConfiguration().getLimit() + ")"); 492 for (Student st : group.getStudents()) { 493 st.addConfiguration(group.getConfiguration()); 494 } 495 for (Long subpartId: group.getConfiguration().getTopSubpartIds()) { 496 initialSectioning(p, offeringId, courseName, group.getStudents(), group.getConfiguration() 497 .getTopLectures(subpartId)); 498 } 499 } 500 } 501 } 502 503 private static String getClassLabel(Lecture lecture) { 504 return "<A href='classDetail.do?cid=" + lecture.getClassId() + "'>" + lecture.getName() + "</A>"; 505 } 506 507 private static void initialSectioning(Progress p, Long offeringId, String parentName, Collection<Student> students, 508 Collection<Lecture> lectures) { 509 if (lectures == null || lectures.isEmpty()) 510 return; 511 if (students == null || students.isEmpty()) 512 return; 513 for (Lecture lecture : lectures) { 514 if (lecture.classLimit() == 0 && !lecture.isCommitted()) 515 p.warn("Class " + getClassLabel(lecture) + " has zero class limit."); 516 } 517 518 p.trace("sectioning " + students.size() + " students of course " + parentName + " into " + lectures.size() 519 + " sections"); 520 if (lectures.size() == 1) { 521 Lecture lect = lectures.iterator().next(); 522 for (Student st : students) { 523 if (!st.canEnroll(lect)) { 524 p.info("Unable to enroll student " + st.getId() + " in class " + getClassLabel(lect)); 525 } 526 lect.addStudent(st); 527 st.addLecture(lect); 528 } 529 if (lect.hasAnyChildren()) { 530 for (Long subpartId: lect.getChildrenSubpartIds()) { 531 List<Lecture> children = lect.getChildren(subpartId); 532 initialSectioning(p, offeringId, lect.getName(), students, children); 533 } 534 } 535 } else { 536 InitialSectioning sect = new InitialSectioning(p, offeringId, lectures, students); 537 Group[] studentsPerSection = sect.getGroups(); 538 for (int i = 0; i < studentsPerSection.length; i++) { 539 Group group = studentsPerSection[i]; 540 Lecture lect = group.getLecture(); 541 if (group.getStudents().isEmpty()) { 542 p.trace("Lecture " + getClassLabel(lect) + " got no students (cl=" + lect.classLimit() + ")"); 543 continue; 544 } 545 p.trace("Lecture " + getClassLabel(lect) + " got " + group.getStudents().size() 546 + " students (weighted=" + group.size() + ", classLimit=" + lect.classLimit() + ")"); 547 List<Student> studentsThisSection = group.getStudents(); 548 for (Student st : studentsThisSection) { 549 if (!st.canEnroll(lect)) { 550 p.info("Unable to enroll student " + st.getId() + " in class " + getClassLabel(lect)); 551 } 552 lect.addStudent(st); 553 st.addLecture(lect); 554 } 555 if (lect.hasAnyChildren()) { 556 for (Long subpartId: lect.getChildrenSubpartIds()) { 557 List<Lecture> children = lect.getChildren(subpartId); 558 initialSectioning(p, offeringId, lect.getName(), studentsThisSection, children); 559 } 560 } 561 } 562 } 563 } 564 565}