Scheduling T teacher having max S students into S slots

Question

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.

score 2 · Accepted Answer · answered Jun 23 '23 at 00:34

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

score 0 · Answer 2 · answered Jun 19 '23 at 08:41

0

Hopcroft craft with priority to maximum degree vertices will solve this

answered Jun 19 '23 at 08:41

Abhinay Pandey

46
3
15

Scheduling T teacher having max S students into S slots

2 Answers2