    001package org.cpsolver.coursett.criteria.additional;
    002
    003import java.util.BitSet;
    004import java.util.Collection;
    005import java.util.HashMap;
    006import java.util.HashSet;
    007import java.util.List;
    008import java.util.Map;
    009import java.util.Set;
    010import java.util.TreeSet;
    011
    012import org.cpsolver.coursett.Constants;
    013import org.cpsolver.coursett.constraint.InstructorConstraint;
    014import org.cpsolver.coursett.constraint.InstructorConstraint.InstructorConstraintContext;
    015import org.cpsolver.coursett.criteria.TimetablingCriterion;
    016import org.cpsolver.coursett.model.Lecture;
    017import org.cpsolver.coursett.model.Placement;
    018import org.cpsolver.coursett.model.TimetableModel;
    019import org.cpsolver.ifs.assignment.Assignment;
    020import org.cpsolver.ifs.util.DataProperties;
    021
    022
    023/**
    024 * The class represents various criteria concerning compact timetables of
    025 * instructors. The criteria are checked and updated when a variable is
    026 * (un)assigned.
    027 * <br>
    028 * implemented criterion: lunch break
    029 * <br>
    030 * @author  Matej Lukac
    031 * @version CourseTT 1.3 (University Course Timetabling)<br>
    032 *          Copyright (C) 2012 Matej Lukac<br>
    033 * <br>
    034 *          This library is free software; you can redistribute it and/or modify
    035 *          it under the terms of the GNU Lesser General Public License as
    036 *          published by the Free Software Foundation; either version 3 of the
    037 *          License, or (at your option) any later version. <br>
    038 * <br>
    039 *          This library is distributed in the hope that it will be useful, but
    040 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    041 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    042 *          Lesser General Public License for more details. <br>
    043 * <br>
    044 *          You should have received a copy of the GNU Lesser General Public
    045 *          License along with this library; if not see
    046 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    047 */
    048public class InstructorLunchBreak extends TimetablingCriterion {
    049    // lunch attributes
    050    private double iMultiplier;
    051    private int iLunchStart, iLunchEnd, iLunchLength;
    052    private boolean iFullInfo;
    053    private List<BitSet> iWeeks = null;
    054
    055    public InstructorLunchBreak() {
    056        setValueUpdateType(ValueUpdateType.AfterUnassignedAfterAssigned);
    057    }
    058
    059    @Override
    060    public void configure(DataProperties properties) {
    061        super.configure(properties);
    062
    063        iWeight = properties.getPropertyDouble("InstructorLunch.Weight", 0.3d);
    064
    065        // lunch parameters
    066        iLunchStart = properties.getPropertyInt("InstructorLunch.StartSlot", (11 * 60) / 5);
    067        iLunchEnd = properties.getPropertyInt("InstructorLunch.EndSlot", (13 * 60 + 30) / 5);
    068        iLunchLength = properties.getPropertyInt("InstructorLunch.Length", 30 / 5);
    069        iMultiplier = properties.getPropertyDouble("InstructorLunch.Multiplier", 1.2d);
    070        iFullInfo = properties.getPropertyBoolean("InstructorLunch.InfoShowViolations", false);
    071    }
    072
    073    /**
    074     * The method creates date patterns (bitsets) which represent the weeks of a
    075     * semester.
    076     *
    077     * @return a list of BitSets which represents the weeks of a semester.
    078     */
    079    protected List<BitSet> getWeeks() {
    080        if (iWeeks == null) {
    081            TimetableModel model = (TimetableModel) getModel();
    082            iWeeks = model.getWeeks();
    083        }
    084        return iWeeks;
    085    }
    086
    087    private boolean isEmpty(InstructorConstraintContext ic, int slot, BitSet week, Placement p) {
    088        if (p.getTimeLocation().getStartSlot() <= slot && slot < p.getTimeLocation().getStartSlot() + p.getTimeLocation().getLength() && p.getTimeLocation().shareWeeks(week))
    089            return false;
    090        List<Placement> placements = ic.getPlacements(slot, week);
    091        return placements.isEmpty() || (placements.size() == 1 && placements.get(0).variable().equals(p.variable()));
    092    }
    093
    094    @Override
    095    public double getValue(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
    096        double ret = 0.0;
    097        if (value.getTimeLocation().getStartSlot() <= iLunchEnd && value.getTimeLocation().getStartSlot() + value.getTimeLocation().getLength() > iLunchStart) {
    098            InstructorLunchBreakContext context = (InstructorLunchBreakContext)getContext(assignment);
    099            for (InstructorConstraint constraint: value.variable().getInstructorConstraints()) {
    100                InstructorConstraintContext icx = constraint.getContext(assignment);
    101                CompactInfo compactInfo = context.getCompactInfo(constraint);
    102                for (int i = 0; i < Constants.NR_DAYS; i++) {
    103                    // checks only days affected by the placement
    104                    if ((value.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0) {
    105                        int currentLunchStartSlot = Constants.SLOTS_PER_DAY * i + iLunchStart;
    106                        int currentLunchEndSlot = Constants.SLOTS_PER_DAY * i + iLunchEnd;
    107                        int semesterViolations = 0;
    108                        for (BitSet week : getWeeks()) {
    109                            int maxBreak = 0;
    110                            int currentBreak = 0;
    111                            for (int slot = currentLunchStartSlot; slot < currentLunchEndSlot; slot++) {
    112                                if (isEmpty(icx, slot, week, value)) {
    113                                    currentBreak++;
    114                                    if (maxBreak < currentBreak) {
    115                                        maxBreak = currentBreak;
    116                                    }
    117                                } else {
    118                                    currentBreak = 0;
    119                                }
    120                            }
    121                            if (maxBreak < iLunchLength) {
    122                                semesterViolations++;
    123                            }
    124                        }
    125                        // add the difference to the result
    126                        ret += semesterViolations - compactInfo.getLunchDayViolations()[i];
    127                    }
    128                }
    129            }
    130        }
    131        return ret;
    132    }
    133
    134    @Override
    135    public double getValue(Assignment<Lecture, Placement> assignment, Collection<Lecture> variables) {
    136        double lunchValue = 0.0d;
    137        Set<InstructorConstraint> constraints = new HashSet<InstructorConstraint>();
    138        for (Lecture lecture : variables) {
    139            constraints.addAll(lecture.getInstructorConstraints());
    140        }
    141        for (InstructorConstraint instructor : constraints) {
    142            lunchValue += ((InstructorLunchBreakContext)getContext(assignment)).getLunchPreference(assignment, instructor);
    143        }
    144        return lunchValue;
    145    }
    146
    147    @Override
    148    public void getInfo(Assignment<Lecture, Placement> assignment, Map<String, String> info) {
    149        Set<String> violatedLunchBreaks = new TreeSet<String>();
    150        int lunchViolations = 0;
    151        for (InstructorConstraint c : ((TimetableModel)getModel()).getInstructorConstraints()) {
    152            String days = "";
    153            CompactInfo compactInfo = ((InstructorLunchBreakContext)getContext(assignment)).getCompactInfo(c);
    154            for (int i = 0; i < Constants.NR_DAYS; i++) {
    155                if (compactInfo.getLunchDayViolations()[i] > 0) {
    156                    if (iFullInfo)
    157                        days += (days.isEmpty() ? "" : ", ") + compactInfo.getLunchDayViolations()[i] + " &times; " + Constants.DAY_NAMES_SHORT[i];
    158                    lunchViolations += compactInfo.getLunchDayViolations()[i];
    159                }
    160            }
    161            if (iFullInfo && !days.isEmpty())
    162                violatedLunchBreaks.add(c.getName() + ": " + days);
    163        }
    164        if (lunchViolations > 0) {
    165            info.put("Lunch breaks", getPerc(lunchViolations, 0, ((TimetableModel)getModel()).getInstructorConstraints().size() * Constants.NR_DAYS * getWeeks().size()) + "% (" + lunchViolations + ")");
    166            if (iFullInfo && !violatedLunchBreaks.isEmpty()) {
    167                String message = "";
    168                for (String s: violatedLunchBreaks)
    169                    message += (message.isEmpty() ? "" : "<br>") + s;
    170                info.put("Lunch break violations", message);
    171            }
    172        }
    173    }
    174
    175    @Override
    176    public void getInfo(Assignment<Lecture, Placement> assignment, Map<String, String> info, Collection<Lecture> variables) {
    177        Set<InstructorConstraint> constraints = new HashSet<InstructorConstraint>();
    178        for (Lecture lecture : variables) {
    179            for (InstructorConstraint c : lecture.getInstructorConstraints()) {
    180                constraints.add(c);
    181            }
    182        }
    183        Set<String> violatedLunchBreaks = new TreeSet<String>();
    184        int lunchViolations = 0;
    185        for (InstructorConstraint c : constraints) {
    186            String days = "";
    187            CompactInfo compactInfo = ((InstructorLunchBreakContext)getContext(assignment)).getCompactInfo(c);
    188            for (int i = 0; i < Constants.NR_DAYS; i++) {
    189                if (compactInfo.getLunchDayViolations()[i] > 0) {
    190                    if (iFullInfo)
    191                        days += (days.isEmpty() ? "" : ", ") + compactInfo.getLunchDayViolations()[i] + " &times; " + Constants.DAY_NAMES_SHORT[i];
    192                    lunchViolations += compactInfo.getLunchDayViolations()[i];
    193                }
    194            }
    195            if (iFullInfo && !days.isEmpty())
    196                violatedLunchBreaks.add(c.getName() + ": " + days);
    197        }
    198        if (lunchViolations > 0) {
    199            info.put("Lunch breaks", getPerc(lunchViolations, 0, constraints.size() * Constants.NR_DAYS * getWeeks().size()) + "% (" + lunchViolations + ")");
    200            if (iFullInfo && !violatedLunchBreaks.isEmpty()) {
    201                String message = "";
    202                for (String s: violatedLunchBreaks)
    203                    message += (message.isEmpty() ? "" : "; ") + s;
    204                info.put("Lunch break violations", message);
    205            }
    206        }
    207    }
    208
    209    /**
    210     * The class is used as a container of information concerning lunch break
    211     * of instructors. It is designed as an attribute of an
    212     * InstructorConstraint.
    213     */
    214    public static class CompactInfo {
    215        // lunch attributes
    216        private int[] iLunchDayViolations = new int[Constants.NR_DAYS];
    217
    218        public CompactInfo() {
    219        }
    220
    221        public int[] getLunchDayViolations() { return iLunchDayViolations; }
    222    }
    223
    224    public class InstructorLunchBreakContext extends ValueContext {
    225        private Map<InstructorConstraint, CompactInfo> iCompactInfos = new HashMap<InstructorConstraint, CompactInfo>();
    226
    227        protected InstructorLunchBreakContext(Assignment<Lecture, Placement> assignment) {
    228            for (InstructorConstraint constraint: ((TimetableModel)getModel()).getInstructorConstraints())
    229                iTotal += computeLunchPenalty(assignment, constraint);
    230        }
    231
    232        @Override
    233        protected void unassigned(Assignment<Lecture, Placement> assignment, Placement value) {
    234            for (InstructorConstraint constraint: value.variable().getInstructorConstraints())
    235                updateCriterion(assignment, constraint, value);
    236        }
    237
    238        @Override
    239        protected void assigned(Assignment<Lecture, Placement> assignment, Placement value) {
    240            for (InstructorConstraint constraint: value.variable().getInstructorConstraints())
    241                updateCriterion(assignment, constraint, value);
    242        }
    243
    244        /**
    245         * Method checks or sets the CompactInfo of an InstructorConstraint. It
    246         * updates the preference of chosen criteria. The update consists of
    247         * decrementing the criterion value by previous preference, finding the
    248         * current preference and incrementing the criterion value by the current
    249         * preference.
    250         *
    251         * @param assignment current assignment
    252         * @param instructorConstraint
    253         *            the Instructor constraint of an instructor checked for
    254         *            criteria
    255         * @param placement
    256         *            placement of a lecture currently (un)assigned
    257         */
    258        public void updateCriterion(Assignment<Lecture, Placement> assignment, InstructorConstraint instructorConstraint, Placement placement) {
    259            iTotal -= getLunchPreference(assignment, instructorConstraint);
    260            updateLunchPenalty(assignment, instructorConstraint, placement);
    261            iTotal += getLunchPreference(assignment, instructorConstraint);
    262        }
    263
    264        /**
    265         * Get compact info that is associated with an instructor constraint.
    266         * Create a new one if none has been created yet.
    267         * @param constraint instructor constraint
    268         * @return compact info for the given constraint
    269         */
    270        protected CompactInfo getCompactInfo(InstructorConstraint constraint) {
    271            CompactInfo info = iCompactInfos.get(constraint);
    272            if (info == null) {
    273                info = new CompactInfo();
    274                iCompactInfos.put(constraint, info);
    275            }
    276            return info;
    277        }
    278
    279        /**
    280         * Method updates number of violations in days (Mo, Tue, Wed,..) considering
    281         * each week in the semester separately. The current number of violations
    282         * for a day is stored in the CompactInfo.lunchDayViolations of the
    283         * constraint, which must be set properly before the calling of the method.
    284         *
    285         * @param assignment current assignment
    286         * @param constraint
    287         *            the Instructor constraint of an instructor checked for a lunch
    288         *            break
    289         * @param p
    290         *            placement of a lecture currently (un)assigned
    291         */
    292        public void updateLunchPenalty(Assignment<Lecture, Placement> assignment, InstructorConstraint constraint, Placement p) {
    293            // checks only placements in the lunch time
    294            if (p.getTimeLocation().getStartSlot() <= iLunchEnd && p.getTimeLocation().getStartSlot() + p.getTimeLocation().getLength() > iLunchStart) {
    295                CompactInfo compactInfo = getCompactInfo(constraint);
    296                for (int i = 0; i < Constants.NR_DAYS; i++) {
    297                    // checks only days affected by the placement
    298                    if ((p.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0) {
    299                        int currentLunchStartSlot = Constants.SLOTS_PER_DAY * i + iLunchStart;
    300                        int currentLunchEndSlot = Constants.SLOTS_PER_DAY * i + iLunchEnd;
    301                        int semesterViolations = 0;
    302                        for (BitSet week : getWeeks()) {
    303                            int maxBreak = 0;
    304                            int currentBreak = 0;
    305                            for (int slot = currentLunchStartSlot; slot < currentLunchEndSlot; slot++) {
    306                                if (constraint.getContext(assignment).getPlacements(slot, week).isEmpty()) {
    307                                    currentBreak++;
    308                                    if (maxBreak < currentBreak) {
    309                                        maxBreak = currentBreak;
    310                                    }
    311                                } else {
    312                                    currentBreak = 0;
    313                                }
    314                            }
    315                            if (maxBreak < iLunchLength) {
    316                                semesterViolations++;
    317                            }
    318                        }
    319                        // saving the result in the CompactInfo of the
    320                        // InstructorConstraint
    321                        compactInfo.getLunchDayViolations()[i] = semesterViolations;
    322                    }
    323                }
    324            }
    325        }
    326
    327        /**
    328         * Method computes number of violations in days (Mo, Tue, Wed,..) considering
    329         * each week in the semester separately. Updates the compact infos accordingly.
    330         * @param assignment current assignment
    331         * @param constraint instructor constraint
    332         * @return current penalty for the given instructor
    333         */
    334        public double computeLunchPenalty(Assignment<Lecture, Placement> assignment, InstructorConstraint constraint) {
    335            double violations = 0d;
    336            CompactInfo compactInfo = getCompactInfo(constraint);
    337            for (int i = 0; i < Constants.NR_DAYS; i++) {
    338                int currentLunchStartSlot = Constants.SLOTS_PER_DAY * i + iLunchStart;
    339                int currentLunchEndSlot = Constants.SLOTS_PER_DAY * i + iLunchEnd;
    340                int semesterViolations = 0;
    341                for (BitSet week : getWeeks()) {
    342                    int maxBreak = 0;
    343                    int currentBreak = 0;
    344                    for (int slot = currentLunchStartSlot; slot < currentLunchEndSlot; slot++) {
    345                        if (constraint.getContext(assignment).getPlacements(slot, week).isEmpty()) {
    346                            currentBreak++;
    347                            if (maxBreak < currentBreak) {
    348                                maxBreak = currentBreak;
    349                            }
    350                        } else {
    351                            currentBreak = 0;
    352                        }
    353                    }
    354                    if (maxBreak < iLunchLength) {
    355                        semesterViolations++;
    356                    }
    357                }
    358                // saving the result in the CompactInfo of the
    359                // InstructorConstraint
    360                compactInfo.getLunchDayViolations()[i] = semesterViolations;
    361                violations += semesterViolations;
    362            }
    363            return Math.pow(violations, iMultiplier);
    364        }
    365
    366        /**
    367         * Method uses the CompactInfo of the InstructorConstraint and returns the
    368         * lunch preference for this constraint. Calculation formula does not use
    369         * linear function, the number of violations is multiplied by a power of
    370         * iMultiplier.
    371         *
    372         * @param instructorConstraint
    373         *            the Instructor constraint of an instructor checked for a lunch
    374         *            break
    375         * @return the lunch preference for this constraint
    376         */
    377        private double getLunchPreference(Assignment<Lecture, Placement> assignment, InstructorConstraint instructorConstraint) {
    378            double violations = 0d;
    379            CompactInfo info = getCompactInfo(instructorConstraint);
    380            for (int i = 0; i < Constants.NR_DAYS; i++)
    381                violations += info.getLunchDayViolations()[i];
    382            return Math.pow(violations, iMultiplier);
    383        }
    384    }
    385
    386    @Override
    387    public ValueContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
    388        return new InstructorLunchBreakContext(assignment);
    389    }
    390}