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