DM826 - Modeling and Solving Constrained Optimization Problems
Obligatory Assignment 3, Spring 2012 [pdf format]

In this assignment you are asked to help a Danish school to make the timetable of their classes. A class is a body of students that belong to the same grade and the section. The school has 11 grades and about 3 sections per grade. Two of these grades are the grade 0 and 10 and they are scheduled apart. You will have to consider the remaining 9 grades that make the primary school, grades 1 to 3, the middle school, grades 4 to 6, and the high-school, grades 7 to 9.

There are about 15 subjects, and each grade has a required number of hours per week for each subject.

A teacher educated in Denmark usually has 2 to 4 main subjects that they can teach. The assignment of teachers to subjects and classes is predetermined by the school management since this has to satisfy competence requirements and some continuity between grades (for example a teacher that has taught Danish to a class in the first grade of the primary school is typically kept for teaching the same subject to the same class also the year after).

The preassignment of teachers to subjects and classes determines also the total amount of teaching hours per week, which is in any case below a maximum of 24 hours. Part time teachers are also included.

The working week at the school is made of 5 days and each day is divided into 8 time periods of one hour each. Your task is to schedule the meetings between class and subjects in the time periods in such a way that the following conditions are satisfied:

From the subject perspective:

1. [1] all required subject meetings for a class must be scheduled;
2. if a subject has more than one meeting with a class in a day then these meetings must be assigned consecutive time periods.

From the teacher perspective:

1. [1] teachers do not have overlapping meetings;
2. the meetings involving the same class in a day must occur in consecutive time periods;
3. a teacher must be involved in at least 3 meetings on a day or none at all;

From the class (ie, student) perspective:

1. [1] classes do not have overlapping meetings;
2. the meetings involving the same teacher in a day must occur in consecutive time periods;
3. all classes must have at least 4 meetings scheduled each day;
4. all meetings involving classes in the grades 1 through 3 must be scheduled in the time periods from 1 to 5 on each day;
5. all classes in grades 4 to 7 must have meetings scheduled in the first time period of each day;

You are asked to address the following subtasks:

1. [A]Formulate the problem as a constraint satisfaction problem and describe the model with mathematical notation in a written report. Define only constraints that can be found in Gecode.
2. Implement the model in gecode-python and assess its performance on the numerical data provided (see sec. Practicalities). It is very likely that the instance provided cannot be solved within the time limit of 60 seconds that you should use. In this case you should relax some of the constraints and try to achieve the best possible solution with respect to the constraints relaxed. Document in the report the best solution you found providing details about how it was obtained and statistics about which constraints are in case violated.

---

 7:          [2 3 4]          [2 3 4]               []               []               [] 
 8:          [2 3 4]          [1 2 3]               []               []               [] 
16:      [0 1 2 3 4]      [0 1 2 3 4]      [0 1 2 3 4]               []               [] 
19:               []               []               []               []               [] 
21:               []               []      [0 1 2 3 4]      [0 1 2 3 4]      [0 1 2 3 4] 
23:               []               []               []               []               [] 
27:          [2 3 4]        [1 2 3 4]      [0 1 2 3 4]      [0 1 2 3 4]      [0 1 2 3 4] 
28:          [0 1 2]          [2 3 4]               []      [0 1 2 3 4]      [0 1 2 3 4] 
30:               []               []          [2 3 4]          [0 1 2]          [2 3 4] 
51:               []               []          [2 3 4]          [1 2 3]          [2 3 4] 


(1, 0): {0: 'TyF', 1: 'TyF', 2: 'Dan', 3: 'Dan', 4: 'Dan'}
        {0: 'TyF', 1: 'Dan', 2: 'Dan', 3: 'Dan', 4: 'TyF'}
        {0: 'Eng', 1: 'TyF', 2: 'Dan', 3: 'Dan', 4: 'Dan'}
        {0: 'Dan', 1: 'Dan', 2: 'Dan', 3: 'Eng', 4: 'Eng'}
        {0: 'Eng', 1: 'Eng', 2: 'Dan', 3: 'Dan', 4: 'Dan'}
        
(1, 1): {0: 'TyF', 1: 'TyF', 2: 'Dan', 3: 'Dan', 4: 'Dan'}
        {0: 'TyF', 1: 'Dan', 2: 'Dan', 3: 'Dan', 4: 'Kri'}
        {0: 'Kri', 1: 'Kri', 2: 'Mat', 3: 'Mat', 4: 'Mat'}
        {0: 'Mat', 1: 'Mat', 2: 'Mat', 3: 'Kri', 4: 'Kri'}
        {0: 'Kri', 1: 'Kri', 2: 'Mat', 3: 'Mat', 4: 'Mat'}
        
(1, 2): {0: 'Dan', 1: 'Dan', 2: 'Dan', 3: 'Kri', 4: 'Kri'}
        {0: 'Kri', 1: 'Kri', 2: 'Dan', 3: 'Dan', 4: 'Dan'}
        {0: 'Kri', 1: 'Kri', 2: 'Mat', 3: 'Mat', 4: 'Mat'}
        {0: 'Dan', 1: 'Mat', 2: 'Mat', 3: 'Mat', 4: 'Dan'}
        {0: 'Dan', 1: 'Dan', 2: 'Mat', 3: 'Mat', 4: 'Mat'}
        
(2, 0): {0: 'TyF', 1: 'TyF', 2: 'Dan', 3: 'Dan', 4: 'Dan'}
        {0: 'TyF', 1: 'TyF', 2: 'Dan', 3: 'Dan', 4: 'Dan'}
        {0: 'Kri', 1: 'Kri', 2: 'Mat', 3: 'Mat', 4: 'Mat'}
        {0: 'Mat', 1: 'Mat', 2: 'Mat', 3: 'Kri', 4: 'Kri'}
        {0: 'Kri', 1: 'Kri', 2: 'Mat', 3: 'Mat', 4: 'Mat'}
        
(2, 1): {0: 'Dan', 1: 'Dan', 2: 'Dan', 3: 'TyF', 4: 'TyF'}
        {0: 'TyF', 1: 'TyF', 2: 'Dan', 3: 'Dan', 4: 'Dan'}
        {0: 'Eng', 1: 'TyF', 2: 'Dan', 3: 'Dan', 4: 'Dan'}
        {0: 'Eng', 1: 'Kri', 2: 'Kri', 3: 'Kri', 4: 'Eng'}
        {0: 'Eng', 1: 'Eng', 2: 'Kri', 3: 'Kri', 4: 'Kri'}

Figure 1: A solution to a small case with 2 grades and 2 sections. Above is the teacher perspective with the working periods and below the timetable for the four classes identified by (grade, section).

---

Restrict your written report to a length of 3 pages. However, include in an appendix a print out of a solution in a similar fashion as in Figure 1.

Practicalities

The implementation and testing is to be carried out in GECODE. All scripts mentioned below can be found at http://www.imada.sdu.dk/~marco/DM826/Resources/. Download and uncompress the archive dm826-ass3.tgz

• You should use gecode-python version 0.25 (be-aware that it has been updated on the February 22). This version includes the possibility to print out the statistics that are required in the assignment and to halt the search with some parameters.
• There are two python scripts, school.py and school_data.py. The file you have to fill is school.py. The file school_data.py defines the data of the instance. Additional text files are the data regarding the pre-assignment of teachers to subjects and classes.
• The program is run from command line with two parameters: the time limit in seconds and the name of the file where preassignment data are to be found. Example:

  python school 60 A2.txt
  

• The organization of the scripts differs from the first two assignments: there are not function and methods. You can define some if you need but do not change school_data.py.
• There is no solution checker. Check a solution visually inspecting the output in the standard output, in a similar fashion as done in Figure 1. A skeleton waiting to be filled with your variables is started in school.py.
• Submit only the file school.py. It will be copied in a directory containing the same files as those provided with the assignment and it will be run on a linux environment.
• Keep all your files anonymous and use instead your CPRN as identifier.
• The file school_data.py makes available the following data structures (print them to see how they look like):
  • days set of days [0..5]
  • periods periods per day [0..8]
  • nteachers num. of teachers
  • grades a list of grades
  • sections a list of sections per grade
  • id_to_gs mapping class ids to section per grade
  • nclasses total number of classes
  • subjects a list of subjects
  • all_teachers a list of all teachers available

    teacher_duties a dictionary with for each teachers which meeting is assigned (c,s,sbj)

  • teacher_load a dictionary with the weekly working load per teacher
  • teachers subset of teachers really assigned to some work
  • class_load a dictionary with hours of teaching for class per week
  • class_requirements a dictionary that stores for each class a dictionary of subjects and the number of hours for each subject.