001 package net.sf.cpsolver.coursett.model;
002
003 import java.util.Collection;
004 import java.util.Enumeration;
005 import java.util.HashSet;
006 import java.util.Hashtable;
007 import java.util.Iterator;
008 import java.util.Vector;
009
010 import net.sf.cpsolver.ifs.util.Progress;
011
012 /**
013 * Student initial sectioning (before a solver is started).
014 * <br><br>
015 * Many course offerings consist of multiple classes, with students enrolled in the
016 * course divided among them. These classes are often linked by a set of constraints,
017 * namely:<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 course.
021 * <li>If two subparts of a course have a parent–child relationship, a student enrolled
022 * in the parent class must also be enrolled in one of the child classes.
023 * </ul>
024 * Moreover, some of the classes of an offering may be required or prohibited for
025 * certain students, based on reservations that can be set on an offering, a configuration,
026 * or a class.
027 * <br>
028 * Before implementing the solver, an initial sectioning of students into classes
029 * is processed. This sectioning is based on Carter’s homogeneous sectioning
030 * and is intended to minimize future student conflicts. However, it is still possible
031 * to improve on the number of student conflicts in the solution. This can be accomplished
032 * by moving students between alternative classes of the same course
033 * during or after the search (see {@link FinalSectioning}).
034 *
035 * @version
036 * CourseTT 1.1 (University Course Timetabling)<br>
037 * Copyright (C) 2006 Tomáš Müller<br>
038 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
039 * Lazenska 391, 76314 Zlin, Czech Republic<br>
040 * <br>
041 * This library is free software; you can redistribute it and/or
042 * modify it under the terms of the GNU Lesser General Public
043 * License as published by the Free Software Foundation; either
044 * version 2.1 of the License, or (at your option) any later version.
045 * <br><br>
046 * This library is distributed in the hope that it will be useful,
047 * but 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.
050 * <br><br>
051 * You should have received a copy of the GNU Lesser General Public
052 * License along with this library; if not, write to the Free Software
053 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
054 */
055 public class InitialSectioning {
056 Collection iStudents = null;
057 Group[] iGroups = null;
058 Long iOfferingId = null;
059 Progress iProgress = null;
060
061 public InitialSectioning(Progress progress, Long offeringId, Collection lectureOrConfigurations, Collection students) {
062 iOfferingId = offeringId;
063 iStudents = new HashSet(students);
064 iProgress = progress;
065
066 iGroups = new Group[lectureOrConfigurations.size()];
067
068 int idx = 0;
069 double total = 0;
070 for (Iterator i=lectureOrConfigurations.iterator();i.hasNext();idx++) {
071 Object lectureOrConfiguration = i.next();
072 if (lectureOrConfiguration instanceof Lecture) {
073 Lecture lecture = (Lecture)lectureOrConfiguration;
074 iGroups[idx] = new Group(lecture);
075 } else {
076 Configuration configuration = (Configuration)lectureOrConfiguration;
077 iGroups[idx] = new Group(configuration);
078 }
079 total += iGroups[idx].getMaxSize();
080 }
081
082 if (total==0) {
083 for (idx=0;idx<iGroups.length;idx++) {
084 iGroups[idx].setMaxSize(1);
085 total++;
086 }
087 }
088
089 double studentsWeight = 0;
090 for (Iterator i=iStudents.iterator();i.hasNext();) {
091 Student s = (Student)i.next();
092 studentsWeight += s.getOfferingWeight(iOfferingId);
093 }
094
095 double factor = studentsWeight/total;
096 for (idx=0;idx<iGroups.length;idx++) {
097 iGroups[idx].setMaxSize(factor*iGroups[idx].getMaxSize());
098 iGroups[idx].setMinSize(Math.min(iGroups[idx].getMinSize(),0.9*iGroups[idx].getMaxSize()));
099 }
100
101 progress.trace("Initial sectioning:");
102 progress.trace(" going to section "+iStudents.size()+" into "+total+" seats");
103 for (idx=0;idx<iGroups.length;idx++)
104 progress.trace(" "+(idx+1)+". group can accomodate <"+iGroups[idx].getMinSize()+","+iGroups[idx].getMaxSize()+"> students");
105 }
106
107 public void addStudent(Student student) {
108 iStudents.add(student);
109 }
110
111 private boolean moveAwayOneStudent(Group group) {
112 Group newGroup = null;
113 Student movingStudent = null;
114 double curDist = 0, newDist = 0;
115
116 for (Iterator i=group.getStudents().iterator();i.hasNext();) {
117 Student student = (Student)i.next();
118 if (group.isEnrolled(student)) continue;
119 double cd = group.getDistance(student);
120 for (int x=0;x<iGroups.length;x++) {
121 if (group.equals(iGroups[x])) continue;
122 if (iGroups[x].size()>iGroups[x].getMaxSize()) continue;
123 if (!iGroups[x].canEnroll(student)) continue;
124 double nd = iGroups[x].getDistance(student);
125 if (newGroup==null || newDist-curDist<nd-cd) {
126 newGroup = iGroups[x]; movingStudent = student; curDist = cd; newDist = nd;
127 if (newDist-curDist<0.01) break;
128 }
129 }
130 }
131
132 if (newGroup!=null) {
133 group.removeStudent(movingStudent);
134 newGroup.addStudent(movingStudent);
135 return true;
136 }
137
138 return false;
139 }
140
141 public boolean moveIntoOneStudent(Group group) {
142 Group oldGroup = null;
143 Student movingStudent = null;
144 double curDist = 0, newDist = 0;
145
146 for (int x=0;x<iGroups.length;x++) {
147 if (group.equals(iGroups[x])) continue;
148 if (iGroups[x].size()<=iGroups[x].getMinSize()) continue;
149 for (Iterator i=iGroups[x].getStudents().iterator();i.hasNext();) {
150 Student student = (Student)i.next();
151 if (!group.canEnroll(student)) continue;
152 if (iGroups[x].isEnrolled(student)) continue;
153 double cd = iGroups[x].getDistance(student);
154 double nd = group.getDistance(student);
155 if (oldGroup==null || newDist-curDist<nd-cd) {
156 oldGroup = iGroups[x]; movingStudent = student; curDist = cd; newDist = nd;
157 if (newDist-curDist<0.01) break;
158 }
159 }
160 }
161
162 if (oldGroup!=null) {
163 oldGroup.removeStudent(movingStudent);
164 group.addStudent(movingStudent);
165 return true;
166 }
167
168 return false;
169 }
170
171
172 public Group[] getGroups() {
173 double minDist = 1.0/iGroups.length;
174
175 for (Iterator i=iStudents.iterator();i.hasNext();) {
176 Student student = (Student)i.next();
177 Group group = null;
178 for (int idx=0;idx<iGroups.length;idx++) {
179 if (iGroups[idx].isEnrolled(student)) {
180 group = iGroups[idx]; break;
181 }
182 }
183 if (group!=null) {
184 group.addStudent(student);
185 i.remove();
186 }
187 }
188
189 for (Iterator i=iStudents.iterator();i.hasNext();) {
190 Student student = (Student)i.next();
191 double studentWeight = student.getOfferingWeight(iOfferingId);
192
193 Group group = null; double dist = 0.0;
194 for (int idx=0;idx<iGroups.length;idx++) {
195 Group g = iGroups[idx];
196 if (!g.canEnroll(student)) continue;
197 if (g.size()+studentWeight>g.getMaxSize()) continue;
198 double d = g.getDistance(student);
199 if (group==null || d<dist) {
200 group = g; dist = d;
201 if (d<minDist) break;
202 }
203 }
204
205 if (group!=null) {
206 group.addStudent(student);
207 continue;
208 }
209
210 //disobey max size
211 for (int idx=0;idx<iGroups.length;idx++) {
212 Group g = iGroups[idx];
213 if (!g.canEnroll(student)) continue;
214 double d = g.getDistance(student);
215 if (group==null || d<dist) {
216 group = g; dist = d;
217 }
218 }
219
220 if (group!=null) {
221 group.addStudent(student);
222 continue;
223 }
224
225 //disobey max size & can enroll
226 for (int idx=0;idx<iGroups.length;idx++) {
227 Group g = iGroups[idx];
228 double d = g.getDistance(student);
229 if (group==null || d<dist) {
230 group = g; dist = d;
231 }
232 }
233
234 iProgress.debug("Unable to find a valid section for student "+student.getId()+", enrolling to "+(group.getLecture()!=null?group.getLecture().getName():group.getConfiguration().getConfigId().toString()));
235
236 group.addStudent(student);
237 }
238
239 for (int idx=0; idx<iGroups.length; idx++) {
240 Group group = iGroups[idx];
241
242 while (group.size()>group.getMaxSize()) {
243 if (!moveAwayOneStudent(group)) break;
244 }
245
246 while (group.size()>group.getMaxSize()) {
247
248 Group newGroup = null;
249 Student movingStudent = null;
250
251 for (Iterator i=group.getStudents().iterator();i.hasNext();) {
252 Student student = (Student)i.next();
253 if (group.isEnrolled(student)) continue;
254 for (int x=0;x<iGroups.length;x++) {
255 if (idx==x) continue;
256 if (!iGroups[x].canEnroll(student)) continue;
257 while (iGroups[x].size()+student.getOfferingWeight(iOfferingId)>iGroups[x].getMaxSize()) {
258 if (!moveAwayOneStudent(iGroups[x])) break;
259 }
260 if (iGroups[x].size()+student.getOfferingWeight(iOfferingId)>iGroups[x].getMaxSize()) continue;
261 newGroup = iGroups[x];
262 movingStudent = student;
263 break;
264 }
265 if (newGroup!=null) break;
266 }
267
268 if (newGroup!=null) {
269 group.removeStudent(movingStudent);
270 newGroup.addStudent(movingStudent);
271 } else {
272 break;
273 }
274 }
275
276 while (group.size()<group.getMinSize()) {
277 if (!moveIntoOneStudent(group)) break;
278 }
279 }
280
281 return iGroups;
282 }
283
284 public class Group {
285 private Vector iStudents = new Vector();
286 private Lecture iLecture = null;
287 private Configuration iConfiguration = null;
288 private Double iDist = null;
289 private double iMinSize = 0, iMaxSize = 0;
290 private Hashtable iDistCache = new Hashtable();
291 private double iSize = 0.0;
292
293 public Group(Lecture lecture) {
294 iLecture = lecture;
295 iMinSize = lecture.minClassLimit();
296 iMaxSize = lecture.maxAchievableClassLimit();
297 }
298
299 public Group(Configuration configuration) {
300 iConfiguration = configuration;
301 iMinSize = iMaxSize = iConfiguration.getLimit();
302 }
303
304 public Configuration getConfiguration() { return iConfiguration; }
305 public Lecture getLecture() { return iLecture; }
306 public double getMinSize() { return iMinSize; }
307 public double getMaxSize() { return iMaxSize; }
308 public void setMinSize(double minSize) { iMinSize = minSize; }
309 public void setMaxSize(double maxSize) { iMaxSize = maxSize; }
310
311 public double getDistance() {
312 if (iDist==null) {
313 double dist = 0.0;
314 double prob = 10.0 / iStudents.size();
315 int cnt = 0;
316 for (Iterator i=iStudents.iterator();i.hasNext();) {
317 Student s1 = (Student)i.next();
318 if (Math.random()<prob) {
319 for (Iterator j=iStudents.iterator();j.hasNext();) {
320 Student s2 = (Student)j.next();
321 if (s1.getId().compareTo(s2.getId())<=0) continue;
322 if (Math.random()<prob) {
323 dist += s1.getDistance(s2);
324 cnt++;
325 }
326 }
327 }
328 }
329 iDist = new Double(dist / cnt);
330 }
331 return iDist.doubleValue();
332 }
333 public double getDistance(Student student) {
334 Double cachedDist = (Double)iDistCache.get(student);
335 if (cachedDist!=null) return cachedDist.doubleValue();
336 double dist = 0.0;
337 double prob = 10.0 / iStudents.size();
338 int cnt = 0;
339 for (Iterator i=iStudents.iterator();i.hasNext();) {
340 Student s = (Student)i.next();
341 if (prob>=1.0 || Math.random()<prob) {
342 dist += s.getDistance(student);
343 cnt ++;
344 }
345 }
346 iDistCache.put(student, new Double(dist/cnt));
347 return dist/cnt;
348 }
349
350 public void addStudent(Student student) {
351 iStudents.add(student);
352 iSize += student.getOfferingWeight(iOfferingId);
353 iDist = null; iDistCache.clear();
354 }
355
356 public void removeStudent(Student student) {
357 iStudents.remove(student);
358 iSize -= student.getOfferingWeight(iOfferingId);
359 iDist = null; iDistCache.clear();
360 }
361
362 public Vector getStudents() { return iStudents; }
363
364 public double size() { return iSize; }
365
366 public String toString() { return "{"+size()+"-"+getDistance()+"/"+getStudents()+"}"; }
367
368 public boolean canEnroll(Student student) {
369 if (getLecture()!=null) {
370 return student.canEnroll(getLecture());
371 } else {
372 for (Enumeration e=getConfiguration().getTopSubpartIds();e.hasMoreElements();) {
373 Long subpartId = (Long)e.nextElement();
374 boolean canEnrollThisSubpart = false;
375 for (Iterator i=getConfiguration().getTopLectures(subpartId).iterator();i.hasNext();) {
376 Lecture lecture = (Lecture)i.next();
377 if (student.canEnroll(lecture)) {
378 canEnrollThisSubpart = true; break;
379 }
380 }
381 if (!canEnrollThisSubpart) return false;
382 }
383 return true;
384 }
385 }
386
387 public boolean isEnrolled(Student student) {
388 if (getLecture()!=null) {
389 return student.getLectures().contains(getLecture());
390 } else {
391 for (Iterator j=student.getLectures().iterator();j.hasNext();) {
392 Lecture lect = (Lecture)j.next();
393 if (lect.getConfiguration().equals(getConfiguration()))
394 return true;
395 }
396 return false;
397 }
398
399 }
400 }
401
402 public static void initialSectioningCfg(Progress p, Long offeringId, String courseName, Collection students, Vector configurations) {
403 if (students==null || students.isEmpty()) return;
404 if (configurations==null || configurations.isEmpty()) return;
405 if (configurations.size()==1) {
406 Configuration cfg = (Configuration)configurations.firstElement();
407 for (Iterator i=students.iterator();i.hasNext();) {
408 Student st = (Student)i.next();
409 st.addConfiguration(cfg);
410 }
411 for (Enumeration e=cfg.getTopSubpartIds();e.hasMoreElements();) {
412 Long subpartId = (Long)e.nextElement();
413 initialSectioning(p, offeringId, courseName, students, cfg.getTopLectures(subpartId));
414 }
415 } else {
416 p.trace("sectioning "+students.size()+" students of course "+courseName+" into "+configurations.size()+" configurations");
417 InitialSectioning sect = new InitialSectioning(p,offeringId, configurations, students);
418 Group[] studentsPerSection = sect.getGroups();
419 for (int i=0;i<configurations.size();i++) {
420 Group group = (Group)studentsPerSection[i];
421 p.trace((i+1)+". configuration got "+group.getStudents().size()+" students (weighted="+group.size()+", cfgLimit="+group.getConfiguration().getLimit()+")");
422 for (Iterator j=group.getStudents().iterator();j.hasNext();) {
423 Student st = (Student)j.next();
424 st.addConfiguration(group.getConfiguration());
425 }
426 for (Enumeration e=group.getConfiguration().getTopSubpartIds();e.hasMoreElements();) {
427 Long subpartId = (Long)e.nextElement();
428 initialSectioning(p, offeringId, courseName, group.getStudents(), group.getConfiguration().getTopLectures(subpartId));
429 }
430 }
431 }
432 }
433
434 private static String getClassLabel(Lecture lecture) {
435 return "<A href='classDetail.do?cid="+lecture.getClassId()+"'>"+lecture.getName()+"</A>";
436 }
437
438 private static void initialSectioning(Progress p, Long offeringId, String parentName, Collection students, Collection lectures) {
439 if (lectures==null || lectures.isEmpty()) return;
440 if (students==null || students.isEmpty()) return;
441 for (Iterator i=lectures.iterator();i.hasNext();) {
442 Lecture lecture = (Lecture)i.next();
443 if (lecture.classLimit()==0)
444 p.warn("Class "+getClassLabel(lecture)+" has zero class limit.");
445 }
446
447 p.trace("sectioning "+students.size()+" students of course "+parentName+" into "+lectures.size()+" sections");
448 if (lectures.size()==1) {
449 Lecture lect = (Lecture)lectures.iterator().next();
450 for (Iterator j=students.iterator();j.hasNext();) {
451 Student st = (Student)j.next();
452 if (!st.canEnroll(lect)) {
453 p.info("Unable to enroll student "+st.getId()+" in class "+getClassLabel(lect));
454 }
455 lect.addStudent(st);
456 st.addLecture(lect);
457 }
458 if (lect.hasAnyChildren()) {
459 for (Enumeration e1=lect.getChildrenSubpartIds();e1.hasMoreElements();) {
460 Long subpartId = (Long) e1.nextElement();
461 Vector children = lect.getChildren(subpartId);
462 initialSectioning(p, offeringId, lect.getName(),students,children);
463 }
464 }
465 } else {
466 InitialSectioning sect = new InitialSectioning(p,offeringId, lectures, students);
467 Group[] studentsPerSection = sect.getGroups();
468 for (int i=0;i<studentsPerSection.length;i++) {
469 Group group = (Group)studentsPerSection[i];
470 Lecture lect = group.getLecture();
471 if (group==null || group.getStudents().isEmpty()) {
472 p.trace("Lecture "+getClassLabel(lect)+" got no students (cl="+lect.classLimit()+")");
473 continue;
474 }
475 p.trace("Lecture "+getClassLabel(lect)+" got "+group.getStudents().size()+" students (weighted="+group.size()+", classLimit="+lect.classLimit()+")");
476 Collection studentsThisSection = group.getStudents();
477 for (Iterator j=studentsThisSection.iterator();j.hasNext();) {
478 Student st = (Student)j.next();
479 if (!st.canEnroll(lect)) {
480 p.info("Unable to enroll student "+st.getId()+" in class "+getClassLabel(lect));
481 }
482 lect.addStudent(st);
483 st.addLecture(lect);
484 }
485 if (lect.hasAnyChildren()) {
486 for (Enumeration e1=lect.getChildrenSubpartIds();e1.hasMoreElements();) {
487 Long subpartId = (Long) e1.nextElement();
488 Vector children = lect.getChildren(subpartId);
489 initialSectioning(p,offeringId, lect.getName(),studentsThisSection,children);
490 }
491 }
492 }
493 }
494 }
495
496 }