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