pythonschedulinglinear-programmingbipartiteford-fulkerson# 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.

Solution

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
```

- Check if dictionary key, value pairs meet user-defined search conditions
- Loading of GDAL library impossible after an upgrade
- Pandas read_csv dtype read all columns but few as string
- ```TypeError: memoryview: a bytes-like object is required, not 'bool'``` when trying to add data to my database
- How to Make Python Module yt-dlp ignore Private Videos When Downloading A Playlist
- How to scroll down google maps using selenium python
- Numpy array to dictionary with indices as values
- Connect to a browser with Pyppeteer
- How to pass a video uploaded via FastAPI to OpenCV VideoCapture?
- Codility OddOccurrencesInArray Problem - Recursion and Python
- How to fix the error "QObject::moveToThread:" in opencv in python?
- Python typing: Does TypedDict allow additional / extra keys?
- Python 'requests' library - define specific DNS?
- read_sql in chunks with polars
- f.readlines() won't return any values
- Specify which python version pylint should evaluate for
- Modelling a robotic arm motion in 3D, ideas?
- How to copy values from two dataframes with datetime index, to fill one data frame?
- How to print list with numbers into nth columns or any tabulated format
- Pandas.eval replacement in polars
- How to extract dominant frequency from NumPy array?
- Python function to return a new list containing the strings that are palindromes and have an even length
- How to return optional parameters in function
- How do I build a permutation invariance neural network in keras?
- Why does keras model predict slower after compile?
- Creating class instance properties from a dictionary?
- Getting joint location(3D pose) w.r.t world of Kuka Iiwa arm in Drake
- How to always provide a context for Flask app tested with PyTest?
- Which is generally faster, a yield or an append?
- Python Enum with multiple attributes