001package org.cpsolver.coursett.custom; 002 003import java.util.ArrayList; 004import java.util.Collection; 005import java.util.Comparator; 006import java.util.Iterator; 007import java.util.Set; 008import java.util.TreeSet; 009 010import org.cpsolver.coursett.model.Configuration; 011import org.cpsolver.coursett.model.DefaultStudentSectioning; 012import org.cpsolver.coursett.model.InitialSectioning; 013import org.cpsolver.coursett.model.Lecture; 014import org.cpsolver.coursett.model.Placement; 015import org.cpsolver.coursett.model.Student; 016import org.cpsolver.coursett.model.StudentSectioning; 017import org.cpsolver.coursett.model.TimetableModel; 018import org.cpsolver.coursett.model.InitialSectioning.Group; 019import org.cpsolver.ifs.assignment.Assignment; 020import org.cpsolver.ifs.solution.Solution; 021import org.cpsolver.ifs.termination.TerminationCondition; 022import org.cpsolver.ifs.util.Progress; 023 024 025/** 026 * Deterministic implementation of the initial student sectioning. This class assign students to groups in 027 * a deterministic way. Students are ordered by their academic information (curriculum) and unique ids and 028 * assigned in this order to the first available group (configuration or lecture). See {@link StudentSectioning} 029 * and {@link DefaultStudentSectioning} for more details about sectioning students during course timetabling. 030 * <br><br> 031 * This deterministic sectioning can be enabled by setting the following parameter:<pre> 032 * <code>StudentSectioning.Class=org.cpsolver.coursett.custom.DeterministicStudentSectioning</code> 033 * </pre> 034 * 035 * @author Tomáš Müller 036 * @version CourseTT 1.3 (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 * This customization has been implemented for <a href='http://www.agh.pl'>AGH, Poland</a>.<br> 041 * <br> 042 * This library is free software; you can redistribute it and/or modify 043 * it under the terms of the GNU Lesser General Public License as 044 * published by the Free Software Foundation; either version 3 of the 045 * License, or (at your option) any later version. <br> 046 * <br> 047 * This library is distributed in the hope that it will be useful, but 048 * WITHOUT ANY WARRANTY; without even the implied warranty of 049 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 050 * Lesser General Public License for more details. <br> 051 * <br> 052 * You should have received a copy of the GNU Lesser General Public 053 * License along with this library; if not see 054 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 055 */ 056public class DeterministicStudentSectioning extends DefaultStudentSectioning { 057 public DeterministicStudentSectioning(TimetableModel model) { 058 super(model); 059 } 060 061 @Override 062 protected Group[] studentsToConfigurations(Long offeringId, Collection<Student> students, Collection<Configuration> configurations) { 063 DeterministicInitialSectioning sect = new DeterministicInitialSectioning(getProgress(), offeringId, configurations, students); 064 sect.setMustFollowReservations(isMustFollowReservations()); 065 return sect.getGroups(); 066 } 067 068 @Override 069 protected Group[] studentsToLectures(Long offeringId, Collection<Student> students, Collection<Lecture> lectures) { 070 Set<Lecture> sortedLectures = new TreeSet<Lecture>(new Comparator<Lecture>() { 071 @Override 072 public int compare(Lecture l1, Lecture l2) { 073 return l1.getClassId().compareTo(l2.getClassId()); 074 } 075 }); 076 sortedLectures.addAll(lectures); 077 DeterministicInitialSectioning sect = new DeterministicInitialSectioning(getProgress(), offeringId, sortedLectures, students); 078 sect.setMustFollowReservations(isMustFollowReservations()); 079 return sect.getGroups(); 080 } 081 082 /** 083 * No re-sectioning (final sectioning) during deterministic student sectioning. 084 */ 085 @Override 086 public boolean hasFinalSectioning() { 087 return false; 088 } 089 090 /** 091 * No re-sectioning (final sectioning) during deterministic student sectioning. 092 */ 093 @Override 094 public void switchStudents(Solution<Lecture, Placement> solution, TerminationCondition<Lecture, Placement> termination) { 095 } 096 097 /** 098 * No re-sectioning (final sectioning) during deterministic student sectioning. 099 */ 100 @Override 101 public void resection(Assignment<Lecture, Placement> assignment, Lecture lecture, boolean recursive, boolean configAsWell) { 102 } 103 104 /** 105 * Assign students to groups in a deterministic way, i.e., first student to first available group etc. 106 * @author Tomáš Müller 107 */ 108 public static class DeterministicInitialSectioning extends InitialSectioning implements Comparator<Student> { 109 110 public DeterministicInitialSectioning(Progress progress, Long offeringId, Collection<?> lectureOrConfigurations, Collection<Student> students) { 111 super(progress, offeringId, lectureOrConfigurations, students); 112 113 // Sort students by their curriculum information first 114 iStudents = new TreeSet<Student>(this); iStudents.addAll(students); 115 } 116 117 @Override 118 protected void tweakSizes(double total) { 119 double studentsWeight = 0; 120 for (Student s : iStudents) { 121 studentsWeight += s.getOfferingWeight(iOfferingId); 122 } 123 124 // if there is not enough space for the given students 125 if (studentsWeight > total) { 126 if (total == 0) { 127 // all limits are zero -> spread students equally 128 for (int idx = 0; idx < iGroups.length; idx++) 129 iGroups[idx].setMaxSize(total / iGroups.length); 130 } else { 131 // enlarge sections proportionally 132 double factor = studentsWeight / total; 133 for (int idx = 0; idx < iGroups.length; idx++) { 134 iGroups[idx].setMaxSize(factor * iGroups[idx].getMaxSize()); 135 iGroups[idx].setMinSize(Math.min(iGroups[idx].getMinSize(), 0.9 * iGroups[idx].getMaxSize())); 136 } 137 } 138 } 139 } 140 141 @Override 142 public Group[] getGroups() { 143 // Assign already enrolled students first 144 students: for (Iterator<Student> i = iStudents.iterator(); i.hasNext();) { 145 Student student = i.next(); 146 for (int idx = 0; idx < iGroups.length; idx++) { 147 if (iGroups[idx].isEnrolled(student)) { 148 iGroups[idx].addStudent(student); 149 i.remove(); 150 continue students; 151 } 152 } 153 } 154 155 // For all other (not enrolled) students 156 students: for (Student student : iStudents) { 157 double studentWeight = student.getOfferingWeight(iOfferingId); 158 159 // enroll into first available group with enough space 160 for (int idx = 0; idx < iGroups.length; idx++) { 161 Group g = iGroups[idx]; 162 if (!g.canEnroll(student) || g.size() >= g.getMaxSize()) continue; 163 // group found -> enroll and continue with the next student 164 g.addStudent(student); 165 continue students; 166 } 167 168 // disobey max size, but prefer sections with smallest excess 169 Group group = null; int excess = 0; 170 for (int idx = 0; idx < iGroups.length; idx++) { 171 Group g = iGroups[idx]; 172 if (!g.canEnroll(student)) continue; 173 int ex = (int)Math.round(g.size() + studentWeight - g.getMaxSize()); 174 if (group == null || ex < excess) { 175 group = g; 176 excess = ex; 177 } 178 } 179 180 if (group != null) { 181 group.addStudent(student); 182 continue; 183 } 184 185 if (isMustFollowReservations()) { 186 getProgress().debug("Unable to find a valid section for student " + student.getId() + "."); 187 } else { 188 // put the student into the first group 189 getProgress().debug("Unable to find a valid section for student " + student.getId() + ", enrolling to " + (iGroups[0].getLecture() != null ? iGroups[0].getLecture().getName() : iGroups[0].getConfiguration().getConfigId().toString())); 190 iGroups[0].addStudent(student); 191 } 192 } 193 194 // try to move students away from groups with an excess of more than a student 195 for (int idx = 0; idx < iGroups.length; idx++) { 196 Group group = iGroups[idx]; 197 if (group.size() > group.getMaxSize()) { 198 // for each student of a group that is not enrolled in it 199 for (Student student : new ArrayList<Student>(group.getStudents())) { 200 if (group.isEnrolled(student)) continue; 201 // excess of a fraction of a student is allowed 202 if (group.size() - student.getOfferingWeight(iOfferingId) < group.getMaxSize()) continue; 203 // look for an available group with enough space 204 for (int x = 0; x < iGroups.length; x++) { 205 if (idx == x) continue; 206 if (!iGroups[x].canEnroll(student) || iGroups[x].size() >= iGroups[x].getMaxSize()) continue; 207 // group found, move the student away 208 group.removeStudent(student); 209 iGroups[x].addStudent(student); 210 break; 211 } 212 if (group.size() <= group.getMaxSize()) break; 213 } 214 } 215 } 216 217 return iGroups; 218 } 219 220 /** 221 * Sort students by their curriculum information and id 222 */ 223 @Override 224 public int compare(Student s1, Student s2) { 225 int cmp = (s1.getCurriculum() == null ? "" : s1.getCurriculum()).compareToIgnoreCase(s2.getCurriculum() == null ? "" : s2.getCurriculum()); 226 if (cmp != 0) return cmp; 227 cmp = (s1.getAcademicArea() == null ? "" : s1.getAcademicArea()).compareToIgnoreCase(s2.getAcademicArea() == null ? "" : s2.getAcademicArea()); 228 if (cmp != 0) return cmp; 229 cmp = (s1.getMajor() == null ? "" : s1.getMajor()).compareToIgnoreCase(s2.getMajor() == null ? "" : s2.getMajor()); 230 if (cmp != 0) return cmp; 231 cmp = (s1.getAcademicClassification() == null ? "" : s1.getAcademicClassification()).compareToIgnoreCase(s2.getAcademicClassification() == null ? "" : s2.getAcademicClassification()); 232 if (cmp != 0) return cmp; 233 return s1.getId().compareTo(s2.getId()); 234 } 235 } 236}