    001package net.sf.cpsolver.coursett.constraint;
    002
    003import java.util.ArrayList;
    004import java.util.Enumeration;
    005import java.util.HashSet;
    006import java.util.Iterator;
    007import java.util.List;
    008import java.util.Set;
    009
    010import net.sf.cpsolver.coursett.Constants;
    011import net.sf.cpsolver.coursett.criteria.SameSubpartBalancingPenalty;
    012import net.sf.cpsolver.coursett.model.Lecture;
    013import net.sf.cpsolver.coursett.model.Placement;
    014import net.sf.cpsolver.ifs.criteria.Criterion;
    015import net.sf.cpsolver.ifs.model.Constraint;
    016import net.sf.cpsolver.ifs.model.WeakeningConstraint;
    017import net.sf.cpsolver.ifs.util.DataProperties;
    018import 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 Tomáš Müller<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
    044public 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}