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