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 } 568 } 569 return true; 570 } 571 572 /** 573 * Check all distribution constraint that this exam is involved in 574 * 575 * @param assignment current assignment 576 * @param room 577 * a room to be assigned to this exam 578 * @return true, if there is no assignment of some other exam in conflict 579 * with the given room 580 */ 581 public boolean checkDistributionConstraints(Assignment<Exam, ExamPlacement> assignment, ExamRoomPlacement room) { 582 for (ExamDistributionConstraint dc : iDistConstraints) { 583 if (!dc.isHard()) 584 continue; 585 for (Exam exam : dc.variables()) { 586 if (exam.equals(this)) 587 continue; 588 ExamPlacement placement = assignment.getValue(exam); 589 if (placement == null) 590 continue; 591 switch (dc.getType()) { 592 case ExamDistributionConstraint.sDistSameRoom: 593 if (!placement.getRoomPlacements().contains(room)) 594 return false; 595 break; 596 case ExamDistributionConstraint.sDistDifferentRoom: 597 if (placement.getRoomPlacements().contains(room)) 598 return false; 599 break; 600 } 601 } 602 } 603 return true; 604 } 605 606 /** 607 * Check all soft distribution constraint that this exam is involved in 608 * 609 * @param assignment current assignment 610 * @param room 611 * a room to be assigned to this exam 612 * @return sum of penalties of violated distribution constraints 613 */ 614 public int getDistributionConstraintPenalty(Assignment<Exam, ExamPlacement> assignment, ExamRoomPlacement room) { 615 int penalty = 0; 616 for (ExamDistributionConstraint dc : iDistConstraints) { 617 if (dc.isHard()) 618 continue; 619 for (Exam exam : dc.variables()) { 620 if (exam.equals(this)) 621 continue; 622 ExamPlacement placement = assignment.getValue(exam); 623 if (placement == null) 624 continue; 625 switch (dc.getType()) { 626 case ExamDistributionConstraint.sDistSameRoom: 627 if (!placement.getRoomPlacements().contains(room)) 628 penalty += dc.getWeight(); 629 break; 630 case ExamDistributionConstraint.sDistDifferentRoom: 631 if (placement.getRoomPlacements().contains(room)) 632 penalty += dc.getWeight(); 633 break; 634 } 635 } 636 } 637 return penalty; 638 } 639 640 /** 641 * Maximal number of rooms that can be assigned to the exam 642 * 643 * @return maximal number of rooms that can be assigned to the exam 644 */ 645 public int getMaxRooms() { 646 return iMaxRooms; 647 } 648 649 /** 650 * Set maximal number of rooms that can be assigned to the exam 651 * 652 * @param maxRooms 653 * maximal number of rooms that can be assigned to the exam 654 */ 655 public void setMaxRooms(int maxRooms) { 656 iMaxRooms = maxRooms; 657 } 658 659 /** 660 * Find best available rooms for the exam in the given period. First of all, 661 * it tries to find the minimal number of rooms that cover the size of the 662 * exam. Among these, a set of rooms of total smallest size is preferred. If 663 * the original room is available and of enough size, it is returned. All 664 * necessary checks are made (availability of rooms, room penalties, room 665 * sizes etc.). 666 * 667 * @param assignment current assignment 668 * @param period 669 * given period. 670 * @return best available rooms for the exam in the given period, null if 671 * there is no valid assignment 672 */ 673 public Set<ExamRoomPlacement> findBestAvailableRooms(Assignment<Exam, ExamPlacement> assignment, ExamPeriodPlacement period) { 674 if (getMaxRooms() == 0) 675 return new HashSet<ExamRoomPlacement>(); 676 double sw = getModel().getCriterion(RoomSizePenalty.class).getWeight(); 677 double pw = getModel().getCriterion(RoomPenalty.class).getWeight(); 678 double cw = getModel().getCriterion(DistributionPenalty.class).getWeight(); 679 ExamRoomSharing sharing = ((ExamModel) getModel()).getRoomSharing(); 680 loop: for (int nrRooms = 1; nrRooms <= getMaxRooms(); nrRooms++) { 681 HashSet<ExamRoomPlacement> rooms = new HashSet<ExamRoomPlacement>(); 682 int size = 0; 683 while (rooms.size() < nrRooms && size < getSize()) { 684 int minSize = (getSize() - size) / (nrRooms - rooms.size()); 685 ExamRoomPlacement best = null; 686 double bestWeight = 0; 687 int bestSize = 0; 688 for (ExamRoomPlacement room : getRoomPlacements()) { 689 if (!room.isAvailable(period.getPeriod())) 690 continue; 691 if (nrRooms == 1 && sharing != null) { 692 if (sharing.inConflict(this, room.getRoom().getPlacements(assignment, period.getPeriod()), room.getRoom())) 693 continue; 694 } else { 695 if (!room.getRoom().getPlacements(assignment, period.getPeriod()).isEmpty()) 696 continue; 697 } 698 if (rooms.contains(room)) 699 continue; 700 if (!checkDistributionConstraints(assignment, room)) 701 continue; 702 int s = room.getSize(hasAltSeating()); 703 if (s < minSize) 704 break; 705 int p = room.getPenalty(period.getPeriod()); 706 double w = pw * p + sw * (s - minSize) + cw * getDistributionConstraintPenalty(assignment, room); 707 double d = 0; 708 if (!rooms.isEmpty()) { 709 for (ExamRoomPlacement r : rooms) { 710 d += r.getDistanceInMeters(room); 711 } 712 w += d / rooms.size(); 713 } 714 if (best == null || bestWeight > w) { 715 best = room; 716 bestSize = s; 717 bestWeight = w; 718 } 719 } 720 if (best == null) 721 continue loop; 722 rooms.add(best); 723 size += bestSize; 724 } 725 if (size >= getSize()) 726 return rooms; 727 } 728 return null; 729 } 730 731 /** 732 * Randomly find a set of available rooms for the exam in the given period. 733 * First of all, it tries to find the minimal number of rooms that cover the 734 * size of the exam. Among these, a set of rooms of total smallest size is 735 * preferred. All necessary checks are made (availability of rooms, room 736 * penalties, room sizes etc.). 737 * 738 * @param assignment current assignment 739 * @param period 740 * given period. 741 * @return randomly computed set of available rooms for the exam in the 742 * given period, null if there is no valid assignment 743 */ 744 public Set<ExamRoomPlacement> findRoomsRandom(Assignment<Exam, ExamPlacement> assignment, ExamPeriodPlacement period) { 745 return findRoomsRandom(assignment, period, true); 746 } 747 748 /** 749 * Randomly find a set of available rooms for the exam in the given period. 750 * First of all, it tries to find the minimal number of rooms that cover the 751 * size of the exam. Among these, a set of rooms of total smallest size is 752 * preferred. All necessary checks are made (availability of rooms, room 753 * penalties, room sizes etc.). 754 * 755 * @param assignment current assignment 756 * @param period 757 * given period. 758 * @param checkConflicts 759 * if false, room and distribution conflicts are not checked 760 * @return randomly computed set of available rooms for the exam in the 761 * given period, null if there is no valid assignment 762 */ 763 public Set<ExamRoomPlacement> findRoomsRandom(Assignment<Exam, ExamPlacement> assignment, ExamPeriodPlacement period, boolean checkConflicts) { 764 if (getMaxRooms() == 0) 765 return new HashSet<ExamRoomPlacement>(); 766 HashSet<ExamRoomPlacement> rooms = new HashSet<ExamRoomPlacement>(); 767 int size = 0; 768 ExamRoomSharing sharing = ((ExamModel) getModel()).getRoomSharing(); 769 loop: while (rooms.size() < getMaxRooms()) { 770 int rx = ToolBox.random(getRoomPlacements().size()); 771 int minSize = (getSize() - size + (getMaxRooms() - rooms.size() - 1)) / (getMaxRooms() - rooms.size()); 772 for (int r = 0; r < getRoomPlacements().size(); r++) { 773 ExamRoomPlacement room = getRoomPlacements().get((r + rx) % getRoomPlacements().size()); 774 int s = room.getSize(hasAltSeating()); 775 if (s < minSize) 776 continue; 777 if (!room.isAvailable(period.getPeriod())) 778 continue; 779 if (checkConflicts) { 780 if (rooms.isEmpty() && sharing != null && !room.getRoom().getPlacements(assignment, period.getPeriod()).isEmpty()) { 781 if (sharing.inConflict(this, room.getRoom().getPlacements(assignment, period.getPeriod()), room.getRoom())) 782 continue; 783 } else { 784 if (!room.getRoom().getPlacements(assignment, period.getPeriod()).isEmpty()) 785 continue; 786 } 787 } 788 if (rooms.contains(room)) 789 continue; 790 if (checkConflicts && !checkDistributionConstraints(assignment, room)) 791 continue; 792 size += s; 793 rooms.add(room); 794 if (size >= getSize()) { 795 for (Iterator<ExamRoomPlacement> j = rooms.iterator(); j.hasNext();) { 796 ExamRoomPlacement rp = j.next(); 797 if (size - rp.getSize(hasAltSeating()) >= getSize()) { 798 j.remove(); 799 size -= rp.getSize(hasAltSeating()); 800 } 801 } 802 return rooms; 803 } 804 continue loop; 805 } 806 break; 807 } 808 return null; 809 } 810 811 private HashSet<Exam> iCorrelatedExams = null; 812 813 /** 814 * Number of exams that are correlated with this exam (there is at least one 815 * student attending both exams). 816 * 817 * @return number of correlated exams 818 */ 819 public int nrStudentCorrelatedExams() { 820 return getStudentCorrelatedExams().size(); 821 } 822 823 /** 824 * Exams that are correlated with this exam (there is at least one 825 * student attending both exams). 826 * 827 * @return number of correlated exams 828 */ 829 public synchronized Set<Exam> getStudentCorrelatedExams() { 830 if (iCorrelatedExams == null) { 831 iCorrelatedExams = new HashSet<Exam>(); 832 for (ExamStudent student : iStudents) { 833 iCorrelatedExams.addAll(student.variables()); 834 } 835 iCorrelatedExams.remove(this); 836 } 837 return iCorrelatedExams; 838 } 839 840 private Integer iEstimatedDomainSize = null; 841 842 private synchronized int estimatedDomainSize() { 843 if (iEstimatedDomainSize == null) { 844 int periods = getPeriodPlacements().size(); 845 int rooms = -1; 846 int split = 0; 847 while (rooms < split && split <= getMaxRooms()) { 848 rooms = 0; 849 split++; 850 for (ExamRoomPlacement room : getRoomPlacements()) { 851 if (room.getSize(hasAltSeating()) >= (getSize() / split)) 852 rooms++; 853 } 854 } 855 iEstimatedDomainSize = new Integer(periods * rooms / split); 856 } 857 return iEstimatedDomainSize.intValue(); 858 } 859 860 /** 861 * An exam with more correlated exams is preferred ( 862 * {@link Exam#nrStudentCorrelatedExams()}). If it is the same, ratio number 863 * of students / number of available periods is used. If the same, exam ids 864 * are used. 865 */ 866 @Override 867 public int compareTo(Exam o) { 868 Exam e = o; 869 int cmp = Double.compare(estimatedDomainSize(), e.estimatedDomainSize()); 870 if (cmp != 0) 871 return cmp; 872 cmp = -Double.compare(nrStudentCorrelatedExams(), e.nrStudentCorrelatedExams()); 873 if (cmp != 0) 874 return cmp; 875 cmp = -Double.compare(((double) getSize()) / getPeriodPlacements().size(), ((double) e.getSize()) 876 / e.getPeriodPlacements().size()); 877 if (cmp != 0) 878 return cmp; 879 return super.compareTo(o); 880 } 881 882 /** 883 * True, if there is a student of this exam (that does not have direct 884 * conflicts allowed, see {@link ExamStudent#canConflict(Exam, Exam)}) that 885 * attends some other exam in the given period. 886 * 887 * @param assignment current assignment 888 * @param period 889 * a period 890 * @return true if there is a student conflict 891 */ 892 public boolean hasStudentConflictWithPreAssigned(Assignment<Exam, ExamPlacement> assignment, ExamPeriod period) { 893 Map<ExamStudent, Set<Exam>> studentsOfPeriod = ((ExamModel)getModel()).getStudentsOfPeriod(assignment, period); 894 for (ExamStudent s : getStudents()) { 895 Set<Exam> exams = studentsOfPeriod.get(s); 896 if (exams == null) continue; 897 for (Exam exam : exams) { 898 if (!exam.equals(this) && !s.canConflict(this, exam)) return true; 899 } 900 } 901 return false; 902 } 903 904 /** 905 * Number of students of this exam (that does not have direct conflicts 906 * allowed, see {@link ExamStudent#canConflict(Exam, Exam)}) that attend 907 * some other exam in the given period. 908 * 909 * @param assignment current assignment 910 * @param period 911 * a period 912 * @return number of direct student conflicts that are prohibited 913 */ 914 public int countStudentConflicts(Assignment<Exam, ExamPlacement> assignment, ExamPeriodPlacement period) { 915 int conf = 0; 916 Map<ExamStudent, Set<Exam>> studentsOfPeriod = ((ExamModel)getModel()).getStudentsOfPeriod(assignment, period.getPeriod()); 917 for (ExamStudent s : getStudents()) { 918 Set<Exam> exams = studentsOfPeriod.get(s); 919 if (exams == null) continue; 920 for (Exam exam : exams) { 921 if (!exam.equals(this) && !s.canConflict(this, exam)) conf++; 922 } 923 } 924 return conf; 925 } 926 927 /** 928 * List of exams that are assigned to the given period and share one or more 929 * students with this exam (that does not have direct conflicts allowed, see 930 * {@link ExamStudent#canConflict(Exam, Exam)}). 931 * 932 * @param assignment current assignment 933 * @param period 934 * a period 935 * @return list of {@link Exam} (other than this exam, that are placed in 936 * the given period and create prohibited direct conflicts) 937 */ 938 public HashSet<Exam> getStudentConflicts(Assignment<Exam, ExamPlacement> assignment, ExamPeriod period) { 939 HashSet<Exam> conf = new HashSet<Exam>(); 940 Map<ExamStudent, Set<Exam>> studentsOfPeriod = ((ExamModel)getModel()).getStudentsOfPeriod(assignment, period); 941 for (ExamStudent s : getStudents()) { 942 Set<Exam> exams = studentsOfPeriod.get(s); 943 if (exams == null) continue; 944 for (Exam exam : exams) { 945 if (!exam.equals(this) && !s.canConflict(this, exam)) conf.add(exam); 946 } 947 } 948 return conf; 949 } 950 951 /** 952 * Allow all direct student conflict for the given period (see 953 * {@link ExamStudent#canConflict(Exam, Exam)}). 954 * 955 * @param assignment current assignment 956 * @param period 957 * a period 958 */ 959 public void allowAllStudentConflicts(Assignment<Exam, ExamPlacement> assignment, ExamPeriod period) { 960 Map<ExamStudent, Set<Exam>> studentsOfPeriod = ((ExamModel)getModel()).getStudentsOfPeriod(assignment, period); 961 for (ExamStudent s : getStudents()) { 962 Set<Exam> exams = studentsOfPeriod.get(s); 963 if (exams == null) continue; 964 for (Exam exam : exams) { 965 if (exam.equals(this)) continue; 966 exam.setAllowDirectConflicts(true); 967 setAllowDirectConflicts(true); 968 s.setAllowDirectConflicts(true); 969 } 970 } 971 } 972 973 /** 974 * String representation 975 * 976 * @return exam id (periods: number of periods, rooms: number of rooms, 977 * student: number of students, maxRooms: max rooms[, alt if 978 * alternate seating is required]) 979 */ 980 @Override 981 public String toString() { 982 return getName() + " (periods:" + getPeriodPlacements().size() + ", rooms:" + getRoomPlacements().size() 983 + ", size:" + getSize() + " ,maxRooms:" + getMaxRooms() + (hasAltSeating() ? ", alt" : "") + ")"; 984 } 985 986 /** Exam name */ 987 @Override 988 public String getName() { 989 return (hasName() ? iName : String.valueOf(getId())); 990 } 991 992 /** Exam name 993 * @param name examination name 994 **/ 995 public void setName(String name) { 996 iName = name; 997 } 998 999 /** Exam name 1000 * @return true if the examination name is set and it is not empty 1001 **/ 1002 public boolean hasName() { 1003 return iName != null && iName.length() > 0; 1004 } 1005 1006 private HashMap<Exam, List<ExamStudent>> iJenrls = null; 1007 1008 /** 1009 * Joint enrollments 1010 * 1011 * @return table {@link Exam} (an exam that has at least one student in 1012 * common with this exam) → {@link List} (list of students in 1013 * common) 1014 */ 1015 public Map<Exam, List<ExamStudent>> getJointEnrollments() { 1016 if (iJenrls != null) 1017 return iJenrls; 1018 iJenrls = new HashMap<Exam, List<ExamStudent>>(); 1019 for (ExamStudent student : getStudents()) { 1020 for (Exam other : student.variables()) { 1021 if (other.equals(this)) 1022 continue; 1023 List<ExamStudent> students = iJenrls.get(other); 1024 if (students == null) { 1025 students = new ArrayList<ExamStudent>(); 1026 iJenrls.put(other, students); 1027 } 1028 students.add(student); 1029 } 1030 } 1031 return iJenrls; 1032 } 1033 1034 /** 1035 * Courses and/or sections that are having this exam 1036 * 1037 * @return list of {@link ExamOwner} 1038 */ 1039 public List<ExamOwner> getOwners() { 1040 return iOwners; 1041 } 1042 1043 /** 1044 * Courses/sections of this exam into which the given student is enrolled 1045 * into 1046 * 1047 * @param student 1048 * a student that is enrolled into this exam 1049 * @return list of courses/sections {@link ExamOwner} which are having this 1050 * exam with the given student enrolled in 1051 */ 1052 public Collection<ExamOwner> getOwners(ExamStudent student) { 1053 Collection<ExamOwner> ret = new ArrayList<ExamOwner>(); 1054 for (ExamOwner owner : iOwners) { 1055 if (owner.getStudents().contains(student)) 1056 ret.add(owner); 1057 } 1058 return ret; 1059 } 1060 1061 /** 1062 * Courses/sections of this exam into which the given instructor is enrolled 1063 * into 1064 * 1065 * @param instructor 1066 * an instructor that is enrolled into this exam 1067 * @return list of courses/sections {@link ExamOwner} which are having this 1068 * exam with the given instructor enrolled in 1069 */ 1070 public Collection<ExamOwner> getOwners(ExamInstructor instructor) { 1071 Collection<ExamOwner> ret = new ArrayList<ExamOwner>(); 1072 for (ExamOwner owner : iOwners) { 1073 if (owner.getIntructors().contains(instructor)) 1074 ret.add(owner); 1075 } 1076 return ret; 1077 } 1078 1079 /** 1080 * Returns appropriate {@link ExamPeriodPlacement} for the given period, if 1081 * it is available for this exam, null otherwise. 1082 * @param periodId period unique id 1083 * @return the appropriate period placement 1084 */ 1085 public ExamPeriodPlacement getPeriodPlacement(Long periodId) { 1086 for (ExamPeriodPlacement periodPlacement : iPeriodPlacements) { 1087 if (periodPlacement.getId().equals(periodId)) 1088 return periodPlacement; 1089 } 1090 return null; 1091 } 1092 1093 /** 1094 * Returns appropriate {@link ExamRoomPlacement} for the given room, if it 1095 * is available for this exam, null otherwise. 1096 * @param roomId room unique id 1097 * @return the appropriate room placement 1098 */ 1099 public ExamRoomPlacement getRoomPlacement(long roomId) { 1100 for (ExamRoomPlacement roomPlacement : iRoomPlacements) { 1101 if (roomPlacement.getId() == roomId) 1102 return roomPlacement; 1103 } 1104 return null; 1105 } 1106 1107 /** 1108 * Returns appropriate {@link ExamPeriodPlacement} for the given period, if 1109 * it is available for this exam, null otherwise. 1110 * @param period period in question 1111 * @return the appropriate period placement 1112 */ 1113 public ExamPeriodPlacement getPeriodPlacement(ExamPeriod period) { 1114 for (ExamPeriodPlacement periodPlacement : getPeriodPlacements()) { 1115 if (periodPlacement.getPeriod().equals(period)) 1116 return periodPlacement; 1117 } 1118 return null; 1119 } 1120 1121 /** 1122 * Returns appropriate {@link ExamRoomPlacement} for the given room, if it 1123 * is available for this exam, null otherwise. 1124 * @param room room in question 1125 * @return the appropriate room placement 1126 */ 1127 public ExamRoomPlacement getRoomPlacement(ExamRoom room) { 1128 for (ExamRoomPlacement roomPlacement : getRoomPlacements()) { 1129 if (roomPlacement.getRoom().equals(room)) 1130 return roomPlacement; 1131 } 1132 return null; 1133 } 1134 1135 /** Return true if there are some values in the domain of this variable */ 1136 @Override 1137 public boolean hasValues() { 1138 return !getPeriodPlacements().isEmpty() && (getMaxRooms() == 0 || !getRoomPlacements().isEmpty()); 1139 } 1140 1141 @Override 1142 public void variableAssigned(Assignment<Exam, ExamPlacement> assignment, long iteration, ExamPlacement placement) { 1143 if (getMaxRooms() > 0) { 1144 int size = 0; 1145 for (ExamRoomPlacement room : placement.getRoomPlacements()) { 1146 size += room.getSize(hasAltSeating()); 1147 } 1148 if (size < getSize() && !placement.getRoomPlacements().isEmpty()) { 1149 Progress.getInstance(getModel()).warn("Selected room(s) are too small " + size + "<" + getSize() + " (" + getName() + " " + placement.getName() + ")"); 1150 } 1151 } 1152 } 1153}