TimeTabling
Camilo Andrés Rodríguez Garzón
The construction of the programming of university schedules is a complex process that considers different types of restrictions and objectives that varies from one institution to another.
The problem solved is a real case presented at EAFIT University, which has a series of restrictions that are necessary and / or desirable for the solution of it. In this article used a metaheuristic that produces good quality solutions for combinatorial optimization problems.
Metaheuristics has been tested for the problems proposed in the literature. The evidences shows that metaheuristic developed is an effective tool that provide solutions that meet restrictions, schedules and resources.
Requirements
Libraries
Quick Start
To run Timetabling, you must have provided the events, rooms, slots and teachers. For this, you should make the files in the path with the follow information:
In addition, you have a file for the configuration of someone important data that you can use in order to make a more specific enviroment to build the solution. In the path you can modify the parameters that algorithm provide.
You should define the files follow:
- Incompatible slots: You should provide the incompatible slots if exist these for the correct functioning.
- Teacher availability time: This file provide a specification about different types of contract that the University have for the teachers. Including information that is used for make the assign of teachers.
Run project
gradle build run
Example
Below is a set of tables that represent the information needed to build a solution to the Timetabling problem. This information is defined in .csv files.
- Events includes the set of subjects that must be assigned for the current semester. This table has relevant information for programming schedules such as
intensity,frequencyandcompatibility with the rooms.
| Id | Code | Group | Max Student | Type Room | Semester | Career | Intensity | Frequency |
|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 10 | L | 1 | 1 | 1 | 1 |
| 2 | 2 | 1 | 10 | L | 1 | 1 | 10 | 5 |
| 3 | 12 | 1 | 20 | AN | 1 | 1 | 4 | 2 |
| 4 | 13 | 1 | 20 | AN | 1 | 1 | 4 | 2 |
- Room is a table that contains the list of rooms available to the university and the number of maximum students that can be assigned in the classroom.
Fixed room : It is a requirement that the algorithm require in order to run correctly the LNS. The field is equal to 1 if the exact solution must contain the same room result that heuristic solution.
| Id | Code | Type Room | Capacity | Cost |
|---|---|---|---|---|
| 1 | 1 | L | 30 | 3 |
| 2 | 2 | L | 35 | 5 |
| 3 | 3 | L | 20 | 8 |
- Teacher is a table that defines the availability in hours that a teacher can dictate class as well as the type of courses that a teacher can teach.
| Id | Event name | Type contract | Max number events |
|---|---|---|---|
| 1 | 1 | fulltime | 2 |
| 2 | 1 | fulltime | 3 |
| 3 | 2 | fulltime | 2 |
- Slot is a table that contains the possible time intervals defined in an academic week which the allocation of events to classrooms can be made.
Fixed slot: It is a requirement to run correctly the LNS. The field is equal to 1 if the exact solution must contain the same slot result that heuristic solution.
| Code | Day | Start Time | End Time | Fix Room |
|---|---|---|---|---|
| 1 | M | 6 | 8 | 1 |
| 2 | T | 7 | 9 | 0 |
| 3 | W | 9 | 10 | 1 |
- By providing the input data necessary for the correct functioning of the algorithm, the resulting data will provide the following information:
| Room | Type room | Capacity | Event | Group | #Student | Day | Start | End | Teacher | Contract |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | L | 30 | 5 | 1 | 20 | M | 6.0 | 7.0 | ai | fullTime |
| 1 | L | 30 | 8 | 1 | 20 | M | 8.0 | 9.0 | ai | fullTime |
| 2 | L | 35 | 2 | 1 | 30 | W | 8.0 | 10.0 | 2 | fullTime |
| 2 | L | 35 | 10 | 1 | 20 | TH | 8.0 | 9.0 | ai | fullTime |
| 2 | L | 35 | 10 | 1 | 20 | F | 8.0 | 9.0 | ai | fullTime |
| 3 | L | 35 | 11 | 1 | 20 | F | 8.0 | 9.0 | ai | fullTime |
Analysis of results
- The value obtained from the cost function used in the mathematical formulation is plotted for each of the iterations performed by GRASP.
- It is a evaluation wich focus on the variable of desition λ and ψ wich provide if exist a penalization by cause of soft constraint
