001 package net.sf.cpsolver.coursett.model;
002
003 import java.util.ArrayList;
004 import java.util.BitSet;
005 import java.util.Collection;
006 import java.util.HashSet;
007 import java.util.HashMap;
008 import java.util.List;
009 import java.util.Locale;
010 import java.util.Map;
011 import java.util.Set;
012
013 import net.sf.cpsolver.coursett.Constants;
014 import net.sf.cpsolver.coursett.constraint.ClassLimitConstraint;
015 import net.sf.cpsolver.coursett.constraint.DepartmentSpreadConstraint;
016 import net.sf.cpsolver.coursett.constraint.GroupConstraint;
017 import net.sf.cpsolver.coursett.constraint.InstructorConstraint;
018 import net.sf.cpsolver.coursett.constraint.JenrlConstraint;
019 import net.sf.cpsolver.coursett.constraint.FlexibleConstraint;
020 import net.sf.cpsolver.coursett.constraint.RoomConstraint;
021 import net.sf.cpsolver.coursett.constraint.SpreadConstraint;
022 import net.sf.cpsolver.coursett.criteria.BackToBackInstructorPreferences;
023 import net.sf.cpsolver.coursett.criteria.BrokenTimePatterns;
024 import net.sf.cpsolver.coursett.criteria.DepartmentBalancingPenalty;
025 import net.sf.cpsolver.coursett.criteria.DistributionPreferences;
026 import net.sf.cpsolver.coursett.criteria.FlexibleConstraintCriterion;
027 import net.sf.cpsolver.coursett.criteria.Perturbations;
028 import net.sf.cpsolver.coursett.criteria.RoomPreferences;
029 import net.sf.cpsolver.coursett.criteria.RoomViolations;
030 import net.sf.cpsolver.coursett.criteria.SameSubpartBalancingPenalty;
031 import net.sf.cpsolver.coursett.criteria.StudentCommittedConflict;
032 import net.sf.cpsolver.coursett.criteria.StudentConflict;
033 import net.sf.cpsolver.coursett.criteria.StudentDistanceConflict;
034 import net.sf.cpsolver.coursett.criteria.StudentHardConflict;
035 import net.sf.cpsolver.coursett.criteria.StudentOverlapConflict;
036 import net.sf.cpsolver.coursett.criteria.TimePreferences;
037 import net.sf.cpsolver.coursett.criteria.TimeViolations;
038 import net.sf.cpsolver.coursett.criteria.TooBigRooms;
039 import net.sf.cpsolver.coursett.criteria.UselessHalfHours;
040 import net.sf.cpsolver.coursett.criteria.placement.AssignmentCount;
041 import net.sf.cpsolver.coursett.criteria.placement.DeltaTimePreference;
042 import net.sf.cpsolver.coursett.criteria.placement.HardConflicts;
043 import net.sf.cpsolver.coursett.criteria.placement.PotentialHardConflicts;
044 import net.sf.cpsolver.coursett.criteria.placement.WeightedHardConflicts;
045 import net.sf.cpsolver.ifs.constant.ConstantModel;
046 import net.sf.cpsolver.ifs.criteria.Criterion;
047 import net.sf.cpsolver.ifs.model.Constraint;
048 import net.sf.cpsolver.ifs.model.GlobalConstraint;
049 import net.sf.cpsolver.ifs.model.WeakeningConstraint;
050 import net.sf.cpsolver.ifs.util.DataProperties;
051 import net.sf.cpsolver.ifs.util.DistanceMetric;
052
053 /**
054 * Timetable model.
055 *
056 * @version CourseTT 1.2 (University Course Timetabling)<br>
057 * Copyright (C) 2006 - 2010 Tomas Muller<br>
058 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
059 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
060 * <br>
061 * This library is free software; you can redistribute it and/or modify
062 * it under the terms of the GNU Lesser General Public License as
063 * published by the Free Software Foundation; either version 3 of the
064 * License, or (at your option) any later version. <br>
065 * <br>
066 * This library is distributed in the hope that it will be useful, but
067 * WITHOUT ANY WARRANTY; without even the implied warranty of
068 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
069 * Lesser General Public License for more details. <br>
070 * <br>
071 * You should have received a copy of the GNU Lesser General Public
072 * License along with this library; if not see
073 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
074 */
075
076 public class TimetableModel extends ConstantModel<Lecture, Placement> {
077 private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(TimetableModel.class);
078 private static java.text.DecimalFormat sDoubleFormat = new java.text.DecimalFormat("0.00",
079 new java.text.DecimalFormatSymbols(Locale.US));
080
081 private List<InstructorConstraint> iInstructorConstraints = new ArrayList<InstructorConstraint>();
082 private List<JenrlConstraint> iJenrlConstraints = new ArrayList<JenrlConstraint>();
083 private List<RoomConstraint> iRoomConstraints = new ArrayList<RoomConstraint>();
084 private List<DepartmentSpreadConstraint> iDepartmentSpreadConstraints = new ArrayList<DepartmentSpreadConstraint>();
085 private List<SpreadConstraint> iSpreadConstraints = new ArrayList<SpreadConstraint>();
086 private List<GroupConstraint> iGroupConstraints = new ArrayList<GroupConstraint>();
087 private List<ClassLimitConstraint> iClassLimitConstraints = new ArrayList<ClassLimitConstraint>();
088 private List<FlexibleConstraint> iFlexibleConstraints = new ArrayList<FlexibleConstraint>();
089 private DataProperties iProperties = null;
090 private int iYear = -1;
091 private List<BitSet> iWeeks = null;
092
093 private HashSet<Student> iAllStudents = new HashSet<Student>();
094
095 private DistanceMetric iDistanceMetric = null;
096
097
098 public TimetableModel(DataProperties properties) {
099 super();
100 iProperties = properties;
101 iDistanceMetric = new DistanceMetric(properties);
102 if (properties.getPropertyBoolean("OnFlySectioning.Enabled", false))
103 addModelListener(new OnFlySectioning(this));
104 String criteria = properties.getProperty("General.Criteria",
105 // Objectives
106 StudentConflict.class.getName() + ";" +
107 StudentDistanceConflict.class.getName() + ";" +
108 StudentHardConflict.class.getName() + ";" +
109 StudentCommittedConflict.class.getName() + ";" +
110 StudentOverlapConflict.class.getName() + ";" +
111 UselessHalfHours.class.getName() + ";" +
112 BrokenTimePatterns.class.getName() + ";" +
113 TooBigRooms.class.getName() + ";" +
114 TimePreferences.class.getName() + ";" +
115 RoomPreferences.class.getName() + ";" +
116 DistributionPreferences.class.getName() + ";" +
117 SameSubpartBalancingPenalty.class.getName() + ";" +
118 DepartmentBalancingPenalty.class.getName() + ";" +
119 BackToBackInstructorPreferences.class.getName() + ";" +
120 Perturbations.class.getName() + ";" +
121 // Additional placement selection criteria
122 AssignmentCount.class.getName() + ";" +
123 DeltaTimePreference.class.getName() + ";" +
124 HardConflicts.class.getName() + ";" +
125 PotentialHardConflicts.class.getName() + ";" +
126 FlexibleConstraintCriterion.class.getName() + ";" +
127 WeightedHardConflicts.class.getName());
128 // Interactive mode -- count time / room violations
129 if (properties.getPropertyBoolean("General.InteractiveMode", false))
130 criteria += ";" + TimeViolations.class.getName() + ";" + RoomViolations.class.getName();
131 // Additional (custom) criteria
132 criteria += ";" + properties.getProperty("General.AdditionalCriteria", "");
133 for (String criterion: criteria.split("\\;")) {
134 if (criterion == null || criterion.isEmpty()) continue;
135 try {
136 @SuppressWarnings("unchecked")
137 Class<Criterion<Lecture, Placement>> clazz = (Class<Criterion<Lecture, Placement>>)Class.forName(criterion);
138 addCriterion(clazz.newInstance());
139 } catch (Exception e) {
140 sLogger.error("Unable to use " + criterion + ": " + e.getMessage());
141 }
142 }
143 }
144
145 public DistanceMetric getDistanceMetric() {
146 return iDistanceMetric;
147 }
148
149 public DataProperties getProperties() {
150 return iProperties;
151 }
152
153 /**
154 * Student final sectioning (switching students between sections of the same
155 * class in order to minimize overall number of student conflicts)
156 */
157 public void switchStudents() {
158 FinalSectioning sect = new FinalSectioning(this);
159 sect.run();
160 }
161
162 @Override
163 public String toString() {
164 return "TimetableModel{" + "\n super=" + super.toString()
165 + "\n studentConflicts=" + sDoubleFormat.format(getCriterion(StudentConflict.class).getValue())
166 + "\n roomPreferences=" + sDoubleFormat.format(getCriterion(RoomPreferences.class).getValue())
167 + "\n timePreferences=" + sDoubleFormat.format(getCriterion(TimePreferences.class).getValue())
168 + "\n groupConstraintPreferences=" + sDoubleFormat.format(getCriterion(DistributionPreferences.class).getValue())
169 + "\n}";
170 }
171
172 public Map<String, String> getBounds() {
173 Map<String, String> ret = new HashMap<String, String>();
174 ret.put("Room preferences min", "" + getCriterion(RoomPreferences.class).getBounds()[0]);
175 ret.put("Room preferences max", "" + getCriterion(RoomPreferences.class).getBounds()[1]);
176 ret.put("Time preferences min", "" + getCriterion(TimePreferences.class).getBounds()[0]);
177 ret.put("Time preferences max", "" + getCriterion(TimePreferences.class).getBounds()[1]);
178 ret.put("Distribution preferences min", "" + getCriterion(DistributionPreferences.class).getBounds()[0]);
179 ret.put("Distribution preferences max", "" + getCriterion(DistributionPreferences.class).getBounds()[1]);
180 if (getProperties().getPropertyBoolean("General.UseDistanceConstraints", false)) {
181 ret.put("Back-to-back instructor preferences max", "" + getCriterion(BackToBackInstructorPreferences.class).getBounds()[1]);
182 }
183 ret.put("Too big rooms max", "" + getCriterion(TooBigRooms.class).getBounds()[0]);
184 ret.put("Useless half-hours", "" + getCriterion(UselessHalfHours.class).getBounds()[0]);
185 return ret;
186 }
187
188 /** Global info */
189 @Override
190 public Map<String, String> getInfo() {
191 Map<String, String> ret = super.getInfo();
192 ret.put("Memory usage", getMem());
193
194 Criterion<Lecture, Placement> rp = getCriterion(RoomPreferences.class);
195 Criterion<Lecture, Placement> rv = getCriterion(RoomViolations.class);
196 ret.put("Room preferences", getPerc(rp.getValue(), rp.getBounds()[0], rp.getBounds()[1]) + "% (" + Math.round(rp.getValue()) + ")"
197 + (rv != null && rv.getValue() >= 0.5 ? " [hard:" + Math.round(rv.getValue()) + "]" : ""));
198
199 Criterion<Lecture, Placement> tp = getCriterion(TimePreferences.class);
200 Criterion<Lecture, Placement> tv = getCriterion(TimeViolations.class);
201 ret.put("Time preferences", getPerc(tp.getValue(), tp.getBounds()[0], tp.getBounds()[1]) + "% (" + sDoubleFormat.format(tp.getValue()) + ")"
202 + (tv != null && tv.getValue() >= 0.5 ? " [hard:" + Math.round(tv.getValue()) + "]" : ""));
203
204 Criterion<Lecture, Placement> dp = getCriterion(DistributionPreferences.class);
205 ret.put("Distribution preferences", getPerc(dp.getValue(), dp.getBounds()[0], dp.getBounds()[1]) + "% (" + sDoubleFormat.format(dp.getValue()) + ")");
206
207 Criterion<Lecture, Placement> sc = getCriterion(StudentConflict.class);
208 Criterion<Lecture, Placement> shc = getCriterion(StudentHardConflict.class);
209 Criterion<Lecture, Placement> sdc = getCriterion(StudentDistanceConflict.class);
210 Criterion<Lecture, Placement> scc = getCriterion(StudentCommittedConflict.class);
211 ret.put("Student conflicts", Math.round(scc.getValue() + sc.getValue()) +
212 " [committed:" + Math.round(scc.getValue()) +
213 ", distance:" + Math.round(sdc.getValue()) +
214 ", hard:" + Math.round(shc.getValue()) + "]");
215
216 if (!getSpreadConstraints().isEmpty()) {
217 Criterion<Lecture, Placement> ip = getCriterion(BackToBackInstructorPreferences.class);
218 ret.put("Back-to-back instructor preferences", getPerc(ip.getValue(), ip.getBounds()[0], ip.getBounds()[1]) + "% (" + Math.round(ip.getValue()) + ")");
219 }
220
221 if (!getDepartmentSpreadConstraints().isEmpty()) {
222 Criterion<Lecture, Placement> dbp = getCriterion(DepartmentBalancingPenalty.class);
223 ret.put("Department balancing penalty", sDoubleFormat.format(dbp.getValue()));
224 }
225
226 Criterion<Lecture, Placement> sbp = getCriterion(SameSubpartBalancingPenalty.class);
227 ret.put("Same subpart balancing penalty", sDoubleFormat.format(sbp.getValue()));
228
229 Criterion<Lecture, Placement> tbr = getCriterion(TooBigRooms.class);
230 ret.put("Too big rooms", getPercRev(tbr.getValue(), tbr.getBounds()[1], tbr.getBounds()[0]) + "% (" + Math.round(tbr.getValue()) + ")");
231
232 Criterion<Lecture, Placement> uh = getCriterion(UselessHalfHours.class);
233 Criterion<Lecture, Placement> bt = getCriterion(BrokenTimePatterns.class);
234
235 ret.put("Useless half-hours", getPercRev(uh.getValue() + bt.getValue(), 0, Constants.sPreferenceLevelStronglyDiscouraged * bt.getBounds()[0]) +
236 "% (" + Math.round(uh.getValue()) + " + " + Math.round(bt.getValue()) + ")");
237 return ret;
238 }
239
240 @Override
241 public Map<String, String> getInfo(Collection<Lecture> variables) {
242 Map<String, String> ret = super.getInfo(variables);
243
244 ret.put("Memory usage", getMem());
245
246 Criterion<Lecture, Placement> rp = getCriterion(RoomPreferences.class);
247 ret.put("Room preferences", getPerc(rp.getValue(variables), rp.getBounds(variables)[0], rp.getBounds(variables)[1]) + "% (" + Math.round(rp.getValue(variables)) + ")");
248
249 Criterion<Lecture, Placement> tp = getCriterion(TimePreferences.class);
250 ret.put("Time preferences", getPerc(tp.getValue(variables), tp.getBounds(variables)[0], tp.getBounds(variables)[1]) + "% (" + sDoubleFormat.format(tp.getValue(variables)) + ")");
251
252 Criterion<Lecture, Placement> dp = getCriterion(DistributionPreferences.class);
253 ret.put("Distribution preferences", getPerc(dp.getValue(variables), dp.getBounds(variables)[0], dp.getBounds(variables)[1]) + "% (" + sDoubleFormat.format(dp.getValue(variables)) + ")");
254
255 Criterion<Lecture, Placement> sc = getCriterion(StudentConflict.class);
256 Criterion<Lecture, Placement> shc = getCriterion(StudentHardConflict.class);
257 Criterion<Lecture, Placement> sdc = getCriterion(StudentDistanceConflict.class);
258 Criterion<Lecture, Placement> scc = getCriterion(StudentCommittedConflict.class);
259 ret.put("Student conflicts", Math.round(scc.getValue(variables) + sc.getValue(variables)) +
260 " [committed:" + Math.round(scc.getValue(variables)) +
261 ", distance:" + Math.round(sdc.getValue(variables)) +
262 ", hard:" + Math.round(shc.getValue(variables)) + "]");
263
264 if (!getSpreadConstraints().isEmpty()) {
265 Criterion<Lecture, Placement> ip = getCriterion(BackToBackInstructorPreferences.class);
266 ret.put("Back-to-back instructor preferences", getPerc(ip.getValue(variables), ip.getBounds(variables)[0], ip.getBounds(variables)[1]) + "% (" + Math.round(ip.getValue(variables)) + ")");
267 }
268
269 if (!getDepartmentSpreadConstraints().isEmpty()) {
270 Criterion<Lecture, Placement> dbp = getCriterion(DepartmentBalancingPenalty.class);
271 ret.put("Department balancing penalty", sDoubleFormat.format(dbp.getValue(variables)));
272 }
273
274 Criterion<Lecture, Placement> sbp = getCriterion(SameSubpartBalancingPenalty.class);
275 ret.put("Same subpart balancing penalty", sDoubleFormat.format(sbp.getValue(variables)));
276
277 Criterion<Lecture, Placement> tbr = getCriterion(TooBigRooms.class);
278 ret.put("Too big rooms", getPercRev(tbr.getValue(variables), tbr.getBounds(variables)[1], tbr.getBounds(variables)[0]) + "% (" + Math.round(tbr.getValue(variables)) + ")");
279
280 Criterion<Lecture, Placement> uh = getCriterion(UselessHalfHours.class);
281 Criterion<Lecture, Placement> bt = getCriterion(BrokenTimePatterns.class);
282
283 ret.put("Useless half-hours", getPercRev(uh.getValue(variables) + bt.getValue(variables), 0, Constants.sPreferenceLevelStronglyDiscouraged * bt.getBounds(variables)[0]) +
284 "% (" + Math.round(uh.getValue(variables)) + " + " + Math.round(bt.getValue(variables)) + ")");
285 return ret;
286 }
287
288 @Override
289 public void addConstraint(Constraint<Lecture, Placement> constraint) {
290 super.addConstraint(constraint);
291 if (constraint instanceof InstructorConstraint) {
292 iInstructorConstraints.add((InstructorConstraint) constraint);
293 } else if (constraint instanceof JenrlConstraint) {
294 iJenrlConstraints.add((JenrlConstraint) constraint);
295 } else if (constraint instanceof RoomConstraint) {
296 iRoomConstraints.add((RoomConstraint) constraint);
297 } else if (constraint instanceof DepartmentSpreadConstraint) {
298 iDepartmentSpreadConstraints.add((DepartmentSpreadConstraint) constraint);
299 } else if (constraint instanceof SpreadConstraint) {
300 iSpreadConstraints.add((SpreadConstraint) constraint);
301 } else if (constraint instanceof ClassLimitConstraint) {
302 iClassLimitConstraints.add((ClassLimitConstraint) constraint);
303 } else if (constraint instanceof GroupConstraint) {
304 iGroupConstraints.add((GroupConstraint) constraint);
305 } else if (constraint instanceof FlexibleConstraint) {
306 iFlexibleConstraints.add((FlexibleConstraint) constraint);
307 }
308 }
309
310 @Override
311 public void removeConstraint(Constraint<Lecture, Placement> constraint) {
312 super.removeConstraint(constraint);
313 if (constraint instanceof InstructorConstraint) {
314 iInstructorConstraints.remove(constraint);
315 } else if (constraint instanceof JenrlConstraint) {
316 iJenrlConstraints.remove(constraint);
317 } else if (constraint instanceof RoomConstraint) {
318 iRoomConstraints.remove(constraint);
319 } else if (constraint instanceof DepartmentSpreadConstraint) {
320 iDepartmentSpreadConstraints.remove(constraint);
321 } else if (constraint instanceof SpreadConstraint) {
322 iSpreadConstraints.remove(constraint);
323 } else if (constraint instanceof ClassLimitConstraint) {
324 iClassLimitConstraints.remove(constraint);
325 } else if (constraint instanceof GroupConstraint) {
326 iGroupConstraints.remove(constraint);
327 } else if (constraint instanceof FlexibleConstraint) {
328 iFlexibleConstraints.remove(constraint);
329 }
330 }
331
332 /** The list of all instructor constraints */
333 public List<InstructorConstraint> getInstructorConstraints() {
334 return iInstructorConstraints;
335 }
336
337 /** The list of all group constraints */
338 public List<GroupConstraint> getGroupConstraints() {
339 return iGroupConstraints;
340 }
341
342 /** The list of all jenrl constraints */
343 public List<JenrlConstraint> getJenrlConstraints() {
344 return iJenrlConstraints;
345 }
346
347 /** The list of all room constraints */
348 public List<RoomConstraint> getRoomConstraints() {
349 return iRoomConstraints;
350 }
351
352 /** The list of all departmental spread constraints */
353 public List<DepartmentSpreadConstraint> getDepartmentSpreadConstraints() {
354 return iDepartmentSpreadConstraints;
355 }
356
357 public List<SpreadConstraint> getSpreadConstraints() {
358 return iSpreadConstraints;
359 }
360
361 public List<ClassLimitConstraint> getClassLimitConstraints() {
362 return iClassLimitConstraints;
363 }
364
365 public List<FlexibleConstraint> getFlexibleConstraints() {
366 return iFlexibleConstraints;
367 }
368
369 @Override
370 public double getTotalValue() {
371 double ret = 0;
372 for (Criterion<Lecture, Placement> criterion: getCriteria())
373 ret += criterion.getWeightedValue();
374 return ret;
375 }
376
377 @Override
378 public double getTotalValue(Collection<Lecture> variables) {
379 double ret = 0;
380 for (Criterion<Lecture, Placement> criterion: getCriteria())
381 ret += criterion.getWeightedValue(variables);
382 return ret;
383 }
384
385 public int getYear() {
386 return iYear;
387 }
388
389 public void setYear(int year) {
390 iYear = year;
391 }
392
393 public Set<Student> getAllStudents() {
394 return iAllStudents;
395 }
396
397 public void addStudent(Student student) {
398 iAllStudents.add(student);
399 }
400
401 public void removeStudent(Student student) {
402 iAllStudents.remove(student);
403 }
404
405 /**
406 * Returns amount of allocated memory.
407 *
408 * @return amount of allocated memory to be written in the log
409 */
410 public static synchronized String getMem() {
411 Runtime rt = Runtime.getRuntime();
412 return sDoubleFormat.format(((double) (rt.totalMemory() - rt.freeMemory())) / 1048576) + "M";
413 }
414
415
416 /**
417 * Returns the set of conflicting variables with this value, if it is
418 * assigned to its variable. Conflicts with constraints that implement
419 * {@link WeakeningConstraint} are ignored.
420 */
421 public Set<Placement> conflictValuesSkipWeakeningConstraints(Placement value) {
422 Set<Placement> conflictValues = new HashSet<Placement>();
423 for (Constraint<Lecture, Placement> constraint : value.variable().hardConstraints()) {
424 if (constraint instanceof WeakeningConstraint) continue;
425 constraint.computeConflicts(value, conflictValues);
426 }
427 for (GlobalConstraint<Lecture, Placement> constraint : globalConstraints()) {
428 if (constraint instanceof WeakeningConstraint) continue;
429 constraint.computeConflicts(value, conflictValues);
430 }
431 return conflictValues;
432 }
433
434 /**
435 * The method creates date patterns (bitsets) which represent the weeks of a
436 * semester.
437 *
438 * @return a list of BitSets which represents the weeks of a semester.
439 */
440 public List<BitSet> getWeeks() {
441 if (iWeeks == null) {
442 String defaultDatePattern = getProperties().getProperty("DatePattern.CustomDatePattern", null);
443 if (defaultDatePattern == null){
444 defaultDatePattern = getProperties().getProperty("DatePattern.Default");
445 }
446 if (defaultDatePattern == null) return null;
447
448 // Create default date pattern
449 BitSet fullTerm = new BitSet(defaultDatePattern.length());
450 for (int i = 0; i < defaultDatePattern.length(); i++) {
451 if (defaultDatePattern.charAt(i) == 49) {
452 fullTerm.set(i);
453 }
454 }
455
456 // Cut date pattern into weeks (every week contains 7 positive bits)
457 iWeeks = new ArrayList<BitSet>();
458 int cnt = 0;
459 for (int i = 0; i < fullTerm.length(); i++) {
460 if (fullTerm.get(i)) {
461 int w = (cnt++) / 7;
462 if (iWeeks.size() == w) {
463 iWeeks.add(new BitSet(fullTerm.length()));
464 }
465 iWeeks.get(w).set(i);
466 }
467 }
468 }
469 return iWeeks;
470 }
471 }