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 049 public BrokenTimePatterns() { 050 setValueUpdateType(ValueUpdateType.NoUpdate); 051 } 052 053 @Override 054 public double getWeightDefault(DataProperties config) { 055 return Constants.sPreferenceLevelDiscouraged * config.getPropertyDouble("Comparator.UselessSlotWeight", 0.1); 056 } 057 058 @Override 059 public String getPlacementSelectionWeightName() { 060 return "Placement.UselessSlotsWeight"; 061 } 062 063 protected double penalty(Assignment<Lecture, Placement> assignment, Placement value) { 064 if (value.isMultiRoom()) { 065 int ret = 0; 066 for (RoomLocation r : value.getRoomLocations()) { 067 if (r.getRoomConstraint() == null) 068 continue; 069 ret += penalty(r.getRoomConstraint().getContext(assignment), value); 070 } 071 return ret; 072 } else { 073 return (value.getRoomLocation().getRoomConstraint() == null ? 0 : penalty(value.getRoomLocation().getRoomConstraint().getContext(assignment), value)); 074 } 075 } 076 077 protected double penalty(RoomConstraintContext rc) { 078 return countUselessSlotsBrokenTimePatterns(rc) / 6.0; 079 } 080 081 protected double penalty(RoomConstraintContext rc, Placement value) { 082 return countUselessSlotsBrokenTimePatterns(rc, value) / 6.0; 083 } 084 085 @Override 086 public double getValue(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) { 087 double ret = penalty(assignment, value); 088 if (conflicts != null) 089 for (Placement conflict: conflicts) 090 ret -= penalty(assignment, conflict); 091 return ret; 092 } 093 094 @Override 095 public double getValue(Assignment<Lecture, Placement> assignment, Collection<Lecture> variables) { 096 double ret = 0; 097 Set<RoomConstraint> constraints = new HashSet<RoomConstraint>(); 098 for (Lecture lect: variables) { 099 Placement placement = assignment.getValue(lect); 100 if (placement == null) continue; 101 if (placement.isMultiRoom()) { 102 for (RoomLocation r : placement.getRoomLocations()) { 103 if (r.getRoomConstraint() != null && constraints.add(r.getRoomConstraint())) 104 ret += penalty(r.getRoomConstraint().getContext(assignment)); 105 } 106 } else if (placement.getRoomLocation().getRoomConstraint() != null && 107 constraints.add(placement.getRoomLocation().getRoomConstraint())) { 108 ret += penalty(placement.getRoomLocation().getRoomConstraint().getContext(assignment)); 109 } 110 } 111 return ret; 112 } 113 114 @Override 115 protected double[] computeBounds(Assignment<Lecture, Placement> assignment) { 116 return new double[] { 117 ((TimetableModel)getModel()).getRoomConstraints().size() * Constants.SLOTS_PER_DAY_NO_EVENINGS * Constants.NR_DAYS_WEEK, 118 0.0 119 }; 120 } 121 122 @Override 123 public double[] getBounds(Assignment<Lecture, Placement> assignment, Collection<Lecture> variables) { 124 Set<RoomConstraint> constraints = new HashSet<RoomConstraint>(); 125 for (Lecture lect: variables) { 126 Placement placement = assignment.getValue(lect); 127 if (placement == null) continue; 128 if (placement.isMultiRoom()) { 129 for (RoomLocation r : placement.getRoomLocations()) { 130 if (r.getRoomConstraint() != null) 131 constraints.add(r.getRoomConstraint()); 132 } 133 } else if (placement.getRoomLocation().getRoomConstraint() != null) { 134 constraints.add(placement.getRoomLocation().getRoomConstraint()); 135 } 136 } 137 return new double[] { 138 constraints.size() * Constants.SLOTS_PER_DAY_NO_EVENINGS * Constants.NR_DAYS_WEEK, 139 0.0 }; 140 } 141 142 private static int sDaysMWF = Constants.DAY_CODES[0] + Constants.DAY_CODES[2] + Constants.DAY_CODES[4]; 143 private static int sDaysTTh = Constants.DAY_CODES[1] + Constants.DAY_CODES[3]; 144 145 private static boolean isEmpty(RoomConstraintContext rc, int s, int d, Placement placement) { 146 List<Placement> assigned = rc.getPlacements(d * Constants.SLOTS_PER_DAY + s); 147 return assigned.isEmpty() || (placement != null && assigned.size() == 1 && assigned.get(0).variable().equals(placement.variable())); 148 } 149 150 /** Number of broken time patterns for this room 151 * @param rc room constraint 152 * @param placement placement that is being considered 153 * @return number of broken time patterns caused by the given placement 154 **/ 155 protected static int countUselessSlotsBrokenTimePatterns(RoomConstraintContext rc, Placement placement) { 156 int ret = 0; 157 TimeLocation time = placement.getTimeLocation(); 158 int slot = time.getStartSlot() % Constants.SLOTS_PER_DAY; 159 int days = time.getDayCode(); 160 if ((days & sDaysMWF) != 0 && (days & sDaysMWF) != sDaysMWF) { 161 for (int s = slot; s < slot + time.getLength(); s++) { 162 int d = (days & sDaysMWF); 163 if (d == Constants.DAY_CODES[0] && isEmpty(rc, s, 0, placement)) { 164 if (isEmpty(rc, s, 2, placement) != isEmpty(rc, s, 4, placement)) ret ++; 165 if (!isEmpty(rc, s, 2, placement) && !isEmpty(rc, s, 4, placement)) ret --; 166 } else if (d == Constants.DAY_CODES[2] && isEmpty(rc, s, 2, placement)) { 167 if (isEmpty(rc, s, 0, placement) != isEmpty(rc, s, 4, placement)) ret ++; 168 if (!isEmpty(rc, s, 0, placement) && !isEmpty(rc, s, 4, placement)) ret --; 169 } else if (d == Constants.DAY_CODES[4] && isEmpty(rc, s, 4, placement)) { 170 if (isEmpty(rc, s, 0, placement) != isEmpty(rc, s, 2, placement)) ret ++; 171 if (!isEmpty(rc, s, 0, placement) && !isEmpty(rc, s, 2, placement)) ret --; 172 } else if (d == (Constants.DAY_CODES[0] | Constants.DAY_CODES[2]) && isEmpty(rc, s, 0, placement) && isEmpty(rc, s, 2, placement)) { 173 if (isEmpty(rc, s, 4, placement)) ret ++; 174 } else if (d == (Constants.DAY_CODES[2] | Constants.DAY_CODES[4]) && isEmpty(rc, s, 2, placement) && isEmpty(rc, s, 4, placement)) { 175 if (isEmpty(rc, s, 0, placement)) ret ++; 176 } else if (d == (Constants.DAY_CODES[0] | Constants.DAY_CODES[4]) && isEmpty(rc, s, 0, placement) && isEmpty(rc, s, 4, placement)) { 177 if (isEmpty(rc, s, 2, placement)) ret ++; 178 } 179 } 180 } 181 if ((days & sDaysTTh) != 0 && (days & sDaysTTh) != sDaysTTh) { 182 for (int s = slot; s < slot + time.getLength(); s++) { 183 if (isEmpty(rc, s, 1, placement) && isEmpty(rc, s, 3, placement)) ret ++; 184 int d = (days & sDaysTTh); 185 if (d == Constants.DAY_CODES[1] && isEmpty(rc, s, 1, placement) && !isEmpty(rc, s, 3, placement)) ret --; 186 if (d == Constants.DAY_CODES[3] && isEmpty(rc, s, 3, placement) && !isEmpty(rc, s, 1, placement)) ret --; 187 } 188 } 189 return ret; 190 } 191 192 /** Number of useless slots for this room 193 * @param rc room constraint 194 * @return current penalty for the given room 195 **/ 196 public static int countUselessSlotsBrokenTimePatterns(RoomConstraintContext rc) { 197 int ret = 0; 198 for (int d = 0; d < Constants.NR_DAYS; d++) { 199 for (int s = 0; s < Constants.SLOTS_PER_DAY; s++) { 200 int slot = d * Constants.SLOTS_PER_DAY + s; 201 if (rc.getPlacements(slot).isEmpty()) { 202 switch (d) { 203 case 0: 204 if (!rc.getPlacements(2 * Constants.SLOTS_PER_DAY + s).isEmpty() && !rc.getPlacements(4 * Constants.SLOTS_PER_DAY + s).isEmpty()) 205 ret++; 206 break; 207 case 1: 208 if (!rc.getPlacements(3 * Constants.SLOTS_PER_DAY + s).isEmpty()) 209 ret++; 210 break; 211 case 2: 212 if (!rc.getPlacements(0 * Constants.SLOTS_PER_DAY + s).isEmpty() && !rc.getPlacements(4 * Constants.SLOTS_PER_DAY + s).isEmpty()) 213 ret++; 214 break; 215 case 3: 216 if (!rc.getPlacements(1 * Constants.SLOTS_PER_DAY + s).isEmpty()) 217 ret++; 218 break; 219 case 4: 220 if (!rc.getPlacements(0 * Constants.SLOTS_PER_DAY + s).isEmpty() && !rc.getPlacements(2 * Constants.SLOTS_PER_DAY + s).isEmpty()) 221 ret++; 222 break; 223 } 224 } 225 } 226 } 227 return ret; 228 } 229}