Here we use Constraint Programming to schedule the exams at the Faculty of Science at SDU for the ordinary session of January 2022.
A starting package for this case is available Exams.tgz.
Let $E$ be the set of exams for courses that need to have a date scheduled. Let $D$ be the set of days that are available for scheduling exams. Exams that for some reason cannot have overlapping schedules are called conflicting exams. In particular, exams with the same teacher or censor and exams that belong to the same study program are considered conflicting.
An exam schedule is an assignment of exams to days for the exam, that is, it is a function $\sigma : E \to 2^D$. An exam schedule is feasible if it satisfies the following constraints:
Each exam in input is scheduled to start and finish in the days available.
Each exam is assigned a number of days, $|\sigma(e)|$, equal to the number of required days to carry out the exam.
Exams with exam duration more than one day receive consecutive days. No holes due to weekend or holidays are allowed within an exam schedule.
Exams with preassigned dates must respect those dates.
Exams that are joined must have schedules starting on the same day. (The durations for both should be the sum of the durations of the two exams but this is less important).
Exams that are conflicting must be scheduled in sets of days with empty intersection.
The total number of students having written exams in a day must be
smaller than MAX_SEATS_PER_DAY. Exams with predefined dates do not
contribute to this constraint.
The total number of oral exams in a day must be smaller than
MAX_ROOMS_PER_DAY in order to ensure that a room to host them can
be found. Exams with predefined dates do not count in this
constraint.
If a feasible schedule that satisfies all the above constraints is found, then one should try to maximize the distance between the starting times of exams that share students. This optimization task can be achieved in different ways, for example, by introducing a new constraint that enforces a distance of $R$ days between exams that share students and then maximizing $R$ and/or minimizing the number of students violating this constraints, or by devising a penalty scheme that penalizes exams sharing students that are scheduled too close.
If a feasible schedule cannot be found then one must relax the
constraints on the conflicting courses and treat them as those sharing
students but with higher priority in avoiding overlaps. The parameter
WEIGHT_PROGRAMS indicates the relative importance between avoiding
overlaps for conflicting courses and avoiding overlaps for courses that
only share students.
You are given a starting package containing data on the exams for E20 and E21 at the Faculty of Science, SDU and some Python code to read the data, carry out a few calculations, and output it in the format most convinient for your MiniZinc model.
Data about the days available for scheduling and the parameters
MAX_SEATS_PER_DAY, MAX_ROOMS_PER_DAY and WEIGHT_PROGRAMS is
provided in a json file config.json (see below for an example). The
field DAYS contains a list of days with weekends and holidays already
removed. The days are given as a number from DAYONE. You do NOT need
to convert them back in dates. The other fields in the input data are
not relevant for this assignment.
{
"DISTANCE": 3,
"SEMESTER": "e2020",
"SESSION": 0,
"MAX_SEATS_PER_DAY": 300,
"MAX_ROOMS_PER_DAY": 20,
"MAX_STUDENTS_PER_DAY": 16,
"WEIGHT_PROGRAMS": 100,
"YEAR": 2021,
"MAX_EXAMS": 15,
"MAX_ECTS": 40,
"FIRST_DAY": [1,4],
"LAST_DAY": [1,29],
"MONTH": 1,
"DAYS": [4,5,...,28,29],
"DAYONE": "2021-01-01"
}
Data about the exams is provided in a json file consisting of a dictionary, whose elements are the exams $e\in E$. See the code snippet below. The key of each exam $e \in E$ is the STADS identifier. Then, for each entry corresponding to an exam the following information is provided (not all the information is relevant for this assignment):
EKA the STADS code of the exam. The same as the key.
STADS_ID the STADS code of the course to which the exam belongs
NAT_code the corresponding code of the course at the Faculty of
Natural Sciences. This might not be unique as a course might have
both a written exam and an oral exam.
title the title of the course
ECTS the number of ECTS for the course
Prøveform the form of the exam: written or oral
stype a shortname for the form of exam: ‘m’ for oral and ‘s’ for
written
Administrationsenhed the administering unit
institute the administering institute
ECTS/prøve the ECTS per exam component
Eksamensperiode when the exam has to be offered: in the ordinary
session and in the reexam session
students a list of students registered to the exam
nstds the total number of students registered
rdays duration $r_e$ of the exam expressed in number of required
days. A written exam requires one day while the number of days of an
oral exam is the number of students divided by 16, the number of
students that can be examined orally in one day.
schedule if the exam has already been scheduled then information
about the schedule is provided here as a list of days given by the
pair number of day, date.
Faste datoer preassigned dates the same as the previous field, it
can be ignored.
joined a list of exams that must be scheduled jointly, that is
starting on the same days
conflicting a list of exams that must necessarily be scheduled in
different days.
{
"N300003102": {
"STADS_ID": "N300003101",
"NAT_code": "MM531",
"title": "Differentialligninger II",
"ECTS": 5,
"Administrationsenhed": "IMADA",
"EKA": "N300003102",
"Prøveform": "Mundtlig prøve",
"ECTS/prøve": 5.0,
"Eksamensperiode": "Ordinær/reeksamen",
"Faste datoer": null,
"stype": "m",
"institute": "imada",
"students": [
"xxxxxxx",
"yyyyyyy",
"zzzzzzz",
"wwwwwww",
],
"nstds": 4,
"rdays": 1,
"joined": [
"N310004102"
],
"conflicting:" []
},
...
}
An instance of the exam schedule problem consists of two files:
config.json and a file containing details about the exams to schedule.
Specifically, you are given exams composing five different instances of
the problem with different size and difficulty:
| E20 | E21 | |
|---|---|---|
| Exams in samf | 6 | |
| Exams in biologi | 8 | 21 |
| Exams in bmb | 17 | 36 |
| Exams in imada | 41 | 76 |
| Exams in fkf | 45 | 60 |
| Exams in all | 123 | 205 |
The Python code calculates a matrix with the number of shared students between exams that can turn out relevant for the assignment.
For an excellent performance you have to give account of the tasks below in a written report of a most 10 pages (using the template provided in Assignment 1):
design a CP model to find exam schedules according to the constraints and criteria described above
address symmetry issues, if any
implement the model in MiniZinc
test alternative variable-value heuristics
test the contribution of random restarts
Run all computational experiments for a maximum time of 20 minutes. Report the results in tables containing at least the following columns:
name of the instance (biologi, bmb, imada, fkf, all)
time (in sec) when a solution was found or when the program was stopped
number of nodes explored
whether a solution was found
if a solution was not found how many constraints the best solution found was violating (or in case you have chosen to use the penalty scheme, the best penalty value reached).
If you have chosen the approach with the constraint on $R$ then you can report the results for different values of $R$ on the same instance, in which case $R$ should constitute another column.
Der også typen “o” som er for Bachelorprojekt. Skal dettes ses som “oral”, “written” eller slet ikke planlægges?
You are right that ‘o’ is mostly for bachelorprojekt but it has to be interpreted as requiring one single day rather than, as in the oral exams, requiring as many days as the number of participants requires. Bachelorprojekter should be scheduled in the first day of those available. This is because it is supposed to be the submission of the report. All those exams should have a date already given and hence should not require to be scheduled.
Are there any specific requirements on how the output should look like or is it entire up to the student to format the output they wishes?
You can either report the solution in a text file as follows:
N100007102,27
N100008102,6
N100008132,12
N100015102,4
N100018102,6
N100020102,13
N100029102,17,18,19,20
or in a json file as follows:
{
"N100007102": [
27
],
"N100008102": [
6
],
"N100008132": [
12
],
"N100015102": [
4
],
"N100018102": [
6
],
"N100020102": [
13
],
"N100029102": [
17,
18,
19,
20
],
which can be easily obtained oin python importing the module json
and the following line of code, where dates is a
dictionary with exam STADS code as key and the list of days as values:
json.dump(dates, fp=filehandle, sort_keys=False, ignore_nan=True,
indent=4, separators=(',', ': '), ensure_ascii=False)
In config.json in E21 the set of available days start from January
4th, but some of the exams are already scheduled to be at January
3rd. Does this mean that exams can be scheduled at January 3rd as
well?
No, exams can only be scheduled from the 4th. But exams scheduled on the 3rd should count in the distances.
Does this mean that if exams are pre-planned, they should be planned on that date, even though it is a “illegal” day? And thoses exams that are not pre-planned, they need to follow the rules for “legal” days?
Yes. You do not have to plan exams that are already planned and it is fine to leave where they are but they can be taken into account when calculating how isolated an exam is.
Should the “forbidden” and “available” information that is given at some of the exams be used when scheduling them?
That would be nice, yes.
Exams listed in conflicting are courses that belong to the same
study program. Avoiding overlaps among these exams is a hard
constraint. Avoiding overlaps among exams that share students is a
soft constraint.
For E20 it should be possible to avoid overlaps amongs conflicting
exams on all instances. For E21 it is not known. The assignment states
"If a feasible schedule cannot be found then one must relax the
constraints on the conflicting courses and treat them as those sharing
students but with higher priority in avoiding overlaps." In this case,
the WEIGHT_PROGRAMS indictaes the relative importance of the two
overlap constraints.
Note that you if you find infeasible instances it might be good having
a look at what are the reasons for infeasibility. In MiniZinc it is
possible to find the Miminum Unsatisfiable Subset of constraints that
makes a problem unsatisfiable. see Chap 3.7 from the MiniZinc
manual. Known possible infeasibility issues in E20: conflicting
includes the exam itself; the exams B560001102 and B560003102 share a
single student (5a51dabaaa908176c2b9be887a688afd) but are also both
preassigned to start at day 4. Are welcome to resolve issues of this
type by changing the instance data, (eg, removing that student or one
of the exams). However, in doing this operation seek to apply the
minimal impact on the instance.