001package net.sf.cpsolver.coursett.constraint; 002 003import java.util.ArrayList; 004import java.util.BitSet; 005import java.util.Collections; 006import java.util.HashMap; 007import java.util.List; 008import java.util.Map; 009import java.util.Set; 010import java.util.regex.Matcher; 011import java.util.regex.Pattern; 012 013import net.sf.cpsolver.coursett.Constants; 014import net.sf.cpsolver.coursett.model.Lecture; 015import net.sf.cpsolver.coursett.model.Placement; 016import net.sf.cpsolver.ifs.model.WeakeningConstraint; 017import net.sf.cpsolver.ifs.util.ToolBox; 018 019/** 020 * 021 * The MaxBreaks constraint limits the number of blocks of non back-to-back classes of an instructor on a day.<br> 022 * It has two parameters: a maximal number of breaks and a minimal length of a break between two classes not to be considered in the same block.<br> 023 * Reference _MaxBreaks:1:30_ translates to a maximum number of one break (two blocks) on a day of classes not more than 30 minutes a part.<br> 024 * 025 * @version CourseTT 1.2 (University Course Timetabling)<br> 026 * Copyright (C) 2013 Tomáš Müller<br> 027 * <br> 028 * This library is free software; you can redistribute it and/or modify 029 * it under the terms of the GNU Lesser General Public License as 030 * published by the Free Software Foundation; either version 3 of the 031 * License, or (at your option) any later version. <br> 032 * <br> 033 * This library is distributed in the hope that it will be useful, but 034 * WITHOUT ANY WARRANTY; without even the implied warranty of 035 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 036 * Lesser General Public License for more details. <br> 037 * <br> 038 * You should have received a copy of the GNU Lesser General Public 039 * License along with this library; if not see 040 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 041 */ 042public class MaxBreaksFlexibleConstraint extends FlexibleConstraint implements WeakeningConstraint<Lecture, Placement> { 043 private int iMaxBreakBetweenBTB; 044 private int iMaxBlocksOnADay; 045 private Map<Lecture, Placement> iWeakAssignment = new HashMap<Lecture, Placement>(); 046 047 public MaxBreaksFlexibleConstraint(Long id, String owner, String preference, String reference) { 048 super(id, owner, preference, reference); 049 050 Matcher matcher = Pattern.compile(FlexibleConstraintType.MAX_BREAKS.getPattern()).matcher(reference); 051 if (matcher.find()) { 052 iMaxBlocksOnADay = 1 + Integer.parseInt(matcher.group(2)); 053 iMaxBreakBetweenBTB = Integer.parseInt(matcher.group(3)) / Constants.SLOT_LENGTH_MIN; 054 iConstraintType = FlexibleConstraintType.MAX_BREAKS; 055 } 056 } 057 058 public List<Block> getBlocks(int dayCode, Set<Placement> conflicts, Placement value, HashMap<Lecture, Placement> assignments, BitSet week) { 059 List<Placement> toBeSorted = new ArrayList<Placement>(getRelevantPlacements(dayCode, conflicts, value, assignments, week)); 060 Collections.sort(toBeSorted, new PlacementTimeComparator()); 061 062 return mergeToBlocks(toBeSorted, iMaxBreakBetweenBTB); 063 } 064 065 @Override 066 public double getNrViolations(Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) { 067 int penalty = 0; 068 // constraint is checked for every day in week 069 for (int dayCode : Constants.DAY_CODES) { 070 // constraint is checked for every week in semester (or for the whole semester) 071 for (BitSet week : getWeeks()) { 072 // each blocks contains placements which are BTB 073 List<Block> blocks = getBlocks(dayCode, null, null, assignments, week); 074 // too many blocks -> increase penalty 075 if (blocks.size() > iMaxBlocksOnADay) 076 penalty += (blocks.size() - iMaxBlocksOnADay) * (blocks.size() - iMaxBlocksOnADay); 077 } 078 } 079 return penalty; 080 } 081 082 @Override 083 public void computeConflicts(Placement value, Set<Placement> conflicts) { 084 if (!isHard()) return; 085 086 if (value.equals(iWeakAssignment.get(value.variable()))) { 087 for (Lecture v: variables()) 088 if (v.getAssignment() == null && !v.equals(value.variable())) { 089 // incomplete and week -- do not check for conflicts just yet 090 return; 091 } 092 } 093 094 // constraint is checked for every day in week 095 for (int dayCode : Constants.DAY_CODES) { 096 if ((value.getTimeLocation().getDayCode() & dayCode) == 0) continue; // ignore other days 097 // constraint is checked for every week in semester (or for the whole semester) 098 for (BitSet week : getWeeks()) { 099 if (week != null && !week.intersects(value.getTimeLocation().getWeekCode())) continue; // ignore other weeks 100 // each blocks contains placements which are BTB 101 List<Block> blocks = getBlocks(dayCode, conflicts, value, null, week); 102 while (blocks.size() > iMaxBlocksOnADay) { 103 // too many blocks -> identify adepts for unassignment 104 List<Block> adepts = new ArrayList<Block>(); int size = 0; 105 for (Block block: blocks) { 106 if (block.getPlacements().contains(value)) continue; // skip block containing given value 107 // select adepts of the smallest size 108 if (adepts.isEmpty() || size > block.getPlacements().size()) { 109 adepts.clear(); 110 adepts.add(block); 111 size = block.getPlacements().size(); 112 } else if (size == block.getPlacements().size()) { 113 adepts.add(block); 114 } 115 } 116 117 // pick one randomly 118 Block block = ToolBox.random(adepts); 119 blocks.remove(block); 120 for (Placement conflict: block.getPlacements()) 121 if (conflict.equals(conflict.variable().getAssignment())) 122 conflicts.add(conflict); 123 } 124 } 125 } 126 } 127 128 @Override 129 public void weaken() { 130 } 131 132 @Override 133 public void weaken(Placement value) { 134 if (isHard()) 135 iWeakAssignment.put(value.variable(), value); 136 } 137 138 @Override 139 public void assigned(long iteration, Placement value) { 140 super.assigned(iteration, value); 141 if (isHard()) 142 iWeakAssignment.remove(value.variable()); 143 } 144}