Hey everyone! I’m working on a school project and I’m stuck. I need to make a timetable for 500 students. Each student has to take 5 classes out of 50 courses. 3 of these are must-take from a group of 10, and 2 are chosen from 40 other options.
I want to use a genetic algorithm to make a timetable that keeps students from walking too far between classes. But I’m not sure how to check if it’s even possible to make a timetable without any time clashes.
For example, if Student A has Math and Physics at the same time, that’s a clash. How can I figure out if there’s a way to arrange all the classes so no student has overlapping courses?
I’ve tried listing out the courses for each student, like this:
Student1 = [Math101, Chem101, Phys101, Art101, History101]
Student2 = [Bio101, Econ101, Psych101, Music101, Geo101]
But I’m lost on how to check if a clash-free timetable is possible. Any ideas on how to approach this? Thanks in advance for any help!
Hey there CreativeChef15! 
Wow, that’s quite a puzzle you’re working on! I’m super curious about how you’re approaching this. Have you considered using graph coloring algorithms? They can be pretty handy for scheduling problems like this.
I’m wondering, how many time slots are you working with in a day? And are there any restrictions on when certain courses can be offered? Like, do some need to be in the morning or afternoon only?
It’s cool that you’re using a genetic algorithm for optimizing walking distances. How are you planning to represent the ‘genes’ in your algorithm?
Oh, and have you thought about using any existing scheduling libraries or tools? Sometimes they can give you a good starting point or at least some ideas.
This project sounds really interesting! I’d love to hear more about how it goes. Keep us updated, okay?
Having worked on similar scheduling problems, I can attest to their complexity. One approach I’ve found effective is using integer linear programming (ILP) to model the constraints and objectives. You could define binary variables for each student-course-timeslot combination and set constraints to ensure no conflicts.
For feasibility checking, you might consider a simplified version of your problem first. Try scheduling just the mandatory courses and see if a conflict-free arrangement is possible. If that works, gradually add the electives.
Another technique that’s proved useful in my experience is to use a SAT solver. These are remarkably efficient at finding solutions to large constraint satisfaction problems, which is essentially what you’re dealing with here.
Remember, even if a perfect solution isn’t possible, you may be able to find a near-optimal one that minimizes conflicts. Good luck with your project!
hey creativechef, thats a tough one! have u tried using a constraint satisfaction algorithm? it might help check if its possible to schedule without conflicts. you could set up constraints like no overlapping classes for each student and see if theres a solution. good luck with ur project!