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