Final Submission ITC-2019

Instance | Cost | Students | Time | Room | Distribution
agh-fis-spr17 | 35139 | 3555 | 2248 | 2312 | 404
agh-ggis-spr17 | 194138 | 26097 | 2737 | 22270 | 2029
mary-spr17 | 51147 | 1114 | 1376 | 805 | 7290
muni-fi-spr16 | 19314 | 3286 | 352 | 628 | 120
muni-fsps-spr17 | 211142 | 2040 | 58 | 292 | 360
pu-llr-spr17 | 68003 | 7642 | 1169 | 2880 | 30
tg-fal17 | 6774 | 0 | 1792 | 30 | 158
agh-ggos-spr17 | 79745 | 8230 | 6045 | 9045 | 358
agh-h-spr17 | 55887 | 1848 | 1442 | 1039 | 2656
lums-spr18 | 820 | 0 | 0 | 575 | 49
muni-fi-spr17 | 18080 | 3212 | 284 | 958 | 21
muni-fsps-spr17c | 618217 | 6048 | 411 | 1027 | 141
muni-pdf-spr16 | 310994 | 7853 | 38680 | 27094 | 900
nbi-spr18 | 49924 | 7196 | 5946 | 9208 | 5
yach-fal17 | 32198 | 4856 | 8 | 1008 | 687
lums-fal17 | 1151 | 0 | 105 | 626 | 63
mary-fal18 | 44097 | 4107 | 596 | 665 | 234
tg-spr18 | 31900 | 0 | 1942 | 3996 | 1201

Journal of Scheduling

How to run the project

./timetabler OriginalProblem.xml OriginalSolution.xml DisruptionsProfile.p Distance_Metric[Hamming|Weighted|GAP] Model[Boolean|Integer|Mixed|GRASP|LNS] [model_parameters] [-c] [-w]

This will generate a valid solution in the output folder. The results is encoded using ITC-2019 XML format.

Arguments of the program

OriginalProblem

The data instance of the problem was to be encoded using ITC-2019 XML format. It is possible to use the XML encoding of ITC-2007 as well.

OriginalProblem

The solution for the data instance was to be encoded using ITC-2019 XML format. It is possible to use the XML encoding of ITC-2007 as well.

Disruptions Profiles

The file with the rules to randomly generate the disruptions.

Format

The format is separated into four types of disruptions due to their common characteristics.

• Disruptions_type[Overlap|Preference_Room|Invalid_Room|Preference_Time|Invalid_Time|Remove_Room|Invalid_Assignment] %percentage_of_occurrences
• Remove_Room_Day %percentage_of_closed_down_rooms %percentage_of_days
• Disruptions_type[Modify_Enrolments|Modify_N_Lectures] %percentage_of_occurrences distribution_mean distribution_standard_deviation
• Disruptions_type #Lectures Average_Length Average_Enrollments

Distance_Metric

There are three distance metrics available:

• Hamming Distance
• Weighted Hamming Distance (the number of students affected by the change)
• GAP: reducing the number of GAPs in students timetable.

Model

There are three LP models that require Gurobi and two local search methods.

The three LP models are:

• Boolean Model - two Boolean variables
• Integer Model - one integer variable
• Mixed Model - one integer and one Boolean variable

The two local search methods:

• GRASP
• LNS

Model Parameters

The Mixed model requires an additional parameter to specify the type of approach. The problem can be solved by:

• 1: splitting into two problems
• 0: solve the complete problem

GRASP method require two additional parameters;

• The number of iterations
• The size of the Restricted Candidate List

Symmetry Cuts

To activate symmetry cuts run with the flag -c.

Warm Start

To activate the warm start procedure run with the flag -w.

Dependencies

Gurobi solver and c++ compiler.

Data Sets

IST

The folders data/input/IST and data/output/IST contain the data sets from Instituto Superior Técnico (IST).

ITC-2007

The folders data/input/ITC-2007 and data/output/ITC-2007 contain the data sets from ITC-2007 Curriculum based timetabling track. The results were obtained from Lindahl et al..

ITC-2019

The folder data/input/ITC-2019 contains some data sets from ITC-2019.

Disruptions Profiles

The folder data/Disruption/profiles/ contains disruptions learn from the timetables of the last 5 years of IST.

Authors

Alexandre Lemos, Pedro T. Monteiro and Inês Lynce.

Contacts:

If you have any comments or questions, please contact us.