CSP-4-Scheduling-CSharp : Problèmes d’Ordonnancement avec OR-Tools CP-SAT natif .NET

Navigation : << CSP-3-Advanced | Index | CSP-5-Optimization >>

Durée estimée : ~1h30 | Prérequis : CSP-3-Advanced, Sudoku-00-Environment-CSharp

Objectifs d’apprentissage

À la fin de ce notebook, vous saurez : 1. Modéliser un problème d’ordonnancement industriel (JSSP, RCPSP, Nurse) avec OR-Tools CP-SAT en C#/.NET 2. Utiliser les contraintes globales CP-SAT (AddNoOverlap, AddCumulative, AddMaxEquality) depuis le binding NuGet officiel 3. Comparer les deux bindings du même moteur (pip ortools côté Python, NuGet Google.OrTools côté .NET) sur les mêmes instances 4. Exploiter le solveur natif sans bridge : CP-SAT expose nativement IntervalVar/NoOverlap/Cumulative, terrain où il brille pour l’ordonnancement (design option b, #4956)

Pourquoi ce notebook ?

Le notebook CSP-4-Scheduling.ipynb (version Python) présente le JSSP, le RCPSP et le Nurse Scheduling avec OR-Tools CP-SAT (pip ortools). Ce binôme .NET reprend les trois mêmes problèmes avec le même moteur via son binding officiel NuGet Google.OrTools : même cœur C++, mêmes contraintes globales, API idiomatique .NET. Objectif : démontrer la parité Python/.NET de la série CSP (cf. epic #4956) — ici au niveau le plus fort du registre de parité, native-both : les deux jumeaux invoquent le solveur natif de leur écosystème.

La route Choco-solver (Java) via IKVM reste démontrée dans la série : Sudoku-11-Choco-CSharp.ipynb et les binômes CSP-1/2/3/5/7.

Ancres savantes – Brucker, P. (2007), Scheduling Algorithms (5e éd.), Springer (job-shop scheduling et ordonnancements à contraintes de ressources) ; Herroelen, W., De Reyck, B. & Demeulemeester, E. (1998), Resource-Constrained Project Scheduling: A Survey of Recent Developments, Computers & Opérations Research 25(4):279-302 (RCPSP, méthodes exactes et heuristiques) ; Burke, E.K. et al. (2004), The State of the Art of Nurse Rostering, Journal of Scheduling 7(6):441-499 (survey de référence sur le Nurse Scheduling Problem).

// Configuration du répertoire de travail
// Recherche le répertoire Part2-CSP depuis le cwd, ou remonte dans l'arborescence
using System;
using System.IO;

string FindCspDir()
{
    var dir = new DirectoryInfo(Directory.GetCurrentDirectory());
    while (dir != null)
    {
        // Check if we're in Part2-CSP directory
        if (File.Exists(Path.Combine(dir.FullName, "CSP-1-Fundamentals.ipynb")))
            return dir.FullName;
        // Check if Part2-CSP is a subdirectory
        var candidate = Path.Combine(dir.FullName, "MyIA.AI.Notebooks", "Search", "Part2-CSP");
        if (Directory.Exists(candidate) && File.Exists(Path.Combine(candidate, "CSP-1-Fundamentals.ipynb")))
            return candidate;
        dir = dir.Parent;
    }
    return Directory.GetCurrentDirectory();
}

var cspDir = FindCspDir();
Directory.SetCurrentDirectory(cspDir);
Console.WriteLine($"Répertoire de travail: {Path.GetFileName(cspDir.TrimEnd(Path.DirectorySeparatorChar, Path.AltDirectorySeparatorChar))}");

Répertoire de travail: Part2-CSP

Choix du solveur : OR-Tools CP-SAT natif .NET (design option b)

Approche : binding officiel NuGet, sans bridge

Le solveur est chargé via le package officiel Google.OrTools (Apache-2.0, maintenu par Google) : - #r "nuget: Google.OrTools" : bindings .NET du moteur C++ CP-SAT - Aucun bridge d’exécution (pas d’IKVM, pas de PythonNet) : le moteur s’exécute nativement dans le process .NET

Pourquoi CP-SAT natif pour l’ordonnancement

Le scheduling (IntervalVar, NoOverlap, Cumulative) est natif en CP-SAT : c’est le terrain où OR-Tools brille pour l’ordonnancement (design option b, #4956). La route alternative — Choco-solver (Java) via IKVM — est démontrée dans les binômes CSP-1/2/3/5/7 de cette même série et dans Sudoku-11-Choco-CSharp : les deux sont des moteurs SOTA réels, le choix est documenté par binôme dans le registre de parité.

Configuration OR-Tools CP-SAT (solveur natif .NET)

// Configuration OR-Tools CP-SAT (solveur natif .NET, NuGet -- pas de bridge IKVM)
// Le scheduling (IntervalVar / NoOverlap / Cumulative) est natif en CP-SAT :
// c'est le terrain ou OR-Tools brille pour l'ordonnancement (design option b #4956).
#r "nuget: Google.OrTools"
using Google.OrTools.Sat;
Console.WriteLine("OR-Tools CP-SAT charge (Google.OrTools natif .NET)");

OR-Tools CP-SAT charge (Google.OrTools natif .NET)

1. Job-Shop Scheduling Problem (JSSP) avec OR-Tools CP-SAT

Le JSSP est un problème classique d’ordonnancement : - n jobs à traiter sur m machines - Chaque job = séquence d’opérations (machine, durée) - Précédence : les opérations d’un job sont ordonnées - Disjonction : une machine traite au plus une opération à la fois - Objectif : minimiser le makespan (fin de la dernière opération)

Modélisation OR-Tools CP-SAT

• IntVar start/end liés par NewIntervalVar(s, durée, e) : une plage par opération
• cp.AddNoOverlap(intervalList) par machine : contrainte globale de disjonction (équivalent exact du noOverlap Choco)
• cp.Add(end[o] <= start[o+1]) : précédence entre opérations d’un même job (opérateurs linéaires surchargés)
• cp.AddMaxEquality(makespan, lastEnds) + cp.Minimize(makespan) : objectif de minimisation du makespan

using Google.OrTools.Sat;
// Exemple resolu : JSSP 3 jobs x 3 machines (CP-SAT natif, optimal = 11 unites)
//   Job 0 : M0(3u) -> M1(2u) -> M2(2u)
//   Job 1 : M0(2u) -> M2(1u) -> M1(4u)
//   Job 2 : M1(4u) -> M2(3u)
//   Objectif : minimiser le makespan. Optimal connu : 11 unites (cf. CSP-4-Scheduling.ipynb).
int[][][] jobsData = new int[3][][];
jobsData[0] = new int[][] { new[]{0,3}, new[]{1,2}, new[]{2,2} };
jobsData[1] = new int[][] { new[]{0,2}, new[]{2,1}, new[]{1,4} };
jobsData[2] = new int[][] { new[]{1,4}, new[]{2,3} };

int horizon = 0;
foreach (var j in jobsData) foreach (var op in j) horizon += op[1];

var cp = new CpModel();
var starts = new System.Collections.Generic.Dictionary<(int,int),IntVar>();
var ends = new System.Collections.Generic.Dictionary<(int,int),IntVar>();
var machineToIntervals = new System.Collections.Generic.Dictionary<int,System.Collections.Generic.List<IntervalVar>>();

// Variables : pour chaque operation (job, opIdx) un intervalle [start, start+dur, end]
for (int j = 0; j < jobsData.Length; j++) {
    for (int o = 0; o < jobsData[j].Length; o++) {
        int m = jobsData[j][o][0], dur = jobsData[j][o][1];
        var s = cp.NewIntVar(0, horizon, $"s_{j}_{o}");
        var e = cp.NewIntVar(0, horizon, $"e_{j}_{o}");
        var iv = cp.NewIntervalVar(s, dur, e, $"i_{j}_{o}");
        starts[(j, o)] = s; ends[(j, o)] = e;
        if (!machineToIntervals.ContainsKey(m)) machineToIntervals[m] = new System.Collections.Generic.List<IntervalVar>();
        machineToIntervals[m].Add(iv);
    }
}

// Contrainte 1 : precedence intra-job (op(o+1) commence apres fin de op(o))
for (int j = 0; j < jobsData.Length; j++)
    for (int o = 0; o < jobsData[j].Length - 1; o++)
        cp.Add(ends[(j, o)] <= starts[(j, o + 1)]);

// Contrainte 2 : disjonction par machine (AddNoOverlap natif CP-SAT)
foreach (var kvp in machineToIntervals)
    cp.AddNoOverlap(kvp.Value);

// Objectif : minimiser le makespan = max(dernieres fins de chaque job)
var makespan = cp.NewIntVar(0, horizon, "makespan");
var lastEnds = new System.Collections.Generic.List<LinearExpr>();
for (int j = 0; j < jobsData.Length; j++)
    lastEnds.Add(ends[(j, jobsData[j].Length - 1)]);
cp.AddMaxEquality(makespan, lastEnds);
cp.Minimize(makespan);

var solver = new CpSolver();
var status = solver.Solve(cp);

Console.WriteLine($"JSSP : Statut = {status}");
if (status == CpSolverStatus.Optimal) {
    Console.WriteLine($"JSSP : Makespan optimal = {solver.Value(makespan)} unites");
    Console.WriteLine();
    Console.WriteLine("Schedule detaille :");
    for (int j = 0; j < jobsData.Length; j++)
        for (int o = 0; o < jobsData[j].Length; o++)
            Console.WriteLine($"  Job {j} Op {o} : M{jobsData[j][o][0]} [{solver.Value(starts[(j,o)])}->{solver.Value(ends[(j,o)])}] (duree {jobsData[j][o][1]})");
} else {
    Console.WriteLine("JSSP : Pas de solution optimale trouvee.");
}

JSSP : Statut = Optimal
JSSP : Makespan optimal = 11 unites

Schedule detaille :
  Job 0 Op 0 : M0 [0->3] (duree 3)
  Job 0 Op 1 : M1 [4->6] (duree 2)
  Job 0 Op 2 : M2 [9->11] (duree 2)
  Job 1 Op 0 : M0 [3->5] (duree 2)
  Job 1 Op 1 : M2 [5->6] (duree 1)
  Job 1 Op 2 : M1 [6->10] (duree 4)
  Job 2 Op 0 : M1 [0->4] (duree 4)
  Job 2 Op 1 : M2 [6->9] (duree 3)

Lecture du planning JSSP (cellule ci-dessus) :

Le solveur confirme le makespan optimal = 11 unités annoncé en tête de cellule, et le planning détaillé permet de lire pourquoi 11 :

• M1 est la machine goulot : elle enchaîne Job 2 [0→4], Job 0 [4→6] puis Job 1 [6→10], soit 10 unités de charge sur 11 — une seule unité d’inactivité, en fin d’horizon. M0 (charge 5) et M2 (charge 6) sont largement sous-utilisées.
• Les chaînes de jobs ne suffisent pas à expliquer l’optimum : chaque job somme à 7 unités (3+2+2, 2+1+4, 4+3) — la borne « chaîne » vaut 7, la borne « charge machine » vaut 10 (M1). L’optimum 11 dépasse ces deux bornes prises séparément : c’est leur interaction qui le fixe.
• L’unité décisive se lit sur M2 : la dernière opération de Job 0 (M2, 2 u) ne peut démarrer ni avant la fin de Job 0 Op 1 (t = 6), ni avant la libération de M2 — occupée par Job 1 Op 1 [5→6] puis Job 2 Op 1 [6→9]. D’où le créneau [9→11], et le makespan 11.

C’est exactement le rôle d’une contrainte globale AddNoOverlap : le solveur raisonne nativement sur les disjonctions par machine (paires d’intervalles), là où une modélisation naïve énumérerait O(n²) inégalités binaires par machine.

2. Resource-Constrained Project Scheduling (RCPSP) avec OR-Tools CP-SAT

Le RCPSP généralise le JSSP : - Tâches avec durées et prédécesseurs - Ressources renouvelables avec capacité limitée (personnel, machines) - Contrainte cumulative : la consommation totale à tout instant ≤ capacité

Modélisation OR-Tools CP-SAT

• NewIntervalVar(s, durée, e) pour chaque tâche (durée fixée)
• Précédence : cp.Add(s[t] >= e[pred])
• Cumulative : cp.AddCumulative(capacity).AddDemands(intervals, demands) — la forme builder fluent du binding .NET (le binding Python prend les mêmes arguments en liste) ; c’est la contrainte globale de cumul, bien plus efficace que d’écrire toutes les paires
• Objectif : cp.AddMaxEquality(makespan, ends) + cp.Minimize(makespan) (idem JSSP)

using Google.OrTools.Sat;
// Exemple resolu : RCPSP 6 taches, 2 ressources (R0 cap=4, R1 cap=3) (CP-SAT, optimal = 10)
//   T0 (2u,pred=[])   R0:2 R1:1
//   T1 (3u,pred=[0])  R0:1 R1:2
//   T2 (4u,pred=[0])  R0:3 R1:0
//   T3 (2u,pred=[1])  R0:0 R1:2
//   T4 (3u,pred=[2])  R0:1 R1:1
//   T5 (1u,pred=[3,4])R0:2 R1:0
int numTasks = 6;
int[] durations = { 2, 3, 4, 2, 3, 1 };
int[][] predecessors = { new int[0], new[]{0}, new[]{0}, new[]{1}, new[]{2}, new[]{3,4} };
int[][] resourceNeeds = { new[]{2,1}, new[]{1,2}, new[]{3,0}, new[]{0,2}, new[]{1,1}, new[]{2,0} };
int[] capacities = { 4, 3 };
int horizonRcpsp = 20;

var cp2 = new CpModel();
var s2 = new IntVar[numTasks];
var e2 = new IntVar[numTasks];
var iv2 = new IntervalVar[numTasks];
for (int t = 0; t < numTasks; t++) {
    s2[t] = cp2.NewIntVar(0, horizonRcpsp, $"s_{t}");
    e2[t] = cp2.NewIntVar(0, horizonRcpsp, $"e_{t}");
    iv2[t] = cp2.NewIntervalVar(s2[t], durations[t], e2[t], $"i_{t}");
}

// Precedences
for (int t = 0; t < numTasks; t++)
    foreach (int pred in predecessors[t])
        cp2.Add(s2[t] >= e2[pred]);

// Contraintes cumulatives par ressource (AddCumulative natif CP-SAT)
for (int r = 0; r < capacities.Length; r++) {
    var ivs = new System.Collections.Generic.List<IntervalVar>();
    var demands = new System.Collections.Generic.List<long>();
    for (int t = 0; t < numTasks; t++) {
        int need = resourceNeeds[t][r];
        if (need > 0) { ivs.Add(iv2[t]); demands.Add(need); }
    }
    // API moderne CP-SAT : AddCumulative(capacity) retourne un builder fluent
if (ivs.Count > 0) cp2.AddCumulative((long)capacities[r]).AddDemands(ivs, demands);
}

// Objectif : minimiser le makespan
var makespan2 = cp2.NewIntVar(0, horizonRcpsp, "makespan_rcpsp");
cp2.AddMaxEquality(makespan2, e2);
cp2.Minimize(makespan2);

var solver2 = new CpSolver();
var status2 = solver2.Solve(cp2);
Console.WriteLine($"RCPSP : Statut = {status2}");
if (status2 == CpSolverStatus.Optimal) {
    Console.WriteLine($"RCPSP : Makespan optimal = {solver2.Value(makespan2)} unites");
    Console.WriteLine();
    Console.WriteLine("Schedule detaille :");
    for (int t = 0; t < numTasks; t++)
        Console.WriteLine($"  Tache {t} : [{solver2.Value(s2[t])}->{solver2.Value(e2[t])}] (duree {durations[t]})");
} else {
    Console.WriteLine("RCPSP : Pas de solution optimale trouvee.");
}

RCPSP : Statut = Optimal
RCPSP : Makespan optimal = 10 unites

Schedule detaille :
  Tache 0 : [0->2] (duree 2)
  Tache 1 : [2->5] (duree 3)
  Tache 2 : [2->6] (duree 4)
  Tache 3 : [5->7] (duree 2)
  Tache 4 : [6->9] (duree 3)
  Tache 5 : [9->10] (duree 1)

Lecture du planning RCPSP (cellule ci-dessus) :

Le makespan optimal = 10 unités se lit comme la longueur du chemin de précédence critique : T0 [0→2] → T2 [2→6] → T4 [6→9] → T5 [9→10] cumule exactement 2 + 4 + 3 + 1 = 10 unités. Aucun planning ne peut raccourcir cette chaîne : 10 est une borne inférieure atteinte — l’instance est contrainte par les précédences, pas par les ressources.

Les deux tâches hors chemin critique vivent dans la marge : T1 [2→5] se glisse en parallèle de T2, et T3 [5→7] démarre dès la fin de son prédécesseur T1. Le détail fin : sur la fenêtre [2→5], la ressource R0 est exactement saturée (T1 consomme 1, T2 consomme 3, capacité 4) — le couplage précédence × ressource est visible dans la sortie, sans pour autant allonger le makespan au-delà du chemin critique.

C’est la lisibilité propre au RCPSP : la contrainte globale AddCumulative (cumul par instant) laisse le raisonnement chronologique au premier plan, et le builder fluent AddCumulative(capacity).AddDemands(intervals, demands) exprime chaque ressource en une seule ligne.

3. Nurse Scheduling Problem avec OR-Tools CP-SAT

Le Nurse Scheduling affecte n infirmiers sur d jours à p postes (matin, après-midi, nuit) : - Couverture : au moins k infirmiers par poste - Unicité : un infirmier n’a qu’un poste par jour - Charge : entre min_shifts et max_shifts par infirmier sur la période

Modélisation OR-Tools CP-SAT

• BoolVar x[n, d, s] : 1 si infirmier n travaille le jour d au poste s
• cp.Add(LinearExpr.Sum(vars) >= k) : contrainte de couverture par poste
• cp.Add(LinearExpr.Sum(vars) <= 1) : unicité journalière
• Charge : cp.Add(LinearExpr.Sum(perNurse) <= maxShifts) par infirmier
• Objectif : cp.Add(total == LinearExpr.Sum(all)) + cp.Minimize(total) (couverture minimale exacte)

using Google.OrTools.Sat;
// Exemple resolu : Nurse Scheduling - 6 infirmiers x 7 jours x 3 postes (CP-SAT)
//   min_nurses_per_shift = 2, max_shifts_per_nurse = 7
//   Optimal connu : 42 shifts assignes (= 2 x 7 x 3, couverture minimale exacte)
int numNurses = 6;
int numDays = 7;
int shiftsPerDay = 3;
int minNursesPerShift = 2;
int maxShiftsPerNurse = 7;

var cp3 = new CpModel();
// x[n,d,s] booleen : 1 si l'infirmier n travaille le jour d au poste s
var x = new BoolVar[numNurses, numDays, shiftsPerDay];
for (int n = 0; n < numNurses; n++)
    for (int d = 0; d < numDays; d++)
        for (int s = 0; s < shiftsPerDay; s++)
            x[n, d, s] = cp3.NewBoolVar($"x_{n}_{d}_{s}");

// Contrainte 1 : couverture minimale par poste (>= minNursesPerShift par (d, s))
for (int d = 0; d < numDays; d++)
    for (int s = 0; s < shiftsPerDay; s++) {
        var perShift = new System.Collections.Generic.List<LinearExpr>();
        for (int n = 0; n < numNurses; n++) perShift.Add(x[n, d, s]);
        cp3.Add(LinearExpr.Sum(perShift) >= minNursesPerShift);
    }

// Contrainte 2 : au plus un poste par infirmier par jour
for (int n = 0; n < numNurses; n++)
    for (int d = 0; d < numDays; d++) {
        var perDay = new System.Collections.Generic.List<LinearExpr>();
        for (int s = 0; s < shiftsPerDay; s++) perDay.Add(x[n, d, s]);
        cp3.Add(LinearExpr.Sum(perDay) <= 1);
    }

// Contrainte 3 : au plus maxShiftsPerNurse sur toute la periode
for (int n = 0; n < numNurses; n++) {
    var perNurse = new System.Collections.Generic.List<LinearExpr>();
    for (int d = 0; d < numDays; d++)
        for (int s = 0; s < shiftsPerDay; s++) perNurse.Add(x[n, d, s]);
    cp3.Add(LinearExpr.Sum(perNurse) <= maxShiftsPerNurse);
}

// Objectif : minimiser le nombre total de shifts (couverture minimale exacte)
var totalShifts = cp3.NewIntVar(0, numNurses * numDays * shiftsPerDay, "total");
var allX = new System.Collections.Generic.List<LinearExpr>();
for (int n = 0; n < numNurses; n++)
    for (int d = 0; d < numDays; d++)
        for (int s = 0; s < shiftsPerDay; s++) allX.Add(x[n, d, s]);
cp3.Add(totalShifts == LinearExpr.Sum(allX));
cp3.Minimize(totalShifts);

var solver3 = new CpSolver();
var status3 = solver3.Solve(cp3);
Console.WriteLine($"Nurse : Statut = {status3}");
if (status3 == CpSolverStatus.Optimal) {
    Console.WriteLine($"Nurse : Shifts assignes = {solver3.Value(totalShifts)} (optimum = couverture minimale)");
    Console.WriteLine();
    Console.WriteLine("Planning (jour / poste : infirmiers) :");
    for (int d = 0; d < numDays; d++) {
        string line = $"  J{d} : ";
        for (int s = 0; s < shiftsPerDay; s++) {
            var assigned = new System.Collections.Generic.List<int>();
            for (int n = 0; n < numNurses; n++) if (solver3.Value(x[n, d, s]) == 1) assigned.Add(n);
            line += $"P{s}=[{string.Join(",", assigned)}] ";
        }
        Console.WriteLine(line);
    }
} else {
    Console.WriteLine("Nurse : Pas de solution optimale trouvee.");
}

Nurse : Statut = Optimal
Nurse : Shifts assignes = 42 (optimum = couverture minimale)

Planning (jour / poste : infirmiers) :
  J0 : P0=[3,5] P1=[1,4] P2=[0,2] 
  J1 : P0=[0,3] P1=[1,5] P2=[2,4] 
  J2 : P0=[1,2] P1=[4,5] P2=[0,3] 
  J3 : P0=[1,3] P1=[2,4] P2=[0,5] 
  J4 : P0=[3,4] P1=[0,2] P2=[1,5] 
  J5 : P0=[0,1] P1=[3,4] P2=[2,5] 
  J6 : P0=[0,4] P1=[1,3] P2=[2,5] 

Lecture du planning Nurse (cellule ci-dessus) :

L’optimum 42 shifts est une double saturation que la sortie rend vérifiable :

• Côté demande : 7 jours × 3 postes × 2 infirmiers (le plancher de couverture) = 42. Chaque créneau du planning affiche exactement 2 infirmiers, jamais 3 — le plancher est serré partout.
• Côté offre : 6 infirmiers × 7 shifts (le plafond de charge) = 42. En comptant les affectations par infirmier dans la sortie, chacun travaille exactement 7 shifts — aucun à 6, aucun à 5. Charge totale = capacité totale : le solveur n’a aucune marge.

L’unicité journalière se vérifie de même : chaque jour, chaque infirmier n’apparaît que sur un seul poste. Minimiser le total de shifts sous un plancher de couverture revient ici à serrer simultanément les deux bornes — c’est pourquoi Minimize(total) trouve 42, et pas un shift de plus.

Note de modélisation : le modèle n’impose pas d’équité entre infirmiers au-delà du plafond — l’exercice 3 ci-dessous introduit précisément un plancher individuel (min_shifts = 6) et une contrainte de jours consécutifs pour durcir cet aspect.

4. Comparaison des deux bindings d’OR-Tools CP-SAT (pip Python vs NuGet .NET)

Les deux jumeaux de cette paire invoquent le même moteur — le cœur C++ CP-SAT — via les bindings officiels de leurs écosystèmes respectifs. La comparaison se joue au niveau du binding, pas du solveur :

Aspect	Python (pip install ortools)	C#/.NET (#r "nuget: Google.OrTools")
Moteur	C++ CP-SAT natif	C++ CP-SAT natif (même cœur)
Espace de noms	ortools.sat.python.cp_model	Google.OrTools.Sat
Variables	NewIntVar, NewIntervalVar, NewBoolVar	NewIntVar, NewIntervalVar, NewBoolVar (noms identiques)
Contraintes globales	AddNoOverlap, AddCumulative(list, capacity)	AddNoOverlap, AddCumulative(capacity).AddDemands(...) (builder fluent)
Objectif	model.Minimize(var)	cp.Minimize(var)
Solve	solver.Solve(model)	solver.Solve(cp)
Statut	OPTIMAL / FEASIBLE / INFEASIBLE	CpSolverStatus.Optimal / Feasible / Infeasible
Sommes linéaires	sum(...) natif Python	LinearExpr.Sum(list) + LinearExpr.Constant(c)
Performance pure	État de l’art	Identique (même cœur C++)
Friction d’installation	Aucune (pip)	Aucune (NuGet, restore automatique)

Verdict : les deux bindings modélisent les mêmes problèmes (JSSP-3×3, RCPSP-6×2×2, Nurse-6×7×3) avec les mêmes contraintes globales. Les makespans optimaux = 11 / 10 / 42 sont visibles dans les outputs des sections 1, 2 et 3 ci-dessus, et correspondent exactement aux valeurs du binôme Python : c’est la parité native-both au sens du registre twin-parity (See #10382).

5. Exercices

Trois exercices pour approfondir l’usage d’OR-Tools CP-SAT. Chaque exercice étend un modèle résolu ci-dessus avec une variante réaliste.

// EXERCICE 1 : JSSP avec deadlines (variante du modèle de la cellule 6)
//
// Énoncé : Reprenez le JSSP 3 jobs × 3 machines de la cellule 6 et ajoutez une
// **deadline** (date de fin au plus tard) pour chaque job : Job 0 ≤ 10, Job 1 ≤ 12, Job 2 ≤ 8.
// Minimisez le **retard maximal** (max_lateness = max(0, completion - deadline)).
//
// Indice :
//   1. Pour chaque job, créez une variable IntVar lateness[j] (0..horizon).
//   2. Ajoutez la contrainte linéaire : lateness[j] + deadlines[j] >= end[lastOpOfJob(j)]
//      (en CP-SAT .NET : cp.Add(lateness[j] + deadlines[j] >= ends[(j, lastOp)]) — opérateurs surchargés).
//   3. Créez une variable maxLateness (0..horizon) et liez-la : cp.AddMaxEquality(maxLateness, lateness[0..2]).
//   4. Minimisez maxLateness via cp.Minimize(maxLateness).
//
// Données :
//   int[] deadlines = { 10, 12, 8 };
//   jobsData, horizon identiques à la cellule 6.

// Votre code ici
Console.WriteLine("Exercice à compléter");

Exercice à compléter

// EXERCICE 2 : RCPSP avec budget (variante du modèle de la cellule 8)
//
// Énoncé : Étendez le RCPSP de la cellule 8 avec une **ressource non-renouvelable** :
// budget = 14 unités. Chaque tâche a un coût (3, 2, 4, 1, 2, 1 respectivement) ;
// la somme des coûts des tâches doit rester ≤ 14. Le makespan reste à minimiser.
//
// Indice :
//   1. Pour la ressource non-renouvelable, ce n'est PAS une AddCumulative (qui est temporelle).
//      C'est une simple contrainte de somme : la somme des coûts des tâches <= budget.
//   2. Construisez les termes constants : var costTerms = costs.Select(c => LinearExpr.Constant(c)).ToList();
//      puis liez-les : var sumCost = cp2.NewIntVar(0, 100, "sum_cost");
//      cp2.Add(sumCost == LinearExpr.Sum(costTerms)); cp2.Add(sumCost <= budget);
//   3. Vérifiez que la somme des coûts (3+2+4+1+2+1 = 13) est ≤ 14 : instance faisable.
//
// Données :
//   int[] costs = { 3, 2, 4, 1, 2, 1 };  // somme = 13, budget = 14 → 1 unité de marge
//   int budget = 14;
//   Reste des paramètres identique à la cellule 8.

// Votre code ici
Console.WriteLine("Exercice à compléter");

Exercice à compléter

// EXERCICE 3 : Nurse Scheduling avec équilibrage de charge (variante cellule 10)
//
// Énoncé : Modifiez le modèle Nurse de la cellule 10 pour imposer un **équilibrage strict** :
//   1. Chaque infirmier doit travailler **au moins 6 shifts** sur la semaine (min_shifts = 6).
//   2. Pas plus de **5 jours consécutifs** travaillés (contrainte supplémentaire).
//   3. Continuez à minimiser le total des shifts (= 42 = couverture exacte, comme la cellule 10).
//
// Indice pour la contrainte "5 jours consécutifs" :
//   Pour chaque infirmier n et chaque jour d de 0 à 2 (= 7-5) :
//     sum(x[n, d..d+4, 0..2]) <= 5
//   Cela force "pas plus de 5 jours travaillés d'affilée".
//
// Données :
//   int minShifts = 6;
//   Reste identique à la cellule 10.

// Votre code ici
Console.WriteLine("Exercice à compléter");

Exercice à compléter

Conclusion

Ce notebook a démontré la parité Python/.NET sur trois problèmes d’ordonnancement industriel classiques — au niveau le plus fort du registre de parité, native-both : les deux jumeaux invoquent le même moteur (OR-Tools CP-SAT) via le binding natif de leur écosystème.

Problème	Modélisation CP-SAT	Makespan (identique des deux jumeaux)
JSSP 3×3	AddNoOverlap par machine + précédence intra-job	11
RCPSP 6×2	AddCumulative par ressource + précédence	10
Nurse 6×7×3	BoolVar + LinearExpr.Sum (>=, <=)	42 (couverture exacte)

Points clés à retenir

1. Binding NuGet natif : #r "nuget: Google.OrTools" charge le moteur C++ CP-SAT et ses bindings .NET officiels — sans bridge d’exécution (design option b, #4956).
2. Contraintes globales : AddNoOverlap et AddCumulative(capacity).AddDemands(...) (builder fluent) sont les primitives d’ordonnancement natives de CP-SAT.
3. Objectif : cp.AddMaxEquality(makespan, ends) puis cp.Minimize(makespan).
4. Sommes linéaires : LinearExpr.Sum(list) et LinearExpr.Constant(c) remplacent le sum(...) natif Python.
5. Convergence des jumeaux : makespans optimaux 11/10/42 identiques au binôme Python — même moteur, même optimal, deux écosystèmes.
6. Route alternative vivante : la même série démontre Choco-solver (Java) via IKVM dans les binômes CSP-1/2/3/5/7 et Sudoku-11-Choco-CSharp.

Voir aussi

• CSP-4-Scheduling.ipynb — jumeau Python (OR-Tools CP-SAT, pip)
• Sudoku-11-Choco-CSharp.ipynb — la route Choco-solver via IKVM
• EPIC #4956 — parité .NET ⇄ Python des séries de notebooks