001package org.cpsolver.exam.model; 002 003import java.util.ArrayList; 004import java.util.Collection; 005import java.util.Collections; 006import java.util.Comparator; 007import java.util.HashSet; 008import java.util.HashMap; 009import java.util.Iterator; 010import java.util.List; 011import java.util.Locale; 012import java.util.Map; 013import java.util.Set; 014import java.util.TreeSet; 015 016 017import org.apache.log4j.Logger; 018import org.cpsolver.exam.criteria.DistributionPenalty; 019import org.cpsolver.exam.criteria.ExamRotationPenalty; 020import org.cpsolver.exam.criteria.RoomPenalty; 021import org.cpsolver.exam.criteria.RoomSizePenalty; 022import org.cpsolver.exam.criteria.RoomSplitPenalty; 023import org.cpsolver.ifs.assignment.Assignment; 024import org.cpsolver.ifs.model.Constraint; 025import org.cpsolver.ifs.model.Model; 026import org.cpsolver.ifs.model.Variable; 027import org.cpsolver.ifs.util.Progress; 028import org.cpsolver.ifs.util.ToolBox; 029 030/** 031 * Representation of an exam (problem variable). Each exam has defined a length 032 * (in minutes), type (whether it is a section or a course exam), seating type 033 * (whether it requires normal or alternate seating) and a maximal number of 034 * rooms. If the maximal number of rooms is zero, the exam will be timetabled 035 * only in time (it does not require a room). <br> 036 * <br> 037 * An exam can be only assigned to a period {@link ExamPeriod} that is long 038 * enough (see {@link ExamPeriod#getLength()}) and that is available for the 039 * exam (see {@link Exam#getPeriodPlacements()}). <br> 040 * <br> 041 * A set of rooms that are available in the given period (see 042 * {@link ExamRoom#isAvailable(ExamPeriod)}, 043 * {@link ExamRoomPlacement#isAvailable(ExamPeriod)}), and which together cover 044 * the size of exam (number of students attending the exam) has to be assigned 045 * to an exam. Based on the type of seating (see {@link Exam#hasAltSeating()}), 046 * either room sizes (see {@link ExamRoom#getSize()}) or alternative seating 047 * sizes (see {@link ExamRoom#getAltSize()}) are used. An exam has a list of 048 * available rooms with their penalties assiciated with (see 049 * {@link Exam#getRoomPlacements()}). <br> 050 * <br> 051 * Various penalties for an assignment of a period or a set of rooms may apply. 052 * See {@link ExamPlacement} for more details. <br> 053 * <br> 054 * 055 * @version ExamTT 1.3 (Examination Timetabling)<br> 056 * Copyright (C) 2008 - 2014 Tomas Muller<br> 057 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 058 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 059 * <br> 060 * This library is free software; you can redistribute it and/or modify 061 * it under the terms of the GNU Lesser General Public License as 062 * published by the Free Software Foundation; either version 3 of the 063 * License, or (at your option) any later version. <br> 064 * <br> 065 * This library is distributed in the hope that it will be useful, but 066 * WITHOUT ANY WARRANTY; without even the implied warranty of 067 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 068 * Lesser General Public License for more details. <br> 069 * <br> 070 * You should have received a copy of the GNU Lesser General Public 071 * License along with this library; if not see 072 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 073 */ 074public class Exam extends Variable<Exam, ExamPlacement> { 075 private static boolean sAlterMaxSize = false; 076 private static Logger sLog = Logger.getLogger(Exam.class); 077 protected static java.text.DecimalFormat sDoubleFormat = new java.text.DecimalFormat("0.00", 078 new java.text.DecimalFormatSymbols(Locale.US)); 079 080 private ArrayList<ExamStudent> iStudents = new ArrayList<ExamStudent>(); 081 private ArrayList<ExamInstructor> iInstructors = new ArrayList<ExamInstructor>(); 082 private ArrayList<ExamDistributionConstraint> iDistConstraints = new ArrayList<ExamDistributionConstraint>(); 083 084 private boolean iAllowDirectConflicts = true; 085 086 private String iName = null; 087 private int iLength = 0; 088 private int iMaxRooms = 0; 089 private int iMinSize = 0; 090 private boolean iAltSeating = false; 091 private int iAveragePeriod = -1; 092 private Integer iSize = null; 093 private Integer iPrintOffset = null; 094 095 private ArrayList<ExamOwner> iOwners = new ArrayList<ExamOwner>(); 096 private List<ExamPeriodPlacement> iPeriodPlacements = null; 097 private List<ExamRoomPlacement> iRoomPlacements = null; 098 private List<ExamRoomPlacement> iRoomPreferredPlacements = null; 099 100 /** 101 * Constructor 102 * 103 * @param id 104 * exam unique id 105 * @param name exam name 106 * @param length 107 * exam length in minutes 108 * @param altSeating 109 * true if alternative seating is requested 110 * @param maxRooms 111 * maximum number of rooms to be used 112 * @param minSize 113 * minimal size of rooms into which an exam can be assigned (see 114 * {@link Exam#getSize()}) 115 * @param periodPlacements 116 * list of periods and their penalties 117 * {@link ExamPeriodPlacement} into which an exam can be assigned 118 * @param roomPlacements 119 * list of rooms and their penalties {@link ExamRoomPlacement} 120 * into which an exam can be assigned 121 */ 122 public Exam(long id, String name, int length, boolean altSeating, int maxRooms, int minSize, 123 java.util.List<ExamPeriodPlacement> periodPlacements, java.util.List<ExamRoomPlacement> roomPlacements) { 124 super(); 125 iId = id; 126 iName = name; 127 iLength = length; 128 iAltSeating = altSeating; 129 iMaxRooms = maxRooms; 130 iMinSize = minSize; 131 iPeriodPlacements = new ArrayList<ExamPeriodPlacement>(periodPlacements); 132 Collections.sort(iPeriodPlacements, new Comparator<ExamPeriodPlacement>() { 133 @Override 134 public int compare(ExamPeriodPlacement p1, ExamPeriodPlacement p2) { 135 return p1.getPeriod().compareTo(p2.getPeriod()); 136 } 137 }); 138 iRoomPlacements = new ArrayList<ExamRoomPlacement>(roomPlacements); 139 Collections.sort(iRoomPlacements, new Comparator<ExamRoomPlacement>() { 140 @Override 141 public int compare(ExamRoomPlacement p1, ExamRoomPlacement p2) { 142 int cmp = -Double.compare(p1.getSize(hasAltSeating()), p2.getSize(hasAltSeating())); 143 if (cmp != 0) 144 return cmp; 145 return p1.getRoom().compareTo(p2.getRoom()); 146 } 147 }); 148 } 149 150 /** 151 * Exam size, it is bigger from {@link Exam#getMinSize()} and the number of 152 * students enrolled into the exam {@link Exam#getStudents()}. If 153 * {@link Exam#getMaxRooms()} is greater than zero, an exam must be assigned 154 * into rooms which overall size (or alternative seating size if 155 * {@link Exam#hasAltSeating()}) must be equal or greater than this size. 156 * @return examination size 157 */ 158 public int getSize() { 159 return (iSize == null ? Math.max(iMinSize, getStudents().size()) : iSize.intValue()); 160 } 161 162 /** 163 * Override exam size with given value (revert to default when null) 164 * @param size examination size override 165 */ 166 public void setSizeOverride(Integer size) { 167 iSize = size; 168 } 169 170 /** 171 * Override exam size with given value (revert to default when null) 172 * @return examination size override 173 */ 174 public Integer getSizeOverride() { 175 return iSize; 176 } 177 178 /** 179 * Print offset -- for reporting purposes 180 * @return print offset in minutes 181 */ 182 public Integer getPrintOffset() { 183 return iPrintOffset; 184 } 185 186 /** 187 * Print offset -- for reporting purposes 188 * @param printOffset print offset in minutes 189 */ 190 public void setPrintOffset(Integer printOffset) { 191 iPrintOffset = printOffset; 192 } 193 194 /** 195 * Minimal exam size, see {@link Exam#getSize()} 196 * @return minimal examination size 197 */ 198 public int getMinSize() { 199 return iMinSize; 200 } 201 202 /** 203 * Minimal exam size, see {@link Exam#getSize()} 204 * @param minSize minimal examination size 205 */ 206 public void setMinSize(int minSize) { 207 iMinSize = minSize; 208 } 209 210 /** 211 * Values (assignment of a period and a set of rooms) 212 * 213 * @return list of {@link ExamPlacement} 214 */ 215 @Override 216 public List<ExamPlacement> values(Assignment<Exam, ExamPlacement> assignment) { 217 if (super.values(assignment) == null) 218 init(); 219 return super.values(assignment); 220 } 221 222 /** 223 * Return list of possible room placements. 224 * 225 * @return list of {@link ExamRoomPlacement} 226 */ 227 public List<ExamRoomPlacement> getRoomPlacements() { 228 return iRoomPlacements; 229 } 230 231 /** 232 * Return list of possible room placements that are strongly preferred. 233 * 234 * @return list of {@link ExamRoomPlacement} 235 */ 236 public synchronized List<ExamRoomPlacement> getPreferredRoomPlacements() { 237 if (iRoomPreferredPlacements == null) { 238 iRoomPreferredPlacements = new ArrayList<ExamRoomPlacement>(); 239 for (ExamRoomPlacement room: iRoomPlacements) { 240 if (room.getPenalty() < -2) 241 iRoomPreferredPlacements.add(room); 242 } 243 } 244 return iRoomPreferredPlacements; 245 } 246 247 /** 248 * Return list of possible period placements. 249 * 250 * @return list of {@link ExamPeriodPlacement} 251 */ 252 public List<ExamPeriodPlacement> getPeriodPlacements() { 253 return iPeriodPlacements; 254 } 255 256 /** 257 * Initialize exam's domain. 258 */ 259 private boolean init() { 260 if (sAlterMaxSize && iRoomPlacements.size() > 50) { 261 ExamRoomPlacement med = iRoomPlacements.get(Math.min(50, iRoomPlacements.size() / 2)); 262 setMaxRooms(Math.min(getMaxRooms(), 1 + getSize() / med.getSize(hasAltSeating()))); 263 } 264 ArrayList<ExamPlacement> values = new ArrayList<ExamPlacement>(); 265 if (getMaxRooms() == 0) { 266 for (ExamPeriodPlacement periodPlacement : getPeriodPlacements()) { 267 values.add(new ExamPlacement(this, periodPlacement, new HashSet<ExamRoomPlacement>())); 268 } 269 } else { 270 if (getRoomPlacements().isEmpty()) { 271 sLog.error(" Exam " + getName() + " has no rooms."); 272 setValues(new ArrayList<ExamPlacement>(0)); 273 return false; 274 } 275 for (ExamPeriodPlacement periodPlacement : getPeriodPlacements()) { 276 TreeSet<RoomSet> roomSets = new TreeSet<RoomSet>(); 277 genRoomSets(periodPlacement.getPeriod(), Math.min(100, iRoomPlacements.size()), roomSets, 0, 278 getMaxRooms(), new HashSet<ExamRoomPlacement>(), 0, 0); 279 for (RoomSet roomSet : roomSets) { 280 values.add(new ExamPlacement(this, periodPlacement, roomSet.rooms())); 281 } 282 } 283 } 284 if (values.isEmpty()) 285 sLog.error("Exam " + getName() + " has no placement."); 286 setValues(values); 287 return !values.isEmpty(); 288 } 289 290 private void genRoomSets(ExamPeriod period, int maxRoomSets, TreeSet<RoomSet> roomSets, int roomIdx, int maxRooms, 291 Set<ExamRoomPlacement> roomsSoFar, int sizeSoFar, int penaltySoFar) { 292 if (sizeSoFar >= getSize()) { 293 double penalty = 294 getModel().getCriterion(RoomSplitPenalty.class).getWeight() * (roomsSoFar.size() - 1) * (roomsSoFar.size() - 1) + 295 getModel().getCriterion(RoomSizePenalty.class).getWeight() * (sizeSoFar - getSize()) + 296 getModel().getCriterion(RoomPenalty.class).getWeight() * penaltySoFar; 297 if (roomSets.size() >= maxRoomSets) { 298 RoomSet last = roomSets.last(); 299 if (penalty < last.penalty()) { 300 roomSets.remove(last); 301 roomSets.add(new RoomSet(roomsSoFar, penalty)); 302 } 303 } else 304 roomSets.add(new RoomSet(roomsSoFar, penalty)); 305 return; 306 } 307 if (!roomSets.isEmpty()) { 308 RoomSet roomSet = roomSets.first(); 309 maxRooms = Math.min(maxRooms, (1 + roomSet.rooms().size()) - roomsSoFar.size()); 310 } 311 if (maxRooms == 0) 312 return; 313 int sizeBound = sizeSoFar; 314 for (int i = 0; i < maxRooms && roomIdx + i < iRoomPlacements.size(); i++) 315 sizeBound += iRoomPlacements.get(roomIdx + i).getSize(hasAltSeating()); 316 while (roomIdx < iRoomPlacements.size()) { 317 if (sizeBound < getSize()) 318 break; 319 ExamRoomPlacement room = iRoomPlacements.get(roomIdx); 320 if (room.isAvailable(period)) { 321 roomsSoFar.add(room); 322 genRoomSets(period, maxRoomSets, roomSets, roomIdx + 1, maxRooms - 1, roomsSoFar, 323 sizeSoFar + room.getSize(hasAltSeating()), penaltySoFar + room.getPenalty(period)); 324 roomsSoFar.remove(room); 325 } 326 sizeBound -= room.getSize(hasAltSeating()); 327 if (roomIdx + maxRooms < iRoomPlacements.size()) 328 sizeBound += iRoomPlacements.get(roomIdx + maxRooms).getSize(hasAltSeating()); 329 roomIdx++; 330 if (roomSets.size() == maxRoomSets) { 331 RoomSet last = roomSets.last(); 332 if (last.rooms().size() < roomsSoFar.size() + 1) 333 return; 334 } 335 } 336 } 337 338 private class RoomSet implements Comparable<RoomSet> { 339 private Set<ExamRoomPlacement> iRooms; 340 private double iPenalty; 341 342 public RoomSet(Set<ExamRoomPlacement> rooms, double penalty) { 343 iRooms = new HashSet<ExamRoomPlacement>(rooms); 344 iPenalty = penalty; 345 } 346 347 public Set<ExamRoomPlacement> rooms() { 348 return iRooms; 349 } 350 351 public double penalty() { 352 return iPenalty; 353 } 354 355 public int compareTo(Set<ExamRoomPlacement> rooms, double penalty) { 356 int cmp = Double.compare(iRooms.size(), rooms.size()); 357 if (cmp != 0) 358 return cmp; 359 cmp = Double.compare(penalty(), penalty); 360 if (cmp != 0) 361 return cmp; 362 return rooms().toString().compareTo(rooms.toString()); 363 } 364 365 @Override 366 public int compareTo(RoomSet r) { 367 return compareTo(r.rooms(), r.penalty()); 368 } 369 } 370 371 /** 372 * True if alternative seating is required ({@link ExamRoom#getAltSize()} is 373 * to be used), false if normal seating is required ( 374 * {@link ExamRoom#getSize()} is to be used). 375 * 376 * @return true if alternative seating is required, false otherwise 377 */ 378 public boolean hasAltSeating() { 379 return iAltSeating; 380 } 381 382 /** 383 * Length of the exam in minutes. The assigned period has to be of the same 384 * or greater length. 385 * 386 * @return length of the exam in minutes 387 */ 388 public int getLength() { 389 return iLength; 390 } 391 392 /** 393 * Set average period. This represents an average period that the exam was 394 * assigned to in the past. If set, it is used in exam rotation penalty 395 * {@link ExamRotationPenalty} in order to put more weight on 396 * exams that were badly assigned last time(s) and ensuring some form of 397 * fairness. 398 * 399 * @param period 400 * average period 401 */ 402 public void setAveragePeriod(int period) { 403 iAveragePeriod = period; 404 } 405 406 /** 407 * Average period. This represents an average period that the exam was 408 * assigned to in the past. If set, it is used in exam rotation penalty 409 * {@link ExamRotationPenalty} in order to put more weight on 410 * exams that were badly assigned last time(s) and ensuring some form of 411 * fairness. 412 * 413 * @return average period 414 */ 415 public int getAveragePeriod() { 416 return iAveragePeriod; 417 } 418 419 /** 420 * True if there is an average period assigned to the exam. This represents 421 * an average period that the exam was assigned to in the past. If set, it 422 * is used in exam rotation penalty 423 * {@link ExamRotationPenalty} in order to put more weight on 424 * exams that were badly assigned last time(s) and ensuring some form of 425 * fairness. 426 * @return true if the exam has an average period set 427 */ 428 public boolean hasAveragePeriod() { 429 return iAveragePeriod >= 0; 430 } 431 432 /** 433 * True if a direct student conflict is allowed, see 434 * {@link ExamStudent#canConflict(Exam, Exam)} 435 * 436 * @return true if a direct student conflict is allowed 437 */ 438 public boolean isAllowDirectConflicts() { 439 return iAllowDirectConflicts; 440 } 441 442 /** 443 * Set whether a direct student conflict is allowed, see 444 * {@link ExamStudent#canConflict(Exam, Exam)} 445 * 446 * @param allowDirectConflicts 447 * true if a direct student conflict is allowed 448 */ 449 public void setAllowDirectConflicts(boolean allowDirectConflicts) { 450 iAllowDirectConflicts = allowDirectConflicts; 451 } 452 453 /** 454 * Adds a constraint. Called automatically when the constraint is added to 455 * the model, i.e., {@link Model#addConstraint(Constraint)} is called. 456 * 457 * @param constraint 458 * added constraint 459 */ 460 @Override 461 public void addContstraint(Constraint<Exam, ExamPlacement> constraint) { 462 if (constraint instanceof ExamStudent) 463 iStudents.add((ExamStudent) constraint); 464 if (constraint instanceof ExamDistributionConstraint) 465 iDistConstraints.add((ExamDistributionConstraint) constraint); 466 if (constraint instanceof ExamInstructor) 467 iInstructors.add((ExamInstructor) constraint); 468 super.addContstraint(constraint); 469 } 470 471 /** 472 * Removes a constraint. Called automatically when the constraint is removed 473 * from the model, i.e., {@link Model#removeConstraint(Constraint)} is 474 * called. 475 * 476 * @param constraint 477 * added constraint 478 */ 479 @Override 480 public void removeContstraint(Constraint<Exam, ExamPlacement> constraint) { 481 if (constraint instanceof ExamStudent) 482 iStudents.remove(constraint); 483 if (constraint instanceof ExamDistributionConstraint) 484 iDistConstraints.remove(constraint); 485 if (constraint instanceof ExamInstructor) 486 iInstructors.remove(constraint); 487 super.removeContstraint(constraint); 488 } 489 490 /** 491 * List of students that are enrolled in the exam 492 * 493 * @return list of {@link ExamStudent} 494 */ 495 public List<ExamStudent> getStudents() { 496 return iStudents; 497 } 498 499 /** 500 * List of distribution constraints that this exam is involved in 501 * 502 * @return list of {@link ExamDistributionConstraint} 503 */ 504 public List<ExamDistributionConstraint> getDistributionConstraints() { 505 return iDistConstraints; 506 } 507 508 /** 509 * List of instructors that are assigned to this exam 510 * 511 * @return list of {@link ExamInstructor} 512 */ 513 public List<ExamInstructor> getInstructors() { 514 return iInstructors; 515 } 516 517 /** 518 * Check all distribution constraint that this exam is involved in 519 * 520 * @param assignment current assignment 521 * @param period 522 * a period to be assigned to this exam 523 * @return true, if there is no assignment of some other exam in conflict 524 * with the given period 525 */ 526 public boolean checkDistributionConstraints(Assignment<Exam, ExamPlacement> assignment, ExamPeriodPlacement period) { 527 for (ExamDistributionConstraint dc : iDistConstraints) { 528 if (!dc.isHard()) 529 continue; 530 boolean before = true; 531 for (Exam exam : dc.variables()) { 532 if (exam.equals(this)) { 533 before = false; 534 continue; 535 } 536 ExamPlacement placement = assignment.getValue(exam); 537 if (placement == null) 538 continue; 539 switch (dc.getType()) { 540 case ExamDistributionConstraint.sDistSamePeriod: 541 if (period.getIndex() != placement.getPeriod().getIndex()) 542 return false; 543 break; 544 case ExamDistributionConstraint.sDistDifferentPeriod: 545 if (period.getIndex() == placement.getPeriod().getIndex()) 546 return false; 547 break; 548 case ExamDistributionConstraint.sDistPrecedence: 549 if (before) { 550 if (period.getIndex() <= placement.getPeriod().getIndex()) 551 return false; 552 } else { 553 if (period.getIndex() >= placement.getPeriod().getIndex()) 554 return false; 555 } 556 break; 557 case ExamDistributionConstraint.sDistPrecedenceRev: 558 if (before) { 559 if (period.getIndex() >= placement.getPeriod().getIndex()) 560 return false; 561 } else { 562 if (period.getIndex() <= placement.getPeriod().getIndex()) 563 return false; 564 } 565 break; 566 567 case ExamDistributionConstraint.sDistSameDay: 568 if (period.getPeriod().getDay() != placement.getPeriod().getDay()) 569 return false; 570 break; 571 case ExamDistributionConstraint.sDistDifferentDay: 572 if (period.getPeriod().getDay() == placement.getPeriod().getDay()) 573 return false; 574 break; 575 } 576 } 577 } 578 return true; 579 } 580 581 /** 582 * Check all distribution constraint that this exam is involved in 583 * 584 * @param assignment current assignment 585 * @param room 586 * a room to be assigned to this exam 587 * @return true, if there is no assignment of some other exam in conflict 588 * with the given room 589 */ 590 public boolean checkDistributionConstraints(Assignment<Exam, ExamPlacement> assignment, ExamRoomPlacement room) { 591 for (ExamDistributionConstraint dc : iDistConstraints) { 592 if (!dc.isHard()) 593 continue; 594 for (Exam exam : dc.variables()) { 595 if (exam.equals(this)) 596 continue; 597 ExamPlacement placement = assignment.getValue(exam); 598 if (placement == null) 599 continue; 600 switch (dc.getType()) { 601 case ExamDistributionConstraint.sDistSameRoom: 602 if (!placement.getRoomPlacements().contains(room)) 603 return false; 604 break; 605 case ExamDistributionConstraint.sDistDifferentRoom: 606 if (placement.getRoomPlacements().contains(room)) 607 return false; 608 break; 609 } 610 } 611 } 612 return true; 613 } 614 615 /** 616 * Check all soft distribution constraint that this exam is involved in 617 * 618 * @param assignment current assignment 619 * @param room 620 * a room to be assigned to this exam 621 * @return sum of penalties of violated distribution constraints 622 */ 623 public int getDistributionConstraintPenalty(Assignment<Exam, ExamPlacement> assignment, ExamRoomPlacement room) { 624 int penalty = 0; 625 for (ExamDistributionConstraint dc : iDistConstraints) { 626 if (dc.isHard()) 627 continue; 628 for (Exam exam : dc.variables()) { 629 if (exam.equals(this)) 630 continue; 631 ExamPlacement placement = assignment.getValue(exam); 632 if (placement == null) 633 continue; 634 switch (dc.getType()) { 635 case ExamDistributionConstraint.sDistSameRoom: 636 if (!placement.getRoomPlacements().contains(room)) 637 penalty += dc.getWeight(); 638 break; 639 case ExamDistributionConstraint.sDistDifferentRoom: 640 if (placement.getRoomPlacements().contains(room)) 641 penalty += dc.getWeight(); 642 break; 643 } 644 } 645 } 646 return penalty; 647 } 648 649 /** 650 * Maximal number of rooms that can be assigned to the exam 651 * 652 * @return maximal number of rooms that can be assigned to the exam 653 */ 654 public int getMaxRooms() { 655 return iMaxRooms; 656 } 657 658 /** 659 * Set maximal number of rooms that can be assigned to the exam 660 * 661 * @param maxRooms 662 * maximal number of rooms that can be assigned to the exam 663 */ 664 public void setMaxRooms(int maxRooms) { 665 iMaxRooms = maxRooms; 666 } 667 668 /** 669 * Find best available rooms for the exam in the given period. First of all, 670 * it tries to find the minimal number of rooms that cover the size of the 671 * exam. Among these, a set of rooms of total smallest size is preferred. If 672 * the original room is available and of enough size, it is returned. All 673 * necessary checks are made (availability of rooms, room penalties, room 674 * sizes etc.). 675 * 676 * @param assignment current assignment 677 * @param period 678 * given period. 679 * @return best available rooms for the exam in the given period, null if 680 * there is no valid assignment 681 */ 682 public Set<ExamRoomPlacement> findBestAvailableRooms(Assignment<Exam, ExamPlacement> assignment, ExamPeriodPlacement period) { 683 if (getMaxRooms() == 0) 684 return new HashSet<ExamRoomPlacement>(); 685 double sw = getModel().getCriterion(RoomSizePenalty.class).getWeight(); 686 double pw = getModel().getCriterion(RoomPenalty.class).getWeight(); 687 double cw = getModel().getCriterion(DistributionPenalty.class).getWeight(); 688 ExamRoomSharing sharing = ((ExamModel) getModel()).getRoomSharing(); 689 loop: for (int nrRooms = 1; nrRooms <= getMaxRooms(); nrRooms++) { 690 HashSet<ExamRoomPlacement> rooms = new HashSet<ExamRoomPlacement>(); 691 int size = 0; 692 while (rooms.size() < nrRooms && size < getSize()) { 693 int minSize = (getSize() - size) / (nrRooms - rooms.size()); 694 ExamRoomPlacement best = null; 695 double bestWeight = 0; 696 int bestSize = 0; 697 for (ExamRoomPlacement room : getRoomPlacements()) { 698 if (!room.isAvailable(period.getPeriod())) 699 continue; 700 if (nrRooms == 1 && sharing != null) { 701 if (sharing.inConflict(this, room.getRoom().getPlacements(assignment, period.getPeriod()), room.getRoom())) 702 continue; 703 } else { 704 if (!room.getRoom().getPlacements(assignment, period.getPeriod()).isEmpty()) 705 continue; 706 } 707 if (rooms.contains(room)) 708 continue; 709 if (!checkDistributionConstraints(assignment, room)) 710 continue; 711 int s = room.getSize(hasAltSeating()); 712 if (s < minSize) 713 break; 714 int p = room.getPenalty(period.getPeriod()); 715 double w = pw * p + sw * (s - minSize) + cw * getDistributionConstraintPenalty(assignment, room); 716 double d = 0; 717 if (!rooms.isEmpty()) { 718 for (ExamRoomPlacement r : rooms) { 719 d += r.getDistanceInMeters(room); 720 } 721 w += d / rooms.size(); 722 } 723 if (best == null || bestWeight > w) { 724 best = room; 725 bestSize = s; 726 bestWeight = w; 727 } 728 } 729 if (best == null) 730 continue loop; 731 rooms.add(best); 732 size += bestSize; 733 } 734 if (size >= getSize()) 735 return rooms; 736 } 737 return null; 738 } 739 740 /** 741 * Randomly find a set of available rooms for the exam in the given period. 742 * First of all, it tries to find the minimal number of rooms that cover the 743 * size of the exam. Among these, a set of rooms of total smallest size is 744 * preferred. All necessary checks are made (availability of rooms, room 745 * penalties, room sizes etc.). 746 * 747 * @param assignment current assignment 748 * @param period 749 * given period. 750 * @return randomly computed set of available rooms for the exam in the 751 * given period, null if there is no valid assignment 752 */ 753 public Set<ExamRoomPlacement> findRoomsRandom(Assignment<Exam, ExamPlacement> assignment, ExamPeriodPlacement period) { 754 return findRoomsRandom(assignment, period, true); 755 } 756 757 /** 758 * Randomly find a set of available rooms for the exam in the given period. 759 * First of all, it tries to find the minimal number of rooms that cover the 760 * size of the exam. Among these, a set of rooms of total smallest size is 761 * preferred. All necessary checks are made (availability of rooms, room 762 * penalties, room sizes etc.). 763 * 764 * @param assignment current assignment 765 * @param period 766 * given period. 767 * @param checkConflicts 768 * if false, room and distribution conflicts are not checked 769 * @return randomly computed set of available rooms for the exam in the 770 * given period, null if there is no valid assignment 771 */ 772 public Set<ExamRoomPlacement> findRoomsRandom(Assignment<Exam, ExamPlacement> assignment, ExamPeriodPlacement period, boolean checkConflicts) { 773 if (getMaxRooms() == 0) 774 return new HashSet<ExamRoomPlacement>(); 775 HashSet<ExamRoomPlacement> rooms = new HashSet<ExamRoomPlacement>(); 776 int size = 0; 777 ExamRoomSharing sharing = ((ExamModel) getModel()).getRoomSharing(); 778 loop: while (rooms.size() < getMaxRooms()) { 779 int rx = ToolBox.random(getRoomPlacements().size()); 780 int minSize = (getSize() - size + (getMaxRooms() - rooms.size() - 1)) / (getMaxRooms() - rooms.size()); 781 for (int r = 0; r < getRoomPlacements().size(); r++) { 782 ExamRoomPlacement room = getRoomPlacements().get((r + rx) % getRoomPlacements().size()); 783 int s = room.getSize(hasAltSeating()); 784 if (s < minSize) 785 continue; 786 if (!room.isAvailable(period.getPeriod())) 787 continue; 788 if (checkConflicts) { 789 if (rooms.isEmpty() && sharing != null && !room.getRoom().getPlacements(assignment, period.getPeriod()).isEmpty()) { 790 if (sharing.inConflict(this, room.getRoom().getPlacements(assignment, period.getPeriod()), room.getRoom())) 791 continue; 792 } else { 793 if (!room.getRoom().getPlacements(assignment, period.getPeriod()).isEmpty()) 794 continue; 795 } 796 } 797 if (rooms.contains(room)) 798 continue; 799 if (checkConflicts && !checkDistributionConstraints(assignment, room)) 800 continue; 801 size += s; 802 rooms.add(room); 803 if (size >= getSize()) { 804 for (Iterator<ExamRoomPlacement> j = rooms.iterator(); j.hasNext();) { 805 ExamRoomPlacement rp = j.next(); 806 if (size - rp.getSize(hasAltSeating()) >= getSize()) { 807 j.remove(); 808 size -= rp.getSize(hasAltSeating()); 809 } 810 } 811 return rooms; 812 } 813 continue loop; 814 } 815 break; 816 } 817 return null; 818 } 819 820 private HashSet<Exam> iCorrelatedExams = null; 821 822 /** 823 * Number of exams that are correlated with this exam (there is at least one 824 * student attending both exams). 825 * 826 * @return number of correlated exams 827 */ 828 public int nrStudentCorrelatedExams() { 829 return getStudentCorrelatedExams().size(); 830 } 831 832 /** 833 * Exams that are correlated with this exam (there is at least one 834 * student attending both exams). 835 * 836 * @return number of correlated exams 837 */ 838 public synchronized Set<Exam> getStudentCorrelatedExams() { 839 if (iCorrelatedExams == null) { 840 iCorrelatedExams = new HashSet<Exam>(); 841 for (ExamStudent student : iStudents) { 842 iCorrelatedExams.addAll(student.variables()); 843 } 844 iCorrelatedExams.remove(this); 845 } 846 return iCorrelatedExams; 847 } 848 849 private Integer iEstimatedDomainSize = null; 850 851 private synchronized int estimatedDomainSize() { 852 if (iEstimatedDomainSize == null) { 853 int periods = getPeriodPlacements().size(); 854 int rooms = -1; 855 int split = 0; 856 while (rooms < split && split <= getMaxRooms()) { 857 rooms = 0; 858 split++; 859 for (ExamRoomPlacement room : getRoomPlacements()) { 860 if (room.getSize(hasAltSeating()) >= (getSize() / split)) 861 rooms++; 862 } 863 } 864 iEstimatedDomainSize = new Integer(periods * rooms / split); 865 } 866 return iEstimatedDomainSize.intValue(); 867 } 868 869 /** 870 * An exam with more correlated exams is preferred ( 871 * {@link Exam#nrStudentCorrelatedExams()}). If it is the same, ratio number 872 * of students / number of available periods is used. If the same, exam ids 873 * are used. 874 */ 875 @Override 876 public int compareTo(Exam o) { 877 Exam e = o; 878 int cmp = Double.compare(estimatedDomainSize(), e.estimatedDomainSize()); 879 if (cmp != 0) 880 return cmp; 881 cmp = -Double.compare(nrStudentCorrelatedExams(), e.nrStudentCorrelatedExams()); 882 if (cmp != 0) 883 return cmp; 884 cmp = -Double.compare(((double) getSize()) / getPeriodPlacements().size(), ((double) e.getSize()) 885 / e.getPeriodPlacements().size()); 886 if (cmp != 0) 887 return cmp; 888 return super.compareTo(o); 889 } 890 891 /** 892 * True, if there is a student of this exam (that does not have direct 893 * conflicts allowed, see {@link ExamStudent#canConflict(Exam, Exam)}) that 894 * attends some other exam in the given period. 895 * 896 * @param assignment current assignment 897 * @param period 898 * a period 899 * @return true if there is a student conflict 900 */ 901 public boolean hasStudentConflictWithPreAssigned(Assignment<Exam, ExamPlacement> assignment, ExamPeriod period) { 902 Map<ExamStudent, Set<Exam>> studentsOfPeriod = ((ExamModel)getModel()).getStudentsOfPeriod(assignment, period); 903 for (ExamStudent s : getStudents()) { 904 Set<Exam> exams = studentsOfPeriod.get(s); 905 if (exams == null) continue; 906 for (Exam exam : exams) { 907 if (!exam.equals(this) && !s.canConflict(this, exam)) return true; 908 } 909 } 910 return false; 911 } 912 913 /** 914 * Number of students of this exam (that does not have direct conflicts 915 * allowed, see {@link ExamStudent#canConflict(Exam, Exam)}) that attend 916 * some other exam in the given period. 917 * 918 * @param assignment current assignment 919 * @param period 920 * a period 921 * @return number of direct student conflicts that are prohibited 922 */ 923 public int countStudentConflicts(Assignment<Exam, ExamPlacement> assignment, ExamPeriodPlacement period) { 924 int conf = 0; 925 Map<ExamStudent, Set<Exam>> studentsOfPeriod = ((ExamModel)getModel()).getStudentsOfPeriod(assignment, period.getPeriod()); 926 for (ExamStudent s : getStudents()) { 927 Set<Exam> exams = studentsOfPeriod.get(s); 928 if (exams == null) continue; 929 for (Exam exam : exams) { 930 if (!exam.equals(this) && !s.canConflict(this, exam)) conf++; 931 } 932 } 933 return conf; 934 } 935 936 /** 937 * List of exams that are assigned to the given period and share one or more 938 * students with this exam (that does not have direct conflicts allowed, see 939 * {@link ExamStudent#canConflict(Exam, Exam)}). 940 * 941 * @param assignment current assignment 942 * @param period 943 * a period 944 * @return list of {@link Exam} (other than this exam, that are placed in 945 * the given period and create prohibited direct conflicts) 946 */ 947 public HashSet<Exam> getStudentConflicts(Assignment<Exam, ExamPlacement> assignment, ExamPeriod period) { 948 HashSet<Exam> conf = new HashSet<Exam>(); 949 Map<ExamStudent, Set<Exam>> studentsOfPeriod = ((ExamModel)getModel()).getStudentsOfPeriod(assignment, period); 950 for (ExamStudent s : getStudents()) { 951 Set<Exam> exams = studentsOfPeriod.get(s); 952 if (exams == null) continue; 953 for (Exam exam : exams) { 954 if (!exam.equals(this) && !s.canConflict(this, exam)) conf.add(exam); 955 } 956 } 957 return conf; 958 } 959 960 /** 961 * Allow all direct student conflict for the given period (see 962 * {@link ExamStudent#canConflict(Exam, Exam)}). 963 * 964 * @param assignment current assignment 965 * @param period 966 * a period 967 */ 968 public void allowAllStudentConflicts(Assignment<Exam, ExamPlacement> assignment, ExamPeriod period) { 969 Map<ExamStudent, Set<Exam>> studentsOfPeriod = ((ExamModel)getModel()).getStudentsOfPeriod(assignment, period); 970 for (ExamStudent s : getStudents()) { 971 Set<Exam> exams = studentsOfPeriod.get(s); 972 if (exams == null) continue; 973 for (Exam exam : exams) { 974 if (exam.equals(this)) continue; 975 exam.setAllowDirectConflicts(true); 976 setAllowDirectConflicts(true); 977 s.setAllowDirectConflicts(true); 978 } 979 } 980 } 981 982 /** 983 * String representation 984 * 985 * @return exam id (periods: number of periods, rooms: number of rooms, 986 * student: number of students, maxRooms: max rooms[, alt if 987 * alternate seating is required]) 988 */ 989 @Override 990 public String toString() { 991 return getName() + " (periods:" + getPeriodPlacements().size() + ", rooms:" + getRoomPlacements().size() 992 + ", size:" + getSize() + " ,maxRooms:" + getMaxRooms() + (hasAltSeating() ? ", alt" : "") + ")"; 993 } 994 995 /** Exam name */ 996 @Override 997 public String getName() { 998 return (hasName() ? iName : String.valueOf(getId())); 999 } 1000 1001 /** Exam name 1002 * @param name examination name 1003 **/ 1004 public void setName(String name) { 1005 iName = name; 1006 } 1007 1008 /** Exam name 1009 * @return true if the examination name is set and it is not empty 1010 **/ 1011 public boolean hasName() { 1012 return iName != null && iName.length() > 0; 1013 } 1014 1015 private HashMap<Exam, List<ExamStudent>> iJenrls = null; 1016 1017 /** 1018 * Joint enrollments 1019 * 1020 * @return table {@link Exam} (an exam that has at least one student in 1021 * common with this exam) → {@link List} (list of students in 1022 * common) 1023 */ 1024 public Map<Exam, List<ExamStudent>> getJointEnrollments() { 1025 if (iJenrls != null) 1026 return iJenrls; 1027 iJenrls = new HashMap<Exam, List<ExamStudent>>(); 1028 for (ExamStudent student : getStudents()) { 1029 for (Exam other : student.variables()) { 1030 if (other.equals(this)) 1031 continue; 1032 List<ExamStudent> students = iJenrls.get(other); 1033 if (students == null) { 1034 students = new ArrayList<ExamStudent>(); 1035 iJenrls.put(other, students); 1036 } 1037 students.add(student); 1038 } 1039 } 1040 return iJenrls; 1041 } 1042 1043 /** 1044 * Courses and/or sections that are having this exam 1045 * 1046 * @return list of {@link ExamOwner} 1047 */ 1048 public List<ExamOwner> getOwners() { 1049 return iOwners; 1050 } 1051 1052 /** 1053 * Courses/sections of this exam into which the given student is enrolled 1054 * into 1055 * 1056 * @param student 1057 * a student that is enrolled into this exam 1058 * @return list of courses/sections {@link ExamOwner} which are having this 1059 * exam with the given student enrolled in 1060 */ 1061 public Collection<ExamOwner> getOwners(ExamStudent student) { 1062 Collection<ExamOwner> ret = new ArrayList<ExamOwner>(); 1063 for (ExamOwner owner : iOwners) { 1064 if (owner.getStudents().contains(student)) 1065 ret.add(owner); 1066 } 1067 return ret; 1068 } 1069 1070 /** 1071 * Courses/sections of this exam into which the given instructor is enrolled 1072 * into 1073 * 1074 * @param instructor 1075 * an instructor that is enrolled into this exam 1076 * @return list of courses/sections {@link ExamOwner} which are having this 1077 * exam with the given instructor enrolled in 1078 */ 1079 public Collection<ExamOwner> getOwners(ExamInstructor instructor) { 1080 Collection<ExamOwner> ret = new ArrayList<ExamOwner>(); 1081 for (ExamOwner owner : iOwners) { 1082 if (owner.getIntructors().contains(instructor)) 1083 ret.add(owner); 1084 } 1085 return ret; 1086 } 1087 1088 /** 1089 * Returns appropriate {@link ExamPeriodPlacement} for the given period, if 1090 * it is available for this exam, null otherwise. 1091 * @param periodId period unique id 1092 * @return the appropriate period placement 1093 */ 1094 public ExamPeriodPlacement getPeriodPlacement(Long periodId) { 1095 for (ExamPeriodPlacement periodPlacement : iPeriodPlacements) { 1096 if (periodPlacement.getId().equals(periodId)) 1097 return periodPlacement; 1098 } 1099 return null; 1100 } 1101 1102 /** 1103 * Returns appropriate {@link ExamRoomPlacement} for the given room, if it 1104 * is available for this exam, null otherwise. 1105 * @param roomId room unique id 1106 * @return the appropriate room placement 1107 */ 1108 public ExamRoomPlacement getRoomPlacement(long roomId) { 1109 for (ExamRoomPlacement roomPlacement : iRoomPlacements) { 1110 if (roomPlacement.getId() == roomId) 1111 return roomPlacement; 1112 } 1113 return null; 1114 } 1115 1116 /** 1117 * Returns appropriate {@link ExamPeriodPlacement} for the given period, if 1118 * it is available for this exam, null otherwise. 1119 * @param period period in question 1120 * @return the appropriate period placement 1121 */ 1122 public ExamPeriodPlacement getPeriodPlacement(ExamPeriod period) { 1123 for (ExamPeriodPlacement periodPlacement : getPeriodPlacements()) { 1124 if (periodPlacement.getPeriod().equals(period)) 1125 return periodPlacement; 1126 } 1127 return null; 1128 } 1129 1130 /** 1131 * Returns appropriate {@link ExamRoomPlacement} for the given room, if it 1132 * is available for this exam, null otherwise. 1133 * @param room room in question 1134 * @return the appropriate room placement 1135 */ 1136 public ExamRoomPlacement getRoomPlacement(ExamRoom room) { 1137 for (ExamRoomPlacement roomPlacement : getRoomPlacements()) { 1138 if (roomPlacement.getRoom().equals(room)) 1139 return roomPlacement; 1140 } 1141 return null; 1142 } 1143 1144 /** Return true if there are some values in the domain of this variable */ 1145 @Override 1146 public boolean hasValues() { 1147 return !getPeriodPlacements().isEmpty() && (getMaxRooms() == 0 || !getRoomPlacements().isEmpty()); 1148 } 1149 1150 @Override 1151 public void variableAssigned(Assignment<Exam, ExamPlacement> assignment, long iteration, ExamPlacement placement) { 1152 if (getMaxRooms() > 0) { 1153 int size = 0; 1154 for (ExamRoomPlacement room : placement.getRoomPlacements()) { 1155 size += room.getSize(hasAltSeating()); 1156 } 1157 if (size < getSize() && !placement.getRoomPlacements().isEmpty()) { 1158 Progress.getInstance(getModel()).warn("Selected room(s) are too small " + size + "<" + getSize() + " (" + getName() + " " + placement.getName() + ")"); 1159 } 1160 } 1161 } 1162}