001 package net.sf.cpsolver.coursett.model; 002 003 import java.util.Collection; 004 import java.util.List; 005 006 import net.sf.cpsolver.coursett.model.InitialSectioning.Group; 007 import 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 Tomas Muller<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 */ 055 public class DefaultStudentSectioning implements StudentSectioning { 056 protected Progress iProgress = null; 057 protected FinalSectioning iFinalSectioning = null; 058 059 /** 060 * Constructor 061 */ 062 public DefaultStudentSectioning(TimetableModel model) { 063 iProgress = Progress.getInstance(model); 064 iFinalSectioning = new FinalSectioning(model); 065 } 066 067 /** 068 * Enroll students into the given offering during the initial data load using {@link InitialSectioning}. 069 * @param offeringId instructional offering id 070 * @param courseName course name 071 * @param students list of students to be sectioned 072 * @param configurations list of configurations the students are to be sectioned into 073 */ 074 @Override 075 public void initialSectioning(Long offeringId, String courseName, Collection<Student> students, Collection<Configuration> configurations) { 076 if (students == null || students.isEmpty()) 077 return; 078 if (configurations == null || configurations.isEmpty()) 079 return; 080 if (configurations.size() == 1) { 081 Configuration cfg = configurations.iterator().next(); 082 for (Student st : students) { 083 st.addConfiguration(cfg); 084 } 085 for (Long subpartId: cfg.getTopSubpartIds()) { 086 initialSectioningLectures(offeringId, courseName, students, cfg.getTopLectures(subpartId)); 087 } 088 } else { 089 iProgress.trace("sectioning " + students.size() + " students of course " + courseName + " into " + configurations.size() + " configurations"); 090 Group[] studentsPerSection = studentsToConfigurations(offeringId, students, configurations); 091 for (int i = 0; i < configurations.size(); i++) { 092 Group group = studentsPerSection[i]; 093 iProgress.trace((i + 1) + ". configuration got " + group.getStudents().size() + " students (weighted=" + group.size() + ", cfgLimit=" + group.getConfiguration().getLimit() + ")"); 094 for (Student st : group.getStudents()) { 095 st.addConfiguration(group.getConfiguration()); 096 } 097 for (Long subpartId: group.getConfiguration().getTopSubpartIds()) { 098 initialSectioningLectures(offeringId, courseName, group.getStudents(), group.getConfiguration().getTopLectures(subpartId)); 099 } 100 } 101 } 102 } 103 104 /** 105 * Class label 106 * @param lecture a class 107 * @return class label including a link to be printed in the log 108 */ 109 protected String getClassLabel(Lecture lecture) { 110 return "<A href='classDetail.do?cid=" + lecture.getClassId() + "'>" + lecture.getName() + "</A>"; 111 } 112 113 /** 114 * Enroll students into the given classes during the initial data load using {@link InitialSectioning}. 115 * @param offeringId instructional offering id 116 * @param courseName course name 117 * @param students list of students to be sectioned 118 * @param lectures list of lectures the students are to be sectioned into 119 */ 120 protected void initialSectioningLectures(Long offeringId, String courseName, Collection<Student> students, Collection<Lecture> lectures) { 121 if (lectures == null || lectures.isEmpty()) 122 return; 123 if (students == null || students.isEmpty()) 124 return; 125 for (Lecture lecture : lectures) { 126 if (lecture.classLimit() == 0 && !lecture.isCommitted()) 127 iProgress.warn("Class " + getClassLabel(lecture) + " has zero class limit."); 128 } 129 130 iProgress.trace("sectioning " + students.size() + " students of course " + courseName + " into " + lectures.size() + " sections"); 131 if (lectures.size() == 1) { 132 Lecture lect = lectures.iterator().next(); 133 for (Student st : students) { 134 if (!st.canEnroll(lect)) { 135 iProgress.info("Unable to enroll student " + st.getId() + " in class " + getClassLabel(lect)); 136 } 137 lect.addStudent(st); 138 st.addLecture(lect); 139 } 140 if (lect.hasAnyChildren()) { 141 for (Long subpartId: lect.getChildrenSubpartIds()) { 142 List<Lecture> children = lect.getChildren(subpartId); 143 initialSectioningLectures(offeringId, lect.getName(), students, children); 144 } 145 } 146 } else { 147 Group[] studentsPerSection = studentsToLectures(offeringId, students, lectures); 148 for (int i = 0; i < studentsPerSection.length; i++) { 149 Group group = studentsPerSection[i]; 150 Lecture lect = group.getLecture(); 151 if (group.getStudents().isEmpty()) { 152 iProgress.trace("Lecture " + getClassLabel(lect) + " got no students (cl=" + lect.classLimit() + ")"); 153 continue; 154 } 155 iProgress.trace("Lecture " + getClassLabel(lect) + " got " + group.getStudents().size() + " students (weighted=" + group.size() + ", classLimit=" + lect.classLimit() + ")"); 156 List<Student> studentsThisSection = group.getStudents(); 157 for (Student st : studentsThisSection) { 158 if (!st.canEnroll(lect)) { 159 iProgress.info("Unable to enroll student " + st.getId() + " in class " + getClassLabel(lect)); 160 } 161 lect.addStudent(st); 162 st.addLecture(lect); 163 } 164 if (lect.hasAnyChildren()) { 165 for (Long subpartId: lect.getChildrenSubpartIds()) { 166 List<Lecture> children = lect.getChildren(subpartId); 167 initialSectioningLectures(offeringId, lect.getName(), studentsThisSection, children); 168 } 169 } 170 } 171 } 172 } 173 174 /** 175 * Section students into configurations. This method calls the actual initial sectioning {@link InitialSectioning#getGroups()}. 176 * @param offeringId instructional offering id 177 * @param students list of students to be sectioned 178 * @param configurations list of configurations the students are to be sectioned into 179 * @return list of {@link Group} 180 */ 181 protected Group[] studentsToConfigurations(Long offeringId, Collection<Student> students, Collection<Configuration> configurations) { 182 InitialSectioning sect = new InitialSectioning(iProgress, offeringId, configurations, students); 183 return sect.getGroups(); 184 } 185 186 /** 187 * Section students into lectures. This method calls the actual initial sectioning {@link InitialSectioning#getGroups()}. 188 * @param offeringId instructional offering id 189 * @param students list of students to be sectioned 190 * @param lectures list of lectures the students are to be sectioned into 191 * @return list of {@link Group} 192 */ 193 protected Group[] studentsToLectures(Long offeringId, Collection<Student> students, Collection<Lecture> lectures) { 194 InitialSectioning sect = new InitialSectioning(iProgress, offeringId, lectures, students); 195 return sect.getGroups(); 196 } 197 198 /** 199 * Return true if final student sectioning is implemented. 200 */ 201 @Override 202 public boolean hasFinalSectioning() { 203 return true; 204 } 205 206 /** 207 * Run student final sectioning (switching students between sections of the same 208 * class in order to minimize overall number of student conflicts). 209 */ 210 @Override 211 public void switchStudents(TimetableModel model) { 212 iFinalSectioning.run(); 213 } 214 215 /** 216 * Perform sectioning on the given lecture 217 * @param lecture given lecture 218 * @param recursive recursively resection lectures affected by a student swap 219 * @param configAsWell resection students between configurations as well 220 **/ 221 @Override 222 public void resection(Lecture lecture, boolean recursive, boolean configAsWell) { 223 iFinalSectioning.resection(lecture, recursive, configAsWell); 224 } 225 226 }