Genetic Timetabler (Internship)

Context

For my 4th year intership i had to go in an internship abroad because i didn’t went abroad in 3rd year. Otherwise i don’t think i would have choosen this subject. And hell i was wrong !

It was a really interesting subject which was conducted in 2017 by a guy who now was an employee of the company. It was fun to ask him question on code he wrote 5 years ago.

I was with 5 guys from my school (but parisian) and a 2 year Dutch guy. But i mostly worked alone, it was too hard for me at this time too keep the 5 lazy parisians focus on the project and the Dutch need a real mentor because i didn’t had any programming experience.

Most of the time i will say “my work” because a block of chatgpt code that i have to correct doesn’t count.

The goal

You have different element : Student, Teacher, Lesson, Rooms(With Facilities) and Groups (in reality there was more because the previous intern wanted to cover a large amount of possibility but it was overkill)

Student, Teacher and Rooms may have TimeSlots preferences.

The goal is to build a timetable maximizing the global Satisfation.

Also it need to run in less than a week for the whole Timetable and less than an our to patch modification.

Research

To be sure to not test dumb stuff i first check how other people was solving the same kind of problem, and as far as i was able to see most of them use genetic algorithm. So i decided to go for it and the previously intern agree with me.

Building database

I wanted to be able to perform test on a various range of possibilities so i made a script in python to generate an SQL database following the already existing Hibernate.

After making this i found out that their was somwhere a problème with key identifier and it was impossible to patch without changing the whole structure of the db. I decided to go for a JSON for test it was enough, we don’t have anymore key problems and we can keep the structure of the DB.

My DB generator script was able to take different quantities of groups (the TUI for selection was made by one of my teammate !)

Genetic Algorithm

Then i just add to implement a genetic algorithm in Java, a language that i may add practice a total of 10hours before, easy 😎, by the power of chatGPT and the motivation of being stuck in a room with guys playing League of Legend and Rocket League, I made it !

It was working but a little slow, so i performe a little optimisation and implement multithreading (so easy in Java).

I builded a gigantic database representing the number of student of the biggest indian university and … i didn’t wait for the result, it was too long.

So more reasonnable with number that may match the current university we were working in (don’t really remembers but more than 20k students) and it found a good solution in less than an hour. so we matched our needed and it just need to be used in the real project.

At the end we have this kind of timetable :

The html preview has been made by the previous intern.

So it kinda match the preference of the person event if he choose a discouraged (it’s a group of 60 person, hard to satisfy everyone)

Comments

I’m not angry against the guy i was “working” with, to be honest it was a good opportunity and being fully independent is not that bad.

If a had to continue working on it i would also had another algorithm for group repartition optimisation (i’m not sure if the test i made were working or not). Also i’d like to minimize the fact that the algorithm put more lesson at the start of the week, maybe with a first random gluttony solution.

Also my first intuition to solve this problem fast enough was to make the solver in C to be faster and i’m curious to see the effectiveness of a lower level implementation. But for the PoC Java is better, we can code faster complex mechanism.

Furthermore, work around lazy people totally remove the stress of the job and it allow me to fully enjoy my experience abroad and still working on the project how i want when i want.

It was also possible because our boss give us nearly complete freedom on our working hours, we just needed to be here before 10am and leave when we finished todays tasks.