001 package net.sf.cpsolver.exam.neighbours;
002
003 import java.util.Set;
004 import java.util.Vector;
005
006 import net.sf.cpsolver.exam.model.Exam;
007 import net.sf.cpsolver.exam.model.ExamModel;
008 import net.sf.cpsolver.exam.model.ExamPeriodPlacement;
009 import net.sf.cpsolver.exam.model.ExamPlacement;
010 import net.sf.cpsolver.exam.model.ExamRoomPlacement;
011 import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
012 import net.sf.cpsolver.ifs.model.Neighbour;
013 import net.sf.cpsolver.ifs.solution.Solution;
014 import net.sf.cpsolver.ifs.solver.Solver;
015 import net.sf.cpsolver.ifs.util.DataProperties;
016 import net.sf.cpsolver.ifs.util.ToolBox;
017
018 /**
019 * Try to swap a room between two exams. An exam is selected randomly, a different (available)
020 * room is randomly selected for the exam -- the exam is assigned into the new room (if the room is
021 * used, it tries to swap the rooms between the selected exam and the one that is using it).
022 * If an exam is assigned into two or more rooms, only one room is swapped at a time.
023 * <br><br>
024 *
025 * @version
026 * ExamTT 1.1 (Examination Timetabling)<br>
027 * Copyright (C) 2008 Tomáš Müller<br>
028 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
029 * Lazenska 391, 76314 Zlin, Czech Republic<br>
030 * <br>
031 * This library is free software; you can redistribute it and/or
032 * modify it under the terms of the GNU Lesser General Public
033 * License as published by the Free Software Foundation; either
034 * version 2.1 of the License, or (at your option) any later version.
035 * <br><br>
036 * This library is distributed in the hope that it will be useful,
037 * but WITHOUT ANY WARRANTY; without even the implied warranty of
038 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
039 * Lesser General Public License for more details.
040 * <br><br>
041 * You should have received a copy of the GNU Lesser General Public
042 * License along with this library; if not, write to the Free Software
043 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
044 */
045 public class ExamRoomMove implements NeighbourSelection {
046 private boolean iCheckStudentConflicts = false;
047 private boolean iCheckDistributionConstraints = true;
048
049 /**
050 * Constructor
051 * @param properties problem properties
052 */
053 public ExamRoomMove(DataProperties properties) {
054 iCheckStudentConflicts = properties.getPropertyBoolean("ExamRoomMove.CheckStudentConflicts", iCheckStudentConflicts);
055 iCheckDistributionConstraints = properties.getPropertyBoolean("ExamRoomMove.CheckDistributionConstraints", iCheckDistributionConstraints);
056 }
057
058 /**
059 * Initialization
060 */
061 public void init(Solver solver) {}
062
063 /**
064 * Select an exam randomly,
065 * select an available period randomly (if it is not assigned, from {@link Exam#getPeriodPlacements()}),
066 * select rooms using {@link Exam#findRoomsRandom(ExamPeriodPlacement)}
067 */
068 public Neighbour selectNeighbour(Solution solution) {
069 ExamModel model = (ExamModel)solution.getModel();
070 Exam exam = (Exam)ToolBox.random(model.variables());
071 if (exam.getMaxRooms()<=0) return null;
072 ExamPlacement placement = (ExamPlacement)exam.getAssignment();
073 ExamPeriodPlacement period = (placement!=null?placement.getPeriodPlacement():(ExamPeriodPlacement)ToolBox.random(exam.getPeriodPlacements()));
074 if (iCheckStudentConflicts && placement==null && exam.countStudentConflicts(period)>0) return null;
075 if (iCheckDistributionConstraints && placement==null && !exam.checkDistributionConstraints(period)) return null;
076 Set rooms = (placement!=null?placement.getRoomPlacements():exam.findBestAvailableRooms(period));
077 if (rooms==null || rooms.isEmpty()) return null;
078 if (placement==null)
079 placement = new ExamPlacement(exam, period, rooms);
080 Vector roomVect = new Vector(rooms);
081 int rx = ToolBox.random(roomVect.size());
082 for (int r=0;r<roomVect.size();r++) {
083 ExamRoomPlacement current = (ExamRoomPlacement)roomVect.elementAt((r+rx)%roomVect.size());
084 int mx = ToolBox.random(exam.getRoomPlacements().size());
085 for (int m=0;m<exam.getRoomPlacements().size();m++) {
086 ExamRoomPlacement swap = (ExamRoomPlacement)exam.getRoomPlacements().elementAt((m+mx)%exam.getRoomPlacements().size());
087 ExamRoomSwapNeighbour n = new ExamRoomSwapNeighbour(placement, current, swap);
088 if (n.canDo()) return n;
089 }
090 }
091 rooms = exam.findRoomsRandom(period);
092 if (rooms==null) return null;
093 return new ExamSimpleNeighbour(new ExamPlacement(exam, period, rooms));
094 }
095 }