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.model.WeakeningConstraint;
017 import 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 Tomas Muller<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
068 public 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 }