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