001 package net.sf.cpsolver.coursett.model; 002 003 import java.util.ArrayList; 004 import java.util.Collection; 005 import java.util.HashSet; 006 import java.util.HashMap; 007 import java.util.Iterator; 008 import java.util.List; 009 010 import 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 Tomas Muller<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 */ 057 public class InitialSectioning { 058 Collection<Student> iStudents = null; 059 Group[] iGroups = null; 060 Long iOfferingId = null; 061 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 if (total == 0) { 086 for (idx = 0; idx < iGroups.length; idx++) { 087 iGroups[idx].setMaxSize(1); 088 total++; 089 } 090 } 091 092 double studentsWeight = 0; 093 for (Student s : iStudents) { 094 studentsWeight += s.getOfferingWeight(iOfferingId); 095 } 096 097 double factor = studentsWeight / total; 098 for (idx = 0; idx < iGroups.length; idx++) { 099 iGroups[idx].setMaxSize(factor * iGroups[idx].getMaxSize()); 100 iGroups[idx].setMinSize(Math.min(iGroups[idx].getMinSize(), 0.9 * iGroups[idx].getMaxSize())); 101 } 102 103 progress.trace("Initial sectioning:"); 104 progress.trace(" going to section " + iStudents.size() + " into " + total + " seats"); 105 for (idx = 0; idx < iGroups.length; idx++) 106 progress.trace(" " + (idx + 1) + ". group can accomodate <" + iGroups[idx].getMinSize() + "," 107 + iGroups[idx].getMaxSize() + "> students"); 108 } 109 110 public void addStudent(Student student) { 111 iStudents.add(student); 112 } 113 114 private boolean moveAwayOneStudent(Group group) { 115 Group newGroup = null; 116 Student movingStudent = null; 117 double curDist = 0, newDist = 0; 118 119 for (Student student : group.getStudents()) { 120 if (group.isEnrolled(student)) 121 continue; 122 double cd = group.getDistance(student); 123 for (int x = 0; x < iGroups.length; x++) { 124 if (group.equals(iGroups[x])) 125 continue; 126 if (iGroups[x].size() > iGroups[x].getMaxSize()) 127 continue; 128 if (!iGroups[x].canEnroll(student)) 129 continue; 130 double nd = iGroups[x].getDistance(student); 131 if (newGroup == null || newDist - curDist < nd - cd) { 132 newGroup = iGroups[x]; 133 movingStudent = student; 134 curDist = cd; 135 newDist = nd; 136 if (newDist - curDist < 0.01) 137 break; 138 } 139 } 140 } 141 142 if (newGroup != null) { 143 group.removeStudent(movingStudent); 144 newGroup.addStudent(movingStudent); 145 return true; 146 } 147 148 return false; 149 } 150 151 public boolean moveIntoOneStudent(Group group) { 152 Group oldGroup = null; 153 Student movingStudent = null; 154 double curDist = 0, newDist = 0; 155 156 for (int x = 0; x < iGroups.length; x++) { 157 if (group.equals(iGroups[x])) 158 continue; 159 if (iGroups[x].size() <= iGroups[x].getMinSize()) 160 continue; 161 for (Student student : iGroups[x].getStudents()) { 162 if (!group.canEnroll(student)) 163 continue; 164 if (iGroups[x].isEnrolled(student)) 165 continue; 166 double cd = iGroups[x].getDistance(student); 167 double nd = group.getDistance(student); 168 if (oldGroup == null || newDist - curDist < nd - cd) { 169 oldGroup = iGroups[x]; 170 movingStudent = student; 171 curDist = cd; 172 newDist = nd; 173 if (newDist - curDist < 0.01) 174 break; 175 } 176 } 177 } 178 179 if (oldGroup != null) { 180 oldGroup.removeStudent(movingStudent); 181 group.addStudent(movingStudent); 182 return true; 183 } 184 185 return false; 186 } 187 188 public Group[] getGroups() { 189 double minDist = 1.0 / iGroups.length; 190 191 for (Iterator<Student> i = iStudents.iterator(); i.hasNext();) { 192 Student student = i.next(); 193 Group group = null; 194 for (int idx = 0; idx < iGroups.length; idx++) { 195 if (iGroups[idx].isEnrolled(student)) { 196 group = iGroups[idx]; 197 break; 198 } 199 } 200 if (group != null) { 201 group.addStudent(student); 202 i.remove(); 203 } 204 } 205 206 for (Student student : iStudents) { 207 double studentWeight = student.getOfferingWeight(iOfferingId); 208 209 Group group = null; 210 double dist = 0.0; 211 for (int idx = 0; idx < iGroups.length; idx++) { 212 Group g = iGroups[idx]; 213 if (!g.canEnroll(student)) 214 continue; 215 if (g.size() + studentWeight > g.getMaxSize()) 216 continue; 217 double d = g.getDistance(student); 218 if (group == null || d < dist) { 219 group = g; 220 dist = d; 221 if (d < minDist) 222 break; 223 } 224 } 225 226 if (group != null) { 227 group.addStudent(student); 228 continue; 229 } 230 231 // disobey max size, but prefer sections with smallest excess 232 int excess = 0; 233 for (int idx = 0; idx < iGroups.length; idx++) { 234 Group g = iGroups[idx]; 235 if (!g.canEnroll(student)) 236 continue; 237 double d = g.getDistance(student); 238 int ex = (int)Math.round(g.size() + studentWeight - g.getMaxSize()); 239 if (group == null || ex < excess || (ex == excess && d < dist)) { 240 group = g; 241 dist = d; 242 excess = ex; 243 } 244 } 245 246 if (group != null) { 247 group.addStudent(student); 248 continue; 249 } 250 251 // disobey max size & can enroll 252 for (int idx = 0; idx < iGroups.length; idx++) { 253 Group g = iGroups[idx]; 254 double d = g.getDistance(student); 255 if (group == null || d < dist) { 256 group = g; 257 dist = d; 258 } 259 } 260 261 iProgress.debug("Unable to find a valid section for student " 262 + student.getId() 263 + ", enrolling to " 264 + (group.getLecture() != null ? group.getLecture().getName() : group.getConfiguration() 265 .getConfigId().toString())); 266 267 group.addStudent(student); 268 } 269 270 for (int idx = 0; idx < iGroups.length; idx++) { 271 Group group = iGroups[idx]; 272 273 while (group.size() > group.getMaxSize()) { 274 if (!moveAwayOneStudent(group)) 275 break; 276 } 277 278 while (group.size() > group.getMaxSize()) { 279 280 Group newGroup = null; 281 Student movingStudent = null; 282 283 for (Student student : group.getStudents()) { 284 if (group.isEnrolled(student)) 285 continue; 286 for (int x = 0; x < iGroups.length; x++) { 287 if (idx == x) 288 continue; 289 if (!iGroups[x].canEnroll(student)) 290 continue; 291 while (iGroups[x].size() + student.getOfferingWeight(iOfferingId) > iGroups[x].getMaxSize()) { 292 if (!moveAwayOneStudent(iGroups[x])) 293 break; 294 } 295 if (iGroups[x].size() + student.getOfferingWeight(iOfferingId) > iGroups[x].getMaxSize()) 296 continue; 297 newGroup = iGroups[x]; 298 movingStudent = student; 299 break; 300 } 301 if (newGroup != null) 302 break; 303 } 304 305 if (newGroup != null) { 306 group.removeStudent(movingStudent); 307 newGroup.addStudent(movingStudent); 308 } else { 309 break; 310 } 311 } 312 313 while (group.size() < group.getMinSize()) { 314 if (!moveIntoOneStudent(group)) 315 break; 316 } 317 } 318 319 return iGroups; 320 } 321 322 public class Group { 323 private ArrayList<Student> iStudents = new ArrayList<Student>(); 324 private Lecture iLecture = null; 325 private Configuration iConfiguration = null; 326 private Double iDist = null; 327 private double iMinSize = 0, iMaxSize = 0; 328 private HashMap<Student, Double> iDistCache = new HashMap<Student, Double>(); 329 private double iSize = 0.0; 330 331 public Group(Lecture lecture) { 332 iLecture = lecture; 333 iMinSize = lecture.minClassLimit(); 334 iMaxSize = lecture.maxAchievableClassLimit(); 335 } 336 337 public Group(Configuration configuration) { 338 iConfiguration = configuration; 339 iMinSize = iMaxSize = iConfiguration.getLimit(); 340 } 341 342 public Configuration getConfiguration() { 343 return iConfiguration; 344 } 345 346 public Lecture getLecture() { 347 return iLecture; 348 } 349 350 public double getMinSize() { 351 return iMinSize; 352 } 353 354 public double getMaxSize() { 355 return iMaxSize; 356 } 357 358 public void setMinSize(double minSize) { 359 iMinSize = minSize; 360 } 361 362 public void setMaxSize(double maxSize) { 363 iMaxSize = maxSize; 364 } 365 366 public double getDistance() { 367 if (iDist == null) { 368 double dist = 0.0; 369 double prob = 10.0 / iStudents.size(); 370 int cnt = 0; 371 for (Student s1 : iStudents) { 372 if (Math.random() < prob) { 373 for (Student s2 : iStudents) { 374 if (s1.getId().compareTo(s2.getId()) <= 0) 375 continue; 376 if (Math.random() < prob) { 377 dist += s1.getDistance(s2); 378 cnt++; 379 } 380 } 381 } 382 } 383 iDist = new Double(dist / cnt); 384 } 385 return iDist.doubleValue(); 386 } 387 388 public double getDistance(Student student) { 389 Double cachedDist = iDistCache.get(student); 390 if (cachedDist != null) 391 return cachedDist.doubleValue(); 392 double dist = 0.0; 393 double prob = 10.0 / iStudents.size(); 394 int cnt = 0; 395 for (Student s : iStudents) { 396 if (prob >= 1.0 || Math.random() < prob) { 397 dist += s.getDistance(student); 398 cnt++; 399 } 400 } 401 iDistCache.put(student, new Double(dist / cnt)); 402 return dist / cnt; 403 } 404 405 public void addStudent(Student student) { 406 iStudents.add(student); 407 iSize += student.getOfferingWeight(iOfferingId); 408 iDist = null; 409 iDistCache.clear(); 410 } 411 412 public void removeStudent(Student student) { 413 iStudents.remove(student); 414 iSize -= student.getOfferingWeight(iOfferingId); 415 iDist = null; 416 iDistCache.clear(); 417 } 418 419 public List<Student> getStudents() { 420 return iStudents; 421 } 422 423 public double size() { 424 return iSize; 425 } 426 427 @Override 428 public String toString() { 429 return "{" + size() + "-" + getDistance() + "/" + getStudents() + "}"; 430 } 431 432 public boolean canEnroll(Student student) { 433 if (getLecture() != null) { 434 return student.canEnroll(getLecture()); 435 } else { 436 for (Long subpartId: getConfiguration().getTopSubpartIds()) { 437 boolean canEnrollThisSubpart = false; 438 for (Lecture lecture : getConfiguration().getTopLectures(subpartId)) { 439 if (student.canEnroll(lecture)) { 440 canEnrollThisSubpart = true; 441 break; 442 } 443 } 444 if (!canEnrollThisSubpart) 445 return false; 446 } 447 return true; 448 } 449 } 450 451 public boolean isEnrolled(Student student) { 452 if (getLecture() != null) { 453 return student.getLectures().contains(getLecture()); 454 } else { 455 for (Lecture lect : student.getLectures()) { 456 if (lect.getConfiguration().equals(getConfiguration())) 457 return true; 458 } 459 return false; 460 } 461 462 } 463 } 464 465 public static void initialSectioningCfg(Progress p, Long offeringId, String courseName, Collection<Student> students, 466 List<Configuration> configurations) { 467 if (students == null || students.isEmpty()) 468 return; 469 if (configurations == null || configurations.isEmpty()) 470 return; 471 if (configurations.size() == 1) { 472 Configuration cfg = configurations.get(0); 473 for (Student st : students) { 474 st.addConfiguration(cfg); 475 } 476 for (Long subpartId: cfg.getTopSubpartIds()) { 477 initialSectioning(p, offeringId, courseName, students, cfg.getTopLectures(subpartId)); 478 } 479 } else { 480 p.trace("sectioning " + students.size() + " students of course " + courseName + " into " 481 + configurations.size() + " configurations"); 482 InitialSectioning sect = new InitialSectioning(p, offeringId, configurations, students); 483 Group[] studentsPerSection = sect.getGroups(); 484 for (int i = 0; i < configurations.size(); i++) { 485 Group group = studentsPerSection[i]; 486 p.trace((i + 1) + ". configuration got " + group.getStudents().size() + " students (weighted=" 487 + group.size() + ", cfgLimit=" + group.getConfiguration().getLimit() + ")"); 488 for (Student st : group.getStudents()) { 489 st.addConfiguration(group.getConfiguration()); 490 } 491 for (Long subpartId: group.getConfiguration().getTopSubpartIds()) { 492 initialSectioning(p, offeringId, courseName, group.getStudents(), group.getConfiguration() 493 .getTopLectures(subpartId)); 494 } 495 } 496 } 497 } 498 499 private static String getClassLabel(Lecture lecture) { 500 return "<A href='classDetail.do?cid=" + lecture.getClassId() + "'>" + lecture.getName() + "</A>"; 501 } 502 503 private static void initialSectioning(Progress p, Long offeringId, String parentName, Collection<Student> students, 504 Collection<Lecture> lectures) { 505 if (lectures == null || lectures.isEmpty()) 506 return; 507 if (students == null || students.isEmpty()) 508 return; 509 for (Lecture lecture : lectures) { 510 if (lecture.classLimit() == 0 && !lecture.isCommitted()) 511 p.warn("Class " + getClassLabel(lecture) + " has zero class limit."); 512 } 513 514 p.trace("sectioning " + students.size() + " students of course " + parentName + " into " + lectures.size() 515 + " sections"); 516 if (lectures.size() == 1) { 517 Lecture lect = lectures.iterator().next(); 518 for (Student st : students) { 519 if (!st.canEnroll(lect)) { 520 p.info("Unable to enroll student " + st.getId() + " in class " + getClassLabel(lect)); 521 } 522 lect.addStudent(st); 523 st.addLecture(lect); 524 } 525 if (lect.hasAnyChildren()) { 526 for (Long subpartId: lect.getChildrenSubpartIds()) { 527 List<Lecture> children = lect.getChildren(subpartId); 528 initialSectioning(p, offeringId, lect.getName(), students, children); 529 } 530 } 531 } else { 532 InitialSectioning sect = new InitialSectioning(p, offeringId, lectures, students); 533 Group[] studentsPerSection = sect.getGroups(); 534 for (int i = 0; i < studentsPerSection.length; i++) { 535 Group group = studentsPerSection[i]; 536 Lecture lect = group.getLecture(); 537 if (group.getStudents().isEmpty()) { 538 p.trace("Lecture " + getClassLabel(lect) + " got no students (cl=" + lect.classLimit() + ")"); 539 continue; 540 } 541 p.trace("Lecture " + getClassLabel(lect) + " got " + group.getStudents().size() 542 + " students (weighted=" + group.size() + ", classLimit=" + lect.classLimit() + ")"); 543 List<Student> studentsThisSection = group.getStudents(); 544 for (Student st : studentsThisSection) { 545 if (!st.canEnroll(lect)) { 546 p.info("Unable to enroll student " + st.getId() + " in class " + getClassLabel(lect)); 547 } 548 lect.addStudent(st); 549 st.addLecture(lect); 550 } 551 if (lect.hasAnyChildren()) { 552 for (Long subpartId: lect.getChildrenSubpartIds()) { 553 List<Lecture> children = lect.getChildren(subpartId); 554 initialSectioning(p, offeringId, lect.getName(), studentsThisSection, children); 555 } 556 } 557 } 558 } 559 } 560 561 }