Is it feasible to create a conflict-free schedule for 500 students taking 5 courses each from a pool of 50 classes?

Courses
1

Hey folks! I’m working on this cool project to make class schedules that cut down on students’ walking time. Here’s the deal:

  • We’ve got 500 students
  • Each student takes 5 classes
  • There are 50 classes total (10 required, 40 electives)
  • Students pick 3 from the required list and 2 from the electives

I’m using a genetic algorithm to sort this out, but I’m stuck on one thing. How can I tell if it’s even possible to make a schedule where no student has overlapping classes?

For example, a student’s schedule might look like:

1. Math101 (timeslot 1)
2. Physics200 (timeslot 3)
3. Chemistry150 (timeslot 2)
4. Art105 (timeslot 4)
5. History110 (timeslot 5)

But I need to figure out if there’s a way to assign timeslots so nobody has two classes at once. Any ideas on how to check this? Thanks!

2

hey oliver, cool project! have u considered using a constraint satisfaction problem approach? might help check if its possible to assign timeslots without conflicts. also, whats ur max number of timeslots? that could impact feasibility. good luck with the walking time optimization too!

3

I’ve worked on similar scheduling problems before, and it’s definitely a challenging task. The feasibility largely depends on the number of available timeslots and any constraints on specific classes. With 50 classes and 500 students, you’d need at least 10 distinct timeslots to avoid conflicts, assuming even distribution.

One approach to check feasibility is to use graph coloring algorithms. Represent each class as a node and create edges between classes that share students. Then, try to color the graph with the minimum number of colors (timeslots). If it’s possible with your available timeslots, a conflict-free schedule exists.

Have you considered using integer linear programming? It can be effective for these types of problems, allowing you to model constraints and optimize for walking time simultaneously. Just be prepared for potentially long computation times with this many variables.

4

Hey Oliver63! That’s a really interesting project you’ve got going on there. :smiley:

I’m curious about a few things - have you considered how many timeslots you have available in total? And are there any constraints on when certain classes can be offered (like lab times for science courses)?

It seems like the feasibility might depend a lot on how flexible the timeslots can be. With 50 classes and 5 slots per student, you’d need at least 10 unique timeslots to avoid conflicts, right? But then you’d also need to make sure the popular required classes don’t all end up in the same slots.

Have you thought about running some simulations with different numbers of timeslots to see where the sweet spot might be? I’d be super interested to hear what you find out!

Also, just wondering - how are you handling the walking time optimization part? Are you factoring in distances between buildings or something like that? Sounds like a cool challenge!