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