001package org.cpsolver.coursett.model; 002 003import java.util.ArrayList; 004import java.util.Collection; 005import java.util.List; 006import java.util.Locale; 007import java.util.Map; 008 009import org.cpsolver.coursett.model.InitialSectioning.Group; 010import org.cpsolver.coursett.sectioning.StudentSwapSectioning; 011import org.cpsolver.ifs.assignment.Assignment; 012import org.cpsolver.ifs.model.InfoProvider; 013import org.cpsolver.ifs.solution.Solution; 014import org.cpsolver.ifs.termination.TerminationCondition; 015import org.cpsolver.ifs.util.Progress; 016 017 018/** 019 * Default implementation of the student sectioning functions needed within the course timetabling solver 020 * consisting of {@link InitialSectioning} and {@link FinalSectioning}. 021 * <br> 022 * <br> 023 * Many course offerings consist of multiple classes, with students enrolled in 024 * the course divided among them. These classes are often linked by a set of 025 * constraints, namely: 026 * <ul> 027 * <li>Each class has a limit stating the maximum number of students who can be 028 * enrolled in it. 029 * <li>A student must be enrolled in exactly one class for each subpart of a 030 * course. 031 * <li>If two subparts of a course have a parent-child relationship, a student 032 * enrolled in the parent class must also be enrolled in one of the child 033 * classes. 034 * </ul> 035 * Moreover, some of the classes of an offering may be required or prohibited 036 * for certain students, based on reservations that can be set on an offering, a 037 * configuration, or a class. <br> 038 * While the data are loaded into the solver, an initial sectioning of students into 039 * classes is processed (see {@link InitialSectioning}). However, it 040 * is still possible to improve on the number of student conflicts in the 041 * solution. This can be accomplished by moving students between alternative 042 * classes of the same course during or after the search (see 043 * {@link FinalSectioning}). 044 * 045 * @author Tomáš Müller 046 * @version CourseTT 1.3 (University Course Timetabling)<br> 047 * Copyright (C) 2014 Tomáš Müller<br> 048 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 049 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 050 * <br> 051 * This library is free software; you can redistribute it and/or modify 052 * it under the terms of the GNU Lesser General Public License as 053 * published by the Free Software Foundation; either version 3 of the 054 * License, or (at your option) any later version. <br> 055 * <br> 056 * This library is distributed in the hope that it will be useful, but 057 * WITHOUT ANY WARRANTY; without even the implied warranty of 058 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 059 * Lesser General Public License for more details. <br> 060 * <br> 061 * You should have received a copy of the GNU Lesser General Public 062 * License along with this library; if not see 063 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 064 */ 065public class DefaultStudentSectioning implements StudentSectioning, InfoProvider<Lecture, Placement> { 066 protected TimetableModel iModel = null; 067 private Progress iProgress = null; 068 protected FinalSectioning iFinalSectioning = null; 069 protected boolean iMustFollowReservations = false; 070 protected static java.text.DecimalFormat sDF2 = new java.text.DecimalFormat("0.00", new java.text.DecimalFormatSymbols(Locale.US)); 071 072 /** 073 * Constructor 074 * @param model problem model 075 */ 076 public DefaultStudentSectioning(TimetableModel model) { 077 iModel = model; 078 iFinalSectioning = new FinalSectioning(model); 079 iMustFollowReservations = model.getProperties().getPropertyBoolean("StudentSectioning.MustFollowReservations", false); 080 } 081 082 public Progress getProgress() { 083 if (iProgress == null) iProgress = Progress.getInstance(iModel); 084 return iProgress; 085 } 086 087 /** 088 * Enroll students into the given offering during the initial data load using {@link InitialSectioning}. 089 * @param offeringId instructional offering id 090 * @param courseName course name 091 * @param students list of students to be sectioned 092 * @param configurations list of configurations the students are to be sectioned into 093 */ 094 @Override 095 public void initialSectioning(Assignment<Lecture, Placement> assignment, Long offeringId, String courseName, Collection<Student> students, Collection<Configuration> configurations) { 096 if (students == null || students.isEmpty()) 097 return; 098 if (configurations == null || configurations.isEmpty()) 099 return; 100 if (configurations.size() == 1) { 101 if (isMustFollowReservations()) { 102 Collection<Student> availableStudents = new ArrayList<Student>(students.size()); 103 Configuration cfg = configurations.iterator().next(); 104 for (Student st : students) { 105 if (st.canEnroll(cfg)) { 106 availableStudents.add(st); 107 st.addConfiguration(cfg); 108 } else { 109 getProgress().debug("Unable to enroll student " + st.getId() + " in " + courseName); 110 } 111 for (Long subpartId: cfg.getTopSubpartIds()) { 112 initialSectioningLectures(assignment, offeringId, courseName, availableStudents, cfg.getTopLectures(subpartId)); 113 } 114 } 115 } else { 116 Configuration cfg = configurations.iterator().next(); 117 for (Student st : students) { 118 st.addConfiguration(cfg); 119 } 120 for (Long subpartId: cfg.getTopSubpartIds()) { 121 initialSectioningLectures(assignment, offeringId, courseName, students, cfg.getTopLectures(subpartId)); 122 } 123 } 124 } else { 125 getProgress().trace("sectioning " + students.size() + " students of course " + courseName + " into " + configurations.size() + " configurations"); 126 Group[] studentsPerSection = studentsToConfigurations(offeringId, students, configurations); 127 for (int i = 0; i < configurations.size(); i++) { 128 Group group = studentsPerSection[i]; 129 getProgress().trace((i + 1) + ". configuration got " + group.getStudents().size() + " students (weighted=" + group.size() + ", cfgLimit=" + group.getConfiguration().getLimit() + ")"); 130 for (Student st : group.getStudents()) { 131 st.addConfiguration(group.getConfiguration()); 132 } 133 for (Long subpartId: group.getConfiguration().getTopSubpartIds()) { 134 initialSectioningLectures(assignment, offeringId, courseName, group.getStudents(), group.getConfiguration().getTopLectures(subpartId)); 135 } 136 } 137 if (isMustFollowReservations()) { 138 for (Student st : students) { 139 boolean hasConfig = false; 140 for (Configuration cfg: configurations) 141 if (st.getConfigurations().contains(cfg)) { 142 hasConfig = true; 143 break; 144 } 145 if (!hasConfig) 146 getProgress().debug("Unable to enroll student " + st.getId() + " in " + courseName); 147 } 148 } 149 } 150 } 151 152 /** 153 * Class label 154 * @param lecture a class 155 * @return class label including a link to be printed in the log 156 */ 157 protected String getClassLabel(Lecture lecture) { 158 return "<A href='classDetail.do?cid=" + lecture.getClassId() + "'>" + lecture.getName() + "</A>"; 159 } 160 161 /** 162 * Enroll students into the given classes during the initial data load using {@link InitialSectioning}. 163 * @param assignment current assignment 164 * @param offeringId instructional offering id 165 * @param courseName course name 166 * @param students list of students to be sectioned 167 * @param lectures list of lectures the students are to be sectioned into 168 */ 169 protected void initialSectioningLectures(Assignment<Lecture, Placement> assignment, Long offeringId, String courseName, Collection<Student> students, Collection<Lecture> lectures) { 170 if (lectures == null || lectures.isEmpty()) 171 return; 172 if (students == null || students.isEmpty()) 173 return; 174 for (Lecture lecture : lectures) { 175 if (lecture.classLimit(assignment) == 0 && !lecture.isCommitted()) 176 getProgress().warn("Class " + getClassLabel(lecture) + " has zero class limit."); 177 } 178 179 getProgress().trace("sectioning " + students.size() + " students of course " + courseName + " into " + lectures.size() + " sections"); 180 if (lectures.size() == 1) { 181 Collection<Student> availableStudents = (isMustFollowReservations() ? new ArrayList<Student>(students.size()) : students); 182 Lecture lect = lectures.iterator().next(); 183 for (Student st : students) { 184 if (!st.canEnroll(lect)) { 185 getProgress().debug("Unable to enroll student " + st.getId() + " in class " + getClassLabel(lect)); 186 if (isMustFollowReservations()) continue; 187 } 188 lect.addStudent(assignment, st); 189 st.addLecture(lect); 190 if (isMustFollowReservations()) availableStudents.add(st); 191 } 192 if (lect.hasAnyChildren()) { 193 for (Long subpartId: lect.getChildrenSubpartIds()) { 194 List<Lecture> children = lect.getChildren(subpartId); 195 initialSectioningLectures(assignment, offeringId, lect.getName(), availableStudents, children); 196 } 197 } 198 } else { 199 Group[] studentsPerSection = studentsToLectures(offeringId, students, lectures); 200 for (int i = 0; i < studentsPerSection.length; i++) { 201 Group group = studentsPerSection[i]; 202 Lecture lect = group.getLecture(); 203 if (group.getStudents().isEmpty()) { 204 getProgress().trace("Lecture " + getClassLabel(lect) + " got no students (cl=" + lect.classLimit(assignment) + ")"); 205 continue; 206 } 207 getProgress().trace("Lecture " + getClassLabel(lect) + " got " + group.getStudents().size() + " students (weighted=" + group.size() + ", classLimit=" + lect.classLimit(assignment) + ")"); 208 List<Student> studentsThisSection = group.getStudents(); 209 for (Student st : studentsThisSection) { 210 if (!st.canEnroll(lect)) { 211 if (isMustFollowReservations()) { 212 // should not really happen 213 getProgress().info("Unable to enroll student " + st.getId() + " in class " + getClassLabel(lect)); 214 continue; 215 } else { 216 getProgress().debug("Unable to enroll student " + st.getId() + " in class " + getClassLabel(lect)); 217 } 218 } 219 lect.addStudent(assignment, st); 220 st.addLecture(lect); 221 } 222 if (lect.hasAnyChildren()) { 223 for (Long subpartId: lect.getChildrenSubpartIds()) { 224 List<Lecture> children = lect.getChildren(subpartId); 225 initialSectioningLectures(assignment, offeringId, lect.getName(), studentsThisSection, children); 226 } 227 } 228 } 229 if (isMustFollowReservations()) { 230 for (Student st : students) { 231 boolean hasLecture = false; 232 for (Lecture lect: lectures) 233 if (st.getLectures().contains(lect)) { 234 hasLecture = true; 235 break; 236 } 237 if (!hasLecture) 238 getProgress().debug("Unable to enroll student " + st.getId() + " in " + courseName); 239 } 240 } 241 } 242 } 243 244 /** 245 * Section students into configurations. This method calls the actual initial sectioning {@link InitialSectioning#getGroups()}. 246 * @param offeringId instructional offering id 247 * @param students list of students to be sectioned 248 * @param configurations list of configurations the students are to be sectioned into 249 * @return list of {@link Group} 250 */ 251 protected Group[] studentsToConfigurations(Long offeringId, Collection<Student> students, Collection<Configuration> configurations) { 252 InitialSectioning sect = new InitialSectioning(getProgress(), offeringId, configurations, students); 253 sect.setMustFollowReservations(isMustFollowReservations()); 254 return sect.getGroups(); 255 } 256 257 /** 258 * Section students into lectures. This method calls the actual initial sectioning {@link InitialSectioning#getGroups()}. 259 * @param offeringId instructional offering id 260 * @param students list of students to be sectioned 261 * @param lectures list of lectures the students are to be sectioned into 262 * @return list of {@link Group} 263 */ 264 protected Group[] studentsToLectures(Long offeringId, Collection<Student> students, Collection<Lecture> lectures) { 265 InitialSectioning sect = new InitialSectioning(getProgress(), offeringId, lectures, students); 266 sect.setMustFollowReservations(isMustFollowReservations()); 267 return sect.getGroups(); 268 } 269 270 /** 271 * Return true if final student sectioning is implemented. 272 */ 273 @Override 274 public boolean hasFinalSectioning() { 275 return true; 276 } 277 278 /** 279 * Run student final sectioning (switching students between sections of the same 280 * class in order to minimize overall number of student conflicts). 281 */ 282 @Override 283 public void switchStudents(Solution<Lecture, Placement> solution, TerminationCondition<Lecture, Placement> termination) { 284 iFinalSectioning.execute(solution, termination); 285 } 286 287 /** 288 * Perform sectioning on the given lecture 289 * @param lecture given lecture 290 * @param recursive recursively resection lectures affected by a student swap 291 * @param configAsWell resection students between configurations as well 292 **/ 293 @Override 294 public void resection(Assignment<Lecture, Placement> assignment, Lecture lecture, boolean recursive, boolean configAsWell) { 295 iFinalSectioning.resection(assignment, lecture, recursive, configAsWell); 296 } 297 298 @Override 299 public void getInfo(Assignment<Lecture, Placement> assignment, Map<String, String> info) { 300 if (!iModel.getStudentGroups().isEmpty()) 301 info.put("Student groups", sDF2.format(100.0 * StudentSwapSectioning.group(iModel) / iModel.getStudentGroups().size()) + "%"); 302 } 303 304 @Override 305 public void getInfo(Assignment<Lecture, Placement> assignment, Map<String, String> info, Collection<Lecture> variables) { 306 if (!iModel.getStudentGroups().isEmpty()) 307 info.put("Student groups", sDF2.format(StudentSwapSectioning.gp(iModel, variables)) + "%"); 308 } 309 310 /** 311 * Must reservations be followed? When true, a student cannot be placed in a section where {@link Student#canEnroll(Lecture)} is false. 312 * Defaults to false. 313 */ 314 public boolean isMustFollowReservations() { return iMustFollowReservations; } 315 /** 316 * Must reservations be followed? When true, a student cannot be placed in a section where {@link Student#canEnroll(Lecture)} is false. 317 * Defaults to false. 318 */ 319 public void setMustFollowReservations(boolean mustFollow) { iMustFollowReservations = mustFollow; } 320}