001package org.cpsolver.coursett.criteria; 002 003import java.util.Collection; 004import java.util.HashSet; 005import java.util.List; 006import java.util.Set; 007 008import org.cpsolver.coursett.Constants; 009import org.cpsolver.coursett.constraint.RoomConstraint; 010import org.cpsolver.coursett.constraint.RoomConstraint.RoomConstraintContext; 011import org.cpsolver.coursett.model.Lecture; 012import org.cpsolver.coursett.model.Placement; 013import org.cpsolver.coursett.model.RoomLocation; 014import org.cpsolver.coursett.model.TimeLocation; 015import org.cpsolver.coursett.model.TimetableModel; 016import org.cpsolver.ifs.assignment.Assignment; 017import org.cpsolver.ifs.util.DataProperties; 018 019 020/** 021 * Broken time patterns. This criterion counts cases when an unused space is in a room 022 * which follows one of the standard MWF or TTh pattern. E.g., there is a penalty of 023 * Monday is available during a time when Wednesday and/or Friday is occupied. The aim 024 * is to use this space if possible in order to leave the available space in a way that 025 * can be used by MWF or TTh classes. 026 * <br> 027 * 028 * @version CourseTT 1.3 (University Course Timetabling)<br> 029 * Copyright (C) 2006 - 2014 Tomas Muller<br> 030 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 031 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 032 * <br> 033 * This library is free software; you can redistribute it and/or modify 034 * it under the terms of the GNU Lesser General Public License as 035 * published by the Free Software Foundation; either version 3 of the 036 * License, or (at your option) any later version. <br> 037 * <br> 038 * This library is distributed in the hope that it will be useful, but 039 * WITHOUT ANY WARRANTY; without even the implied warranty of 040 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 041 * Lesser General Public License for more details. <br> 042 * <br> 043 * You should have received a copy of the GNU Lesser General Public 044 * License along with this library; if not see 045 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 046 */ 047public class BrokenTimePatterns extends TimetablingCriterion { 048 private int iFirstDaySlot, iLastDaySlot, iFirstWorkDay, iLastWorkDay; 049 050 public BrokenTimePatterns() { 051 setValueUpdateType(ValueUpdateType.NoUpdate); 052 } 053 054 @Override 055 public void configure(DataProperties properties) { 056 super.configure(properties); 057 iFirstDaySlot = properties.getPropertyInt("General.FirstDaySlot", Constants.DAY_SLOTS_FIRST); 058 iLastDaySlot = properties.getPropertyInt("General.LastDaySlot", Constants.DAY_SLOTS_LAST); 059 iFirstWorkDay = properties.getPropertyInt("General.FirstWorkDay", 0); 060 iLastWorkDay = properties.getPropertyInt("General.LastWorkDay", Constants.NR_DAYS_WEEK - 1); 061 } 062 063 @Override 064 public double getWeightDefault(DataProperties config) { 065 return Constants.sPreferenceLevelDiscouraged * config.getPropertyDouble("Comparator.UselessSlotWeight", 0.1); 066 } 067 068 @Override 069 public String getPlacementSelectionWeightName() { 070 return "Placement.UselessSlotsWeight"; 071 } 072 073 protected double penalty(Assignment<Lecture, Placement> assignment, Placement value) { 074 if (value.isMultiRoom()) { 075 int ret = 0; 076 for (RoomLocation r : value.getRoomLocations()) { 077 if (r.getRoomConstraint() == null) 078 continue; 079 ret += penalty(r.getRoomConstraint().getContext(assignment), value); 080 } 081 return ret; 082 } else { 083 return (value.getRoomLocation().getRoomConstraint() == null ? 0 : penalty(value.getRoomLocation().getRoomConstraint().getContext(assignment), value)); 084 } 085 } 086 087 protected double penalty(RoomConstraintContext rc) { 088 return countUselessSlotsBrokenTimePatterns(rc) / 6.0; 089 } 090 091 protected double penalty(RoomConstraintContext rc, Placement value) { 092 return countUselessSlotsBrokenTimePatterns(rc, value) / 6.0; 093 } 094 095 @Override 096 public double getValue(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) { 097 double ret = penalty(assignment, value); 098 if (conflicts != null) 099 for (Placement conflict: conflicts) 100 ret -= penalty(assignment, conflict); 101 return ret; 102 } 103 104 @Override 105 public double getValue(Assignment<Lecture, Placement> assignment, Collection<Lecture> variables) { 106 double ret = 0; 107 Set<RoomConstraint> constraints = new HashSet<RoomConstraint>(); 108 for (Lecture lect: variables) { 109 Placement placement = assignment.getValue(lect); 110 if (placement == null) continue; 111 if (placement.isMultiRoom()) { 112 for (RoomLocation r : placement.getRoomLocations()) { 113 if (r.getRoomConstraint() != null && constraints.add(r.getRoomConstraint())) 114 ret += penalty(r.getRoomConstraint().getContext(assignment)); 115 } 116 } else if (placement.getRoomLocation().getRoomConstraint() != null && 117 constraints.add(placement.getRoomLocation().getRoomConstraint())) { 118 ret += penalty(placement.getRoomLocation().getRoomConstraint().getContext(assignment)); 119 } 120 } 121 return ret; 122 } 123 124 @Override 125 protected double[] computeBounds(Assignment<Lecture, Placement> assignment) { 126 return new double[] { 127 ((TimetableModel)getModel()).getRoomConstraints().size() * (iLastWorkDay - iFirstWorkDay + 1) * (iLastDaySlot - iFirstDaySlot + 1), 128 0.0 }; 129 } 130 131 @Override 132 public double[] getBounds(Assignment<Lecture, Placement> assignment, Collection<Lecture> variables) { 133 Set<RoomConstraint> constraints = new HashSet<RoomConstraint>(); 134 for (Lecture lect: variables) { 135 Placement placement = assignment.getValue(lect); 136 if (placement == null) continue; 137 if (placement.isMultiRoom()) { 138 for (RoomLocation r : placement.getRoomLocations()) { 139 if (r.getRoomConstraint() != null) 140 constraints.add(r.getRoomConstraint()); 141 } 142 } else if (placement.getRoomLocation().getRoomConstraint() != null) { 143 constraints.add(placement.getRoomLocation().getRoomConstraint()); 144 } 145 } 146 return new double[] { 147 constraints.size() * (iLastWorkDay - iFirstWorkDay + 1) * (iLastDaySlot - iFirstDaySlot + 1), 148 0.0 }; 149 } 150 151 private static int sDaysMWF = Constants.DAY_CODES[0] + Constants.DAY_CODES[2] + Constants.DAY_CODES[4]; 152 private static int sDaysTTh = Constants.DAY_CODES[1] + Constants.DAY_CODES[3]; 153 154 private static boolean isEmpty(RoomConstraintContext rc, int s, int d, Placement placement) { 155 List<Placement> assigned = rc.getPlacements(d * Constants.SLOTS_PER_DAY + s); 156 return assigned.isEmpty() || (placement != null && assigned.size() == 1 && assigned.get(0).variable().equals(placement.variable())); 157 } 158 159 /** Number of broken time patterns for this room 160 * @param rc room constraint 161 * @param placement placement that is being considered 162 * @return number of broken time patterns caused by the given placement 163 **/ 164 protected static int countUselessSlotsBrokenTimePatterns(RoomConstraintContext rc, Placement placement) { 165 int ret = 0; 166 TimeLocation time = placement.getTimeLocation(); 167 int slot = time.getStartSlot() % Constants.SLOTS_PER_DAY; 168 int days = time.getDayCode(); 169 if ((days & sDaysMWF) != 0 && (days & sDaysMWF) != sDaysMWF) { 170 for (int s = slot; s < slot + time.getLength(); s++) { 171 int d = (days & sDaysMWF); 172 if (d == Constants.DAY_CODES[0] && isEmpty(rc, s, 0, placement)) { 173 if (isEmpty(rc, s, 2, placement) != isEmpty(rc, s, 4, placement)) ret ++; 174 if (!isEmpty(rc, s, 2, placement) && !isEmpty(rc, s, 4, placement)) ret --; 175 } else if (d == Constants.DAY_CODES[2] && isEmpty(rc, s, 2, placement)) { 176 if (isEmpty(rc, s, 0, placement) != isEmpty(rc, s, 4, placement)) ret ++; 177 if (!isEmpty(rc, s, 0, placement) && !isEmpty(rc, s, 4, placement)) ret --; 178 } else if (d == Constants.DAY_CODES[4] && isEmpty(rc, s, 4, placement)) { 179 if (isEmpty(rc, s, 0, placement) != isEmpty(rc, s, 2, placement)) ret ++; 180 if (!isEmpty(rc, s, 0, placement) && !isEmpty(rc, s, 2, placement)) ret --; 181 } else if (d == (Constants.DAY_CODES[0] | Constants.DAY_CODES[2]) && isEmpty(rc, s, 0, placement) && isEmpty(rc, s, 2, placement)) { 182 if (isEmpty(rc, s, 4, placement)) ret ++; 183 } else if (d == (Constants.DAY_CODES[2] | Constants.DAY_CODES[4]) && isEmpty(rc, s, 2, placement) && isEmpty(rc, s, 4, placement)) { 184 if (isEmpty(rc, s, 0, placement)) ret ++; 185 } else if (d == (Constants.DAY_CODES[0] | Constants.DAY_CODES[4]) && isEmpty(rc, s, 0, placement) && isEmpty(rc, s, 4, placement)) { 186 if (isEmpty(rc, s, 2, placement)) ret ++; 187 } 188 } 189 } 190 if ((days & sDaysTTh) != 0 && (days & sDaysTTh) != sDaysTTh) { 191 for (int s = slot; s < slot + time.getLength(); s++) { 192 if (isEmpty(rc, s, 1, placement) && isEmpty(rc, s, 3, placement)) ret ++; 193 int d = (days & sDaysTTh); 194 if (d == Constants.DAY_CODES[1] && isEmpty(rc, s, 1, placement) && !isEmpty(rc, s, 3, placement)) ret --; 195 if (d == Constants.DAY_CODES[3] && isEmpty(rc, s, 3, placement) && !isEmpty(rc, s, 1, placement)) ret --; 196 } 197 } 198 return ret; 199 } 200 201 /** Number of useless slots for this room 202 * @param rc room constraint 203 * @return current penalty for the given room 204 **/ 205 public static int countUselessSlotsBrokenTimePatterns(RoomConstraintContext rc) { 206 int ret = 0; 207 for (int d = 0; d < Constants.NR_DAYS; d++) { 208 for (int s = 0; s < Constants.SLOTS_PER_DAY; s++) { 209 int slot = d * Constants.SLOTS_PER_DAY + s; 210 if (rc.getPlacements(slot).isEmpty()) { 211 switch (d) { 212 case 0: 213 if (!rc.getPlacements(2 * Constants.SLOTS_PER_DAY + s).isEmpty() && !rc.getPlacements(4 * Constants.SLOTS_PER_DAY + s).isEmpty()) 214 ret++; 215 break; 216 case 1: 217 if (!rc.getPlacements(3 * Constants.SLOTS_PER_DAY + s).isEmpty()) 218 ret++; 219 break; 220 case 2: 221 if (!rc.getPlacements(0 * Constants.SLOTS_PER_DAY + s).isEmpty() && !rc.getPlacements(4 * Constants.SLOTS_PER_DAY + s).isEmpty()) 222 ret++; 223 break; 224 case 3: 225 if (!rc.getPlacements(1 * Constants.SLOTS_PER_DAY + s).isEmpty()) 226 ret++; 227 break; 228 case 4: 229 if (!rc.getPlacements(0 * Constants.SLOTS_PER_DAY + s).isEmpty() && !rc.getPlacements(2 * Constants.SLOTS_PER_DAY + s).isEmpty()) 230 ret++; 231 break; 232 } 233 } 234 } 235 } 236 return ret; 237 } 238}