Repository for OMA assignment 2017-2018 for the degree course in Computer Engineer of Polytechnic of Turin.
Let us consider a set E of exams, to be scheduled during an examination period at the end of the semester, and a set S of students. Each student is enrolled in a subset of exams, at least one. The examination period is divided in t_max ordered time-slots.
By law, conflicting exams (i.e. having enrolled students in common) cannot take place during the same time-slot. Moreover, to incentive universities at creating timetables more sustainable for the students, the Ministry of Education assigns a penalty for each couple of conflicting exams scheduled up to 5 time-slots apart. More precisely, given the number N_(e,e') of students enrolled in both conflicting exams e and e', which are scheduled i time-slots apart, the penalty is calculated as 2^(5-i)*N_(e,e)/abs(S).
The Examination Timetabling Problem (ETP) aims at assigning each exam to a specific time-slot ensuring that:
- Each exam is scheduled once during the period,
- Two conflicting exams are not scheduled in the same time-slot.
The objective is to minimize the total penalty resulting from the created timetable.
Assumptions:
- During each time-slot there is always a number of available rooms greater than the total number of exams;
- Rooms have enough capacity with respect to the number of enrolled students.
The model is described in a OMA_ETT-Model.pdf
document stored in the Latex folder of the project.
The final report of the project is on a file named ETPreport_OMAMZ_group03.pdf
in the report folder.
- Provide a Linear Programming formulation for the ETP (deadline 1).
- Propose a solution approach for the ETP by exploiting one (or more) heuristic and meta-heuristic algorithms presented during the course.
- Develop/implement such a solution algorithm through a know programming language (preferably C/C++ or Java).
- Solve the benchmark instances through the implemented algorithm.
- Deliver the project code, the results, and a report of the work (deadline 2)
- Present the solution method adopted and the results obtained (to be defined within Jan 9–19, 2018, during the last lessons of the course)
- Deadline 1 (problem formulation): 26/11/2017, 23:59.
- Deadline 2 (project code, results, and report): 08/01/2018, 23:59.
Using the provided software by professor, is possible to check the solution using this command:
ETPchecker.exe instance name -check solution file
everything is able and it must work on Windows.
The format of the solution must be like this:
INT1 INT2
where INT1 is the exam ID and INT2 is the ID of the assigned time-slot (IDs must correspond to those read in the instance files).
The solution MUST BE FEASIBLE!
- C - The development language
- Jacopo Maggio - JackMGit
- Stefano Munna - stemunna21
- Jacopo Nasi - Jacopx
- Andrea Santu - androsanta
- Marco Torlaschi - Torla
The property of this project belongs to the Polytechnic of Turin since this project isn't delivered yet. After that it will be published under not-already defined license.
- Vediamo di prendere tutti i punti...
- ... anche i due aggiuntivi.
- Pensaci due volte prima di pushare!