001 package net.sf.cpsolver.coursett.criteria;
002
003 import java.util.Collection;
004 import java.util.HashSet;
005 import java.util.Set;
006
007 import net.sf.cpsolver.coursett.Constants;
008 import net.sf.cpsolver.coursett.constraint.RoomConstraint;
009 import net.sf.cpsolver.coursett.model.Lecture;
010 import net.sf.cpsolver.coursett.model.Placement;
011 import net.sf.cpsolver.coursett.model.RoomLocation;
012 import net.sf.cpsolver.coursett.model.TimeLocation;
013 import net.sf.cpsolver.coursett.model.TimetableModel;
014 import net.sf.cpsolver.ifs.util.DataProperties;
015
016 /**
017 * Broken time patterns. This criterion counts cases when an unused space is in a room
018 * which follows one of the standard MWF or TTh pattern. E.g., there is a penalty of
019 * Monday is available during a time when Wednesday and/or Friday is occupied. The aim
020 * is to use this space if possible in order to leave the available space in a way that
021 * can be used by MWF or TTh classes.
022 * <br>
023 *
024 * @version CourseTT 1.2 (University Course Timetabling)<br>
025 * Copyright (C) 2006 - 2011 Tomas Muller<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 public class BrokenTimePatterns extends TimetablingCriterion {
044
045 public BrokenTimePatterns() {
046 iValueUpdateType = ValueUpdateType.NoUpdate;
047 }
048
049 @Override
050 public double getWeightDefault(DataProperties config) {
051 return Constants.sPreferenceLevelDiscouraged * config.getPropertyDouble("Comparator.UselessSlotWeight", 0.1);
052 }
053
054 @Override
055 public String getPlacementSelectionWeightName() {
056 return "Placement.UselessSlotsWeight";
057 }
058
059 protected int penalty(Placement value) {
060 if (value.isMultiRoom()) {
061 int ret = 0;
062 for (RoomLocation r : value.getRoomLocations()) {
063 if (r.getRoomConstraint() == null)
064 continue;
065 ret += penalty(r.getRoomConstraint(), value.getTimeLocation());
066 }
067 return ret;
068 } else {
069 return (value.getRoomLocation().getRoomConstraint() == null ? 0 : penalty(value.getRoomLocation().getRoomConstraint(), value.getTimeLocation()));
070 }
071 }
072
073 protected int penalty(RoomConstraint rc) {
074 return countUselessSlotsBrokenTimePatterns(rc);
075 }
076
077 protected int penalty(RoomConstraint rc, TimeLocation value) {
078 return countUselessSlotsBrokenTimePatterns(rc, value);
079 }
080
081 @Override
082 public double getValue(Placement value, Set<Placement> conflicts) {
083 double ret = penalty(value);
084 if (conflicts != null)
085 for (Placement conflict: conflicts)
086 ret -= penalty(conflict);
087 return ret;
088 }
089
090 @Override
091 public double getValue(Collection<Lecture> variables) {
092 double ret = 0;
093 Set<RoomConstraint> constraints = new HashSet<RoomConstraint>();
094 for (Lecture lect: variables) {
095 if (lect.getAssignment() == null) continue;
096 if (lect.getAssignment().isMultiRoom()) {
097 for (RoomLocation r : lect.getAssignment().getRoomLocations()) {
098 if (r.getRoomConstraint() != null && constraints.add(r.getRoomConstraint()))
099 ret += penalty(r.getRoomConstraint());
100 }
101 } else if (lect.getAssignment().getRoomLocation().getRoomConstraint() != null &&
102 constraints.add(lect.getAssignment().getRoomLocation().getRoomConstraint())) {
103 ret += penalty(lect.getAssignment().getRoomLocation().getRoomConstraint());
104 }
105 }
106 return ret;
107 }
108
109 @Override
110 protected double[] computeBounds() {
111 return new double[] {
112 ((TimetableModel)getModel()).getRoomConstraints().size() * Constants.SLOTS_PER_DAY_NO_EVENINGS * Constants.NR_DAYS_WEEK,
113 0.0
114 };
115 }
116
117 @Override
118 public double[] getBounds(Collection<Lecture> variables) {
119 Set<RoomConstraint> constraints = new HashSet<RoomConstraint>();
120 for (Lecture lect: variables) {
121 if (lect.getAssignment() == null) continue;
122 if (lect.getAssignment().isMultiRoom()) {
123 for (RoomLocation r : lect.getAssignment().getRoomLocations()) {
124 if (r.getRoomConstraint() != null)
125 constraints.add(r.getRoomConstraint());
126 }
127 } else if (lect.getAssignment().getRoomLocation().getRoomConstraint() != null) {
128 constraints.add(lect.getAssignment().getRoomLocation().getRoomConstraint());
129 }
130 }
131 return new double[] {
132 constraints.size() * Constants.SLOTS_PER_DAY_NO_EVENINGS * Constants.NR_DAYS_WEEK,
133 0.0 };
134 }
135
136 private static int sDaysMWF = Constants.DAY_CODES[0] + Constants.DAY_CODES[2] + Constants.DAY_CODES[4];
137 private static int sDaysTTh = Constants.DAY_CODES[1] + Constants.DAY_CODES[3];
138
139 /** Number of broken time patterns for this room */
140 protected static int countUselessSlotsBrokenTimePatterns(RoomConstraint rc, TimeLocation time) {
141 int ret = 0;
142 int slot = time.getStartSlot() % Constants.SLOTS_PER_DAY;
143 int days = time.getDayCode();
144 if ((days & sDaysMWF) != 0 && (days & sDaysMWF) != sDaysMWF) {
145 for (int s = slot; s < slot + time.getLength(); s++) {
146 int nrEmpty = 0;
147 if ((Constants.DAY_CODES[0] & days) == 0 && rc.getResource(0 * Constants.SLOTS_PER_DAY + s).isEmpty())
148 nrEmpty++;
149 if ((Constants.DAY_CODES[2] & days) == 0 && rc.getResource(2 * Constants.SLOTS_PER_DAY + s).isEmpty())
150 nrEmpty++;
151 if ((Constants.DAY_CODES[4] & days) == 0 && rc.getResource(4 * Constants.SLOTS_PER_DAY + s).isEmpty())
152 nrEmpty++;
153 if (nrEmpty > 0)
154 ret ++;
155 }
156 }
157 if ((days & sDaysTTh) != 0 && (days & sDaysTTh) != sDaysTTh) {
158 for (int s = slot; s < slot + time.getLength(); s++) {
159 int nrEmpty = 0;
160 if ((Constants.DAY_CODES[1] & days) == 0 && rc.getResource(1 * Constants.SLOTS_PER_DAY + s).isEmpty())
161 nrEmpty++;
162 if ((Constants.DAY_CODES[3] & days) == 0 && rc.getResource(3 * Constants.SLOTS_PER_DAY + s).isEmpty())
163 nrEmpty++;
164 if (nrEmpty > 0)
165 ret ++;
166 }
167 }
168 return ret / 6;
169 }
170
171 /** Number of useless slots for this room */
172 public static int countUselessSlotsBrokenTimePatterns(RoomConstraint rc) {
173 int ret = 0;
174 for (int d = 0; d < Constants.NR_DAYS; d++) {
175 for (int s = 0; s < Constants.SLOTS_PER_DAY; s++) {
176 int slot = d * Constants.SLOTS_PER_DAY + s;
177 if (rc.getResource(slot).isEmpty()) {
178 switch (d) {
179 case 0:
180 if (!rc.getResource(2 * Constants.SLOTS_PER_DAY + s).isEmpty()
181 && !rc.getResource(4 * Constants.SLOTS_PER_DAY + s).isEmpty())
182 ret++;
183 break;
184 case 1:
185 if (!rc.getResource(3 * Constants.SLOTS_PER_DAY + s).isEmpty())
186 ret++;
187 break;
188 case 2:
189 if (!rc.getResource(0 * Constants.SLOTS_PER_DAY + s).isEmpty()
190 && !rc.getResource(4 * Constants.SLOTS_PER_DAY + s).isEmpty())
191 ret++;
192 break;
193 case 3:
194 if (!rc.getResource(1 * Constants.SLOTS_PER_DAY + s).isEmpty())
195 ret++;
196 break;
197 case 4:
198 if (!rc.getResource(0 * Constants.SLOTS_PER_DAY + s).isEmpty()
199 && !rc.getResource(2 * Constants.SLOTS_PER_DAY + s).isEmpty())
200 ret++;
201 break;
202 }
203 }
204 }
205 }
206 return Math.round((1.0f / 6.0f) * ret);
207 }
208 }