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