UniTime.org Logo University Timetabling
Comprehensive Academic Scheduling Solutions
Examination Timetabling Benchmark Datasets
Purdue Final Examination Data Sets
The following nine examination data sets were collected using the UniTime application. The are all final examination problems from Purdue University, for each semester starting Fall 2008 when UniTime was used for examination timetabling at the university for the first time. Download all nine data sets in one zip file here.

Problem Characteristics
The data sets have the following properties:
    Problem Fall 2012 Spring 2012 Fall 2011 Spring 2011
    Exams1,8641,7981,9141,866
       with exam seating819780827801
    Students33,27931,59333,85631,688
    Enrollments117,265111,345122,384113,211
    Distribution constraints201361
    Exams fixed in time57635899
    Exams fixed in room24670170
    Large exams (600+)22201817
    Exams needing a room split1092013
    Exams with original room1,5331,4851,5241,485
    Density3.283%3.586%3.456%3.519%
    Average periods28.145 ± 0.40928.022 ± 0.46628.152 ± 0.40627.498 ± 0.710
    Average rooms262.892 ± 6.116265.771 ± 4.696256.247 ± 9.800234.674 ± 11.772
       that are big enough143.300 ± 38.480143.055 ± 37.109135.087 ± 40.072126.626 ± 37.492
     
    Problem Fall 2010 Spring 2010 Fall 2009 Spring 2009 Fall 2008
    Exams2,2232,1021,9932,1672,198
       with exam seating875835890794857
    Students34,41830,35334,23932,21434,988
    Enrollments129,090113,864125,347119,803130,539
    Distribution constraints61081413
    Exams fixed in time121105104161166
    Exams fixed in room89109696274
    Large exams (600+)2117232224
    Exams needing a room split74912
    Exams with original room1,9051,7991,7261,8701,849
    Density2.872%3.025%3.294%2.927%2.985%
    Average periods27.460 ± 0.72827.601 ± 0.66627.494 ± 0.70526.922 ± 0.98226.861 ± 1.005
    Average rooms250.693 ± 5.574260.208 ± 7.252266.016 ± 5.403261.409 ± 3.817261.192 ± 4.846
       that are big enough147.143 ± 33.645156.327 ± 36.201149.011 ± 36.835163.110 ± 31.800156.685 ± 34.262

In the above table, the number of examinations, students, student examination enrollments and the distribution constraints for each data set are presented. All of the datasets have 29 examination periods, all 2 hours long starting at 8 am, 10:30am, 1 pm, 3:30 pm, and 7 pm each day from Monday till Saturday, except of the last period on Saturday (at 7 pm). All four Saturday periods (8 am, 10:30am, 1 pm, and 3:30 pm) are strongly discouraged (penalty = 4), Friday afternoon periods (1 pm, 3:30 pm, and 7 pm) are discouraged (penalty = 1).

In all problems there are only a few distribution constraints and all are marked as hard (they cannot be violated). Moreover, in each problem, there are a few exams pre-assigned in time and/or room. The number of large exams, those exams for 600 or more students, is not very high either, which is good as they all should fit within the first 24 periods (excluding Saturday and the last period on Friday; the density between these exams is over 80%). There are also a few exams in each problem that need to be split into at least two rooms as there is no room big enough for the exam in its domain, either because of the number of students in the exam or due to room requirements that are put on the exam. The probability of a pair of two exams having at least one student in common is shown in the density row. The last three rows show the domain sizes of the problems, i.e., average number of available periods and rooms to an exam. The last column only counts the rooms that are big enough for the exam to fit in without the need to be split into multiple rooms. About 43% of all exams require examination (alternative) seating.

Configurations
The following configurations were used in the MISTA 2013 experiments:
    Weight production base color split
    Direct Conflict1,0001,000,000-1,000,000
    More Than 2 A Day10010,00010,00010,000
    Back-To-Back10100100100
    Period Penalty1111
    Room Penalty1111
    Room Split10101010
    Room Split Distance0.010.010.010.01
    Room Size0.0010.0010.0010.001
    Room Size Factor1.11.11.11.1
    Rotation Penalty0.00010.00010.00010.0001
    Large Exams Weight2,500,0002,500,0002,500,0002,500,000
    Room Distance0.00010.00010.00010.0001
    Hard Constraint Violation--1,000-
    Exam Period Split---5,000

The production configuration contains the weights as they are used in practice by the University. The base configuration gives more weight to direct student conflicts to give a better comparison with the next two configurations. In the color configuration, the graph coloring solution is used to construct an initial assignment of exams to periods and rooms and it is not allowed to create a direct conflict. To be able to do this, however, it was necessary to add the ability to break other hard constraints, namely the ability to use a prohibited period or room by an exam or to break a distribution constraint. It was still not allowed to have multiple examinations in the same room at the same period, to exceed the room capacity, or to assign an exam into more than the given maximal number of rooms.

The last configuration (named split) attempts to minimize the number of direct conflicts by adding the ability to split an exam into two. In these runs, an additional neighborhood was used (along with all the other neighborhoods mentioned above) that allowed splitting a randomly selected examination into two, assigning each in a different period, and moving students freely between these two exams if the improvement in the weighted number of student conflicts (including direct, more than two on a day, and back-to-backs) was higher than the penalization for splitting an exam Exam Period Split. If a randomly selected exam was already split, the neighborhood also tried to reshuffle the students between the two exams or merge the exams back together if the split was no longer needed (i.e., the weighted sum of student conflicts avoided by the split was smaller than the weight of the split).

Results
The following tables contain experimental results for the first five datasets using the above four configurations (the results for the last four data sets are in the MISTA 2013 paper). The experiments were computed on an Apple MacBook Pro with a 3.06 GHz Intel Core 2 Duo processor and 8 GB RAM, running Mac OS X 10.7.3 and Java 1.6.0. In all the experiments the solver was given a time limit of two hours, and the average values of ten independent runs are shown.
    production Fall 2010 Spring 2010 Fall 2009 Spring 2009 Fall 2008
    Direct Conflicts 120.5 ± 2.7 112.3 ± 4.6 129.3 ± 5.0 191.7 ± 3.8 159.0 ± 4.5
    More Than 2 A Day 494.3 ± 14.6 481.6 ± 12.4 455.0 ± 14.6 510.8 ± 9.2 724.8 ± 10.8
    Back-To-Back 5181.5 ± 62.4 4741.6 ± 60.3 4891.8 ± 97.2 5496.1 ± 58.5 5933.7 ± 90.4
    Period Preference [%] 91.1 ± 0.2 91.1 ± 0.3 90.9 ± 0.2 90.7 ± 0.2 90.2 ± 0.2
    Room Preference [%] 72.4 ± 0.5 82.6 ± 0.3 72.8 ± 0.8 75.8 ± 0.4 82.3 ± 0.3
    Room Distance [m] 49.3 ± 1.9 42.4 ± 3.0 54.8 ± 3.8 41.5 ± 1.5 45.0 ± 0.6
    Room Split 37.8 ± 1.7 16.5 ± 3.7 28.2 ± 1.8 5.1 ± 0.9 14.4 ± 1.4
    Room Split Distance [m] 116.2 ± 15.0 51.7 ± 20.0 102.5 ± 4.4 78.3 ± 40.7 210.7 ± 42.5
    Room Size 52.6 ± 1.1 58.6 ± 2.1 52.0 ± 1.5 59.8 ± 1.6 51.7 ± 1.3
    Rotation Penalty 12.89 ± 0.02 12.36 ± 0.04 12.37 ± 0.05 12.04 ± 0.04 12.21 ± 0.03
    Large Exams Penalty 0.0 ± 0.0 0.0 ± 0.0 0.0 ± 0.0 0.0 ± 0.0 0.0 ± 0.0
     
    base Fall 2010 Spring 2010 Fall 2009 Spring 2009 Fall 2008
    Direct Conflicts 111.4 ± 1.9 79.2 ± 3.7 91.6 ± 8.1 130.3 ± 5.8 117.4 ± 4.3
    More Than 2 A Day 576.9 ± 20.4 594.7 ± 16.6 619.8 ± 38.3 721.0 ± 42.8 848.1 ± 43.2
    Back-To-Back 5770.8 ± 96.3 5518.5 ± 195.3 6197.7 ± 289.2 6679.7 ± 211.3 7033.9 ± 71.7
    Period Preference [%] 87.3 ± 0.4 87.5 ± 0.3 88.0 ± 0.4 87.8 ± 0.2 87.5 ± 0.4
    Room Preference [%] 71.4 ± 0.5 81.7 ± 0.4 71.2 ± 0.4 75.1 ± 0.3 81.9 ± 0.3
    Room Distance [m] 49.8 ± 1.5 43.7 ± 1.8 57.2 ± 2.7 44.2 ± 1.1 45.1 ± 1.5
    Room Split 37.1 ± 2.4 6.5 ± 1.2 31.4 ± 4.3 4.0 ± 1.3 16.8 ± 4.1
    Room Split Distance [m] 119.4 ± 20.7 15.4 ± 16.8 88.2 ± 12.0 51.6 ± 30.8 144.2 ± 21.6
    Room Size 50.6 ± 2.8 65.3 ± 1.6 51.4 ± 1.7 60.2 ± 2.1 51.1 ± 3.4
    Rotation Penalty 13.18 ± 0.04 12.61 ± 0.05 12.61 ± 0.06 12.25 ± 0.05 12.39 ± 0.04
    Large Exams Penalty 0.0 ± 0.0 0.0 ± 0.0 1.0 ± 0.0 0.0 ± 0.0 0.0 ± 0.0
     
    color Fall 2010 Spring 2010 Fall 2009 Spring 2009 Fall 2008
    Direct Conflicts 0.0 ± 0.0 0.0 ± 0.0 0.0 ± 0.0 - 0.0 ± 0.0
    More Than 2 A Day 900.8 ± 23.7 1259.9 ± 33.9 1101.6 ± 43.5 - no solution - 1156.1 ± 19.1
    Back-To-Back 7334.2 ± 88.5 6382.3 ± 80.8 7333.7 ± 109.4 - exists - 7652.5 ± 115.7
    Period Preference [%] 86.4 ± 0.2 87.4 ± 0.3 86.1 ± 0.3 - 86.5 ± 0.4
    Room Preference [%] 70.7 ± 0.8 81.5 ± 0.5 70.8 ± 0.4 - 81.6 ± 0.2
    Room Distance [m] 60.1 ± 4.5 49.4 ± 2.4 65.6 ± 3.6 - 30 colors - 49.7 ± 2.0
    Room Split 38.8 ± 7.4 14.9 ± 2.9 23.1 ± 3.3 - needed - 437.1 ± 21.4
    Room Split Distance [m] 235.2 ± 33.3 82.1 ± 39.7 164.3 ± 36.2 - 228.8 ± 18.2
    Room Size 54.5 ± 2.5 57.7 ± 2.5 55.3 ± 1.9 - 53.8 ± 2.4
    Rotation Penalty 13.45 ± 0.03 12.73 ± 0.05 12.93 ± 0.04 - 12.52 ± 0.04
    Large Exams Penalty 2.0 ± 0.0 0.0 ± 0.0 1.0 ± 0.0 - 2.0 ± 0.0
    Unavailable Period 33.7 ± 1.4 26.7 ± 1.2 26.6 ± 1.8 - 49.5 ± 2.5
    Unavailable Room 13.3 ± 1.5 10.7 ± 1.8 13.6 ± 1.3 - 4.4 ± 1.6
    Violated Distribution 2.0 ± 0.0 6.5 ± 0.5 3.0 ± 0.0 - 8.1 ± 0.7
     
    split Fall 2010 Spring 2010 Fall 2009 Spring 2009 Fall 2008
    Direct Conflicts 5.0 ± 0.0 3.0 ± 0.0 1.0 ± 0.0 16.0 ± 0.0 3.0 ± 0.0
    More Than 2 A Day 124.2 ± 20.2 132.3 ± 11.7 80.9 ± 11.9 108.0 ± 18.9 131.8 ± 16.8
    Back-To-Back 2117.6 ± 106.7 2141.4 ± 139.5 1707.3 ± 94.6 1959.7 ± 148.3 2046.8 ± 89.8
    Period Splits 95.90 ± 6.56 90.50 ± 4.45 94.20 ± 2.35 105.40 ± 5.44 113.90 ± 3.70
    Period Preference [%] 87.8 ± 0.2 87.5 ± 0.3 88.1 ± 0.4 87.8 ± 0.5 88.2 ± 0.5
    Room Preference [%] 69.3 ± 0.8 81.2 ± 0.2 70.5 ± 0.4 72.1 ± 5.2 81.1 ± 0.4
    Room Distance [m] 56.2 ± 2.2 46.1 ± 1.8 59.7 ± 2.4 55.5 ± 20.7 49.2 ± 1.5
    Room Split 43.4 ± 10.3 9.5 ± 3.6 26.8 ± 7.9 13.4 ± 6.3 20.6 ± 3.8
    Room Split Distance [m] 95.6 ± 16.6 54.9 ± 29.6 65.9 ± 29.5 135.3 ± 28.1 105.6 ± 46.3
    Room Size 63.1 ± 2.7 72.7 ± 2.1 70.4 ± 2.4 73.5 ± 13.6 63.1 ± 4.2
    Rotation Penalty 13.19 ± 0.05 12.60 ± 0.03 12.62 ± 0.03 12.40 ± 0.12 12.32 ± 0.07
    Large Exams Penalty 0.0 ± 0.0 0.0 ± 0.0 0.0 ± 0.0 0.0 ± 0.0 0.0 ± 0.0

Any of the above experiments can be reproduced using the CPSolver library:
    java -Xmx2g -cp cpsolver-all-1.2.jar net.sf.cpsolver.exam.Test \
       exam-production.cfg pu-exam-fal12.xml pu-exam-fal12-s.xml
where exam-production.cfg is one of the above four configurations, pu-exam-fal12.xml is an input problem and pu-exam-fal12-s.xml is the resulting solution.
  © 2017 UniTime Last modified: March 5, 2012