    001    package ttsolver;
    002
    003    import ifs.model.*;
    004    import ifs.util.*;
    005
    006    import java.util.*;
    007
    008    import ttsolver.constraint.*;
    009    import ttsolver.model.*;
    010
    011    /**
    012     * Timetable model.
    013     *
    014     * @author <a href="mailto:muller@ktiml.mff.cuni.cz">Tomáš Müller</a>
    015     * @version 1.0
    016     */
    017
    018    public class TimetableModel extends Model {
    019        private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(TimetableModel.class);
    020        private static java.text.DecimalFormat sDoubleFormat = new java.text.DecimalFormat("0.00",new java.text.DecimalFormatSymbols(Locale.US));
    021        private static java.text.SimpleDateFormat sDateFormat = new java.text.SimpleDateFormat("dd-MMM-yy_HHmmss",java.util.Locale.US);
    022        private long iGlobalRoomPreference = 0;
    023        private double iGlobalTimePreference = 0;
    024        private long iBestRoomPreference = 0;
    025        private long iBestInstructorDistancePreference = 0;
    026        private double iBestTimePreference = 0;
    027        private int iBestDepartmentSpreadPenalty = 0;
    028        private Counter iGlobalGroupConstraintPreference = new Counter();
    029        private Counter iViolatedStudentConflicts = new Counter();
    030        private FastVector iInstructorConstraints = new FastVector();
    031        private FastVector iJenrlConstraints = new FastVector();
    032        private FastVector iRoomConstraints = new FastVector();
    033        private FastVector iDepartmentSpreadConstraints = new FastVector();
    034        private FastVector iGroupConstraints = new FastVector();
    035        private FastVector iIgnoredClasses  = new FastVector();
    036        private boolean iSwitchStudents = false;
    037        private DataProperties iProperties = null;
    038
    039        /** For MPP generator */
    040        public Vector ignoredClasses() { return iIgnoredClasses; }
    041
    042        public TimetableModel(DataProperties properties) {
    043            super();
    044            iSwitchStudents            = properties.getPropertyBoolean("General.SwitchStudents",true);
    045            iProperties = properties;
    046            InstructorConstraint.sNoPreferenceLimit = iProperties.getPropertyDouble("General.Distance.NoPreferenceLimit",0.0);
    047            InstructorConstraint.sDiscouragedLimit = iProperties.getPropertyDouble("General.Distance.DiscouragedLimit",5.0);
    048            InstructorConstraint.sProhibitedLimit = iProperties.getPropertyDouble("General.Distance.ProhibitedLimit",20.0);
    049        }
    050
    051        public DataProperties getProperties() { return iProperties; }
    052
    053        /** Check validity of JENRL constraints from student enrollments */
    054        public void checkJenrl() {
    055            try {
    056                System.err.println("Checking jenrl ...");
    057                for (Enumeration i1=variables().elements();i1.hasMoreElements();) {
    058                    Lecture l1 = (Lecture)i1.nextElement();
    059                    System.err.println("Checking "+l1.getName()+" ...");
    060                    for (Enumeration i2=variables().elements();i2.hasMoreElements();) {
    061                        Lecture l2 = (Lecture)i2.nextElement();
    062                        if (l1.getId()<l2.getId()) {
    063                            int jenrl = 0;
    064                            Vector jenrlStudents = new FastVector();
    065                            for (Enumeration i3=l1.students().elements(); i3.hasMoreElements(); ) {
    066                                String student = (String)i3.nextElement();
    067                                if (l2.students().contains(student)) {
    068                                    jenrl++;
    069                                    jenrlStudents.addElement(student);
    070                                }
    071                            }
    072                            boolean found = false;
    073                            for (Enumeration i3=iJenrlConstraints.elements();i3.hasMoreElements(); ) {
    074                                JenrlConstraint j = (JenrlConstraint)i3.nextElement();
    075                                Lecture a=(Lecture)j.first();
    076                                Lecture b=(Lecture)j.second();
    077                                if ((a.equals(l1) && b.equals(l2)) || (a.equals(l2) && b.equals(l1))) {
    078                                    found = true;
    079                                    if (j.getJenrl()!=jenrl) {
    080                                        sLogger.error("ERROR: Wrong jenrl between "+l1.getName()+" and "+l2.getName()+" (constraint="+j.getJenrl()+" != computed="+jenrl+").");
    081                                        sLogger.error("       "+l1.getName()+" has students: "+l1.students());
    082                                        sLogger.error("       "+l2.getName()+" has students: "+l2.students());
    083                                        sLogger.error("       intersection: "+jenrlStudents);
    084                                    }
    085                                }
    086                            }
    087                            if (!found && jenrl>0) {
    088                                System.err.println("ERROR: Missing jenrl between "+l1.getName()+" and "+l2.getName()+" (computed="+jenrl+").");
    089                                sLogger.error("ERROR: Missing jenrl between "+l1.getName()+" and "+l2.getName()+" (computed="+jenrl+").");
    090                                sLogger.error("       "+l1.getName()+" has students: "+l1.students());
    091                                sLogger.error("       "+l2.getName()+" has students: "+l2.students());
    092                                sLogger.error("       intersection: "+jenrlStudents);
    093                            }
    094                        }
    095                    }
    096                }
    097                System.err.println("Check done.");
    098            } catch (Exception e) {
    099                            edu.purdue.smas.timetable.util.Debug.error(e);
    100                e.printStackTrace();
    101            }
    102        }
    103
    104        /** Overall room preference */
    105        public long getGlobalRoomPreference() { return iGlobalRoomPreference; }
    106        /** Overall time preference */
    107        public double getGlobalTimePreference() { return iGlobalTimePreference; }
    108        /** Number of student conflicts */
    109        public long getViolatedStudentConflicts() { return iViolatedStudentConflicts.get(); }
    110        /** Number of student conflicts */
    111        public long countViolatedStudentConflicts() {
    112            long studentConflicts = 0;
    113            for (Enumeration it1=iJenrlConstraints.elements();it1.hasMoreElements();) {
    114                JenrlConstraint jenrl = (JenrlConstraint)it1.nextElement();
    115                Lecture a = (Lecture)jenrl.first();
    116                Lecture b = (Lecture)jenrl.second();
    117                if (a.getAssignment()!=null && b.getAssignment()!=null && JenrlConstraint.isInConflict((Placement)a.getAssignment(),(Placement)b.getAssignment()))
    118                    studentConflicts+=jenrl.getJenrl();
    119            }
    120            return studentConflicts;
    121        }
    122        /** Number of student conflicts */
    123        public Counter getViolatedStudentConflictsCounter() { return iViolatedStudentConflicts; }
    124        /** Overall group constraint preference */
    125        public long getGlobalGroupConstraintPreference() { return iGlobalGroupConstraintPreference.get(); }
    126        /** Overall group constraint preference */
    127        public Counter getGlobalGroupConstraintPreferenceCounter() { return iGlobalGroupConstraintPreference; }
    128        /** Overall room preference of the best solution ever found */
    129        public long getBestRoomPreference() { return iBestRoomPreference; }
    130        /** Overall time preference of the best solution ever found */
    131        public double getBestTimePreference() { return iBestTimePreference; }
    132        /** Sets overall room preference of the best solution ever found */
    133        public void setBestRoomPreference(long bestRoomPreference) { iBestRoomPreference = bestRoomPreference; }
    134        /** Sets overall time preference of the best solution ever found */
    135        public void setBestTimePreference(double bestTimePreference) { iBestTimePreference = bestTimePreference; }
    136        /** Overall instructor distance (back-to-back) preference */
    137        public long getInstructorDistancePreference() {
    138            long pref = 0;
    139            for (Enumeration it1=iInstructorConstraints.elements();it1.hasMoreElements();) {
    140                InstructorConstraint constraint = (InstructorConstraint)it1.nextElement();
    141                pref+=constraint.getPreference();
    142            }
    143            return pref;
    144        }
    145        /** The worst instructor distance (back-to-back) preference */
    146        public long getInstructorWorstDistancePreference() {
    147            long pref = 0;
    148            for (Enumeration it1=iInstructorConstraints.elements();it1.hasMoreElements();) {
    149                InstructorConstraint constraint = (InstructorConstraint)it1.nextElement();
    150                pref+=constraint.getWorstPreference();
    151            }
    152            return pref;
    153        }
    154        /** Overall number of useless time slots */
    155        public long getUselessSlots() {
    156            long uselessSlots = 0;
    157            for (Enumeration it1=iRoomConstraints.elements();it1.hasMoreElements();) {
    158                RoomConstraint constraint = (RoomConstraint)it1.nextElement();
    159                uselessSlots+=((RoomConstraint)constraint).countUselessSlots();
    160            }
    161            return uselessSlots;
    162        }
    163        /** Overall number of student conflicts caused by distancies (back-to-back classes are too far)*/
    164        public long getStudentDistanceConflicts() {
    165            long nrConflicts = 0;
    166            for (Enumeration it1=iJenrlConstraints.elements();it1.hasMoreElements();) {
    167                JenrlConstraint jenrl = (JenrlConstraint)it1.nextElement();
    168                if (jenrl.isInConflict() &&
    169                        !((Placement)jenrl.first().getAssignment()).getTimeLocation().hasIntersection(((Placement)jenrl.second().getAssignment()).getTimeLocation()))
    170                        nrConflicts += jenrl.getJenrl();
    171            }
    172            return nrConflicts;
    173        }
    174        /** Overall hard student conflicts (student conflict between single section classes) */
    175        public long getHardStudentConflicts() {
    176            if (!iSwitchStudents) return 0;
    177            long hardStudentConflicts = 0;
    178            for (Enumeration it1=iJenrlConstraints.elements();it1.hasMoreElements();) {
    179                JenrlConstraint jenrl = (JenrlConstraint)it1.nextElement();
    180                if (jenrl.isInConflict()) {
    181                    Lecture l1 = (Lecture)jenrl.first();
    182                    Lecture l2 = (Lecture)jenrl.second();
    183                    if (l1.sameLectures()!=null && l1.sameLectures().size()==1 &&
    184                    l2.sameLectures()!=null && l2.sameLectures().size()==1)
    185                        hardStudentConflicts+=jenrl.getJenrl();
    186                }
    187            }
    188            return hardStudentConflicts;
    189        }
    190
    191        /** When a value is assigned to a variable -- update gloval preferences */
    192        public void afterAssigned(long iteration, Value value) {
    193            super.afterAssigned(iteration, value);
    194            if (value==null) return;
    195            Placement placement = (Placement)value;
    196            iGlobalRoomPreference += placement.getRoomLocation().getPreference();
    197            iGlobalTimePreference += placement.getTimeLocation().getNormalizedPreference();
    198        }
    199        /** When a value is unassigned from a variable -- update gloval preferences */
    200        public void afterUnassigned(long iteration, Value value) {
    201            super.afterUnassigned(iteration, value);
    202            if (value==null) return;
    203            Placement placement = (Placement)value;
    204            iGlobalRoomPreference -= placement.getRoomLocation().getPreference();
    205            iGlobalTimePreference -= placement.getTimeLocation().getNormalizedPreference();
    206        }
    207
    208        /** Student final sectioning (switching students between sections of the same class in order to minimize overall number of student conflicts) */
    209        public void switchStudents() {
    210            if (iSwitchStudents) {
    211                long before;
    212                Progress.getInstance().save();
    213                Collection variables = variables();
    214                do {
    215                    //sLogger.debug("Shifting students ...");
    216                    Progress.getInstance().setPhase("Shifting students ...",variables().size());
    217                    before = getViolatedStudentConflictsCounter().get();
    218                    HashSet lecturesToRecompute = new HashSet(variables.size());
    219                    for (Iterator i=variables.iterator();i.hasNext();) {
    220                        Lecture lecture = (Lecture)i.next();
    221                        //sLogger.debug("Shifting students for "+lecture);
    222                        Set lects = lecture.swapStudents();
    223                        //sLogger.debug("Lectures to recompute: "+lects);
    224                        if (lects!=null) lecturesToRecompute.addAll(lects);
    225                        Progress.getInstance().incProgress();
    226                    }
    227                    //sLogger.debug("Shifting done, "+getViolatedStudentConflictsCounter().get()+" conflicts.");
    228                    variables = lecturesToRecompute;
    229                } while (!variables.isEmpty() && before>getViolatedStudentConflictsCounter().get());
    230                Progress.getInstance().restore();
    231            }
    232        }
    233
    234        public String toString() {
    235            return "TimetableModel{"+
    236            "\n  super="+super.toString()+
    237            "\n  studentConflicts="+iViolatedStudentConflicts.get()+
    238    //        "\n  studentConflicts(violated room distance)="+iViolatedRoomDistanceStudentConflicts.get()+
    239    //        "\n  studentPreferences="+iRoomDistanceStudentPreference.get()+
    240            "\n  roomPreferences="+iGlobalRoomPreference+"/"+iBestRoomPreference+
    241            "\n  timePreferences="+iGlobalTimePreference+"/"+iBestTimePreference+
    242            "\n  groupConstraintPreferences="+iGlobalGroupConstraintPreference.get()+
    243            "\n}";
    244        }
    245
    246        /** Overall number of too big rooms (rooms with more than 3/2 seats than needed) */
    247        public int countTooBigRooms() {
    248            int tooBigRooms=0;
    249            for (Enumeration it1=assignedVariables().elements();it1.hasMoreElements();) {
    250                Lecture lecture = (Lecture)it1.nextElement();
    251                if (lecture.getAssignment()==null) continue;
    252                Placement placement = (Placement)lecture.getAssignment();
    253                long roomSize = placement.getRoomLocation().getRoomSize();
    254                long students = lecture.countStudents();
    255                if (roomSize>TimetableModel.getMaxCapacity(students)) tooBigRooms++;
    256            }
    257            return tooBigRooms;
    258        }
    259
    260        /** Overall departmental spread penalty */
    261        public int getDepartmentSpreadPenalty() {
    262            if (iDepartmentSpreadConstraints.isEmpty()) return 0;
    263            int penalty = 0;
    264            for (Enumeration e=iDepartmentSpreadConstraints.elements();e.hasMoreElements();) {
    265                DepartmentSpreadConstraint c = (DepartmentSpreadConstraint)e.nextElement();
    266                penalty += ((DepartmentSpreadConstraint)c).getPenalty();
    267            }
    268            return penalty;
    269        }
    270
    271        /** Global info */
    272        public java.util.Hashtable getInfo() {
    273            Hashtable ret = super.getInfo();
    274            ret.put("Memory usage", edu.purdue.smas.timetable.util.Debug.getMem());
    275            ret.put("Room preferences", iGlobalRoomPreference+" / "+iBestRoomPreference);
    276            ret.put("Time preferences", sDoubleFormat.format(iGlobalTimePreference)+" / "+sDoubleFormat.format(iBestTimePreference));
    277            ret.put("Group constraint preferences", new Long(iGlobalGroupConstraintPreference.get()));
    278            if (getProperties().getPropertyBoolean("General.UseDistanceConstraints",false)) {
    279                ret.put("Distance student conflicts", new Long(getStudentDistanceConflicts()));
    280                ret.put("Distance instructor preferences", getInstructorDistancePreference()+" / "+getInstructorWorstDistancePreference());
    281            }
    282            if (getProperties().getPropertyBoolean("General.UseDepartmentSpreadConstraints", false)) {
    283                ret.put("Department balancing penalty", new Integer(getDepartmentSpreadPenalty()));
    284            }
    285            ret.put("Student conflicts", new Long(getViolatedStudentConflicts()));
    286            ret.put("Too big rooms", new Integer(countTooBigRooms()));
    287            ret.put("Hard student conflicts", new Long(getHardStudentConflicts()));
    288            ret.put("Useless half-hours", new Long(getUselessSlots()));
    289            return ret;
    290        }
    291
    292        private int iBestTooBigRooms;
    293        private long iBestUselessSlots;
    294        private double iBestGlobalTimePreference;
    295        private long iBestGlobalRoomPreference;
    296        private long iBestGlobalGroupConstraintPreference;
    297        private long iBestViolatedStudentConflicts;
    298        private long iBestHardStudentConflicts;
    299
    300        /** Overall number of too big rooms of the best solution ever found */
    301        public int bestTooBigRooms() { return iBestTooBigRooms; }
    302        /** Overall number of useless slots of the best solution ever found */
    303        public long bestUselessSlots() { return iBestUselessSlots;}
    304        /** Overall time preference of the best solution ever found */
    305        public double bestGlobalTimePreference() { return iBestGlobalTimePreference;}
    306        /** Overall room preference of the best solution ever found */
    307        public long bestGlobalRoomPreference() { return iBestGlobalRoomPreference;}
    308        /** Overall group constraint preference of the best solution ever found */
    309        public long bestGlobalGroupConstraintPreference() { return iBestGlobalGroupConstraintPreference;}
    310        /** Overall number of student conflicts of the best solution ever found */
    311        public long bestViolatedStudentConflicts() { return iBestViolatedStudentConflicts;}
    312        /** Overall number of student conflicts between single section classes of the best solution ever found */
    313        public long bestHardStudentConflicts() { return iBestHardStudentConflicts;}
    314        /** Overall instructor distance preference of the best solution ever found */
    315        public long bestInstructorDistancePreference() { return iBestInstructorDistancePreference; }
    316        /** Overall departmental spread penalty of the best solution ever found */
    317        public int bestDepartmentSpreadPenalty() { return iBestDepartmentSpreadPenalty; }
    318
    319        public void saveBest() {
    320            super.saveBest();
    321            iBestTooBigRooms = countTooBigRooms();
    322            iBestUselessSlots = getUselessSlots();
    323            iBestGlobalTimePreference = getGlobalTimePreference();
    324            iBestGlobalRoomPreference = getGlobalRoomPreference();
    325            iBestGlobalGroupConstraintPreference = getGlobalGroupConstraintPreference();
    326            iBestViolatedStudentConflicts = getViolatedStudentConflicts();
    327            iBestHardStudentConflicts = getHardStudentConflicts();
    328            iBestInstructorDistancePreference = getInstructorDistancePreference();
    329            iBestDepartmentSpreadPenalty = getDepartmentSpreadPenalty();
    330        }
    331
    332        public void addConstraint(Constraint constraint) {
    333            super.addConstraint(constraint);
    334            if (constraint instanceof InstructorConstraint) {
    335                iInstructorConstraints.addElement(constraint);
    336            } else if (constraint instanceof JenrlConstraint) {
    337                iJenrlConstraints.addElement(constraint);
    338            } else if (constraint instanceof RoomConstraint) {
    339                iRoomConstraints.addElement(constraint);
    340            } else if (constraint instanceof DepartmentSpreadConstraint) {
    341                iDepartmentSpreadConstraints.addElement(constraint);
    342            } else if (constraint instanceof GroupConstraint) {
    343                iGroupConstraints.addElement(constraint);
    344            }
    345        }
    346        public void removeConstraint(Constraint constraint) {
    347            super.removeConstraint(constraint);
    348            if (constraint instanceof InstructorConstraint) {
    349                iInstructorConstraints.removeElement(constraint);
    350            } else if (constraint instanceof JenrlConstraint) {
    351                iJenrlConstraints.removeElement(constraint);
    352            } else if (constraint instanceof RoomConstraint) {
    353                iRoomConstraints.removeElement(constraint);
    354            } else if (constraint instanceof DepartmentSpreadConstraint) {
    355                iDepartmentSpreadConstraints.removeElement(constraint);
    356            } else if (constraint instanceof GroupConstraint) {
    357                iGroupConstraints.removeElement(constraint);
    358            }
    359        }
    360
    361        /** The list of all instructor constraints */
    362        public Vector getInstructorConstraints() { return iInstructorConstraints; }
    363        /** The list of all group constraints */
    364        public Vector getGroupConstraints() { return iGroupConstraints; }
    365        /** The list of all jenrl constraints */
    366        public Vector getJenrlConstraints() { return iJenrlConstraints; }
    367        /** The list of all room constraints */
    368        public Vector getRoomConstraints() { return iRoomConstraints; }
    369        /** The list of all departmental spread constraints */
    370        public Vector getDepartmentSpreadConstraints() { return iDepartmentSpreadConstraints;  }
    371        /** Max capacity for too big rooms (3/2 of the number of students) */
    372        public static long getMaxCapacity(long nrStudents) {
    373            return (3*nrStudents)/2;
    374        }
    375    }