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


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


enter image description here

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
        # 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} '
                    line+=f'      '
        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:


    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