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