Scheduling T teacher having max S students into S slots

There are T teachers who can each have a maximum of S students. Each student can have a maximum of S teachers. There are S time slots for the student and teacher to meet.

In each slot a teacher will teach one of its student and then teacher gets another student while the student goes to another teacher.

For S = 3

Input:

Teacher 1 - Student 1, Student 2

Teacher 2 - Student 2, Student 3

Teacher 3 - Student 1, Student 3

Teacher 4 - Student 1, Student 3, Student 2

Solution:

Tried this, but it's for a single Teacher and its mentee and can be used to check if it's possible to assign the students to the current teacher or not, but otherwise it doesnt provide the optimal way of scheduling so that there is no conflict in the future.

This problem can also be solved efficiently with Integer Linear Programming. An out-of-the-box python interface to the open-source solver CBC can be found in the python package PuLP. PuLP also ships with a solver binary so no additional installation steps are required.

We define our decision variables and add the relevant constraints to the optimization model:

from pulp import *
def parse_constraints(constraints_string):
constraints = {}
lines = constraints_string.split("\n")
for line in lines:
line = line.strip()
if line:
teacher, students = line.split("-")
teacher = int(teacher.strip().split()[1])
students = [int(s.strip().split()[1]) for s in students.split(",")]
constraints[teacher] = students
return constraints
def get_teacher_student_pairings(constraints):
pairings = []
for teacher, students in constraints.items():
for student in students:
pairings.append((teacher, student))
return pairings
def optimize_schedule(teachers, students, time_slots,pairings):
prob = LpProblem("Teacher-Student Schedule Optimization", LpMinimize)
# Decision variables
x = LpVariable.dicts("x", [(t, s, ts) for t in teachers for s in students for ts in time_slots], cat="Binary")
# Eeach student is paired with each of their assigned teacher exactly once
for t,s in pairings:
prob += lpSum([x[t, s, ts] for ts in time_slots]) == 1
# Each teacher can only teach 1 student at a time
for t in teachers:
for ts in time_slots:
prob += lpSum([x[t, s, ts] for s in students]) <= 1
# Each student can only be taught by  1 teacher at a time
for s in students:
for ts in time_slots:
prob += lpSum([x[t, s, ts] for t in teachers]) <= 1
prob.solve()
# Extract solution
schedule = []
for ts in time_slots:
line=f'Slot {ts} - '
for t in teachers:
for s in students:
if value(x[t, s, ts]) == 1:
line+=f'T{t}-S{s} '
break
else:
line+=f'      '
schedule.append(line)
return schedule

This produces the desired schedule:

teachers = [1, 2, 3, 4]
students = [1, 2, 3]
time_slots = [1, 2, 3]
constraints_string = """
Teacher 1 - Student 1, Student 2
Teacher 2 - Student 2, Student 3
Teacher 3 - Student 1, Student 3
Teacher 4 - Student 1, Student 3, Student 2
"""
assignments = parse_constraints(constraints_string)
pairings = get_teacher_student_pairings(assignments)
schedule = optimize_schedule(teachers, students, time_slots,pairings)
for time_slot in schedule:
print(time_slot)

Output:

Result - Optimal solution found
Objective value:                0.00000000
Enumerated nodes:               0
Total iterations:               0
Time (CPU seconds):             0.00
Time (Wallclock seconds):       0.02
Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.01   (Wallclock seconds):       0.03
Slot 1 -       T2-S2 T3-S1 T4-S3 
Slot 2 - T1-S1       T3-S3 T4-S2 
Slot 3 - T1-S2 T2-S3       T4-S1 

Hopcroft craft with priority to maximum degree vertices will solve this