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