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