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 }