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    }