Optimisation et ordonnancement¶

Allouer des ressources limitees a des tâches concurrentes est un problème d'optimisation — et la plupart des outils que vous utilisez en resolvant des instances concrètes chaque seconde.

Programmation lineaire¶

La programmation lineaire (PL) résout des problèmes ou il faut maximiser (ou minimiser) une fonction objectif lineaire sous des contraintes lineaires. C'est l'un des outils les plus utilisés en opérations research, de la logistique au capacity planning.

Formulation standard¶

Un problème de PL se décrit par :

• Variables de décision : les quantites a déterminer
• Fonction objectif : ce qu'on veut maximiser ou minimiser
• Contraintes : les limites sur les variables

Exemple concret — allocation de capacité :

Un datacenter a deux types de serveurs (A et B). Le type A consomme 200W et généré 500€ de revenue/heure. Le type B consomme 150W et généré 350€/heure. Budget électrique : 10 000W. Contrats : au moins 20 serveurs A et 10 serveurs B. Objectif : maximiser le revenue.

Maximiser :  500 * x_A + 350 * x_B

Sous :
  200 * x_A + 150 * x_B <= 10 000   (contrainte electrique)
  x_A >= 20                          (contrat minimum A)
  x_B >= 10                          (contrat minimum B)
  x_A, x_B >= 0                      (non-negativite)

from scipy.optimize import linprog

# linprog minimise — on minimise le negatif pour maximiser
c = [-500, -350]  # fonction objectif (negee pour maximisation)

# Contraintes d'inegalite : A_ub @ x <= b_ub
A_ub = [[200, 150]]
b_ub = [10_000]

# Bornes des variables
x_A_bounds = (20, None)   # x_A >= 20
x_B_bounds = (10, None)   # x_B >= 10

result = linprog(
    c,
    A_ub=A_ub,
    b_ub=b_ub,
    bounds=[x_A_bounds, x_B_bounds],
    method='highs'
)

print(f"x_A = {result.x[0]:.1f} serveurs A")
print(f"x_B = {result.x[1]:.1f} serveurs B")
print(f"Revenue max = {-result.fun:.0f} €/heure")
# x_A = 20.0 serveurs A
# x_B = 36.7 serveurs B
# Revenue max = 22 833 €/heure

L'espace de solutions est un polyedre convexe (polytope).
La solution optimale est TOUJOURS sur un sommet du polytope.

Contrainte electrique
     |     (10000W max)
x_B  |   \
36.7 |.....\
     |      \
10   |-------o (x_A=20, x_B=10)  <- sommet, borne contrainte
     |       |
     +-------\------> x_A
             20  50

Le simplexe explore les sommets du polytope en partant d'un
sommet initial et en se deplacant vers le voisin ameliorant
la fonction objectif — garantit d'atteindre l'optimum global.

L'algorithme du Simplexe¶

Le simplexe (Dantzig, 1947) n'explore pas tout l'espace des solutions — il se déplacé de sommet en sommet du polytope des contraintes, toujours dans le sens d'amélioration de l'objectif. La solution optimale, si elle existe, est atteinte quand aucun voisin n'est meilleur.

Complexité : exponentielle dans le pire cas théorique, mais polynomiale en pratique pour presque tous les problèmes réels. Les solveurs modernes (HiGHS, Gurobi, CPLEX) résolvent des problèmes avec des millions de variables en quelques secondes.

Dualite¶

Chaque problème PL (le "primal") a un problème "dual" associe. La solution du dual fournit les prix duaux (shadow prices) : combien l'objectif s'ameliorerait si on relachait une contrainte d'une unite.

Dans notre exemple, le prix dual de la contrainte électrique indique de combien le revenue augmenterait si on avait 1W de plus. Cette information est directement actionnable : vaut-il la peine d'investir dans plus de capacité électrique ?

Programmation entière¶

Si les variables doivent être entières (nombre de serveurs, nombre de pods), c'est un problème de programmation entière mixte (MIP). C'est NP-hard en général. Les solveurs utilisent le branch-and-bound : résoudre le problème continu, puis brancher sur les variables fractionnaires en ajoutant des contraintes d'intégrité.

Problèmes de flot¶

Les problèmes de flot modelisent la circulation de ressources dans un réseau (graphe orienté avec capacités sur les aretes).

Flot maximal¶

Problème : dans un réseau avec des capacités sur les aretes, quel est le flot maximum qu'on peut faire passer de la source S vers le puits T ?

Théorème max-flot min-coupe (Ford-Fulkerson) : la valeur du flot maximum est egale à la capacité de la coupe minimale — l'ensemble d'aretes dont la suppression déconnecté S de T avec la capacité totale minimale.

Application directe : dimensionnement de bande passante, routing de paquets, allocation de licences logicielles.

from collections import defaultdict, deque

def max_flow(graph: dict, source: str, sink: str) -> int:
    """
    graph : {noeud: {voisin: capacite}}
    Retourne le flot maximal de source a sink.
    """
    def bfs_path(residual, src, snk):
        """Trouve un chemin augmentant par BFS."""
        visited = {src}
        queue = deque([(src, [src])])
        while queue:
            node, path = queue.popleft()
            for neighbor, cap in residual[node].items():
                if neighbor not in visited and cap > 0:
                    visited.add(neighbor)
                    new_path = path + [neighbor]
                    if neighbor == snk:
                        return new_path
                    queue.append((neighbor, new_path))
        return None

    # Construire le graphe residuel
    residual = defaultdict(lambda: defaultdict(int))
    for u, edges in graph.items():
        for v, cap in edges.items():
            residual[u][v] += cap

    total_flow = 0
    while path := bfs_path(residual, source, sink):
        # Capacite du chemin = minimum des capacites residuelles
        flow = min(residual[path[i]][path[i+1]] for i in range(len(path)-1))
        # Mettre a jour le graphe residuel
        for i in range(len(path)-1):
            residual[path[i]][path[i+1]] -= flow
            residual[path[i+1]][path[i]] += flow
        total_flow += flow

    return total_flow

# Exemple : datacenter avec 3 switches intermediaires
network = {
    "source": {"sw1": 10, "sw2": 8},
    "sw1": {"sw3": 6, "sink": 5},
    "sw2": {"sw3": 9, "sink": 4},
    "sw3": {"sink": 12},
    "sink": {}
}
print(max_flow(network, "source", "sink"))  # -> 16

Flot a coût minimal¶

Variante ou chaque arete a une capacité ET un coût. On cherche à faire passer un flot donne en minimisant le coût total. Modélisé : routage de trafic avec des liens de coût variable, acheminement de marchandises, affectation de tâches a des machines avec des coûts différents.

Problème d'affectation¶

Cas special du flot a coût minimal : affecter N travailleurs a N tâches pour minimiser le coût total. L'algorithme hongrois résout ce problème en O(n³).

from scipy.optimize import linear_sum_assignment
import numpy as np

# Matrice de cout : cout[i][j] = cout d'affecter worker i a task j
cout = np.array([
    [4, 1, 3],   # worker-0 : cout 4 sur task-0, 1 sur task-1, 3 sur task-2
    [2, 0, 5],   # worker-1
    [3, 2, 2],   # worker-2
])

row_ind, col_ind = linear_sum_assignment(cout)
print("Affectations optimales :")
for w, t in zip(row_ind, col_ind):
    print(f"  worker-{w} -> task-{t} (cout: {cout[w, t]})")
print(f"Cout total : {cout[row_ind, col_ind].sum()}")
# worker-0 -> task-1 (cout: 1)
# worker-1 -> task-0 (cout: 2)
# worker-2 -> task-2 (cout: 2)
# Cout total : 5

Ordonnancement de tâches¶

L'ordonnancement (scheduling) décidé quel tâche s'exécuté quand, sur quelle ressource, dans quel ordre — pour maximiser l'utilisation, minimiser la latence, ou respecter des deadlines.

Modèles de tâches¶

Jobs indépendants : chaque tâche a une durée et optionnellement une deadline. Pas de dépendances entre tâches.

Jobs avec dépendances (DAG) : certaines tâches doivent être completees avant que d'autres puissent démarrer. Modélisé par un graphe orienté acyclique (DAG) — le modèle de MapReduce, Spark, et les pipelines CI/CD.

Earliest Deadline First (EDF)¶

EDF est optimal pour les systèmes temps-réel preemptifs : à tout instant, on exécuté la tâche avec la deadline la plus proche. Si EDF échoué (une deadline est ratee), aucun autre algorithme ne peut réussir avec ce jeu de tâches.

import heapq
from dataclasses import dataclass, field

@dataclass(order=True)
class Task:
    deadline: float
    task_id: str = field(compare=False)
    duration: float = field(compare=False)

def edf_schedule(tasks: list[Task], now: float = 0) -> list[tuple]:
    """
    Retourne l'ordre EDF optimal.
    Suppose que toutes les taches sont disponibles immediatement.
    """
    heap = list(tasks)
    heapq.heapify(heap)   # min-heap sur deadline
    schedule = []
    current = now

    while heap:
        task = heapq.heappop(heap)
        start = current
        end = current + task.duration
        missed = end > task.deadline
        schedule.append((task.task_id, start, end, missed))
        current = end

    return schedule

tasks = [
    Task(deadline=10, task_id="T1", duration=3),
    Task(deadline=6,  task_id="T2", duration=2),
    Task(deadline=8,  task_id="T3", duration=4),
]
for task_id, start, end, missed in edf_schedule(tasks):
    status = "MISSED" if missed else "OK"
    print(f"{task_id}: [{start:.0f}, {end:.0f}] deadline={status}")
# T2: [0, 2] deadline=OK
# T3: [2, 6] deadline=OK
# T1: [6, 9] deadline=OK

Rate Monotonic Scheduling¶

Pour les systèmes temps-réel a tâches périodiques (chaque tâche T_i se répété avec une periode P_i et une durée C_i), le RMS affecte les priorités en fonction de la fréquence : la tâche la plus rapide à la priorité la plus haute.

Condition de faisabilite : un ensemble de n tâches est ordonnancable par RMS si :

Pour n grand, cette borne converge vers ln(2) ≈ 0.693. Un système dont l'utilisation CPU totale est sous 69.3% est garanti ordonnancable par RMS.

Chemin critique¶

Dans un projet avec des tâches interdependantes (DAG), le chemin critique est la sequence de tâches la plus longue — elle détermine la durée minimale du projet. Toute tâche sur le chemin critique, si elle prend du retard, retarde l'ensemble du projet.

from collections import defaultdict

def chemin_critique(tasks: dict, deps: dict) -> tuple[float, list]:
    """
    tasks : {task_id: duree}
    deps  : {task_id: [predecesseurs]}
    Retourne (duree_totale, liste_chemin_critique)
    """
    # Tri topologique + calcul earliest start
    earliest_end = {}
    topo_order = []

    def visit(t, visited=set(), stack=set()):
        if t in stack:
            raise ValueError(f"Cycle detecte autour de {t}")
        if t not in visited:
            stack.add(t)
            for pred in deps.get(t, []):
                visit(pred, visited, stack)
            stack.discard(t)
            visited.add(t)
            topo_order.append(t)

    for t in tasks:
        visit(t)

    # Calcul du earliest finish
    earliest_finish = {}
    pred_ef = {}
    for t in topo_order:
        predecessors = deps.get(t, [])
        if predecessors:
            start = max(earliest_finish[p] for p in predecessors)
            pred_ef[t] = max(predecessors, key=lambda p: earliest_finish[p])
        else:
            start = 0
            pred_ef[t] = None
        earliest_finish[t] = start + tasks[t]

    # Reconstruire le chemin critique depuis la fin
    end_task = max(earliest_finish, key=earliest_finish.get)
    path = []
    current = end_task
    while current:
        path.append(current)
        current = pred_ef[current]

    return earliest_finish[end_task], list(reversed(path))

# Pipeline de deploiement
durees = {"build": 10, "test": 8, "lint": 3, "docker": 5, "deploy": 2}
dependances = {
    "test": ["build"],
    "lint": ["build"],
    "docker": ["test"],
    "deploy": ["docker", "lint"],
}
duree, chemin = chemin_critique(durees, dependances)
print(f"Duree totale : {duree} min")
print(f"Chemin critique : {' -> '.join(chemin)}")
# Duree totale : 25 min
# Chemin critique : build -> test -> docker -> deploy

Bin Packing¶

Le bin packing consiste à ranger des objets de tailles variables dans des conteneurs de capacité fixe en minimisant le nombre de conteneurs utilisés. C'est un problème NP-hard.

Analogie directe avec l'infrastructure : placer des pods Kubernetes sur des nœuds, affecter des VMs a des hôtes physiques, scheduler des jobs batch sur des machines.

Heuristiques classiques¶

def first_fit_decreasing(items: list[float], capacity: float) -> list[list[float]]:
    """
    Trie les items par taille decroissante, puis place chaque item
    dans le premier bin ou il tient.
    Garantit une solution <= (11/9) * OPT + 6/9
    """
    sorted_items = sorted(items, reverse=True)
    bins = []
    remaining = []

    for item in sorted_items:
        placed = False
        for i, rem in enumerate(remaining):
            if rem >= item:
                bins[i].append(item)
                remaining[i] -= item
                placed = True
                break
        if not placed:
            bins.append([item])
            remaining.append(capacity - item)

    return bins

# Placement de pods (demande CPU en millicores)
pods = [400, 200, 350, 150, 500, 100, 250, 300]
noeuds = first_fit_decreasing(pods, capacity=1000)

for i, noeud in enumerate(noeuds):
    util = sum(noeud)
    print(f"Noeud-{i}: {noeud} = {util}m/{1000}m ({util/10:.0f}%)")
# Noeud-0: [500, 400] = 900m/1000m (90%)
# Noeud-1: [350, 300, 200] = 850m/1000m (85%)
# Noeud-2: [250, 150, 100] = 500m/1000m (50%)

def best_fit_decreasing(items: list[float], capacity: float) -> list[list[float]]:
    """
    Trie par taille decroissante, place chaque item dans le bin
    ou il laisse le moins d'espace libre (meilleure utilisation).
    """
    sorted_items = sorted(items, reverse=True)
    bins = []
    remaining = []

    for item in sorted_items:
        best_idx = -1
        best_rem = float('inf')
        for i, rem in enumerate(remaining):
            if rem >= item and rem - item < best_rem:
                best_idx = i
                best_rem = rem - item

        if best_idx >= 0:
            bins[best_idx].append(item)
            remaining[best_idx] -= item
        else:
            bins.append([item])
            remaining.append(capacity - item)

    return bins

Comparaison des heuristiques¶

Applications en production¶

Kubernetes Scheduler¶

Le scheduler Kubernetes est essentiellement un solver de bin packing avec contraintes. Pour chaque pod a placer :

1. Filtering : éliminer les nœuds qui ne satisfont pas les contraintes obligatoires (ressources insuffisantes, taints, node affinity)
2. Scoring : classer les nœuds restants selon plusieurs critères ponderes :
   • LeastAllocated : favorise les nœuds les moins charges (spreading)
   • MostAllocated : favorise les nœuds les plus charges (bin packing serré — réduit le nombre de nœuds actifs)
   • BalancedResourceAllocation : équilibre CPU et mémoire
   • NodeAffinity, PodTopologySpread : contraintes de placement
3. Binding : affecter le pod au nœud gagnant

Le scheduler peut être configuré pour privilegier le bin packing serree (economiser des nœuds) ou le spreading (résilience aux pannes de nœuds).

Load Balancing : problème d'affectation¶

Distribuer les requêtes HTTP sur N serveurs est un problème d'ordonnancement temps-réel. Les algorithmes courants :

Le "least connections" est une approximation greedy du problème d'affectation optimal — à chaque nouvelle requête, on choisit le serveur qui minimise le temps d'attente estime.

Capacity Planning : programmation lineaire¶

Le capacity planning résout : "quel mix de types d'instances cloud minimise le coût tout en satisfaisant les SLOs de performance ?"

Variables : nombre d'instances de chaque type (m5.large, m5.xlarge, c5.2xlarge, ...) Contraintes : CPU total >= demande peak * 1.3 (marge), RAM totale >= baseline, budget \<= B Objectif : minimiser le coût horaire total

Ce problème se formule directement en PL. En pratique, des outils comme Spot.io, ParkMyCloud ou des scripts internes en scipy/PuLP résolvent ce problème quotidiennement pour optimiser les flottes cloud.

MapReduce : ordonnancement de tâches DAG¶

MapReduce ordonnance des milliers de tâches sur des centaines de machines. Le scheduler YARN (Yet Another Resource Negotiator) résout un problème d'ordonnancement avec :

• Localité des données : favoriser l'exécution d'une tâche sur le nœud qui contient ses données (éviter le transfert réseau)
• Fairness : plusieurs jobs se partagent le cluster equitablement (Fair Scheduler)
• Capacité : des queues de priorité garantissent un minimum de ressources par équipe (Capacity Scheduler)

Le chemin critique d'un job MapReduce détermine sa latence minimale — l'optimisation passe par la parallelisation maximale des tâches indépendantes.

Recapitulatif¶