001package org.cpsolver.coursett.criteria.additional; 002 003import java.util.Collection; 004import java.util.HashSet; 005import java.util.Map; 006import java.util.Set; 007 008import org.cpsolver.coursett.constraint.JenrlConstraint; 009import org.cpsolver.coursett.criteria.StudentConflict; 010import org.cpsolver.coursett.model.Lecture; 011import org.cpsolver.coursett.model.Placement; 012import org.cpsolver.coursett.model.Student; 013import org.cpsolver.coursett.model.TimeLocation; 014import org.cpsolver.coursett.model.TimetableModel; 015import org.cpsolver.ifs.assignment.Assignment; 016import org.cpsolver.ifs.util.DataProperties; 017 018/** 019 * Naive, yet effective approach for minimizing holes in student schedule. This criterion 020 * is based on {@link StudentConflict} and it penalizes all cases where a student has 021 * two classes taught on the same day that are not back-to-back. The penalisation 022 * is based on the time distance between the two classes, computed in hours. 023 * These penalties are weighted by Comparator.MinimizeStudentScheduleHolesWeight, 024 * which defaults to 1/20 of the Comparator.StudentConflictWeight. 025 * 026 * <br> 027 * 028 * @version CourseTT 1.3 (University Course Timetabling)<br> 029 * Copyright (C) 2006 - 2014 Tomáš Müller<br> 030 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 031 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 032 * <br> 033 * This library is free software; you can redistribute it and/or modify 034 * it under the terms of the GNU Lesser General Public License as 035 * published by the Free Software Foundation; either version 3 of the 036 * License, or (at your option) any later version. <br> 037 * <br> 038 * This library is distributed in the hope that it will be useful, but 039 * WITHOUT ANY WARRANTY; without even the implied warranty of 040 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 041 * Lesser General Public License for more details. <br> 042 * <br> 043 * You should have received a copy of the GNU Lesser General Public 044 * License along with this library; if not see 045 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 046 */ 047public class StudentMinimizeScheduleHoles extends StudentConflict { 048 049 /** 050 * Time distance between two placements in hours. The classes must be on the same days and weeks, 051 * but not overlapping in time. If the two classes are taught on multiple days during the week, the 052 * distance is also multiplied by the number of shared days of week. 053 * @param p1 first placement 054 * @param p2 second placement 055 * @return distance between the two classes in hours 056 */ 057 public static double btbDistance(Placement p1, Placement p2) { 058 if (p1 == null || p2 == null) return 0.0; 059 return btbDistance(p1.getTimeLocation(), p2.getTimeLocation()); 060 } 061 062 private static double btbDistance(TimeLocation t1, TimeLocation t2) { 063 if (!t1.shareDays(t2) || !t1.shareWeeks(t2) || t1.shareHours(t2)) return 0.0; 064 int s1 = t1.getStartSlot(), e1 = s1 + t1.getLength(); 065 int s2 = t2.getStartSlot(), e2 = s2 + t2.getLength(); 066 if (e1 < s2) { 067 return t1.nrSharedDays(t2) * (s2 - e1) / 12.0; 068 } else if (e2 < s1) { 069 return t1.nrSharedDays(t2) * (s1 - e2) / 12.0; 070 } 071 return 0.0; 072 } 073 074 @Override 075 public boolean inConflict(Placement p1, Placement p2) { 076 return btbDistance(p1, p2) > 0.0; 077 } 078 079 @Override 080 protected double jointEnrollment(JenrlConstraint jenrl, Placement p1, Placement p2) { 081 return btbDistance(p1, p2) * jenrl.jenrl(); 082 } 083 084 @Override 085 protected double jointEnrollment(JenrlConstraint jenrl) { 086 double max = 0; 087 for (TimeLocation t1: jenrl.first().timeLocations()) 088 for (TimeLocation t2: jenrl.second().timeLocations()) { 089 double distance = btbDistance(t1, t2); 090 if (distance > max) max = distance; 091 } 092 return max; 093 } 094 095 @Override 096 public boolean isApplicable(Lecture l1, Lecture l2) { 097 return l1 != null && l2 != null && !ignore(l1, l2) && applicable(l1, l2); 098 } 099 100 @Override 101 public void incJenrl(Assignment<Lecture, Placement> assignment, JenrlConstraint jenrl, double studentWeight, Double conflictPriority, Student student) { 102 if (isApplicable(student, jenrl.first(), jenrl.second())) 103 inc(assignment, studentWeight * btbDistance(assignment.getValue(jenrl.first()), assignment.getValue(jenrl.second()))); 104 } 105 106 @Override 107 public double getWeightDefault(DataProperties config) { 108 return config.getPropertyDouble("Comparator.MinimizeStudentScheduleHolesWeight", 0.05 * config.getPropertyDouble("Comparator.StudentConflictWeight", 1.0)); 109 } 110 111 @Override 112 public String getPlacementSelectionWeightName() { 113 return "Placement.MinimizeStudentScheduleHolesWeight"; 114 } 115 116 @Override 117 public void getInfo(Assignment<Lecture, Placement> assignment, Map<String, String> info) { 118 super.getInfo(assignment, info); 119 double total = 0; 120 for (JenrlConstraint jenrl: ((TimetableModel)getModel()).getJenrlConstraints()) { 121 if (!jenrl.isToBeIgnored()) 122 total += jenrl.jenrl(); 123 } 124 info.put("Student class distance", sDoubleFormat.format(60.0 * getValue(assignment) / total) + " minutes"); 125 } 126 127 @Override 128 public void getInfo(Assignment<Lecture, Placement> assignment, Map<String, String> info, Collection<Lecture> variables) { 129 super.getInfo(assignment, info, variables); 130 Set<JenrlConstraint> jenrls = new HashSet<JenrlConstraint>(); 131 double distance = 0; 132 double total = 0; 133 for (Lecture lecture: variables) { 134 for (JenrlConstraint jenrl: lecture.jenrlConstraints()) 135 if (jenrls.add(jenrl) && !jenrl.isToBeIgnored()) { 136 distance += jenrl.jenrl() * btbDistance(assignment.getValue(jenrl.first()), assignment.getValue(jenrl.second())); 137 total += jenrl.jenrl(); 138 } 139 } 140 info.put("Student class distance", sDoubleFormat.format(60.0 * distance / total) + " minutes"); 141 } 142 143}