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