    001package org.cpsolver.coursett.constraint;
    002
    003import org.cpsolver.coursett.Constants;
    004import org.cpsolver.coursett.criteria.DepartmentBalancingPenalty;
    005import org.cpsolver.coursett.model.Lecture;
    006import org.cpsolver.coursett.model.Placement;
    007import org.cpsolver.ifs.criteria.Criterion;
    008import org.cpsolver.ifs.util.DataProperties;
    009
    010/**
    011 * Departmental ballancing constraint. <br>
    012 * <br>
    013 * The new implementation of the balancing times for departments works as
    014 * follows: Initially, there is a histogram for each department computed. For
    015 * each time slot, it says how many placements of all classes (of the
    016 * department) include this time slot. Each such placement has the weight of 1 /
    017 * number of placements of the class, so the total sum of all values in the
    018 * histogram (i.e., for all time slots) is equal to the total sum of half-hours
    019 * required by the given set of classes. <br>
    020 * <br>
    021 * On the other hand, each class splits its number of half-hours (e.g., 2x50 has
    022 * 4 half-hours, "4 points") into the time slots which it can occupy, according
    023 * to the frequencies of the utilization of each time slots (i.e., number of
    024 * placements containing the time slots divided by the number of all placements
    025 * of the class). <br>
    026 * <br>
    027 * For example, a histogram for department 1286:<pre><code>
    028 * 1: [0.10,0.00,0.10,0.00,0.10] &larr; 7:30 [Mon, Tue, Wed, Thu, Fri]
    029 * 2: [0.10,0.00,0.10,0.00,0.10] &larr; 8:00 [Mon, Tue, Wed, Thu, Fri]
    030 * 3: [0.35,0.62,0.48,0.62,0.10] ... and so on
    031 * 4: [0.35,0.62,0.48,0.62,0.10]
    032 * 5: [1.35,1.12,1.48,0.12,1.10]
    033 * 6: [1.35,1.12,1.48,0.12,1.10]
    034 * 7: [0.35,0.62,0.48,1.63,0.10]
    035 * 8: [0.35,0.62,0.48,1.63,0.10]
    036 * 9: [0.35,0.12,0.48,0.12,0.10]
    037 * 10:[0.35,0.12,0.48,0.12,0.10]
    038 * 11:[0.35,0.12,0.48,0.12,0.10]
    039 * 12:[0.35,0.12,0.48,0.12,0.10]
    040 * 13:[0.35,0.12,0.48,1.12,0.10]
    041 * 14:[0.35,0.12,0.48,1.12,0.10]
    042 * 15:[0.35,0.12,0.48,0.12,0.10]
    043 * 16:[0.35,0.12,0.48,0.12,0.10]
    044 * 17:[0.35,0.12,0.48,0.12,0.10]
    045 * 18:[0.35,0.12,0.48,0.12,0.10]
    046 * 19:[0.10,0.00,0.10,0.00,0.10]
    047 * 20:[0.10,0.00,0.10,0.00,0.10]
    048 * 21:[0.00,0.00,0.00,0.00,0.00]
    049 * </code></pre>
    050 * You can easily see, that the time slots which are prohibited for all of the
    051 * classes of the department have zero values, also some time slots are used
    052 * much often than the others. Note that there are no preferences involved in
    053 * this computation, only prohibited / not used times are less involved. <br>
    054 * <br>
    055 * The idea is to setup the initial limits for each of the time slots according
    056 * to the above values. The reason for doing so is to take the requirements
    057 * (time patterns, required/prohibited times) of all classes of the department
    058 * into account. For instance, take two classes A and B of type MWF 2x100 with
    059 * two available locations starting from 7:30 and 8:30. Note that the time slot
    060 * Monday 8:30-9:00 will be always used by both of the classes and for instance
    061 * the time slot Monday 7:30-8:00 (or Friday 9:30-10:00) can be used by none of
    062 * them, only one of them or both of them. From the balancing point of the view,
    063 * I believe it should be preferred to have one class starting from 7:30 and the
    064 * other one from 8:30. <br>
    065 * <br>
    066 * So, after the histogram is computed, its values are increased by the given
    067 * percentage (same reason as before, to allow some space between the actual
    068 * value and the limit, also not to make the limits for a department with 21
    069 * time slots less strict than a department with 20 time slots etc.). The
    070 * initial limits are than computed as these values rounded upwards (1.90
    071 * results in 2). <br>
    072 * <br>
    073 * Moreover, the value is increased only when the histogram value of a time slot
    074 * is below the following value: spread factor * (number of used time slots /
    075 * number of all time slots). Is assures a department of at least the given
    076 * percentage more time slots than required, but does not provide an additional
    077 * reward for above average use of time slots based on 'required' times. <br>
    078 * <br>
    079 * For example, the department 1286 will have the following limits (histogram
    080 * increased by 20% (i.e., each value is 20% higher) and rounded upwards):
    081 * <pre><code>
    082 * 1: [1,0,1,0,1]
    083 * 2: [1,0,1,0,1]
    084 * 3: [1,1,1,1,1]
    085 * 4: [1,1,1,1,1]
    086 * 5: [2,2,2,1,2]
    087 * 6: [2,2,2,1,2]
    088 * 7: [1,1,1,2,1]
    089 * 8: [1,1,1,2,1]
    090 * 9: [1,1,1,1,1]
    091 * 10:[1,1,1,1,1]
    092 * 11:[1,1,1,1,1]
    093 * 12:[1,1,1,1,1]
    094 * 13:[1,1,1,2,1]
    095 * 14:[1,1,1,2,1]
    096 * 15:[1,1,1,1,1]
    097 * 16:[1,1,1,1,1]
    098 * 17:[1,1,1,1,1]
    099 * 18:[1,1,1,1,1]
    100 * 19:[1,0,1,0,1]
    101 * 20:[1,0,1,0,1]
    102 * 21:[0,0,0,0,0]
    103 * </code></pre>
    104 * The maximal penalty (i.e., the maximal number of half-hours which can be used
    105 * above the pre-computed limits by a department) of a constraint is used.
    106 * Initially, the maximal penalty is set to zero. It is increased by one after
    107 * each time when the constraint causes the given number (e.g., 100) of
    108 * un-assignments. <br>
    109 * <br>
    110 * Also, the balancing penalty (the total number of half-hours over the initial
    111 * limits) is computed and it can be minimized during the search (soft
    112 * constraint). <br>
    113 * <br>
    114 * Parameters:
    115 * <table border='1'><caption>Related Solver Parameters</caption>
    116 * <tr>
    117 * <th>Parameter</th>
    118 * <th>Type</th>
    119 * <th>Comment</th>
    120 * </tr>
    121 * <tr>
    122 * <td>DeptBalancing.SpreadFactor</td>
    123 * <td>{@link Double}</td>
    124 * <td>Initial allowance of the slots for a particular time (factor)<br>
    125 * Allowed slots = ROUND(SpreadFactor * (number of requested slots / number of
    126 * slots per day))</td>
    127 * </tr>
    128 * <tr>
    129 * <td>DeptBalancing.Unassignments2Weaken</td>
    130 * <td>{@link Integer}</td>
    131 * <td>Increase the initial allowance when it causes the given number of
    132 * unassignments</td>
    133 * </tr>
    134 * </table>
    135 *
    136 * @author  Tomáš Müller
    137 * @version CourseTT 1.3 (University Course Timetabling)<br>
    138 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
    139 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    140 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    141 * <br>
    142 *          This library is free software; you can redistribute it and/or modify
    143 *          it under the terms of the GNU Lesser General Public License as
    144 *          published by the Free Software Foundation; either version 3 of the
    145 *          License, or (at your option) any later version. <br>
    146 * <br>
    147 *          This library is distributed in the hope that it will be useful, but
    148 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    149 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    150 *          Lesser General Public License for more details. <br>
    151 * <br>
    152 *          You should have received a copy of the GNU Lesser General Public
    153 *          License along with this library; if not see
    154 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    155 */
    156
    157public class DepartmentSpreadConstraint extends SpreadConstraint {
    158    private Long iDepartment = null;
    159
    160    public DepartmentSpreadConstraint(DataProperties config, Long department, String name) {
    161        super(name,
    162                config.getPropertyDouble("DeptBalancing.SpreadFactor", 1.20),
    163                config.getPropertyInt("DeptBalancing.Unassignments2Weaken", 250),
    164                config.getPropertyBoolean("General.InteractiveMode", false),
    165                config.getPropertyInt("General.FirstDaySlot", Constants.DAY_SLOTS_FIRST),
    166                config.getPropertyInt("General.LastDaySlot", Constants.DAY_SLOTS_LAST),
    167                config.getPropertyInt("General.FirstWorkDay", 0),
    168                config.getPropertyInt("General.LastWorkDay", Constants.NR_DAYS_WEEK - 1)
    169                );
    170        iDepartment = department;
    171    }
    172
    173    public Long getDepartmentId() {
    174        return iDepartment;
    175    }
    176
    177    @Override
    178    protected Criterion<Lecture, Placement> getCriterion() {
    179        return getModel().getCriterion(DepartmentBalancingPenalty.class);
    180    }
    181
    182    @Override
    183    public String toString() {
    184        return "Departmental Balancing for " + getName();
    185    }
    186}