001package net.sf.cpsolver.coursett.constraint; 002 003import java.util.ArrayList; 004import java.util.Collections; 005import java.util.Comparator; 006import java.util.HashSet; 007import java.util.Iterator; 008import java.util.List; 009import java.util.Set; 010 011import net.sf.cpsolver.coursett.Constants; 012import net.sf.cpsolver.coursett.model.Lecture; 013import net.sf.cpsolver.coursett.model.Placement; 014import net.sf.cpsolver.coursett.model.TimeLocation; 015import net.sf.cpsolver.ifs.model.Constraint; 016import net.sf.cpsolver.ifs.model.WeakeningConstraint; 017import net.sf.cpsolver.ifs.util.DataProperties; 018 019/** 020 * Minimize number of used groups of time within a set of classes. <br> 021 * <br> 022 * 023 * This constraint implements the following distribution/group constraints: <br> 024 * <br> 025 * 026 * MIN_GRUSE(10x1h) (Minimize Use Of 1h Groups)<br> 027 * Minimize number of groups of time that are used by the given classes. The 028 * time is spread into the following 10 groups of one hour: 7:30a-8:30a, 029 * 8:30a-9:30a, 9:30a-10:30a, ... 4:30p-5:30p. <br> 030 * <br> 031 * 032 * MIN_GRUSE(5x2h) (Minimize Use Of 2h Groups)<br> 033 * Minimize number of groups of time that are used by the given classes. The 034 * time is spread into the following 5 groups of two hours: 7:30a-9:30a, 035 * 9:30a-11:30a, 11:30a-1:30p, 1:30p-3:30p, 3:30p-5:30p. <br> 036 * <br> 037 * 038 * MIN_GRUSE(3x3h) (Minimize Use Of 3h Groups)<br> 039 * Minimize number of groups of time that are used by the given classes. The 040 * time is spread into the following 3 groups: 7:30a-10:30a, 10:30a-2:30p, 041 * 2:30p-5:30p. <br> 042 * <br> 043 * 044 * MIN_GRUSE(2x5h) (Minimize Use Of 5h Groups)<br> 045 * Minimize number of groups of time that are used by the given classes. The 046 * time is spread into the following 2 groups: 7:30a-12:30a, 12:30a-5:30p. 047 * 048 * @version CourseTT 1.2 (University Course Timetabling)<br> 049 * Copyright (C) 2006 - 2010 Tomáš Müller<br> 050 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 051 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 052 * <br> 053 * This library is free software; you can redistribute it and/or modify 054 * it under the terms of the GNU Lesser General Public License as 055 * published by the Free Software Foundation; either version 3 of the 056 * License, or (at your option) any later version. <br> 057 * <br> 058 * This library is distributed in the hope that it will be useful, but 059 * WITHOUT ANY WARRANTY; without even the implied warranty of 060 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 061 * Lesser General Public License for more details. <br> 062 * <br> 063 * You should have received a copy of the GNU Lesser General Public 064 * License along with this library; if not see 065 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 066 */ 067 068public class MinimizeNumberOfUsedGroupsOfTime extends Constraint<Lecture, Placement> implements WeakeningConstraint<Lecture, Placement> { 069 private int iUnassignmentsToWeaken = 250; 070 private long iUnassignment = 0; 071 private int iLimit = 1; 072 private GroupOfTime iGroupsOfTime[]; 073 private HashSet<Placement> iUsage[]; 074 private boolean iEnabled = false; 075 076 private String iName = null; 077 078 public static GroupOfTime[] sGroups2of5h = new GroupOfTime[] { 079 new GroupOfTime(Constants.time2slot(7, 30), Constants.time2slot(12, 30), Constants.DAY_CODE_ALL), 080 new GroupOfTime(Constants.time2slot(12, 30), Constants.time2slot(17, 30), Constants.DAY_CODE_ALL), }; 081 public static GroupOfTime[] sGroups3of3h = new GroupOfTime[] { 082 new GroupOfTime(Constants.time2slot(7, 30), Constants.time2slot(10, 30), Constants.DAY_CODE_ALL), 083 new GroupOfTime(Constants.time2slot(10, 30), Constants.time2slot(14, 30), Constants.DAY_CODE_ALL), 084 new GroupOfTime(Constants.time2slot(14, 30), Constants.time2slot(17, 30), Constants.DAY_CODE_ALL) }; 085 public static GroupOfTime[] sGroups5of2h = new GroupOfTime[] { 086 new GroupOfTime(Constants.time2slot(7, 30), Constants.time2slot(9, 30), Constants.DAY_CODE_ALL), 087 new GroupOfTime(Constants.time2slot(9, 30), Constants.time2slot(11, 30), Constants.DAY_CODE_ALL), 088 new GroupOfTime(Constants.time2slot(11, 30), Constants.time2slot(13, 30), Constants.DAY_CODE_ALL), 089 new GroupOfTime(Constants.time2slot(13, 30), Constants.time2slot(15, 30), Constants.DAY_CODE_ALL), 090 new GroupOfTime(Constants.time2slot(15, 30), Constants.time2slot(17, 30), Constants.DAY_CODE_ALL) }; 091 public static GroupOfTime[] sGroups10of1h = new GroupOfTime[] { 092 new GroupOfTime(Constants.time2slot(7, 30), Constants.time2slot(8, 30), Constants.DAY_CODE_ALL), 093 new GroupOfTime(Constants.time2slot(8, 30), Constants.time2slot(9, 30), Constants.DAY_CODE_ALL), 094 new GroupOfTime(Constants.time2slot(9, 30), Constants.time2slot(10, 30), Constants.DAY_CODE_ALL), 095 new GroupOfTime(Constants.time2slot(10, 30), Constants.time2slot(11, 30), Constants.DAY_CODE_ALL), 096 new GroupOfTime(Constants.time2slot(11, 30), Constants.time2slot(12, 30), Constants.DAY_CODE_ALL), 097 new GroupOfTime(Constants.time2slot(12, 30), Constants.time2slot(13, 30), Constants.DAY_CODE_ALL), 098 new GroupOfTime(Constants.time2slot(13, 30), Constants.time2slot(14, 30), Constants.DAY_CODE_ALL), 099 new GroupOfTime(Constants.time2slot(14, 30), Constants.time2slot(15, 30), Constants.DAY_CODE_ALL), 100 new GroupOfTime(Constants.time2slot(15, 30), Constants.time2slot(16, 30), Constants.DAY_CODE_ALL), 101 new GroupOfTime(Constants.time2slot(16, 30), Constants.time2slot(17, 30), Constants.DAY_CODE_ALL) }; 102 103 @SuppressWarnings("unchecked") 104 public MinimizeNumberOfUsedGroupsOfTime(DataProperties config, String name, GroupOfTime[] groupsOfTime) { 105 iGroupsOfTime = groupsOfTime; 106 iUnassignmentsToWeaken = config.getPropertyInt("MinimizeNumberOfUsedGroupsOfTime.Unassignments2Weaken", 107 iUnassignmentsToWeaken); 108 iName = name; 109 iUsage = new HashSet[iGroupsOfTime.length]; 110 for (int i = 0; i < iUsage.length; i++) 111 iUsage[i] = new HashSet<Placement>(); 112 } 113 114 public int currentUsage() { 115 int ret = 0; 116 for (int i = 0; i < iUsage.length; i++) 117 if (!iUsage[i].isEmpty()) 118 ret++; 119 return ret; 120 } 121 122 @Override 123 public void weaken() { 124 iUnassignment++; 125 if (iUnassignmentsToWeaken > 0 && iUnassignment % iUnassignmentsToWeaken == 0) 126 iLimit++; 127 } 128 129 public boolean isOverLimit(Placement placement) { 130 return getOverLimit(placement) > 0; 131 } 132 133 public int getOverLimit(Placement placement) { 134 if (!iEnabled) 135 return 0; // not enabled 136 if (iUnassignmentsToWeaken == 0) 137 return 0; // not working 138 139 Lecture lecture = placement.variable(); 140 TimeLocation time = placement.getTimeLocation(); 141 142 if (lecture.isCommitted()) 143 return 0; // commited class 144 145 int usage = 0; 146 for (int i = 0; i < iGroupsOfTime.length; i++) { 147 GroupOfTime groupOfTime = iGroupsOfTime[i]; 148 if (!iUsage[i].isEmpty() || groupOfTime.overlap(time)) 149 usage++; 150 } 151 152 return usage - iLimit; 153 } 154 155 public int estimateLimit() { 156 int nrSlotsUsed = 0; 157 int minSlotsUsed = 0; 158 boolean firstLecture = true; 159 for (Lecture lecture : variables()) { 160 boolean first = true; 161 int minSlotsUsedThisLecture = 0; 162 for (TimeLocation time : lecture.timeLocations()) { 163 int min = 0; 164 for (int i = 0; i < iGroupsOfTime.length; i++) { 165 if (iGroupsOfTime[i].overlap(time)) 166 min++; 167 } 168 if (first) { 169 nrSlotsUsed += time.getLength() * time.getNrMeetings(); 170 minSlotsUsedThisLecture = min; 171 first = false; 172 } else { 173 minSlotsUsedThisLecture = Math.min(minSlotsUsedThisLecture, min); 174 } 175 } 176 if (firstLecture) { 177 minSlotsUsed = minSlotsUsedThisLecture; 178 firstLecture = false; 179 } else { 180 minSlotsUsed = Math.min(minSlotsUsed, minSlotsUsedThisLecture); 181 } 182 } 183 return Math.max(Math.max(1, (int) Math.ceil(((double) nrSlotsUsed) / iGroupsOfTime[0].size())), minSlotsUsed); 184 } 185 186 @Override 187 public void computeConflicts(Placement placement, Set<Placement> conflicts) { 188 int overLimit = getOverLimit(placement); 189 if (overLimit > 0) { 190 TimeLocation time = placement.getTimeLocation(); 191 192 List<List<Placement>> adepts = new ArrayList<List<Placement>>(); 193 for (int i = 0; i < iGroupsOfTime.length; i++) { 194 GroupOfTime groupOfTime = iGroupsOfTime[i]; 195 HashSet<Placement> usage = iUsage[i]; 196 if (groupOfTime.overlap(time) || usage.isEmpty()) 197 continue; 198 boolean canUnassign = true; 199 List<Placement> placementsToUnassign = new ArrayList<Placement>(usage.size()); 200 for (Placement p : usage) { 201 Lecture l = p.variable(); 202 if (l.isCommitted()) { 203 canUnassign = false; 204 break; 205 } 206 if (!conflicts.contains(p)) 207 placementsToUnassign.add(p); 208 } 209 if (!canUnassign) 210 continue; 211 adepts.add(placementsToUnassign); 212 } 213 if (adepts.size() < overLimit) { 214 conflicts.add(placement); 215 } else { 216 Collections.sort(adepts, new Comparator<List<Placement>>() { 217 @Override 218 public int compare(List<Placement> c1, List<Placement> c2) { 219 return Double.compare(c1.size(), c2.size()); 220 } 221 }); 222 for (int i = 0; i < overLimit; i++) { 223 conflicts.addAll(adepts.get(i)); 224 } 225 } 226 } 227 } 228 229 @Override 230 public boolean inConflict(Placement placement) { 231 return isOverLimit(placement); 232 } 233 234 @Override 235 public boolean isConsistent(Placement value1, Placement value2) { 236 return (isOverLimit(value1) || isOverLimit(value2)); 237 } 238 239 @Override 240 public void assigned(long iteration, Placement placement) { 241 super.assigned(iteration, placement); 242 TimeLocation time = placement.getTimeLocation(); 243 for (int i = 0; i < iGroupsOfTime.length; i++) { 244 GroupOfTime groupOfTime = iGroupsOfTime[i]; 245 HashSet<Placement> usage = iUsage[i]; 246 if (groupOfTime.overlap(time)) 247 usage.add(placement); 248 } 249 } 250 251 @Override 252 public void unassigned(long iteration, Placement placement) { 253 super.unassigned(iteration, placement); 254 TimeLocation time = placement.getTimeLocation(); 255 for (int i = 0; i < iGroupsOfTime.length; i++) { 256 GroupOfTime groupOfTime = iGroupsOfTime[i]; 257 HashSet<Placement> usage = iUsage[i]; 258 if (groupOfTime.overlap(time)) 259 usage.remove(placement); 260 } 261 } 262 263 public String getConstraintName() { 264 return "MIN_GRUSE(" + iName + ")"; 265 } 266 267 @Override 268 public String getName() { 269 return "Minimize number of used groups of time (" + iName + ")"; 270 } 271 272 public void setEnabled(boolean enabled) { 273 iEnabled = enabled; 274 iLimit = Math.max(currentUsage(), estimateLimit()); 275 } 276 277 public boolean isEnabled() { 278 return iEnabled; 279 } 280 281 private static class GroupOfTime { 282 private int iStartSlot = 0; 283 private int iEndSlot = 0; 284 private int iDays = 0; 285 286 public GroupOfTime(int startSlot, int endSlot, int days) { 287 iStartSlot = startSlot; 288 iEndSlot = endSlot; 289 iDays = days; 290 } 291 292 public int getStartSlot() { 293 return iStartSlot; 294 } 295 296 public int getEndSlot() { 297 return iEndSlot; 298 } 299 300 public int getDays() { 301 return iDays; 302 } 303 304 public int nrDays() { 305 int ret = 0; 306 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 307 if ((getDays() & Constants.DAY_CODES[i]) != 0) 308 ret++; 309 } 310 return ret; 311 } 312 313 public int size() { 314 return (getEndSlot() - getStartSlot()) * nrDays(); 315 } 316 317 public boolean overlap(TimeLocation timeLocation) { 318 if ((timeLocation.getDayCode() & iDays) == 0) 319 return false; 320 int end = Math.min(iEndSlot, timeLocation.getStartSlot() + timeLocation.getLength()); 321 int start = Math.max(iStartSlot, timeLocation.getStartSlot()); 322 int nrSharedSlots = (end < start ? 0 : end - start); 323 return (nrSharedSlots > 0); 324 } 325 } 326 327 @Override 328 public String toString() { 329 StringBuffer sb = new StringBuffer(); 330 sb.append("Minimize Use Of " 331 + (Constants.SLOT_LENGTH_MIN * (iGroupsOfTime[0].getEndSlot() - iGroupsOfTime[0].getStartSlot())) 332 + "min Groups between "); 333 for (Iterator<Lecture> e = variables().iterator(); e.hasNext();) { 334 Lecture v = e.next(); 335 sb.append(v.getName()); 336 if (e.hasNext()) 337 sb.append(", "); 338 } 339 return sb.toString(); 340 } 341 342 @Override 343 public void weaken(Placement value) { 344 if (isOverLimit(value)) 345 iLimit += getOverLimit(value); 346 } 347 348}