001 package net.sf.cpsolver.coursett.constraint;
002
003 import java.util.Enumeration;
004 import java.util.HashSet;
005 import java.util.Iterator;
006 import java.util.Locale;
007 import java.util.Set;
008 import java.util.Vector;
009
010 import net.sf.cpsolver.coursett.Constants;
011 import net.sf.cpsolver.coursett.model.Lecture;
012 import net.sf.cpsolver.coursett.model.Placement;
013 import net.sf.cpsolver.coursett.model.TimeLocation.IntEnumeration;
014 import net.sf.cpsolver.ifs.model.Constraint;
015 import net.sf.cpsolver.ifs.model.Value;
016 import net.sf.cpsolver.ifs.model.Variable;
017 import net.sf.cpsolver.ifs.util.DataProperties;
018 import net.sf.cpsolver.ifs.util.ToolBox;
019
020 /** Spread given set of classes in time as much as possible.
021 * See {@link DepartmentSpreadConstraint} for more details.
022 *
023 * @version
024 * CourseTT 1.1 (University Course Timetabling)<br>
025 * Copyright (C) 2006 Tomáš Müller<br>
026 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
027 * Lazenska 391, 76314 Zlin, Czech Republic<br>
028 * <br>
029 * This library is free software; you can redistribute it and/or
030 * modify it under the terms of the GNU Lesser General Public
031 * License as published by the Free Software Foundation; either
032 * version 2.1 of the License, or (at your option) any later version.
033 * <br><br>
034 * This library is distributed in the hope that it will be useful,
035 * but WITHOUT ANY WARRANTY; without even the implied warranty of
036 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
037 * Lesser General Public License for more details.
038 * <br><br>
039 * You should have received a copy of the GNU Lesser General Public
040 * License along with this library; if not, write to the Free Software
041 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
042 */
043
044 public class SpreadConstraint extends Constraint implements WeakeningConstraint {
045 private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(DepartmentSpreadConstraint.class);
046 private static java.text.DecimalFormat sDoubleFormat = new java.text.DecimalFormat("0.00",new java.text.DecimalFormatSymbols(Locale.US));
047 private static java.text.DecimalFormat sIntFormat = new java.text.DecimalFormat("0",new java.text.DecimalFormatSymbols(Locale.US));
048 private int iMaxCourses[][] = null;
049 private int iCurrentPenalty = 0;
050 private int iMaxAllowedPenalty = 0;
051
052 private boolean iInitialized = false;
053 private int[][] iNrCourses = null;
054 private Vector [][] iCourses = null;
055 private double iSpreadFactor = 1.20;
056 private int iUnassignmentsToWeaken = 250;
057 private long iUnassignment = 0;
058 private String iName = null;
059
060 public static boolean USE_MOST_IMPROVEMENT_ADEPTS = false;
061
062 public SpreadConstraint(String name, double spreadFactor, int unassignmentsToWeaken, boolean interactiveMode) {
063 iName = name;
064 iSpreadFactor = spreadFactor;
065 iUnassignmentsToWeaken = unassignmentsToWeaken;
066 iNrCourses = new int[Constants.SLOTS_PER_DAY_NO_EVENINGS][Constants.NR_DAYS_WEEK];
067 iCourses = new Vector[Constants.SLOTS_PER_DAY_NO_EVENINGS][Constants.NR_DAYS_WEEK];
068 if (interactiveMode)
069 iUnassignmentsToWeaken = 0;
070 for (int i=0;i<iNrCourses.length;i++) {
071 for (int j=0;j<Constants.NR_DAYS_WEEK;j++) {
072 iNrCourses[i][j] = 0;
073 iCourses[i][j]=new Vector(10,5);
074 }
075 }
076 }
077
078 public SpreadConstraint(DataProperties config, String name) {
079 this(
080 name,
081 config.getPropertyDouble("Spread.SpreadFactor",1.20),
082 config.getPropertyInt("Spread.Unassignments2Weaken", 250),
083 config.getPropertyBoolean("General.InteractiveMode", false)
084 );
085 }
086
087 /** Initialize constraint (to be called after all variables are added to this constraint) */
088 public void init() {
089 if (iInitialized) return;
090 double histogramPerDay[][] = new double[Constants.SLOTS_PER_DAY_NO_EVENINGS][Constants.NR_DAYS_WEEK];
091 iMaxCourses = new int[Constants.SLOTS_PER_DAY_NO_EVENINGS][Constants.NR_DAYS_WEEK];
092 for (int i=0;i<Constants.SLOTS_PER_DAY_NO_EVENINGS;i++)
093 for (int j=0;j<Constants.NR_DAYS_WEEK;j++)
094 histogramPerDay[i][j]=0.0;
095 int totalUsedSlots = 0;
096 for (Enumeration e=variables().elements();e.hasMoreElements();) {
097 Lecture lecture = (Lecture)e.nextElement();
098 Placement firstPlacement = (lecture.values().isEmpty()?null:(Placement)lecture.values().firstElement());
099 if (firstPlacement!=null) {
100 totalUsedSlots += firstPlacement.getTimeLocation().getNrSlotsPerMeeting()*firstPlacement.getTimeLocation().getNrMeetings();
101 }
102 for (Enumeration e2=lecture.values().elements();e2.hasMoreElements();) {
103 Placement p = (Placement)e2.nextElement();
104 int firstSlot = p.getTimeLocation().getStartSlot();
105 if (firstSlot>Constants.DAY_SLOTS_LAST) continue;
106 int endSlot = firstSlot+p.getTimeLocation().getNrSlotsPerMeeting()-1;
107 if (endSlot<Constants.DAY_SLOTS_FIRST) continue;
108 for (int i=Math.max(firstSlot,Constants.DAY_SLOTS_FIRST);i<=Math.min(endSlot,Constants.DAY_SLOTS_LAST);i++) {
109 int dayCode = p.getTimeLocation().getDayCode();
110 for (int j=0;j<Constants.NR_DAYS_WEEK;j++) {
111 if ((dayCode & Constants.DAY_CODES[j])!=0) {
112 histogramPerDay[i-Constants.DAY_SLOTS_FIRST][j] += 1.0 / lecture.values().size();
113 }
114 }
115 }
116 }
117 }
118 //System.out.println("Histogram for department "+iDepartment+":");
119 double threshold = iSpreadFactor*((double)totalUsedSlots/(Constants.NR_DAYS_WEEK*Constants.SLOTS_PER_DAY_NO_EVENINGS));
120 //System.out.println("Threshold["+iDepartment+"] = "+threshold);
121 int totalAvailableSlots = 0;
122 for (int i=0;i<Constants.SLOTS_PER_DAY_NO_EVENINGS;i++) {
123 //System.out.println(" "+fmt(i+1)+": "+fmt(histogramPerDay[i]));
124 for (int j=0;j<Constants.NR_DAYS_WEEK;j++) {
125 iMaxCourses[i][j]=(int)(0.999+(histogramPerDay[i][j]<=threshold?iSpreadFactor*histogramPerDay[i][j]:histogramPerDay[i][j]));
126 totalAvailableSlots += iMaxCourses[i][j];
127 }
128 }
129 for (Enumeration e=variables().elements();e.hasMoreElements();) {
130 Lecture lecture = (Lecture)e.nextElement();
131 Placement placement = (Placement)lecture.getAssignment();
132 if (placement==null) continue;
133 int firstSlot = placement.getTimeLocation().getStartSlot();
134 if (firstSlot>Constants.DAY_SLOTS_LAST) continue;
135 int endSlot = firstSlot+placement.getTimeLocation().getNrSlotsPerMeeting()-1;
136 if (endSlot<Constants.DAY_SLOTS_FIRST) continue;
137 for (int i=Math.max(firstSlot,Constants.DAY_SLOTS_FIRST);i<=Math.min(endSlot,Constants.DAY_SLOTS_LAST);i++) {
138 for (int j=0;j<Constants.NR_DAYS_WEEK;j++) {
139 int dayCode = Constants.DAY_CODES[j];
140 if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) {
141 iNrCourses[i-Constants.DAY_SLOTS_FIRST][j]++;
142 iCourses[i-Constants.DAY_SLOTS_FIRST][j].addElement(placement);
143 }
144 }
145 }
146 }
147 iCurrentPenalty = 0;
148 for (int i=0;i<Constants.SLOTS_PER_DAY_NO_EVENINGS;i++) {
149 for (int j=0;j<Constants.NR_DAYS_WEEK;j++) {
150 iCurrentPenalty += Math.max(0,iNrCourses[i][j]-iMaxCourses[i][j]);
151 }
152 }
153 iMaxAllowedPenalty = iCurrentPenalty;
154 //System.out.println("Initial penalty = "+fmt(iMaxAllowedPenalty));
155 iInitialized = true;
156 }
157
158 public Placement getAdept(Placement placement, int[][] nrCourses, Set conflicts) {
159 Placement adept = null;
160 int improvement = 0;
161
162 //take uncommitted placements first
163 for (Enumeration e=variables().elements();e.hasMoreElements();) {
164 Lecture lect = (Lecture)e.nextElement();
165 if (lect.isCommitted()) continue;
166 Placement plac = (Placement)lect.getAssignment();
167 if (plac==null || plac.equals(placement) || placement.variable().equals(plac.variable()) || conflicts.contains(plac)) continue;
168 int imp = getPenaltyIfUnassigned(plac,nrCourses);
169 if (imp==0) continue;
170 if (adept==null || imp>improvement) {
171 adept = plac; improvement = imp;
172 }
173 }
174 if (adept!=null) return adept;
175
176 // no uncommitted placement found -- take committed one
177 for (Enumeration e=variables().elements();e.hasMoreElements();) {
178 Lecture lect = (Lecture)e.nextElement();
179 if (!lect.isCommitted()) continue;
180 Placement plac = (Placement)lect.getAssignment();
181 if (plac==null || plac.equals(placement) || conflicts.contains(plac)) continue;
182 int imp = getPenaltyIfUnassigned(plac,nrCourses);
183 if (imp==0) continue;
184 if (adept==null || imp>improvement) {
185 adept = plac; improvement = imp;
186 }
187 }
188
189 return adept;
190 }
191
192 private Set[] getAdepts(Placement placement, int[][] nrCourses, Set conflicts) {
193 int firstSlot = placement.getTimeLocation().getStartSlot();
194 if (firstSlot>Constants.DAY_SLOTS_LAST) return null;
195 int endSlot = firstSlot+placement.getTimeLocation().getNrSlotsPerMeeting()-1;
196 if (endSlot<Constants.DAY_SLOTS_FIRST) return null;
197 HashSet adepts[] = new HashSet[] {new HashSet(),new HashSet()};
198 for (int i=Math.max(firstSlot,Constants.DAY_SLOTS_FIRST);i<=Math.min(endSlot,Constants.DAY_SLOTS_LAST);i++) {
199 for (int j=0;j<Constants.NR_DAYS_WEEK;j++) {
200 int dayCode = Constants.DAY_CODES[j];
201 if ((dayCode & placement.getTimeLocation().getDayCode()) != 0 && nrCourses[i-Constants.DAY_SLOTS_FIRST][j]>=iMaxCourses[i-Constants.DAY_SLOTS_FIRST][j]) {
202 for (Enumeration e=iCourses[i-Constants.DAY_SLOTS_FIRST][j].elements();e.hasMoreElements();) {
203 Placement p = (Placement)e.nextElement();
204 if (conflicts.contains(p)) continue;
205 if (p.equals(placement)) continue;
206 if (p.variable().equals(placement.variable())) continue;
207 adepts[((Lecture)p.variable()).isCommitted()?1:0].add(p);
208 }
209 }
210 }
211 }
212 return adepts;
213 //sLogger.debug(" -- adept "+adept+" selected, penalty will be decreased by "+improvement);
214 }
215
216 private int getPenaltyIfUnassigned(Placement placement, int[][] nrCourses) {
217 int firstSlot = placement.getTimeLocation().getStartSlot();
218 if (firstSlot>Constants.DAY_SLOTS_LAST) return 0;
219 int endSlot = firstSlot+placement.getTimeLocation().getNrSlotsPerMeeting()-1;
220 if (endSlot<Constants.DAY_SLOTS_FIRST) return 0;
221 int penalty = 0;
222 for (int i=Math.max(firstSlot,Constants.DAY_SLOTS_FIRST);i<=Math.min(endSlot,Constants.DAY_SLOTS_LAST);i++) {
223 for (int j=0;j<Constants.NR_DAYS_WEEK;j++) {
224 int dayCode = Constants.DAY_CODES[j];
225 if ((dayCode & placement.getTimeLocation().getDayCode()) != 0 &&
226 nrCourses[i-Constants.DAY_SLOTS_FIRST][j]>iMaxCourses[i-Constants.DAY_SLOTS_FIRST][j]) penalty ++;
227 }
228 }
229 return penalty;
230 }
231
232 private int tryUnassign(Placement placement, int[][] nrCourses) {
233 //sLogger.debug(" -- trying to unassign "+placement);
234 int firstSlot = placement.getTimeLocation().getStartSlot();
235 if (firstSlot>Constants.DAY_SLOTS_LAST) return 0;
236 int endSlot = firstSlot+placement.getTimeLocation().getNrSlotsPerMeeting()-1;
237 if (endSlot<Constants.DAY_SLOTS_FIRST) return 0;
238 int improvement = 0;
239 for (int i=Math.max(firstSlot,Constants.DAY_SLOTS_FIRST);i<=Math.min(endSlot,Constants.DAY_SLOTS_LAST);i++) {
240 for (int j=0;j<Constants.NR_DAYS_WEEK;j++) {
241 int dayCode = Constants.DAY_CODES[j];
242 if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) {
243 if (nrCourses[i-Constants.DAY_SLOTS_FIRST][j]>iMaxCourses[i-Constants.DAY_SLOTS_FIRST][j]) improvement++;
244 nrCourses[i-Constants.DAY_SLOTS_FIRST][j]--;
245 }
246 }
247 }
248 //sLogger.debug(" -- penalty is decreased by "+improvement);
249 return improvement;
250 }
251
252 private int tryAssign(Placement placement, int[][] nrCourses) {
253 //sLogger.debug(" -- trying to assign "+placement);
254 int firstSlot = placement.getTimeLocation().getStartSlot();
255 if (firstSlot>Constants.DAY_SLOTS_LAST) return 0;
256 int endSlot = firstSlot+placement.getTimeLocation().getNrSlotsPerMeeting()-1;
257 if (endSlot<Constants.DAY_SLOTS_FIRST) return 0;
258 int penalty = 0;
259 for (int i=Math.max(firstSlot,Constants.DAY_SLOTS_FIRST);i<=Math.min(endSlot,Constants.DAY_SLOTS_LAST);i++) {
260 for (int j=0;j<Constants.NR_DAYS_WEEK;j++) {
261 int dayCode = Constants.DAY_CODES[j];
262 if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) {
263 nrCourses[i-Constants.DAY_SLOTS_FIRST][j]++;
264 if (nrCourses[i-Constants.DAY_SLOTS_FIRST][j]>iMaxCourses[i-Constants.DAY_SLOTS_FIRST][j]) penalty++;
265 }
266 }
267 }
268 //sLogger.debug(" -- penalty is incremented by "+penalty);
269 return penalty;
270 }
271
272 public void computeConflicts(Value value, Set conflicts) {
273 if (!iInitialized || iUnassignmentsToWeaken==0) return;
274 Placement placement = (Placement)value;
275 int penalty = iCurrentPenalty + getPenalty(placement);
276 if (penalty<=iMaxAllowedPenalty) return;
277 int firstSlot = placement.getTimeLocation().getStartSlot();
278 if (firstSlot>Constants.DAY_SLOTS_LAST) return;
279 int endSlot = firstSlot+placement.getTimeLocation().getNrSlotsPerMeeting()-1;
280 if (endSlot<Constants.DAY_SLOTS_FIRST) return;
281 //sLogger.debug("-- computing conflict for value "+value+" ... (penalty="+iCurrentPenalty+", penalty with the value="+penalty+", max="+iMaxAllowedPenalty+")");
282 int[][] nrCourses = new int[iNrCourses.length][Constants.NR_DAYS_WEEK];
283 for (int i=0;i<iNrCourses.length;i++)
284 for (int j=0;j<Constants.NR_DAYS_WEEK;j++)
285 nrCourses[i][j] = iNrCourses[i][j];
286 tryAssign(placement, nrCourses);
287 //sLogger.debug(" -- nrCurses="+fmt(nrCourses));
288 for (Enumeration e=variables().elements();e.hasMoreElements();) {
289 Lecture lect = (Lecture)e.nextElement();
290 if (conflicts.contains(lect)) {
291 penalty -= tryUnassign((Placement)lect.getAssignment(), nrCourses);
292 }
293 if (penalty<=iMaxAllowedPenalty) return;
294 }
295 if (USE_MOST_IMPROVEMENT_ADEPTS) {
296 while (penalty>iMaxAllowedPenalty) {
297 Placement plac = getAdept(placement, nrCourses, conflicts);
298 if (plac==null) break;
299 conflicts.add(plac);
300 penalty -= tryUnassign(plac, nrCourses);
301 }
302 } else {
303 if (penalty>iMaxAllowedPenalty) {
304 Set adepts[] = getAdepts(placement, nrCourses, conflicts);
305 for (int i=0;penalty>iMaxAllowedPenalty && i<adepts.length;i++) {
306 while (!adepts[i].isEmpty() && penalty>iMaxAllowedPenalty) {
307 Placement plac = (Placement)ToolBox.random(adepts[i]);
308 adepts[i].remove(plac);
309 conflicts.add(plac);
310 //sLogger.debug(" -- conflict "+lect.getAssignment()+" added");
311 penalty -= tryUnassign(plac, nrCourses);
312 }
313 }
314 }
315 }
316 }
317
318 public boolean inConflict(Value value) {
319 if (!iInitialized || iUnassignmentsToWeaken==0) return false;
320 Placement placement = (Placement)value;
321 return getPenalty(placement)+iCurrentPenalty>iMaxAllowedPenalty;
322 }
323
324 public boolean isConsistent(Value value1, Value value2) {
325 if (!iInitialized || iUnassignmentsToWeaken==0) return true;
326 Placement p1 = (Placement)value1;
327 Placement p2 = (Placement)value2;
328 if (!p1.getTimeLocation().hasIntersection(p2.getTimeLocation())) return true;
329 int firstSlot = Math.max(p1.getTimeLocation().getStartSlot(),p2.getTimeLocation().getStartSlot());
330 if (firstSlot>Constants.DAY_SLOTS_LAST) return true;
331 int endSlot = Math.min(p1.getTimeLocation().getStartSlot()+p1.getTimeLocation().getNrSlotsPerMeeting()-1,p2.getTimeLocation().getStartSlot()+p2.getTimeLocation().getNrSlotsPerMeeting()-1);
332 if (endSlot<Constants.DAY_SLOTS_FIRST) return true;
333 int penalty = 0;
334 for (int i=Math.max(firstSlot,Constants.DAY_SLOTS_FIRST);i<=Math.min(endSlot,Constants.DAY_SLOTS_LAST);i++) {
335 for (int j=0;j<Constants.NR_DAYS_WEEK;j++) {
336 int dayCode = Constants.DAY_CODES[j];
337 if ((dayCode & p1.getTimeLocation().getDayCode()) != 0 && (dayCode & p2.getTimeLocation().getDayCode()) != 0) {
338 penalty += Math.max(0,2-iMaxCourses[i-Constants.DAY_SLOTS_FIRST][j]);
339 }
340 }
341 }
342 return (penalty<iMaxAllowedPenalty);
343 }
344
345 public void weaken() {
346 if (!iInitialized || iUnassignmentsToWeaken==0) return;
347 iUnassignment ++;
348 if (iUnassignment%iUnassignmentsToWeaken==0)
349 iMaxAllowedPenalty ++;
350 }
351
352 public void assigned(long iteration, Value value) {
353 super.assigned(iteration, value);
354 if (!iInitialized) return;
355 Placement placement = (Placement)value;
356 int firstSlot = placement.getTimeLocation().getStartSlot();
357 if (firstSlot>Constants.DAY_SLOTS_LAST) return;
358 int endSlot = firstSlot+placement.getTimeLocation().getNrSlotsPerMeeting()-1;
359 if (endSlot<Constants.DAY_SLOTS_FIRST) return;
360 for (int i=Math.max(firstSlot,Constants.DAY_SLOTS_FIRST);i<=Math.min(endSlot,Constants.DAY_SLOTS_LAST);i++) {
361 for (int j=0;j<Constants.NR_DAYS_WEEK;j++) {
362 int dayCode = Constants.DAY_CODES[j];
363 if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) {
364 iNrCourses[i-Constants.DAY_SLOTS_FIRST][j]++;
365 if (iNrCourses[i-Constants.DAY_SLOTS_FIRST][j]>iMaxCourses[i-Constants.DAY_SLOTS_FIRST][j]) iCurrentPenalty++;
366 iCourses[i-Constants.DAY_SLOTS_FIRST][j].addElement(value);
367 }
368 }
369 }
370 }
371
372 public void unassigned(long iteration, Value value) {
373 super.unassigned(iteration, value);
374 if (!iInitialized) return;
375 Placement placement = (Placement)value;
376 int firstSlot = placement.getTimeLocation().getStartSlot();
377 if (firstSlot>Constants.DAY_SLOTS_LAST) return;
378 int endSlot = firstSlot+placement.getTimeLocation().getNrSlotsPerMeeting()-1;
379 if (endSlot<Constants.DAY_SLOTS_FIRST) return;
380 for (int i=Math.max(firstSlot,Constants.DAY_SLOTS_FIRST);i<=Math.min(endSlot,Constants.DAY_SLOTS_LAST);i++) {
381 for (int j=0;j<Constants.NR_DAYS_WEEK;j++) {
382 int dayCode = Constants.DAY_CODES[j];
383 if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) {
384 if (iNrCourses[i-Constants.DAY_SLOTS_FIRST][j]>iMaxCourses[i-Constants.DAY_SLOTS_FIRST][j]) iCurrentPenalty--;
385 iNrCourses[i-Constants.DAY_SLOTS_FIRST][j]--;
386 iCourses[i-Constants.DAY_SLOTS_FIRST][j].removeElement(value);
387 }
388 }
389 }
390 }
391
392 public String getName() { return iName; }
393
394 public String toString() {
395 StringBuffer sb = new StringBuffer();
396 sb.append("Time Spread between ");
397 for (Enumeration e=variables().elements();e.hasMoreElements();) {
398 Variable v = (Variable)e.nextElement();
399 sb.append(v.getName());
400 if (e.hasMoreElements()) sb.append(", ");
401 }
402 return sb.toString();
403 }
404
405 /** Department balancing penalty for this department */
406 public int getPenalty() {
407 if (!iInitialized) return getPenaltyEstimate();
408 return iCurrentPenalty;
409 }
410
411 public int getPenaltyEstimate() {
412 double histogramPerDay[][] = new double[Constants.SLOTS_PER_DAY_NO_EVENINGS][Constants.NR_DAYS_WEEK];
413 int maxCourses[][] = new int[Constants.SLOTS_PER_DAY_NO_EVENINGS][Constants.NR_DAYS_WEEK];
414 int nrCourses[][] = new int[Constants.SLOTS_PER_DAY_NO_EVENINGS][Constants.NR_DAYS_WEEK];
415 for (int i=0;i<Constants.SLOTS_PER_DAY_NO_EVENINGS;i++)
416 for (int j=0;j<Constants.NR_DAYS_WEEK;j++)
417 histogramPerDay[i][j]=0.0;
418 int totalUsedSlots = 0;
419 for (Enumeration e=variables().elements();e.hasMoreElements();) {
420 Lecture lecture = (Lecture)e.nextElement();
421 Placement firstPlacement = (lecture.values().isEmpty()?null:(Placement)lecture.values().firstElement());
422 if (firstPlacement!=null) {
423 totalUsedSlots += firstPlacement.getTimeLocation().getNrSlotsPerMeeting()*firstPlacement.getTimeLocation().getNrMeetings();
424 }
425 for (Enumeration e2=lecture.values().elements();e2.hasMoreElements();) {
426 Placement p = (Placement)e2.nextElement();
427 int firstSlot = p.getTimeLocation().getStartSlot();
428 if (firstSlot>Constants.DAY_SLOTS_LAST) continue;
429 int endSlot = firstSlot+p.getTimeLocation().getNrSlotsPerMeeting()-1;
430 if (endSlot<Constants.DAY_SLOTS_FIRST) continue;
431 for (int i=Math.max(firstSlot,Constants.DAY_SLOTS_FIRST);i<=Math.min(endSlot,Constants.DAY_SLOTS_LAST);i++) {
432 int dayCode = p.getTimeLocation().getDayCode();
433 for (int j=0;j<Constants.NR_DAYS_WEEK;j++) {
434 if ((dayCode & Constants.DAY_CODES[j])!=0) {
435 histogramPerDay[i-Constants.DAY_SLOTS_FIRST][j] += 1.0 / lecture.values().size();
436 }
437 }
438 }
439 }
440 }
441 double threshold = iSpreadFactor*((double)totalUsedSlots/(Constants.NR_DAYS_WEEK*Constants.SLOTS_PER_DAY_NO_EVENINGS));
442 for (int i=0;i<Constants.SLOTS_PER_DAY_NO_EVENINGS;i++) {
443 for (int j=0;j<Constants.NR_DAYS_WEEK;j++) {
444 nrCourses[i][j]=0;
445 maxCourses[i][j]=(int)(0.999+(histogramPerDay[i][j]<=threshold?iSpreadFactor*histogramPerDay[i][j]:histogramPerDay[i][j]));
446 }
447 }
448 int currentPenalty = 0;
449 for (Enumeration e=variables().elements();e.hasMoreElements();) {
450 Lecture lecture = (Lecture)e.nextElement();
451 Placement placement = (Placement)lecture.getAssignment();
452 if (placement==null) continue;
453 int firstSlot = placement.getTimeLocation().getStartSlot();
454 if (firstSlot>Constants.DAY_SLOTS_LAST) continue;
455 int endSlot = firstSlot+placement.getTimeLocation().getNrSlotsPerMeeting()-1;
456 if (endSlot<Constants.DAY_SLOTS_FIRST) continue;
457 for (int i=Math.max(firstSlot,Constants.DAY_SLOTS_FIRST);i<=Math.min(endSlot,Constants.DAY_SLOTS_LAST);i++) {
458 for (int j=0;j<Constants.NR_DAYS_WEEK;j++) {
459 int dayCode = Constants.DAY_CODES[j];
460 if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) {
461 nrCourses[i-Constants.DAY_SLOTS_FIRST][j]++;
462 }
463 }
464 }
465 }
466 for (int i=0;i<Constants.SLOTS_PER_DAY_NO_EVENINGS;i++) {
467 for (int j=0;j<Constants.NR_DAYS_WEEK;j++) {
468 currentPenalty += Math.max(0,nrCourses[i][j]-maxCourses[i][j]);
469 }
470 }
471 iMaxAllowedPenalty = Math.max(iMaxAllowedPenalty,currentPenalty);
472 return currentPenalty;
473 }
474
475 public int getMaxPenalty(Placement placement) {
476 int penalty = 0;
477 for (IntEnumeration e=placement.getTimeLocation().getSlots();e.hasMoreElements();) {
478 int slot = e.nextInt();
479 int day = slot/Constants.SLOTS_PER_DAY;
480 int time = slot%Constants.SLOTS_PER_DAY;
481 if (time<Constants.DAY_SLOTS_FIRST || time>Constants.DAY_SLOTS_LAST) continue;
482 if (day>=Constants.NR_DAYS_WEEK) continue;
483 int dif = iNrCourses[time-Constants.DAY_SLOTS_FIRST][day]-iMaxCourses[time-Constants.DAY_SLOTS_FIRST][day];
484 if (dif>penalty) penalty = dif;
485 }
486 return penalty;
487 }
488
489 /** Department balancing penalty of the given placement */
490 public int getPenalty(Placement placement) {
491 if (!iInitialized) return 0;
492 int firstSlot = placement.getTimeLocation().getStartSlot();
493 if (firstSlot>Constants.DAY_SLOTS_LAST) return 0;
494 Placement initialPlacement = (Placement)placement.variable().getAssignment();
495 int endSlot = firstSlot+placement.getTimeLocation().getNrSlotsPerMeeting()-1;
496 if (endSlot<Constants.DAY_SLOTS_FIRST) return 0;
497 int penalty = 0;
498 int min = Math.max(firstSlot,Constants.DAY_SLOTS_FIRST);
499 int max = Math.min(endSlot,Constants.DAY_SLOTS_LAST);
500 for (int j=0;j<Constants.NR_DAYS_WEEK;j++) {
501 int dayCode = Constants.DAY_CODES[j];
502 if ((dayCode & placement.getTimeLocation().getDayCode()) == 0) continue;
503 for (int i=min;i<=max;i++) {
504 if (iNrCourses[i-Constants.DAY_SLOTS_FIRST][j]>=iMaxCourses[i-Constants.DAY_SLOTS_FIRST][j]+(initialPlacement==null?0:iCourses[i-Constants.DAY_SLOTS_FIRST][j].contains(initialPlacement)?1:0))
505 penalty ++;
506 }
507 }
508 return penalty;
509 }
510
511 private String fmt(double value) {
512 return sDoubleFormat.format(value);
513 }
514
515 private String fmt(double[] values) {
516 if (values==null) return null;
517 StringBuffer sb = new StringBuffer("[");
518 for (int i=0;i<Math.min(5,values.length);i++)
519 sb.append(i==0?"":",").append(sDoubleFormat.format(values[i]));
520 sb.append("]");
521 return sb.toString();
522 }
523
524 private String fmt(double[][] values) {
525 if (values==null) return null;
526 StringBuffer sb = new StringBuffer("[");
527 for (int i=0;i<values.length;i++) {
528 sb.append(i==0?"":",").append(fmt(values[i]));
529 }
530 sb.append("]");
531 return sb.toString();
532 }
533
534 private String fmt(int value) {
535 return sIntFormat.format(value);
536 }
537
538 private String fmt(int[] values) {
539 if (values==null) return null;
540 StringBuffer sb = new StringBuffer("[");
541 for (int i=0;i<Math.min(5,values.length);i++)
542 sb.append(i==0?"":",").append(sIntFormat.format(values[i]));
543 sb.append("]");
544 return sb.toString();
545 }
546
547 private String fmt(int[][] values) {
548 if (values==null) return null;
549 StringBuffer sb = new StringBuffer("[");
550 for (int i=0;i<values.length;i++) {
551 sb.append(i==0?"":",").append(fmt(values[i]));
552 }
553 sb.append("]");
554 return sb.toString();
555 }
556
557 public int[][] getMaxCourses() { return iMaxCourses; }
558 public int[][] getNrCourses() { return iNrCourses; }
559 public Vector[][] getCourses() { return iCourses; }
560
561 public void addVariable(Variable variable) {
562 Lecture lecture = (Lecture)variable;
563 if (lecture.canShareRoom()) {
564 for (Iterator i=lecture.groupConstraints().iterator();i.hasNext();) {
565 GroupConstraint gc = (GroupConstraint)i.next();
566 if (gc.getType()==GroupConstraint.TYPE_MEET_WITH) {
567 if (gc.variables().indexOf(lecture)>0) return;
568 }
569 }
570 }
571 super.addVariable(variable);
572 }
573 }