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