App-5 : Emploi du temps universitaire (University Timetabling)

# Parameters
BATCH_MODE = "true"

Navigation : << App-4 JobShopScheduling | Index | App-6 Minesweeper >>

Objectifs d’apprentissage

A la fin de ce notebook, vous saurez : 1. Modeliser un problème d’emploi du temps universitaire comme un CSP 2. Distinguer contraintes dures et contraintes souples 3. Comparer une approche heuristique gloutonne avec un solveur CP-SAT 4. Decouvrir la modelisation declarative MiniZinc 5. Visualiser et analyser la qualite d’un emploi du temps

Prerequis

• Python 3.10+, numpy, matplotlib, ortools
• CSP-3 : Advanced

Duree estimee : 50 minutes

---

1. Introduction (~5 min)

La planification d’emplois du temps (university timetabling) est un problème classique d’optimisation sous contraintes. Chaque universite doit, a chaque semestre, affecter des cours a des creneaux horaires et des salles, en respectant de nombreuses règles.

Pourquoi ce problème est-il difficile ?

Le university timetabling est NP-difficile. Même avec seulement 8 cours, 3 salles et 20 creneaux, le nombre d’affectations possibles (sans contraintes) est :

\[\text{Espace brut} = (\text{nb salles} \times \text{nb creneaux})^{\text{nb cours}} = (3 \times 20)^8 = 60^8 \approx 1.7 \times 10^{14}\]

Les contraintes vont eliminer l’immense majorite de ces combinaisons, mais l’espace reste gigantesque.

Contraintes dures vs contraintes souples

Type	Description	Exemples	Violation
Contrainte dure	Doit etre satisfaite (sinon pas de solution)	Pas de chevauchement de salle, capacite suffisante	Solution invalide
Contrainte souple	Souhaitable mais non obligatoire	Minimiser les trous, préférences enseignants	Solution de moindre qualite

En pratique, on cherche une solution qui satisfait toutes les contraintes dures et minimise les violations de contraintes souples.

Éléments du problème

Élément	Rôle	Exemple
Cours	Activites a planifier	Algorithmique, Probabilites…
Salles	Lieux d’enseignement (capacite, equipements)	Amphi A (120 places, video-projecteur)
Creneaux	Plages horaires (jour + heure)	Lundi 8h-10h, Mardi 14h-16h
Enseignants	Personnes affectees aux cours	Prof. Dupont (Algo + Systèmes)

# Imports pour tout le notebook
import sys
import os
import time
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
from collections import defaultdict
from itertools import combinations

# OR-Tools CP-SAT
from ortools.sat.python import cp_model

# Helpers partages de la serie Search
sys.path.insert(0, os.path.abspath('../..'))
from search_helpers import benchmark_table

print("Imports OK")
print(f"OR-Tools version: {cp_model.__name__} charge")

Imports OK
OR-Tools version: ortools.sat.python.cp_model charge

---

2. Données du problème (~5 min)

Definissons une instance realiste mais de taille maitrisable : 8 cours, 3 salles, 20 creneaux (5 jours x 4 creneaux par jour) et 4 enseignants.

Structure des données

Chaque cours est decrit par : - son nom et son identifiant - le nombre d’etudiants inscrits - l’enseignant responsable - les equipements requis (ex : ordinateurs, labo)

Chaque salle est decrite par : - sa capacite maximale - les equipements disponibles

# === Donnees du probleme ===

# Jours et creneaux horaires
DAYS = ["Lundi", "Mardi", "Mercredi", "Jeudi", "Vendredi"]
SLOTS_PER_DAY = 4  # 8h-10h, 10h-12h, 14h-16h, 16h-18h
SLOT_LABELS = ["8h-10h", "10h-12h", "14h-16h", "16h-18h"]
NUM_SLOTS = len(DAYS) * SLOTS_PER_DAY  # 20 creneaux au total

# Enseignants
TEACHERS = {
    "Dupont":  {"id": 0, "name": "Prof. Dupont"},
    "Martin":  {"id": 1, "name": "Prof. Martin"},
    "Bernard": {"id": 2, "name": "Prof. Bernard"},
    "Leroy":   {"id": 3, "name": "Prof. Leroy"},
}

# Cours : nom, nb etudiants, enseignant, equipement requis
COURSES = {
    "Algo":     {"id": 0, "students": 90,  "teacher": "Dupont",  "equipment": "standard"},
    "Probas":   {"id": 1, "students": 75,  "teacher": "Martin",  "equipment": "standard"},
    "Systemes": {"id": 2, "students": 60,  "teacher": "Dupont",  "equipment": "standard"},
    "Reseaux":  {"id": 3, "students": 50,  "teacher": "Bernard", "equipment": "labo"},
    "BDD":      {"id": 4, "students": 80,  "teacher": "Leroy",   "equipment": "standard"},
    "IA":       {"id": 5, "students": 100, "teacher": "Martin",  "equipment": "standard"},
    "Securite": {"id": 6, "students": 40,  "teacher": "Bernard", "equipment": "labo"},
    "Web":      {"id": 7, "students": 55,  "teacher": "Leroy",   "equipment": "labo"},
}

# Salles : capacite et equipement
ROOMS = {
    "Amphi_A":  {"id": 0, "capacity": 120, "equipment": "standard"},
    "Salle_B":  {"id": 1, "capacity": 60,  "equipment": "standard"},
    "Labo_C":   {"id": 2, "capacity": 40,  "equipment": "labo"},
    "Labo_D":   {"id": 3, "capacity": 60,  "equipment": "labo"},  # nouvelle
}

# Listes pour acces par indice
course_names = list(COURSES.keys())
room_names = list(ROOMS.keys())
teacher_names = list(TEACHERS.keys())

num_courses = len(COURSES)
num_rooms = len(ROOMS)
num_teachers = len(TEACHERS)

# Affichage recapitulatif
print("Donnees du probleme d'emploi du temps")
print("=" * 55)
print(f"Cours       : {num_courses}")
print(f"Salles      : {num_rooms}")
print(f"Creneaux    : {NUM_SLOTS} ({len(DAYS)} jours x {SLOTS_PER_DAY} creneaux)")
print(f"Enseignants : {num_teachers}")
print(f"Espace brut : ({num_rooms} x {NUM_SLOTS})^{num_courses} = {(num_rooms * NUM_SLOTS)**num_courses:.2e}")
print()

print("Cours :")
print(f"  {'Nom':<12} {'Etudiants':>10} {'Enseignant':<12} {'Equipement':<12}")
print(f"  {'-'*46}")
for name, info in COURSES.items():
    print(f"  {name:<12} {info['students']:>10} {info['teacher']:<12} {info['equipment']:<12}")

print()
print("Salles :")
print(f"  {'Nom':<12} {'Capacite':>10} {'Equipement':<12}")
print(f"  {'-'*34}")
for name, info in ROOMS.items():
    print(f"  {name:<12} {info['capacity']:>10} {info['equipment']:<12}")

Donnees du probleme d'emploi du temps
=======================================================
Cours       : 8
Salles      : 4
Creneaux    : 20 (5 jours x 4 creneaux)
Enseignants : 4
Espace brut : (4 x 20)^8 = 1.68e+15

Cours :
  Nom           Etudiants Enseignant   Equipement  
  ----------------------------------------------
  Algo                 90 Dupont       standard    
  Probas               75 Martin       standard    
  Systemes             60 Dupont       standard    
  Reseaux              50 Bernard      labo        
  BDD                  80 Leroy        standard    
  IA                  100 Martin       standard    
  Securite             40 Bernard      labo        
  Web                  55 Leroy        labo        

Salles :
  Nom            Capacite Equipement  
  ----------------------------------
  Amphi_A             120 standard    
  Salle_B              60 standard    
  Labo_C               40 labo        
  Labo_D               60 labo        

Interpretation : données du problème

Points cles a observer :

Aspect	Observation	Consequence
Capacite Amphi_A (120)	Seule salle pour Algo (90) et IA (100)	Conflit pour l’amphi
Equipement “labo”	Reseaux, Securite, Web le necessitent	Labo_C ou Labo_D
Dupont enseigne 2 cours	Algo + Systèmes	Pas au même creneau
Martin enseigne 2 cours	Probas + IA	Idem

Ces observations font emerger les premières contraintes : 1. Les cours a gros effectif (Algo, IA) doivent aller dans Amphi_A 2. Les cours “labo” (Reseaux, Securite, Web) doivent aller dans Labo_C ou Labo_D (Reseaux et Web uniquement dans Labo_D) 3. Dupont et Martin ont chacun 2 cours : pas de chevauchement possible

Fonctions utilitaires

Avant de passer aux algorithmes, definissons les fonctions de conversion et de visualisation qui seront reutilisees tout au long du notebook.

# === Fonctions utilitaires ===

def slot_to_day_hour(slot_index):
    """Convertit un indice de creneau (0-19) en (jour, heure)."""
    day = slot_index // SLOTS_PER_DAY
    hour = slot_index % SLOTS_PER_DAY
    return day, hour

def slot_label(slot_index):
    """Retourne un libelle lisible pour un creneau."""
    day, hour = slot_to_day_hour(slot_index)
    return f"{DAYS[day]} {SLOT_LABELS[hour]}"

def get_compatible_rooms(course_name):
    """Retourne la liste des salles compatibles avec un cours (capacite + equipement)."""
    course = COURSES[course_name]
    compatible = []
    for rname, rinfo in ROOMS.items():
        # Capacite suffisante ?
        if rinfo["capacity"] < course["students"]:
            continue
        # Equipement compatible ? (labo requiert labo, standard accepte tout)
        if course["equipment"] == "labo" and rinfo["equipment"] != "labo":
            continue
        compatible.append(rname)
    return compatible

def get_teacher_courses(teacher_name):
    """Retourne la liste des cours d'un enseignant."""
    return [c for c, info in COURSES.items() if info["teacher"] == teacher_name]

# Verification des compatibilites
print("Compatibilite cours -> salles :")
print(f"  {'Cours':<12} {'Salles compatibles'}")
print(f"  {'-'*40}")
for cname in course_names:
    rooms = get_compatible_rooms(cname)
    marker = " [!]" if len(rooms) == 1 else ""
    print(f"  {cname:<12} {rooms}{marker}")

print()
print("Affectation enseignant -> cours :")
for tname in teacher_names:
    courses = get_teacher_courses(tname)
    print(f"  {tname:<10} : {courses}")

Compatibilite cours -> salles :
  Cours        Salles compatibles
  ----------------------------------------
  Algo         ['Amphi_A'] [!]
  Probas       ['Amphi_A'] [!]
  Systemes     ['Amphi_A', 'Salle_B', 'Labo_D']
  Reseaux      ['Labo_D'] [!]
  BDD          ['Amphi_A'] [!]
  IA           ['Amphi_A'] [!]
  Securite     ['Labo_C', 'Labo_D']
  Web          ['Labo_D'] [!]

Affectation enseignant -> cours :
  Dupont     : ['Algo', 'Systemes']
  Martin     : ['Probas', 'IA']
  Bernard    : ['Reseaux', 'Securite']
  Leroy      : ['BDD', 'Web']

Definissons également les fonctions de visualisation et d’evaluation de la qualite d’un emploi du temps. Ces fonctions seront reutilisees pour comparer les différentes approches.

# === Fonctions de visualisation ===

# Palette de couleurs pour les cours
COURSE_COLORS = {
    "Algo":     "#4E79A7",
    "Probas":   "#F28E2B",
    "Systemes": "#E15759",
    "Reseaux":  "#76B7B2",
    "BDD":      "#59A14F",
    "IA":       "#EDC948",
    "Securite": "#B07AA1",
    "Web":      "#FF9DA7",
}


def visualize_timetable(schedule, title="Emploi du temps", figsize=(16, 8)):
    """Visualise l'emploi du temps sous forme de grille.

    schedule: dict {course_name: (room_name, slot_index)}
    """
    fig, axes = plt.subplots(1, num_rooms, figsize=figsize, sharey=True)
    if num_rooms == 1:
        axes = [axes]

    for r_idx, rname in enumerate(room_names):
        ax = axes[r_idx]
        ax.set_title(f"{rname}\n(cap. {ROOMS[rname]['capacity']}, {ROOMS[rname]['equipment']})",
                     fontsize=11, fontweight='bold')

        # Grille de fond
        for d in range(len(DAYS)):
            for h in range(SLOTS_PER_DAY):
                color = "#F5F5F5" if d % 2 == 0 else "#EBEBEB"
                rect = plt.Rectangle((d, SLOTS_PER_DAY - 1 - h), 1, 1,
                                     facecolor=color, edgecolor="#CCCCCC",
                                     linewidth=0.5)
                ax.add_patch(rect)

        # Placer les cours
        for cname, (assigned_room, slot) in schedule.items():
            if assigned_room != rname:
                continue
            day, hour = slot_to_day_hour(slot)
            color = COURSE_COLORS.get(cname, "#999999")
            rect = plt.Rectangle((day + 0.05, SLOTS_PER_DAY - 1 - hour + 0.05),
                                 0.9, 0.9,
                                 facecolor=color, edgecolor="black",
                                 linewidth=1.5, alpha=0.85)
            ax.add_patch(rect)
            teacher = COURSES[cname]["teacher"]
            ax.text(day + 0.5, SLOTS_PER_DAY - 1 - hour + 0.55,
                    cname, ha='center', va='center',
                    fontsize=9, fontweight='bold', color='white')
            ax.text(day + 0.5, SLOTS_PER_DAY - 1 - hour + 0.25,
                    teacher, ha='center', va='center',
                    fontsize=7, color='white', style='italic')

        ax.set_xlim(0, len(DAYS))
        ax.set_ylim(0, SLOTS_PER_DAY)
        ax.set_xticks([d + 0.5 for d in range(len(DAYS))])
        ax.set_xticklabels([d[:3] for d in DAYS], fontsize=9)
        if r_idx == 0:
            ax.set_yticks([h + 0.5 for h in range(SLOTS_PER_DAY)])
            ax.set_yticklabels(list(reversed(SLOT_LABELS)), fontsize=9)
        ax.set_aspect('equal')

    fig.suptitle(title, fontsize=14, fontweight='bold', y=1.02)
    plt.tight_layout()
    return fig


def evaluate_schedule(schedule):
    """Evalue la qualite d'un emploi du temps (contraintes souples).

    Retourne un dict de metriques.
    """
    metrics = {}

    # 1. Nombre de trous par enseignant par jour
    total_gaps = 0
    for tname in teacher_names:
        teacher_courses = get_teacher_courses(tname)
        for day in range(len(DAYS)):
            hours_today = []
            for cname in teacher_courses:
                if cname in schedule:
                    _, slot = schedule[cname]
                    d, h = slot_to_day_hour(slot)
                    if d == day:
                        hours_today.append(h)
            if len(hours_today) >= 2:
                hours_today.sort()
                for i in range(len(hours_today) - 1):
                    gap = hours_today[i + 1] - hours_today[i] - 1
                    total_gaps += max(0, gap)
    metrics["gaps_total"] = total_gaps

    # 2. Preference pour les creneaux du matin (slots 0 et 1 de chaque jour)
    morning_count = 0
    for cname, (_, slot) in schedule.items():
        _, hour = slot_to_day_hour(slot)
        if hour < 2:  # 8h-10h ou 10h-12h
            morning_count += 1
    metrics["morning_pct"] = morning_count / max(len(schedule), 1) * 100

    # 3. Equilibre des jours (ecart-type du nombre de cours par jour)
    courses_per_day = [0] * len(DAYS)
    for cname, (_, slot) in schedule.items():
        day, _ = slot_to_day_hour(slot)
        courses_per_day[day] += 1
    metrics["day_balance_std"] = float(np.std(courses_per_day))
    metrics["courses_per_day"] = courses_per_day

    # 4. Taux d'utilisation des salles
    room_usage = {rname: 0 for rname in room_names}
    for cname, (rname, _) in schedule.items():
        room_usage[rname] += 1
    metrics["room_usage"] = room_usage
    metrics["room_utilization_pct"] = {
        rname: count / NUM_SLOTS * 100 for rname, count in room_usage.items()
    }

    return metrics


def print_metrics(metrics, label=""):
    """Affiche les metriques de qualite."""
    print(f"\nMetriques de qualite {label}")
    print("=" * 45)
    print(f"Trous enseignants (total) : {metrics['gaps_total']}")
    print(f"Cours le matin            : {metrics['morning_pct']:.0f}%")
    print(f"Equilibre des jours (std) : {metrics['day_balance_std']:.2f}")
    print(f"Cours par jour            : {metrics['courses_per_day']}")
    print(f"Utilisation salles :")
    for rname, pct in metrics['room_utilization_pct'].items():
        print(f"  {rname:<12} : {metrics['room_usage'][rname]} cours ({pct:.0f}%)")


print("Fonctions de visualisation et d'evaluation definies.")

Fonctions de visualisation et d'evaluation definies.

---

3. Approche 1 : heuristique gloutonne (~8 min)

Avant d’utiliser un solveur specialise, testons une approche simple et naturelle : l’heuristique gloutonne.

Principe

1. Trier les cours par degré de contrainte decroissant (les plus contraints d’abord)
2. Pour chaque cours, parcourir les creneaux et salles dans l’ordre :
   • Verifier que la salle est compatible (capacite, equipement)
   • Verifier qu’il n’y a pas de conflit de salle (même creneau)
   • Verifier qu’il n’y a pas de conflit d’enseignant (même creneau)
3. Affecter au premier creneau+salle valide trouve

L’idee du tri par contrainte (“fail-first”) est la même que l’heuristique MRV vue dans les fondations CSP.

Limites attendues

• Le glouton ne revient jamais en arriere (pas de backtracking)
• Il peut echouer a trouver une solution même s’il en existe une
• Il ne minimise pas les contraintes souples (pas d’optimisation)

def greedy_timetable():
    """Affecte les cours par heuristique gloutonne.

    Trie les cours par nombre de salles compatibles (croissant),
    puis affecte au premier creneau+salle disponible.

    Retourne (schedule, success) ou schedule est un dict {cours: (salle, creneau)}.
    """
    # Trier par contrainte decroissante : peu de salles compatibles d'abord
    sorted_courses = sorted(
        course_names,
        key=lambda c: len(get_compatible_rooms(c))
    )

    schedule = {}  # cours -> (salle, creneau)
    room_slot_used = set()  # ensemble de (salle, creneau) deja occupes
    teacher_slot_used = set()  # ensemble de (enseignant, creneau) deja occupes

    for cname in sorted_courses:
        placed = False
        compatible_rooms = get_compatible_rooms(cname)
        teacher = COURSES[cname]["teacher"]

        for slot in range(NUM_SLOTS):
            for rname in compatible_rooms:
                # Verifier absence de conflit
                if (rname, slot) in room_slot_used:
                    continue
                if (teacher, slot) in teacher_slot_used:
                    continue

                # Affecter
                schedule[cname] = (rname, slot)
                room_slot_used.add((rname, slot))
                teacher_slot_used.add((teacher, slot))
                placed = True
                break
            if placed:
                break

        if not placed:
            print(f"  [ECHEC] Impossible de placer : {cname}")

    success = len(schedule) == num_courses
    return schedule, success


# Execution
start = time.time()
greedy_schedule, greedy_success = greedy_timetable()
greedy_time = (time.time() - start) * 1000

print("Heuristique gloutonne")
print("=" * 50)
print(f"Succes            : {'Oui' if greedy_success else 'Non'}")
print(f"Cours places      : {len(greedy_schedule)} / {num_courses}")
print(f"Temps             : {greedy_time:.2f} ms")
print()

if greedy_success:
    print("Affectations :")
    print(f"  {'Cours':<12} {'Salle':<12} {'Creneau'}")
    print(f"  {'-'*45}")
    for cname in course_names:
        if cname in greedy_schedule:
            rname, slot = greedy_schedule[cname]
            print(f"  {cname:<12} {rname:<12} {slot_label(slot)}")

Heuristique gloutonne
==================================================
Succes            : Oui
Cours places      : 8 / 8
Temps             : 0.07 ms

Affectations :
  Cours        Salle        Creneau
  ---------------------------------------------
  Algo         Amphi_A      Lundi 8h-10h
  Probas       Amphi_A      Lundi 10h-12h
  Systemes     Salle_B      Lundi 10h-12h
  Reseaux      Labo_D       Lundi 8h-10h
  BDD          Amphi_A      Lundi 14h-16h
  IA           Amphi_A      Lundi 16h-18h
  Securite     Labo_C       Lundi 10h-12h
  Web          Labo_D       Lundi 10h-12h

Visualisons le résultat sous forme de grille emploi du temps.

if greedy_success:
    visualize_timetable(greedy_schedule, title="Emploi du temps - Heuristique gloutonne")
    plt.show()

    greedy_metrics = evaluate_schedule(greedy_schedule)
    print_metrics(greedy_metrics, label="(glouton)")
else:
    print("Pas de solution gloutonne a visualiser.")

Metriques de qualite (glouton)
=============================================
Trous enseignants (total) : 1
Cours le matin            : 75%
Equilibre des jours (std) : 3.20
Cours par jour            : [8, 0, 0, 0, 0]
Utilisation salles :
  Amphi_A      : 4 cours (20%)
  Salle_B      : 1 cours (5%)
  Labo_C       : 1 cours (5%)
  Labo_D       : 2 cours (10%)

Interpretation : heuristique gloutonne

Sortie obtenue : le glouton parvient a placer tous les cours (l’instance n’est pas trop contrainte), mais la qualite de la solution est perfectible.

Aspect	Observation	Problème
Placement rapide	Quelques millisecondes	Pas de problème
Concentration le lundi	Tous les premiers creneaux sont le lundi	Desequilibre des jours
Pas d’optimisation	Trous possibles pour les enseignants	Qualite mediocre

Limites fondamentales du glouton : 1. L’ordre de parcours des creneaux (Lundi 8h en premier) biaise la solution 2. Aucune optimisation des contraintes souples (trous, equilibre) 3. Sur des instances plus contraintes, le glouton echouerait car il ne revient pas en arriere

Conclusion : pour obtenir une solution de qualite, il faut un solveur capable d’explorer l’espace de recherche et d’optimiser les critères souples.

---

4. Approche 2 : OR-Tools CP-SAT (~15 min)

OR-Tools de Google fournit le solveur CP-SAT (Constraint Programming - Satisfiability), un des solveurs de contraintes les plus performants disponibles.

Modelisation

Pour chaque cours \(c\) : - Variable course_slot[c] \(\in \{0, 1, \ldots, 19\}\) : creneau horaire - Variable course_room[c] \(\in \{0, 1, \ldots, 2\}\) : salle

Contraintes dures

Contrainte	Formulation	Raison
Capacite de la salle	Si course_room[c] = r, alors capacity[r] >= students[c]	Securite
Equipement compatible	Si course_room[c] = r, equipement requis disponible	Fonctionnel
Pas de double reservation salle	Si course_room[c1] == course_room[c2], alors course_slot[c1] != course_slot[c2]	Physique
Pas de double reservation enseignant	Si teacher[c1] == teacher[c2], alors course_slot[c1] != course_slot[c2]	Humain

Contraintes souples (objectif)

On minimise une somme ponderee de penalites :

\[\text{Minimiser} \quad w_1 \cdot \text{trous\_enseignants} + w_2 \cdot \text{penalite\_apres-midi} + w_3 \cdot \text{desequilibre\_jours}\]

def solve_timetable_cpsat(time_limit_s=10.0, verbose=True):
    """Resout le probleme d'emploi du temps avec OR-Tools CP-SAT.

    Retourne (schedule, status, solve_time_ms, objective_value).
    """
    model = cp_model.CpModel()

    # ==========================================
    # Variables de decision
    # ==========================================
    course_slot = {}  # cours -> IntVar (creneau 0..NUM_SLOTS-1)
    course_room = {}  # cours -> IntVar (salle 0..num_rooms-1)

    for cname in course_names:
        course_slot[cname] = model.new_int_var(0, NUM_SLOTS - 1, f"slot_{cname}")

        # Restreindre le domaine des salles aux salles compatibles
        compatible = get_compatible_rooms(cname)
        compatible_ids = [ROOMS[r]["id"] for r in compatible]
        course_room[cname] = model.new_int_var(0, num_rooms - 1, f"room_{cname}")
        model.add_allowed_assignments(
            [course_room[cname]],
            [[rid] for rid in compatible_ids]
        )

    # ==========================================
    # Contraintes dures
    # ==========================================

    # C1 : Pas de double reservation de salle
    # Si deux cours sont dans la meme salle, ils doivent etre a des creneaux differents
    for c1, c2 in combinations(course_names, 2):
        # Creer une variable booleenne : same_room = (room[c1] == room[c2])
        same_room = model.new_bool_var(f"same_room_{c1}_{c2}")
        model.add(course_room[c1] == course_room[c2]).only_enforce_if(same_room)
        model.add(course_room[c1] != course_room[c2]).only_enforce_if(same_room.negated())
        # Si meme salle, creneaux differents
        model.add(course_slot[c1] != course_slot[c2]).only_enforce_if(same_room)

    # C2 : Pas de double reservation d'enseignant
    for tname in teacher_names:
        teacher_courses = get_teacher_courses(tname)
        for c1, c2 in combinations(teacher_courses, 2):
            model.add(course_slot[c1] != course_slot[c2])

    # ==========================================
    # Contraintes souples (penalites)
    # ==========================================
    penalties = []

    # S1 : Penalite pour les creneaux d'apres-midi (preference pour le matin)
    # Creneaux du matin : slot % SLOTS_PER_DAY < 2
    for cname in course_names:
        is_afternoon = model.new_bool_var(f"afternoon_{cname}")
        # hour_in_day = slot % SLOTS_PER_DAY
        hour_var = model.new_int_var(0, SLOTS_PER_DAY - 1, f"hour_{cname}")
        model.add_modulo_equality(hour_var, course_slot[cname], SLOTS_PER_DAY)
        # is_afternoon = (hour_var >= 2)
        model.add(hour_var >= 2).only_enforce_if(is_afternoon)
        model.add(hour_var < 2).only_enforce_if(is_afternoon.negated())
        penalties.append(is_afternoon)  # poids 1 par cours d'apres-midi

    # S2 : Penalite pour les trous dans l'emploi du temps d'un enseignant
    # Pour chaque enseignant et chaque jour, si 2 cours ont un trou entre eux
    gap_penalties = []
    for tname in teacher_names:
        teacher_courses = get_teacher_courses(tname)
        if len(teacher_courses) < 2:
            continue
        for c1, c2 in combinations(teacher_courses, 2):
            # Les deux cours sont le meme jour ?
            day_c1 = model.new_int_var(0, len(DAYS) - 1, f"day_{c1}_{tname}")
            day_c2 = model.new_int_var(0, len(DAYS) - 1, f"day_{c2}_{tname}")
            model.add_division_equality(day_c1, course_slot[c1], SLOTS_PER_DAY)
            model.add_division_equality(day_c2, course_slot[c2], SLOTS_PER_DAY)

            same_day = model.new_bool_var(f"same_day_{c1}_{c2}")
            model.add(day_c1 == day_c2).only_enforce_if(same_day)
            model.add(day_c1 != day_c2).only_enforce_if(same_day.negated())

            # Si meme jour, calculer la distance entre les heures
            hour_c1 = model.new_int_var(0, SLOTS_PER_DAY - 1, f"hour_gap_{c1}")
            hour_c2 = model.new_int_var(0, SLOTS_PER_DAY - 1, f"hour_gap_{c2}")
            model.add_modulo_equality(hour_c1, course_slot[c1], SLOTS_PER_DAY)
            model.add_modulo_equality(hour_c2, course_slot[c2], SLOTS_PER_DAY)

            abs_diff = model.new_int_var(0, SLOTS_PER_DAY, f"abs_diff_{c1}_{c2}")
            model.add_abs_equality(abs_diff,
                                   model.new_int_var(-SLOTS_PER_DAY, SLOTS_PER_DAY,
                                                     f"diff_{c1}_{c2}"))
            model.add(course_slot[c1] - course_slot[c2] ==
                      model.new_int_var(-NUM_SLOTS, NUM_SLOTS, f"raw_diff_{c1}_{c2}"))

            # Penaliser si meme jour et distance > 1 (il y a un trou)
            has_gap = model.new_bool_var(f"gap_{c1}_{c2}")
            # Simplification : penaliser si les cours sont le meme jour
            # (encourage la repartition sur des jours differents)
            gap_penalties.append(same_day)

    # Poids des penalites : favoriser les penalites de trous
    # Total = 1 * afternoon_penalties + 3 * gap_penalties
    objective_terms = []
    for p in penalties:
        objective_terms.append(p)
    for g in gap_penalties:
        objective_terms.append(3 * g)  # poids 3 pour les trous

    if objective_terms:
        model.minimize(sum(objective_terms))

    # ==========================================
    # Resolution
    # ==========================================
    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = time_limit_s

    start = time.time()
    status = solver.solve(model)
    solve_time = (time.time() - start) * 1000

    status_name = solver.status_name(status)

    if verbose:
        print(f"Statut          : {status_name}")
        print(f"Temps de calcul : {solve_time:.1f} ms")

    if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        schedule = {}
        for cname in course_names:
            slot_val = solver.value(course_slot[cname])
            room_val = solver.value(course_room[cname])
            assigned_room = room_names[room_val]
            schedule[cname] = (assigned_room, slot_val)

        obj_val = solver.objective_value if objective_terms else 0

        if verbose:
            print(f"Objectif        : {obj_val}")
            print()
            print("Affectations :")
            print(f"  {'Cours':<12} {'Salle':<12} {'Creneau'}")
            print(f"  {'-'*45}")
            for cname in course_names:
                rname, slot = schedule[cname]
                print(f"  {cname:<12} {rname:<12} {slot_label(slot)}")

        return schedule, status_name, solve_time, obj_val
    else:
        if verbose:
            print("Aucune solution trouvee.")
        return None, status_name, solve_time, None


print("Fonction solve_timetable_cpsat definie.")

Fonction solve_timetable_cpsat definie.

Executons le solveur CP-SAT et analysons la solution obtenue.

print("Resolution par OR-Tools CP-SAT")
print("=" * 50)

cpsat_schedule, cpsat_status, cpsat_time, cpsat_obj = solve_timetable_cpsat(
    time_limit_s=10.0
)

Resolution par OR-Tools CP-SAT
==================================================
Statut          : OPTIMAL
Temps de calcul : 32.5 ms
Objectif        : 0.0

Affectations :
  Cours        Salle        Creneau
  ---------------------------------------------
  Algo         Amphi_A      Mardi 10h-12h
  Probas       Amphi_A      Mardi 8h-10h
  Systemes     Salle_B      Mercredi 8h-10h
  Reseaux      Labo_D       Mardi 10h-12h
  BDD          Amphi_A      Lundi 10h-12h
  IA           Amphi_A      Lundi 8h-10h
  Securite     Labo_C       Mercredi 8h-10h
  Web          Labo_D       Mardi 8h-10h

Visualisons la solution et evaluons sa qualite.

if cpsat_schedule:
    visualize_timetable(cpsat_schedule, title="Emploi du temps - OR-Tools CP-SAT")
    plt.show()

    cpsat_metrics = evaluate_schedule(cpsat_schedule)
    print_metrics(cpsat_metrics, label="(CP-SAT)")

Metriques de qualite (CP-SAT)
=============================================
Trous enseignants (total) : 0
Cours le matin            : 100%
Equilibre des jours (std) : 1.50
Cours par jour            : [2, 4, 2, 0, 0]
Utilisation salles :
  Amphi_A      : 4 cours (20%)
  Salle_B      : 1 cours (5%)
  Labo_C       : 1 cours (5%)
  Labo_D       : 2 cours (10%)

Interpretation : solution CP-SAT

Sortie obtenue : le solveur CP-SAT trouve une solution optimale (ou quasi-optimale) en quelques dizaines de millisecondes (la valeur exacte, dépendante de la machine, figure dans la sortie de la cellule de résolution ci-dessus).

Aspect	Glouton	CP-SAT	Commentaire
Faisabilite	Oui	Oui (garanti si solution existe)	CP-SAT est complet
Temps de calcul	quasi-instantane (cf. mesure)	fraction de seconde (cf. mesure ci-dessus)	Les deux sont rapides ici
Optimisation souples	Non	Oui	Différence majeure
Equilibre des jours	Mediocre	Bien meilleur	Grace a l’objectif
Trous enseignants	Non minimises	Minimises	Grace aux penalites

Points cles : 1. CP-SAT garantit de trouver une solution si elle existe (completude) 2. Les contraintes souples sont modelisees comme un objectif a minimiser 3. Le modèle separe clairement la structure (contraintes dures) de la qualite (objectif) 4. Le temps de resolution reste faible grace aux techniques de propagation et d’elagage internes au solveur

Note technique : CP-SAT utilise en interne une combinaison de backtracking, propagation de contraintes, et SAT solving (clause learning). C’est nettement plus sophistique que notre backtracking du CSP-1.

Comparaison glouton vs CP-SAT

Comparons les deux approches sur les metriques de qualite.

if greedy_success and cpsat_schedule:
    fig, axes = plt.subplots(1, 3, figsize=(16, 5))

    # 1. Cours par jour
    x = np.arange(len(DAYS))
    width = 0.35
    axes[0].bar(x - width/2, greedy_metrics["courses_per_day"], width,
                label="Glouton", color="#E15759", edgecolor="black")
    axes[0].bar(x + width/2, cpsat_metrics["courses_per_day"], width,
                label="CP-SAT", color="#4E79A7", edgecolor="black")
    axes[0].set_xticks(x)
    axes[0].set_xticklabels([d[:3] for d in DAYS])
    axes[0].set_ylabel("Nombre de cours")
    axes[0].set_title("Repartition par jour", fontweight='bold')
    axes[0].legend()
    axes[0].grid(axis='y', alpha=0.3)

    # 2. Utilisation des salles
    greedy_usage = [greedy_metrics["room_usage"][r] for r in room_names]
    cpsat_usage = [cpsat_metrics["room_usage"][r] for r in room_names]
    x2 = np.arange(num_rooms)
    axes[1].bar(x2 - width/2, greedy_usage, width,
                label="Glouton", color="#E15759", edgecolor="black")
    axes[1].bar(x2 + width/2, cpsat_usage, width,
                label="CP-SAT", color="#4E79A7", edgecolor="black")
    axes[1].set_xticks(x2)
    axes[1].set_xticklabels(room_names, fontsize=9)
    axes[1].set_ylabel("Nombre de cours")
    axes[1].set_title("Utilisation des salles", fontweight='bold')
    axes[1].legend()
    axes[1].grid(axis='y', alpha=0.3)

    # 3. Metriques de qualite
    metrics_names = ["Trous\nenseignants", "% matin", "Equilibre\n(std, inv.)"]
    greedy_vals = [
        greedy_metrics["gaps_total"],
        greedy_metrics["morning_pct"],
        1.0 / (1.0 + greedy_metrics["day_balance_std"])
    ]
    cpsat_vals = [
        cpsat_metrics["gaps_total"],
        cpsat_metrics["morning_pct"],
        1.0 / (1.0 + cpsat_metrics["day_balance_std"])
    ]
    x3 = np.arange(len(metrics_names))
    axes[2].bar(x3 - width/2, greedy_vals, width,
                label="Glouton", color="#E15759", edgecolor="black")
    axes[2].bar(x3 + width/2, cpsat_vals, width,
                label="CP-SAT", color="#4E79A7", edgecolor="black")
    axes[2].set_xticks(x3)
    axes[2].set_xticklabels(metrics_names, fontsize=9)
    axes[2].set_title("Metriques de qualite", fontweight='bold')
    axes[2].legend()
    axes[2].grid(axis='y', alpha=0.3)

    fig.suptitle("Comparaison Glouton vs CP-SAT", fontsize=14, fontweight='bold')
    plt.tight_layout()
    plt.show()

    # Tableau recapitulatif
    print("\nTableau comparatif")
    print("=" * 55)
    print(f"{'Metrique':<25} {'Glouton':>12} {'CP-SAT':>12}")
    print("-" * 55)
    print(f"{'Trous enseignants':<25} {greedy_metrics['gaps_total']:>12} {cpsat_metrics['gaps_total']:>12}")
    print(f"{'% cours le matin':<25} {greedy_metrics['morning_pct']:>11.0f}% {cpsat_metrics['morning_pct']:>11.0f}%")
    print(f"{'Ecart-type jours':<25} {greedy_metrics['day_balance_std']:>12.2f} {cpsat_metrics['day_balance_std']:>12.2f}")
    print(f"{'Temps (ms)':<25} {greedy_time:>12.2f} {cpsat_time:>12.1f}")
    print("=" * 55)

Tableau comparatif
=======================================================
Metrique                       Glouton       CP-SAT
-------------------------------------------------------
Trous enseignants                    1            0
% cours le matin                   75%         100%
Ecart-type jours                  3.20         1.50
Temps (ms)                        0.07         32.5
=======================================================

Interpretation : comparaison des approches

Les graphiques et le tableau mettent en evidence les différences fondamentales entre les deux approches.

Critere	Glouton	CP-SAT	Gagnant
Rapidite	Quasi-instantane	Quelques ms	Glouton (leger)
Optimalite	Non garantie	Optimale (ou prouvee proche)	CP-SAT
Completude	Non (peut echouer)	Oui (trouve une solution si possible)	CP-SAT
Facilite de modelisation	Simple (code iteratif)	Plus complexe (variables, contraintes)	Glouton
Flexibilite	Difficile a adapter	Ajout de contraintes facile	CP-SAT

Points cles : 1. Le glouton est utile comme baseline ou pour obtenir une solution initiale rapide 2. CP-SAT excelle des que l’on a des contraintes souples a optimiser 3. Sur des instances plus grandes (50+ cours), le glouton echouerait tandis que CP-SAT resterait performant

---

5. Introduction a MiniZinc (optionnel) (~10 min)

MiniZinc est un langage de modelisation declaratif pour les problemes de contraintes. Contrairement a CP-SAT ou l’on construit le modèle en Python (approche imperative), en MiniZinc on declare les variables, domaines et contraintes dans une syntaxe proche des mathematiques.

Approche imperative vs declarative

Aspect	Imperatif (CP-SAT)	Declaratif (MiniZinc)
Style	“Comment resoudre”	“Quoi resoudre”
Syntaxe	API Python (model.add, model.new_int_var)	Langage dedie (var, constraint, solve)
Solveur	CP-SAT integre	Choix du solveur (Gecode, Chuffed, CP-SAT…)
Lisibilite	Code Python standard	Proche des specifications mathematiques
Flexibilite	Totale (Python complet)	Limitee au langage MiniZinc

Le modèle MiniZinc

Voici le même problème de timetabling exprime en MiniZinc. Observez la concision par rapport a la version Python.

# Modele MiniZinc pour le probleme d'emploi du temps
# (affiche comme chaine de caracteres pour etude)

MINIZINC_MODEL = """
% ===========================================================
% Emploi du temps universitaire - Modele MiniZinc
% ===========================================================

% --- Parametres ---
int: num_courses = 8;
int: num_rooms = 3;
int: num_slots = 20;   % 5 jours x 4 creneaux
int: slots_per_day = 4;

% Capacites des salles
array[1..num_rooms] of int: room_capacity = [120, 60, 40];

% Etudiants par cours
array[1..num_courses] of int: students = [90, 75, 60, 50, 80, 100, 40, 55];

% Enseignant par cours (1=Dupont, 2=Martin, 3=Bernard, 4=Leroy)
array[1..num_courses] of int: teacher = [1, 2, 1, 3, 4, 2, 3, 4];

% Equipement requis (0=standard, 1=labo)
array[1..num_courses] of int: equip_required = [0, 0, 0, 1, 0, 0, 1, 1];
array[1..num_rooms] of int: equip_available = [0, 0, 1];

% --- Variables de decision ---
array[1..num_courses] of var 1..num_slots: course_slot;
array[1..num_courses] of var 1..num_rooms: course_room;

% --- Contraintes dures ---

% C1 : Capacite de la salle suffisante
constraint forall(c in 1..num_courses)(
    room_capacity[course_room[c]] >= students[c]
);

% C2 : Equipement compatible
constraint forall(c in 1..num_courses)(
    equip_required[c] <= equip_available[course_room[c]]
);

% C3 : Pas de double reservation de salle
constraint forall(c1 in 1..num_courses, c2 in c1+1..num_courses)(
    course_room[c1] = course_room[c2] -> course_slot[c1] != course_slot[c2]
);

% C4 : Pas de double reservation d'enseignant
constraint forall(c1 in 1..num_courses, c2 in c1+1..num_courses
                  where teacher[c1] = teacher[c2])(
    course_slot[c1] != course_slot[c2]
);

% --- Objectif : minimiser les cours d'apres-midi ---
var int: afternoon_penalty = sum(c in 1..num_courses)(
    bool2int((course_slot[c] - 1) mod slots_per_day >= 2)
);

solve minimize afternoon_penalty;

% --- Sortie ---
output [
    "Cours " ++ show(c) ++ ": salle=" ++ show(course_room[c])
    ++ " creneau=" ++ show(course_slot[c]) ++ "\\n"
    | c in 1..num_courses
];
"""

print("Modele MiniZinc pour l'emploi du temps :")
print("=" * 55)
print(MINIZINC_MODEL)

Modele MiniZinc pour l'emploi du temps :
=======================================================

% ===========================================================
% Emploi du temps universitaire - Modele MiniZinc
% ===========================================================

% --- Parametres ---
int: num_courses = 8;
int: num_rooms = 3;
int: num_slots = 20;   % 5 jours x 4 creneaux
int: slots_per_day = 4;

% Capacites des salles
array[1..num_rooms] of int: room_capacity = [120, 60, 40];

% Etudiants par cours
array[1..num_courses] of int: students = [90, 75, 60, 50, 80, 100, 40, 55];

% Enseignant par cours (1=Dupont, 2=Martin, 3=Bernard, 4=Leroy)
array[1..num_courses] of int: teacher = [1, 2, 1, 3, 4, 2, 3, 4];

% Equipement requis (0=standard, 1=labo)
array[1..num_courses] of int: equip_required = [0, 0, 0, 1, 0, 0, 1, 1];
array[1..num_rooms] of int: equip_available = [0, 0, 1];

% --- Variables de decision ---
array[1..num_courses] of var 1..num_slots: course_slot;
array[1..num_courses] of var 1..num_rooms: course_room;

% --- Contraintes dures ---

% C1 : Capacite de la salle suffisante
constraint forall(c in 1..num_courses)(
    room_capacity[course_room[c]] >= students[c]
);

% C2 : Equipement compatible
constraint forall(c in 1..num_courses)(
    equip_required[c] <= equip_available[course_room[c]]
);

% C3 : Pas de double reservation de salle
constraint forall(c1 in 1..num_courses, c2 in c1+1..num_courses)(
    course_room[c1] = course_room[c2] -> course_slot[c1] != course_slot[c2]
);

% C4 : Pas de double reservation d'enseignant
constraint forall(c1 in 1..num_courses, c2 in c1+1..num_courses
                  where teacher[c1] = teacher[c2])(
    course_slot[c1] != course_slot[c2]
);

% --- Objectif : minimiser les cours d'apres-midi ---
var int: afternoon_penalty = sum(c in 1..num_courses)(
    bool2int((course_slot[c] - 1) mod slots_per_day >= 2)
);

solve minimize afternoon_penalty;

% --- Sortie ---
output [
    "Cours " ++ show(c) ++ ": salle=" ++ show(course_room[c])
    ++ " creneau=" ++ show(course_slot[c]) ++ "\n"
    | c in 1..num_courses
];

Analyse du modèle MiniZinc

Decomposons la syntaxe MiniZinc :

Élément MiniZinc	Equivalent Python/CP-SAT	Rôle
int: num_courses = 8	num_courses = 8	Paramètre
array[1..n] of int: data	data = [...]	Données
var 1..20: x	model.new_int_var(1, 20, 'x')	Variable de decision
constraint ...	model.add(...)	Contrainte
forall(c in 1..n)(...)	for c in range(n): model.add(...)	Quantificateur universel
-> (implication)	only_enforce_if	Implication logique
solve minimize f	model.minimize(f)	Objectif

Avantage principal : le modèle MiniZinc est beaucoup plus concis. La contrainte C3 (pas de double reservation) s’ecrit de façon plus compacte qu’en CP-SAT.

Pour aller plus loin : voir App-8 MiniZinc pour une introduction complete au langage MiniZinc avec des exemples progressifs.

# Execution du modele MiniZinc.
#
# Le package Python `minizinc` expose `instance.solve()` synchrone, qui echoue
# sous un environnement async (papermill/nbconvert : "asyncio.run() cannot be
# called from a running event loop"). On execute donc via le binaire CLI
# (minizinc --solver gecode), robuste en toutes circonstances.

import shutil, subprocess, tempfile, textwrap

mzn_cli = shutil.which("minizinc")

if mzn_cli is None:
    print("MiniZinc non installe (binaire `minizinc` absent du PATH).")
    print("Installation : https://www.minizinc.org/  (puis `pip install minizinc`)")
    print()
    print("Le modele MiniZinc ci-dessus peut etre copie dans MiniZinc IDE")
    print("pour etre execute directement.")
else:
    with tempfile.NamedTemporaryFile(mode="w", suffix=".mzn", delete=False) as f:
        f.write(textwrap.dedent(MINIZINC_MODEL).strip())
        mzn_path = f.name
    try:
        start = time.time()
        proc = subprocess.run(
            [mzn_cli, "--solver", "gecode", "--time-limit", "10000", mzn_path],
            capture_output=True, text=True, timeout=30,
        )
        mzn_time = (time.time() - start) * 1000
        stdout = proc.stdout.strip()

        print("Resolution MiniZinc (Gecode)")
        print("=" * 45)
        print(f"Temps  : {mzn_time:.1f} ms")

        if proc.returncode == 0:
            if "UNSATISFIABLE" in stdout:
                print("Statut : UNSATISFIABLE (aucune solution faisable)")
                print()
                print("L'instance est trop contrainte pour les 8 cours avec les")
                print("3 salles et 20 creneaux disponibles : aucune affectation ne")
                print("satisfait simultanement toutes les contraintes (conflits")
                print("d'enseignants, de salles et de capacites).")
            else:
                print("Statut : SOLUTION TROUVEE")
                print(stdout)
        else:
            print(f"Statut : ERREUR (code {proc.returncode})")
            print(stdout)
            if proc.stderr.strip():
                print(proc.stderr.strip())
    finally:
        os.unlink(mzn_path)

MiniZinc non installe (binaire `minizinc` absent du PATH).
Installation : https://www.minizinc.org/  (puis `pip install minizinc`)

Le modele MiniZinc ci-dessus peut etre copie dans MiniZinc IDE
pour etre execute directement.

Interpretation : MiniZinc vs CP-SAT

Critere	CP-SAT (Python)	MiniZinc	Commentaire
Concision du modèle	Plus de code	Plus compact	MiniZinc plus concis que CP-SAT
Lisibilite	Bonne (Python)	Excellente (math-like)	MiniZinc plus proche de la specification
Performance	Très bon	Variable selon solveur	CP-SAT souvent plus rapide
Integration Python	Native	Via package minizinc	CP-SAT plus simple a integrer
Multi-solveurs	CP-SAT uniquement	Gecode, Chuffed, CP-SAT…	MiniZinc plus flexible

Quand utiliser quoi ? - CP-SAT : integration dans une application Python, besoin de performance maximale - MiniZinc : prototypage rapide, exploration de modèles, enseignement

Note : il est possible d’utiliser CP-SAT comme solveur pour un modèle MiniZinc. Le meilleur des deux mondes !

---

6. Visualisation et analyse avancees (~5 min)

Explorons la solution CP-SAT sous différents angles : emploi du temps par enseignant et taux d’utilisation des salles.

def visualize_teacher_schedule(schedule, title="Emploi du temps par enseignant"):
    """Affiche l'emploi du temps du point de vue de chaque enseignant."""
    fig, axes = plt.subplots(2, 2, figsize=(16, 10))
    axes = axes.flatten()

    for t_idx, tname in enumerate(teacher_names):
        ax = axes[t_idx]
        ax.set_title(f"{TEACHERS[tname]['name']}", fontsize=12, fontweight='bold')

        # Grille de fond
        for d in range(len(DAYS)):
            for h in range(SLOTS_PER_DAY):
                color = "#F5F5F5" if d % 2 == 0 else "#EBEBEB"
                rect = plt.Rectangle((d, SLOTS_PER_DAY - 1 - h), 1, 1,
                                     facecolor=color, edgecolor="#CCCCCC",
                                     linewidth=0.5)
                ax.add_patch(rect)

        # Placer les cours de cet enseignant
        teacher_courses = get_teacher_courses(tname)
        for cname in teacher_courses:
            if cname not in schedule:
                continue
            rname, slot = schedule[cname]
            day, hour = slot_to_day_hour(slot)
            color = COURSE_COLORS.get(cname, "#999999")
            rect = plt.Rectangle((day + 0.05, SLOTS_PER_DAY - 1 - hour + 0.05),
                                 0.9, 0.9,
                                 facecolor=color, edgecolor="black",
                                 linewidth=1.5, alpha=0.85)
            ax.add_patch(rect)
            ax.text(day + 0.5, SLOTS_PER_DAY - 1 - hour + 0.55,
                    cname, ha='center', va='center',
                    fontsize=9, fontweight='bold', color='white')
            ax.text(day + 0.5, SLOTS_PER_DAY - 1 - hour + 0.25,
                    rname, ha='center', va='center',
                    fontsize=7, color='white', style='italic')

        ax.set_xlim(0, len(DAYS))
        ax.set_ylim(0, SLOTS_PER_DAY)
        ax.set_xticks([d + 0.5 for d in range(len(DAYS))])
        ax.set_xticklabels([d[:3] for d in DAYS], fontsize=8)
        ax.set_yticks([h + 0.5 for h in range(SLOTS_PER_DAY)])
        ax.set_yticklabels(list(reversed(SLOT_LABELS)), fontsize=8)
        ax.set_aspect('equal')

    fig.suptitle(title, fontsize=14, fontweight='bold')
    plt.tight_layout()
    return fig


if cpsat_schedule:
    visualize_teacher_schedule(cpsat_schedule,
                              title="Emploi du temps par enseignant (CP-SAT)")
    plt.show()

Analysons maintenant le taux d’occupation de chaque salle sous forme de heatmap.

def visualize_room_utilization(schedule, title="Utilisation des salles"):
    """Graphique d'utilisation des salles (heatmap)."""
    fig, ax = plt.subplots(figsize=(12, 5))

    # Matrice d'occupation : rooms x slots
    occupation = np.zeros((num_rooms, NUM_SLOTS))
    labels_matrix = [["" for _ in range(NUM_SLOTS)] for _ in range(num_rooms)]

    for cname, (rname, slot) in schedule.items():
        r_idx = room_names.index(rname)
        occupation[r_idx, slot] = 1
        labels_matrix[r_idx][slot] = cname[:4]  # Abbreviation

    # Heatmap
    cmap = plt.cm.colors.ListedColormap(['#F5F5F5', '#4E79A7'])
    ax.imshow(occupation, cmap=cmap, aspect='auto', interpolation='nearest')

    # Labels dans les cellules
    for r in range(num_rooms):
        for s in range(NUM_SLOTS):
            if labels_matrix[r][s]:
                ax.text(s, r, labels_matrix[r][s],
                        ha='center', va='center', fontsize=7,
                        fontweight='bold', color='white')

    # Axes
    slot_tick_labels = []
    for d_idx, day in enumerate(DAYS):
        for h_idx in range(SLOTS_PER_DAY):
            if h_idx == 0:
                slot_tick_labels.append(f"{day[:3]}")
            else:
                slot_tick_labels.append(SLOT_LABELS[h_idx][:4])

    ax.set_xticks(range(NUM_SLOTS))
    ax.set_xticklabels(slot_tick_labels, fontsize=7, rotation=45, ha='right')
    ax.set_yticks(range(num_rooms))
    ax.set_yticklabels(room_names, fontsize=10)

    # Separateurs de jours
    for d in range(1, len(DAYS)):
        ax.axvline(x=d * SLOTS_PER_DAY - 0.5, color='black', linewidth=1.5)

    ax.set_title(title, fontsize=13, fontweight='bold')

    # Taux d'utilisation
    for r in range(num_rooms):
        pct = np.sum(occupation[r, :]) / NUM_SLOTS * 100
        ax.text(NUM_SLOTS + 0.3, r, f"{pct:.0f}%",
                ha='left', va='center', fontsize=10, fontweight='bold')

    plt.tight_layout()
    return fig


if cpsat_schedule:
    visualize_room_utilization(cpsat_schedule,
                              title="Occupation des salles (CP-SAT)")
    plt.show()

Interpretation : analyse de la solution

Vue enseignants : chaque enseignant a un emploi du temps sans conflit. On verifie visuellement qu’aucun enseignant n’a deux cours au même creneau.

Vue salles : la heatmap montre le taux d’occupation de chaque salle.

Salle	Capacite	Cours affectes	Utilisation	Commentaire
Amphi_A	120	Algo, IA (gros effectifs)	Variable	Seule salle pour les grands groupes
Salle_B	60	Systèmes	Variable	Usage modere
Labo_C	40	Securite	Variable	Seul labo pour Securite (40 etu) avec Labo_D

Points cles : 1. Les contraintes d’equipement créent un goulot d’etranglement sur Labo_D (Reseaux et Web ne peuvent aller qu’a Labo_D, 2 cours pour 1 salle) 2. Amphi_A est sous-utilise en proportion mais indispensable pour les gros effectifs 3. L’equilibre des jours depend directement de l’objectif d’optimisation

---

7. Exercices

Exemple guide : contrainte de 3 heures consecutives

Enonce : ajoutez au modèle CP-SAT la contrainte dure suivante :

Aucun enseignant ne doit enseigner 3 creneaux consecutifs dans la même journee.

Conseil : pour chaque enseignant et chaque jour, verifiez que la somme des indicateurs de presence sur 3 creneaux consecutifs ne depasse pas 2.

La cellule ci-dessous presente une implementation complete de cette contrainte dans la fonction solve_timetable_cpsat.

# Exemple resolu : pas de 3 heures consecutives pour un enseignant

def solve_timetable_cpsat(time_limit_s=10.0, verbose=True):
    """Resout le probleme d'emploi du temps avec OR-Tools CP-SAT.

    Retourne (schedule, status, solve_time_ms, objective_value).
    """
    model = cp_model.CpModel()

    # ==========================================
    # Variables de decision
    # ==========================================
    course_slot = {}  # cours -> IntVar (creneau 0..NUM_SLOTS-1)
    course_room = {}  # cours -> IntVar (salle 0..num_rooms-1)

    for cname in course_names:
        course_slot[cname] = model.new_int_var(0, NUM_SLOTS - 1, f"slot_{cname}")

        # Restreindre le domaine des salles aux salles compatibles
        compatible = get_compatible_rooms(cname)
        compatible_ids = [ROOMS[r]["id"] for r in compatible]
        course_room[cname] = model.new_int_var(0, num_rooms - 1, f"room_{cname}")
        model.add_allowed_assignments(
            [course_room[cname]],
            [[rid] for rid in compatible_ids]
        )

    # ==========================================
    # Contraintes dures
    # ==========================================

    # C1 : Pas de double reservation de salle
    # Si deux cours sont dans la meme salle, ils doivent etre a des creneaux differents
    for c1, c2 in combinations(course_names, 2):
        # Creer une variable booleenne : same_room = (room[c1] == room[c2])
        same_room = model.new_bool_var(f"same_room_{c1}_{c2}")
        model.add(course_room[c1] == course_room[c2]).only_enforce_if(same_room)
        model.add(course_room[c1] != course_room[c2]).only_enforce_if(same_room.negated())
        # Si meme salle, creneaux differents
        model.add(course_slot[c1] != course_slot[c2]).only_enforce_if(same_room)

    is_teaching = {}
    for cname in course_names:
        is_teaching[cname] = {}
        for slot in range(NUM_SLOTS):
            var = model.new_bool_var(f"is_teaching_{cname}_at_{slot}")
            model.add(course_slot[cname] == slot).only_enforce_if(var)
            model.add(course_slot[cname] != slot).only_enforce_if(var.negated())
            is_teaching[cname][slot] = var

    # C2 : Pas de double reservation d'enseignant
    for tname in teacher_names:
        teacher_courses = get_teacher_courses(tname)
        for c1, c2 in combinations(teacher_courses, 2):
            model.add(course_slot[c1] != course_slot[c2])
        for day in range(len(DAYS)):
            for h_start in range(SLOTS_PER_DAY - 2): 
                slots_3 = [day * SLOTS_PER_DAY + h_start + k for k in range(3)]
                
                teaching_indicators = [
                    is_teaching[cname][s]
                    for cname in teacher_courses
                    for s in slots_3
                ]
                model.add(sum(teaching_indicators) <= 2)

    # ==========================================
    # Contraintes souples (penalites)
    # ==========================================
    penalties = []

    # S1 : Penalite pour les creneaux d'apres-midi (preference pour le matin)
    # Creneaux du matin : slot % SLOTS_PER_DAY < 2
    for cname in course_names:
        is_afternoon = model.new_bool_var(f"afternoon_{cname}")
        # hour_in_day = slot % SLOTS_PER_DAY
        hour_var = model.new_int_var(0, SLOTS_PER_DAY - 1, f"hour_{cname}")
        model.add_modulo_equality(hour_var, course_slot[cname], SLOTS_PER_DAY)
        # is_afternoon = (hour_var >= 2)
        model.add(hour_var >= 2).only_enforce_if(is_afternoon)
        model.add(hour_var < 2).only_enforce_if(is_afternoon.negated())
        penalties.append(is_afternoon)  # poids 1 par cours d'apres-midi

    # S2 : Penalite pour les trous dans l'emploi du temps d'un enseignant
    # Pour chaque enseignant et chaque jour, si 2 cours ont un trou entre eux
    gap_penalties = []
    for tname in teacher_names:
        teacher_courses = get_teacher_courses(tname)
        if len(teacher_courses) < 2:
            continue
        for c1, c2 in combinations(teacher_courses, 2):
            # Les deux cours sont le meme jour ?
            day_c1 = model.new_int_var(0, len(DAYS) - 1, f"day_{c1}_{tname}")
            day_c2 = model.new_int_var(0, len(DAYS) - 1, f"day_{c2}_{tname}")
            model.add_division_equality(day_c1, course_slot[c1], SLOTS_PER_DAY)
            model.add_division_equality(day_c2, course_slot[c2], SLOTS_PER_DAY)

            same_day = model.new_bool_var(f"same_day_{c1}_{c2}")
            model.add(day_c1 == day_c2).only_enforce_if(same_day)
            model.add(day_c1 != day_c2).only_enforce_if(same_day.negated())

            # Si meme jour, calculer la distance entre les heures
            hour_c1 = model.new_int_var(0, SLOTS_PER_DAY - 1, f"hour_gap_{c1}")
            hour_c2 = model.new_int_var(0, SLOTS_PER_DAY - 1, f"hour_gap_{c2}")
            model.add_modulo_equality(hour_c1, course_slot[c1], SLOTS_PER_DAY)
            model.add_modulo_equality(hour_c2, course_slot[c2], SLOTS_PER_DAY)

            abs_diff = model.new_int_var(0, SLOTS_PER_DAY, f"abs_diff_{c1}_{c2}")
            model.add_abs_equality(abs_diff,
                                   model.new_int_var(-SLOTS_PER_DAY, SLOTS_PER_DAY,
                                                     f"diff_{c1}_{c2}"))
            model.add(course_slot[c1] - course_slot[c2] ==
                      model.new_int_var(-NUM_SLOTS, NUM_SLOTS, f"raw_diff_{c1}_{c2}"))

            # Penaliser si meme jour et distance > 1 (il y a un trou)
            has_gap = model.new_bool_var(f"gap_{c1}_{c2}")
            # Simplification : penaliser si les cours sont le meme jour
            # (encourage la repartition sur des jours differents)
            gap_penalties.append(same_day)

    # Poids des penalites : favoriser les penalites de trous
    # Total = 1 * afternoon_penalties + 3 * gap_penalties
    objective_terms = []
    for p in penalties:
        objective_terms.append(p)
    for g in gap_penalties:
        objective_terms.append(3 * g)  # poids 3 pour les trous

    if objective_terms:
        model.minimize(sum(objective_terms))

    # ==========================================
    # Resolution
    # ==========================================
    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = time_limit_s

    start = time.time()
    status = solver.solve(model)
    solve_time = (time.time() - start) * 1000

    status_name = solver.status_name(status)

    if verbose:
        print(f"Statut          : {status_name}")
        print(f"Temps de calcul : {solve_time:.1f} ms")

    if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        schedule = {}
        for cname in course_names:
            slot_val = solver.value(course_slot[cname])
            room_val = solver.value(course_room[cname])
            assigned_room = room_names[room_val]
            schedule[cname] = (assigned_room, slot_val)

        obj_val = solver.objective_value if objective_terms else 0

        if verbose:
            print(f"Objectif        : {obj_val}")
            print()
            print("Affectations :")
            print(f"  {'Cours':<12} {'Salle':<12} {'Creneau'}")
            print(f"  {'-'*45}")
            for cname in course_names:
                rname, slot = schedule[cname]
                print(f"  {cname:<12} {rname:<12} {slot_label(slot)}")

        return schedule, status_name, solve_time, obj_val
    else:
        if verbose:
            print("Aucune solution trouvee.")
        return None, status_name, solve_time, None


print("Fonction solve_timetable_cpsat definie.")
schedule, status, t, obj = solve_timetable_cpsat(verbose=True)
print(f"Solution trouvee : {status}")

Fonction solve_timetable_cpsat definie.
Statut          : OPTIMAL
Temps de calcul : 50.9 ms
Objectif        : 0.0

Affectations :
  Cours        Salle        Creneau
  ---------------------------------------------
  Algo         Amphi_A      Jeudi 8h-10h
  Probas       Amphi_A      Lundi 8h-10h
  Systemes     Salle_B      Vendredi 10h-12h
  Reseaux      Labo_D       Lundi 10h-12h
  BDD          Amphi_A      Lundi 10h-12h
  IA           Amphi_A      Vendredi 10h-12h
  Securite     Labo_C       Vendredi 10h-12h
  Web          Labo_D       Vendredi 10h-12h
Solution trouvee : OPTIMAL

Exercice 1b : minimiser le temps d’attente entre cours

Enonce : un enseignant qui donne plusieurs cours dans la journee prefere qu’ils soient regroupes plutot qu’eparpilles. Ajoutez un objectif d’optimisation pour minimiser le temps d’attente total des enseignants entre leurs cours.

Consignes : 1. Appelez solve_timetable_cpsat définie ci-dessus pour obtenir une solution de base 2. Copiez et modifiez la fonction pour ajouter une variable idle_time par enseignant et minimisez la somme 3. Comparez les emplois du temps avec et sans l’objectif

# Exercice 1b : minimiser le temps d'attente

# TODO: copiez solve_timetable_cpsat et ajoutez un objectif
# pour minimiser l'ecart entre les creneaux de chaque enseignant
# Indice : pour chaque enseignant, calculez max_slot - min_slot
# et minimisez la somme

# Votre code ici
print("Exercice a completer")

Exercice a completer

Exercice 2 : disponibilite partielle des salles

Enonce : supposez que Labo_C n’est disponible que les Mardi, Mercredi et Jeudi (il est reserve pour la maintenance les lundi et vendredi).

Ajoutez cette contrainte au modèle CP-SAT et resolvez.

Conseil : les creneaux du lundi sont 0-3 et du vendredi 16-19. Si course_room[c] == 2 (Labo_C), alors course_slot[c] ne doit pas etre dans ces creneaux.

# Exercice 2 : disponibilite partielle de Labo_C



# A COMPLETER
# Indice : utiliser model.add_forbidden_assignments ou des implications
#
# labo_id = ROOMS["Labo_C"]["id"]
# forbidden_slots = list(range(0, 4)) + list(range(16, 20))  # Lundi + Vendredi
#
# for cname in course_names:
#     if COURSES[cname]["equipment"] == "labo":
#         # course_room[cname] doit etre labo_id
#         # et slot ne doit pas etre dans forbidden_slots
#         for s in forbidden_slots:
#             model.add(course_slot[cname] != s)



print("Exercice 2 : a completer")

Exercice 2 : a completer

Optimisation avancee

Extension du modèle d’emploi du temps avec contraintes supplementaires.

print("Exercice a completer")

Exercice a completer

Exercice 3 : groupes d’etudiants (pas de chevauchement)

Enonce : supposez que les etudiants de 2eme annee suivent a la fois Algo, Probas et Systèmes. Ces 3 cours ne doivent donc pas etre au même creneau.

De même, les etudiants de 3eme annee suivent IA, Securite et Web.

Ajoutez ces contraintes de non-chevauchement par groupe.

Conseil : c’est similaire aux contraintes d’enseignant – des paires de cours qui ne peuvent pas partager le même creneau.

# Exercice 3 : contraintes de groupes d'etudiants

# A COMPLETER
# student_groups = {
#     "2A": ["Algo", "Probas", "Systemes"],
#     "3A": ["IA", "Securite", "Web"],
# }
#
# for group_name, group_courses in student_groups.items():
#     for c1, c2 in combinations(group_courses, 2):
#         model.add(course_slot[c1] != course_slot[c2])

print("Exercice 3 : a completer")

Exercice 3 : a completer

---

Recapitulatif

Resume des approches

Approche	Principe	Forces	Faiblesses
Heuristique gloutonne	Tri par contrainte + premier disponible	Rapide, simple a implementer	Pas d’optimalite, peut echouer
CP-SAT (OR-Tools)	Variables + contraintes + objectif	Complet, optimal, flexible	Modelisation plus complexe
MiniZinc	Modelisation declarative	Concis, lisible, multi-solveurs	Necessite installation externe

Lecons cles

1. Separation dur/souple : les contraintes dures definissent la faisabilite, les souples la qualite
2. Modelisation > algorithme : bien modeliser le problème est souvent plus important que le choix de l’algorithme
3. Solveurs industriels : CP-SAT peut traiter des instances avec des centaines de cours en quelques secondes
4. Declaratif vs imperatif : MiniZinc permet de prototyper rapidement, CP-SAT s’integre mieux dans une application

Applications reelles

Contexte	Echelle typique	Solveur utilise
Universite (departement)	50-200 cours, 20-50 salles	CP-SAT, Gurobi
Universite (campus)	500-2000 cours	Solveurs commerciaux (UniTime)
École primaire	20-30 cours	CP-SAT suffit largement
Hopital (planning équipes)	100+ employes	Variante du nurse scheduling

Pour aller plus loin

• App-3 NurseScheduling : planification similaire dans le domaine medical
• App-4 JobShopScheduling : ordonnancement avec precedences
• App-8 MiniZinc : modelisation declarative approfondie

References

• Lewis, R. A Guide to Graph Colouring: Algorithms and Applications, Springer, 2021
• Schaerf, A. A Survey of Automated Timetabling, Artificial Intelligence Review, 1999
• Google OR-Tools : https://developers.google.com/optimization
• MiniZinc : https://www.minizinc.org/