TimeTablePlanningUniversity.py

from dataclasses import dataclass

import gurobipy as gp
from gurobipy import GRB

from collections import defaultdict

import matplotlib.pyplot as plt
import textwrap

@dataclass(frozen=True)
class module:
    name: str
    duration: int
    time: list[int]
    lp: int
    start: str # winter, summer, both

modules = [
    # integration
    module("RISE nicht techn. I", 1, [29, 30, 31, 32], 6, "both"),
    module("Management von gesundheitsrelevaten Organisationen", 1, [29, 30, 31, 32], 6, "winter"),
    module("Kognitive Algorithmen", 1, [33, 34], 6, "both"),

    # bwl
    module("Praxisseminar Medizintechnik", 1, [8, 9, 10, 51, 52, 53], 6, "summer"),
    module("Mig KV", 1, [5, 6, 33, 34], 6, "winter"),

    # vwl
    module("Gesundheitsökonomie", 1, [15, 16, 19, 20], 6, "summer"),

    # law
    module("Innovationsrecht", 1, [19, 20, 21, 22], 6, "winter"),

    # health
    module("Modelle zur Informationsverarbeitung im Gehirn", 1, [25, 26, 44, 43], 6, "both"),
    module("Medtech 1", 1, [3, 4, 5, 6], 6, "winter"),
    module("Med. Grundlagen f. Ing.", 2, [43, 44], 6, "both"),
    module("RISE 1 techn.", 1, [29, 30, 31, 32], 6, "both"),

    # free choice
    module("Wissenschaftliche Arbeiten mit Julia", 1, [17, 18], 6, "summer"),
    module("Machine Learning in Neuroscience", 1, [3, 4], 3, "both"),

    # thesis
    module("Masterarbeit", 1, [71], 24, "both")
]

S = 4 # number of semesters

START_SEMESTER = "summer"

SLOTS = range(1, 5*12 + 1) # 5 days, 12 hours each
SEMESTERS = range(1, S + 1)

def create_and_solve_model(modules, S):
    model = gp.Model("TimeTablePlanningUniversity")

    # variables
    x = model.addVars([(m.name, s) for m in modules for s in SEMESTERS], vtype=GRB.BINARY, name="x") # whether the module is taken in that semester

    y = model.addVars([(m.name, s) for m in modules for s in SEMESTERS], vtype=GRB.BINARY, name="y") # whether the module is started in that semester

    # constraints
    # each module must be started exactly once
    for m in modules:
        model.addConstr(sum(y[m.name, s] for s in SEMESTERS) == 1, name=f"StartOnce_{m.name}")

    # no interruption of modules, module must be taken in consecutive semesters
    for m in modules:
        for s in SEMESTERS:
            possible_starts = [s_p for s_p in range(max(1, s - m.duration + 1), s + 1)]
            model.addConstr(x[m.name, s] == gp.quicksum(y[m.name, s_p] for s_p in possible_starts), name=f"Duration_{m.name}_{s}")

    # start of modules in allowed semesters
    for m in modules:
        if m.start == "both":
            continue
        elif m.start == START_SEMESTER:
            allowed_starts = [s for s in SEMESTERS if s % 2 != 0]
        else:
            allowed_starts = [s for s in SEMESTERS if s % 2 == 0]

        model.addConstr(gp.quicksum(y[m.name, s] for s in allowed_starts) == 1, name=f"StartSemester_{m.name}")

    # no time slot conflicts: at most one module can be active in the same time slot in the same semester
    slots_to_modules = defaultdict(list)
    for m in modules:
        for p in m.time:
            slots_to_modules[p].append(m)
    for s in SEMESTERS:
        for p, active_in_slot in slots_to_modules.items():
            if active_in_slot:
                model.addConstr(gp.quicksum(x[m.name, s] for m in active_in_slot) <= 1, name=f"SlotConclict_{p}_{s}")
        
    #objective: minimize the squared deviation of the number of LP per semester from sum(modules.lp)/S (the average if each semester would have the same amount)
    total_lp = sum(m.lp for m in modules)
    mean_lp_per_semester = total_lp / S

    semester_load = {s: gp.quicksum((m.lp / m.duration) * x[m.name, s] for m in modules) for s in SEMESTERS}

    objective = gp.quicksum((semester_load[s] - mean_lp_per_semester) * (semester_load[s] - mean_lp_per_semester) for s in SEMESTERS)
    model.setObjective(objective, GRB.MINIMIZE)

    # fixed slots for modules that are already determined
    # sem1
    fixed_s1 = ["Modelle zur Informationsverarbeitung im Gehirn", "Wissenschaftliche Arbeiten mit Julia", "RISE nicht techn. I", "Praxisseminar Medizintechnik"]
    for m_name in fixed_s1:
        model.addConstr(x[m_name, 1] == 1, name=f"Fixed_{m_name}_1")
    model.addConstr(gp.quicksum(x[m.name, 1] for m in modules) == len(fixed_s1), name="FixedCount_1") #no more and no less than 4 modules in the first semester

    # sem2
    fixed_s2 = ["Medtech 1", "Kognitive Algorithmen", "Management von gesundheitsrelevaten Organisationen", "Med. Grundlagen f. Ing."]
    for m_name in fixed_s2:
        model.addConstr(x[m_name, 2] == 1, name=f"Fixed_{m_name}_2")
    model.addConstr(gp.quicksum(x[m.name, 2] for m in modules) == len(fixed_s2), name="FixedCount_2") #no more and no less than 4 modules in the second semester

    # thesis at the end
    model.addConstr(y["Masterarbeit", S] == 1, name="Masterarbeit_End")


    model.Params.OutputFlag = 0 # no text output
    model.Params.TimeLimit = 300 # limit on solution search time [s]
    model.optimize()

    return model, x, y, mean_lp_per_semester

def evaluate_solution(model, x, y, mean_lp_per_semester, modules, semesters):
    # output
    if model.Status in [GRB.OPTIMAL, GRB.TIME_LIMIT]:
        print(f"\n{'='*40}")
        print(f"{'SEMESTER PLAN OVERVIEW':^40}")
        print(f"{'='*40}")
        
        for s in SEMESTERS:
            current_lp = sum(
                (m.lp / m.duration) for m in modules if x[m.name, s].X > 0.5
            )
            
            print(f"\n[Semester {s}] - Total: {current_lp:>4.1f} LP")
            print("-" * 40)
            
            for m in modules:
                if x[m.name, s].X > 0.5:
                    status = "Start" if y[m.name, s].X > 0.5 else "Cont."
                    print(f"  > {m.name:<30} ({status})")
        
        print(f"\n{'='*40}")
        print(f"Target Mean: {mean_lp_per_semester:.2f} LP/Semester")
        print(f"Objective Value (Variance): {model.ObjVal:.4f}")
        print(f"{'='*40}")

    else:
        print("Optimization was unsuccessful. Status Code:", model.Status)

# visualization
def plot_weekly_schedule(semester, modules, x_vars):
    days_labels = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday"]
    
    plt.figure(figsize=(14, 8))
    colors = plt.cm.tab20.colors
    
    slot_usage_count = {}

    for i, m in enumerate(modules):
        if x_vars[m.name, semester].X > 0.5:
            for p in m.time:
                day = (p - 1) // 12 + 1
                hour = (p - 1) % 12 + 1
                
                pos_key = (day, hour)
                slot_usage_count[pos_key] = slot_usage_count.get(pos_key, 0) + 1
                offset = (slot_usage_count[pos_key] - 1) * 0.4
                
                # Draw point
                plt.scatter(day, hour, s=400, color=colors[i % len(colors)], 
                            edgecolors='black', zorder=3, alpha=0.8)
                
                wrapped_name = "\n".join(textwrap.wrap(m.name, width=25))
                
                plt.text(day, hour + 0.2 + offset, wrapped_name, 
                         ha='center', va='top', fontsize=8, 
                         bbox=dict(facecolor='white', alpha=0.7, edgecolor='none', pad=0.5))

    plt.title(f"Weekly Schedule - Semester {semester} ", pad=20, fontsize=14)
    plt.xticks(range(1, 6), days_labels)
    plt.yticks(range(1, 13), [f"{h}:00" for h in range(8, 20)])
    
    plt.ylim(13.5, 0.5)
    plt.xlim(0.5, 5.5)
    plt.grid(True, linestyle=':', alpha=0.4)
    plt.subplots_adjust(right=0.75)

    plt.show()

def main():
    model, x, y, mean_lp_per_semester = create_and_solve_model(modules, S)
    evaluate_solution(model, x, y, mean_lp_per_semester, modules, SEMESTERS)

    if model.Status in [GRB.OPTIMAL, GRB.TIME_LIMIT]:
        plot_weekly_schedule(1, modules, x)

if __name__ == "__main__":
    main()