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