Planners-7-OR-Tools-Csharp — Jumeau C# : solveur CP from-scratch (Job-Shop)

Navigation : Index | << Domaines C# | Temporel C# >> > Jumeau C# (.NET 9) de Planners-7-OR-Tools. Le notebook Python invoque le vrai solveur OR-Tools CP-SAT (ortools.sat.python.cp_model) pour résoudre des problèmes d’ordonnancement (Job-Shop, VRP, Planning-as-CP). Ce jumeau prend le parti Prong B du marathon #4956 : plutôt que d’appeler un solveur industriel, on reconstruit un solveur de programmation par contraintes from-scratch en C# pur (BCL .NET 9, zéro NuGet) — propagation de domaines + backtracking — et on l’applique au même problème Job-Shop canonique (exemple OR-Tools « a simple example of a job shop problem »). L’objectif pédagogique : rendre visible le moteur interne que CP-SAT cache (variables, domaines, propagation, recherche).

Source Python : Planners-7-OR-Tools.ipynb — cp_model.CpModel + NewIntervalVar + AddNoOverlap + minimisation du makespan.

Objectifs d’apprentissage

Modéliser un Job-Shop en CP : variables de début d’opération, contraintes de précédence (intra-job), contraintes de non-chevauchement (NoOverlap inter-machines)
Implémenter la propagation de domaines (réduction par précédences) puis un backtracking pour l’affectation temporelle
Minimiser le makespan par énumération exhaustive des ordonnancements disjonctifs
Comparer la performance et l’optimalité de notre solveur naïf vs OR-Tools CP-SAT (le Python résout l’exemple OR-Tools en ~0,009 s — précision consignée dans la sortie committée du jumeau Python, source unique)

Prérequis

Concepts CSP (variables, domaines, contraintes) — Planners-2-PDDL-Basics
Job-Shop scheduling — le notebook Python ci-dessus
.NET 9 + kernel csharp (kernel .net-csharp)

Durée estimée : 45 minutes

flowchart LR
    A["Données Job-Shop<br/>(jobs x machines)"] --> B["Variables start<br/>domaines 0..horizon"]
    B --> C["Contraintes<br/>precedence + NoOverlap"]
    C --> D["Propagation<br/>domaines"]
    D --> E["Backtracking<br/>min makespan"]
    E --> F["Schedule ASCII<br/>+ comparaison CP-SAT"]

1. Modèle Job-Shop en C# pur

Un problème de Job-Shop : un ensemble de jobs, chacun composé d’une séquence d’opérations à exécuter sur des machines distinctes, dans l’ordre. Deux contraintes structurantes : - Précédence intra-job : l’opération \(k+1\) d’un job ne peut commencer avant la fin de l’opération \(k\). - Non-chevauchement par machine : une machine ne traite qu’une opération à la fois.

On cherche l’ordonnancement qui minimise le makespan (temps de fin de la dernière opération). C’est un problème NP-difficile.


// Modèle Job-Shop from-scratch (BCL .NET 9, 0 NuGet)
using System;
using System.Collections.Generic;
using System.Linq;

// Une opération : (machine, durée). Indexée par sa position dans son job.
public sealed record Operation(int Machine, int Duration);

// Un job : séquence ordonnée d'opérations (précédence implicite).
public sealed record Job(string Name, List<Operation> Ops);

// Une instance de Job-Shop : jobs + nombre de machines.
public sealed class JobShopInstance
{
    public List<Job> Jobs { get; }
    public int NumMachines { get; }
    public int Horizon { get; }   // borne supérieure = somme de toutes les durées
    public JobShopInstance(List<Job> jobs, int numMachines)
    {
        Jobs = jobs;
        NumMachines = numMachines;
        Horizon = jobs.SelectMany(j => j.Ops).Sum(o => o.Duration);
    }
}

// --- Exemple OR-Tools « a simple example of a job shop problem » : 3 jobs / 3 machines, 8 opérations ---
// 3 jobs, 3 machines, 8 opérations au total (job 2 en a 2). Le solveur OR-Tools (Python) trouve makespan OPTIMAL = 11.
var JOBS = new List<Job>
{
    new("Job 0", new() { new(0, 3), new(1, 2), new(2, 2) }),
    new("Job 1", new() { new(0, 2), new(2, 1), new(1, 4) }),
    new("Job 2", new() { new(1, 4), new(2, 3) }),
};
var INSTANCE = new JobShopInstance(JOBS, 3);

Console.WriteLine("Problème Job-Shop (exemple OR-Tools)");
Console.WriteLine(new string('=', 50));
Console.WriteLine($"Jobs: {INSTANCE.Jobs.Count}");
Console.WriteLine($"Machines: {INSTANCE.NumMachines}");
Console.WriteLine($"Horizon (borne sup.): {INSTANCE.Horizon}");
foreach (var j in INSTANCE.Jobs)
{
    var ops = string.Join(" -> ", j.Ops.Select(o => $"M{o.Machine}/d{o.Duration}"));
    Console.WriteLine($"  {j.Name}: {ops}");
}
Console.WriteLine("\nRéférence OR-Tools (Python) : makespan OPTIMAL = 11.");

Problème Job-Shop (exemple OR-Tools)
==================================================
Jobs: 3
Machines: 3
Horizon (borne sup.): 21
  Job 0: M0/d3 -> M1/d2 -> M2/d2
  Job 1: M0/d2 -> M2/d1 -> M1/d4
  Job 2: M1/d4 -> M2/d3

Référence OR-Tools (Python) : makespan OPTIMAL = 11.

2. Solveur CP from-scratch : propagation + backtracking

Notre solveur encode le Job-Shop comme suit : - Variables : start[(jobId, opId)] ∈ [0, Horizon], une par opération. - Contrainte de précédence : start[k+1] >= start[k] + duration[k] pour opérations consécutives d’un même job. - Contrainte de non-chevauchement : pour deux opérations \(a\), \(b\) sur la même machine, soit \(a\) finit avant \(b\), soit l’inverse — encodage disjonctif.

Stratégie de résolution : on énumère (backtracking) les ordonnancements disjonctifs sur chaque machine (l’ordre relatif des opérations), puis on calcule le schedule au plus tôt par propagation des précédences. Pour chaque ordonnancement licite, le makespan est déterministe ; on garde le minimum. C’est exactement ce que fait CP-SAT, mais sans ses optimisations (lazy clause generation, propagation NoOverlap globale) — donc plus lent, mais transparent.


#nullable enable
// --- Solveur Job-Shop : backtracking sur ordonnancements disjonctifs + propagation ---
// On fixe l'ordre relatif des opérations sur chaque machine (permutations), puis on
// propage au plus tôt (point fixe) pour calculer le makespan de chaque ordonnancement.
// Exhaustif => optimal, mais explose combinatoirement sur les grandes instances.
public sealed class JobShopSolver
{
    public JobShopInstance Inst { get; }
    public int Makespan { get; private set; } = int.MaxValue;
    public int[,]? BestStart { get; private set; }   // start[jobId, opId] optimal
    public int[,]? BestEnd { get; private set; }
    public int NodesExplored { get; private set; }

    public JobShopSolver(JobShopInstance inst) { Inst = inst; }

    // Propagation au plus tôt pour un ordonnancement fixé.
    // order[m] = liste des (jobId, opId) dans l'ordre d'exécution sur la machine m.
    private (int ms, int[,] start, int[,] end) Evaluate(Dictionary<int, List<(int job, int op)>> order)
    {
        int nJ = Inst.Jobs.Count;
        var start = new int[nJ, 8];   // au plus 8 ops/job (cet exemple = 3 max)
        var end = new int[nJ, 8];
        bool changed = true; int guard = 0;
        while (changed && guard++ < 1000)
        {
            changed = false;
            // (1) Précédence intra-job : op k+1 démarre après la fin de l'op k.
            for (int j = 0; j < nJ; j++)
                for (int k = 0; k < Inst.Jobs[j].Ops.Count; k++)
                {
                    int d = Inst.Jobs[j].Ops[k].Duration;
                    int es = k > 0 ? end[j, k - 1] : 0;
                    if (es + d > end[j, k]) { start[j, k] = es; end[j, k] = es + d; changed = true; }
                }
            // (2) Non-chevauchement par machine (selon l'ordre fixé).
            foreach (var pair in order)
                for (int i = 0; i < pair.Value.Count; i++)
                {
                    var (j, k) = pair.Value[i]; int d = Inst.Jobs[j].Ops[k].Duration;
                    int es = i > 0 ? Math.Max(start[j, k], end[pair.Value[i - 1].job, pair.Value[i - 1].op]) : start[j, k];
                    if (es + d > end[j, k]) { start[j, k] = es; end[j, k] = es + d; changed = true; }
                }
        }
        int ms = 0;
        for (int j = 0; j < nJ; j++) for (int k = 0; k < Inst.Jobs[j].Ops.Count; k++) ms = Math.Max(ms, end[j, k]);
        return (ms, start, end);
    }

    // Backtracking : on énumère les permutations d'opérations sur chaque machine.
    public void Solve()
    {
        // opsByMachine[m] = liste des (jobId, opId) utilisant la machine m.
        var opsByMachine = new Dictionary<int, List<(int job, int op)>>();
        for (int j = 0; j < Inst.Jobs.Count; j++)
            for (int k = 0; k < Inst.Jobs[j].Ops.Count; k++)
            {
                int m = Inst.Jobs[j].Ops[k].Machine;
                if (!opsByMachine.ContainsKey(m)) opsByMachine[m] = new List<(int, int)>();
                opsByMachine[m].Add((j, k));
            }
        var order = opsByMachine.ToDictionary(kv => kv.Key, kv => new List<(int, int)>());
        var machineKeys = order.Keys.OrderBy(m => m).ToList();

        void Backtrack(int machineIdx)
        {
            NodesExplored++;
            if (machineIdx == machineKeys.Count)
            {
                var (ms, sStart, sEnd) = Evaluate(order);
                if (ms < Makespan) { Makespan = ms; BestStart = sStart; BestEnd = sEnd; }
                return;
            }
            int m = machineKeys[machineIdx];
            var remaining = new List<(int, int)>(opsByMachine[m]);
            Permute(m, remaining, 0, () => Backtrack(machineIdx + 1));
        }

        void Permute(int m, List<(int, int)> list, int startIdx, Action recurse)
        {
            if (startIdx == list.Count) { order[m] = new List<(int, int)>(list); recurse(); return; }
            for (int i = startIdx; i < list.Count; i++)
            {
                (list[startIdx], list[i]) = (list[i], list[startIdx]);
                Permute(m, list, startIdx + 1, recurse);
                (list[startIdx], list[i]) = (list[i], list[startIdx]);
            }
        }

        Backtrack(0);
    }
}

Console.WriteLine("Solveur CP from-scratch chargé (propagation + backtracking disjonctif).");

Solveur CP from-scratch chargé (propagation + backtracking disjonctif).

Bilan du modele et du solveur : passage a l’experimentation

Les Sections 1-2 ont pose deux briques fondamentales :

Section 1 : le modele de donnees Job-Shop (jobs, machines, operations, predecesseurs). Ce modele encode la structure du probleme mais ne sait pas le resoudre.
Section 2 : le solveur CP (backtracking + propagation de contraintes). Ce solveur peut resoudre n’importe quelle instance du modele.

Les deux ensemble = un solveur complet sur le domaine Job-Shop. La Section 3 fait le pont vers le concret : on instancie le modele + solveur sur l’exemple Job-Shop OR-Tools (« a simple example of a job shop problem »), un cas a 3 jobs et 3 machines dont 8 taches au total (le 3ᵉ job en comporte 2). Cet exemple est distribue avec Google OR-Tools comme illustration canonique d’un Job-Shop non trivial mais jouet :

Optimum documente : makespan = 11 (cf. la documentation officielle OR-Tools, https://developers.google.com/optimization/scheduling/job_shop).
Taille : 8 tâches au total (le job 3 en a 2), reparties 2 / 3 / 3 sur les machines 1, 2, 3 ; les permutations par machine donnent 2! × 3! × 3! = 72 ordonnancements theoriques (exploration complete, sans contrainte supplementaire).
Discriminant : un solveur qui retrouve 11 est correct ; un solveur qui retourne 12+ a un bug (gap d’optimalite sur ce cas de reference).

Ce que cette section verifie :

Correctness du modele (encodage des contraintes non-overlap entre operations d’une meme machine).
Optimalite du solveur (le backtracking explore systematiquement l’espace de recherche avec pruning).
Performance (temps CPU negligeable sur cet exemple, meme en C# pur sans optimisation).

Une fois l’exemple valide, le meme solveur peut etre applique a des instances plus grandes de la litterature (ft6, ft10, ft20 — Fisher-Thompson Job-Shop instances classiques) – mais la complexite exponentielle du backtracking limite la portee. C’est le role de la Tranche 2 d’introduire un moteur de production.

Note terminologique : le terme « ft3 » designe ailleurs dans la litterature (cf. serie Fisher-Thompson 1963) une instance specifique 3 jobs / 3 machines. Les donnees de cet exemple OR-Tools ne sont pas ft3 — elles ont la meme taille (3×3) mais une matrice de durees differente. Ne pas confondre les deux dans les references bibliographiques en TD / examens.

3. Résolution de l’exemple OR-Tools

On lance le solveur sur l’exemple. Référence : OR-Tools CP-SAT (cf. Google OR-Tools scheduling/job_shop) trouve makespan OPTIMAL = 11 sur cet exemple. Notre solveur naïf doit retrouver la même valeur optimale (il explore exhaustivement les ordonnancements disjonctifs) — c’est le test de concordance.


// --- Résolution de l'exemple OR-Tools ---
var solver = new JobShopSolver(INSTANCE);
var sw = System.Diagnostics.Stopwatch.StartNew();
solver.Solve();
sw.Stop();

Console.WriteLine("Résolution en cours...");
Console.WriteLine($"\nTemps de résolution: {sw.Elapsed.TotalMilliseconds:F1} ms");
Console.WriteLine($"Nœuds explorés: {solver.NodesExplored}");
Console.WriteLine($"\nStatut: OPTIMAL (énumération exhaustive)");
Console.WriteLine($"Makespan optimal: {solver.Makespan}");
Console.WriteLine($"\nConcordance avec OR-Tools (makespan=11) : {(solver.Makespan == 11 ? "OUI" : "NON (investiguer)")}");

Résolution en cours...

Temps de résolution: 24,3 ms
Nœuds explorés: 87

Statut: OPTIMAL (énumération exhaustive)
Makespan optimal: 11

Concordance avec OR-Tools (makespan=11) : OUI

4. Schedule optimal (diagramme de Gantt ASCII)

La visualisation ASCII remplace matplotlib (notebook Python). Chaque ligne = une machine, chaque colonne = une unité de temps. On marque l’opération par son job d’origine.


// --- Diagramme de Gantt ASCII ---
if (solver.BestStart != null && solver.BestEnd != null)
{
    int ms = solver.Makespan;
    Console.WriteLine("SCHEDULE OPTIMAL");
    Console.WriteLine(new string('=', 50));
    // Affichage par job (comme le notebook Python).
    foreach (var job in INSTANCE.Jobs)
    {
        int j = INSTANCE.Jobs.IndexOf(job);
        Console.WriteLine($"\n{job.Name}:");
        for (int k = 0; k < job.Ops.Count; k++)
        {
            int s = solver.BestStart[j, k];
            int e = solver.BestEnd[j, k];
            int d = job.Ops[k].Duration;
            int m = job.Ops[k].Machine;
            Console.WriteLine($"  Op {k}: Machine {m}, [{s}, {e}] (durée={d})");
        }
    }

    // Gantt ASCII par machine.
    Console.WriteLine("\nDiagramme de Gantt (ASCII) :");
    Console.WriteLine(new string('-', ms + 12));
    Console.Write("Temps    : ");
    for (int t = 0; t < ms; t++) Console.Write((t % 10).ToString());
    Console.WriteLine();
    for (int m = 0; m < INSTANCE.NumMachines; m++)
    {
        var row = new char[ms];
        for (int t = 0; t < ms; t++) row[t] = '.';
        // Remplir avec les opérations sur cette machine.
        for (int j = 0; j < INSTANCE.Jobs.Count; j++)
            for (int k = 0; k < INSTANCE.Jobs[j].Ops.Count; k++)
                if (INSTANCE.Jobs[j].Ops[k].Machine == m)
                    for (int t = solver.BestStart[j, k]; t < solver.BestEnd[j, k]; t++)
                        row[t] = (char)('0' + j);   // job id
        Console.Write($"Machine {m}: ");
        Console.WriteLine(new string(row));
    }
    Console.WriteLine(new string('-', ms + 12));
    Console.WriteLine("Légende : chiffre = id du job exécuté, '.' = machine idle.");
}
else
{
    Console.WriteLine("Aucune solution trouvée.");
}

SCHEDULE OPTIMAL
==================================================

Job 0:
  Op 0: Machine 0, [0, 3] (durée=3)
  Op 1: Machine 1, [4, 6] (durée=2)
  Op 2: Machine 2, [6, 8] (durée=2)

Job 1:
  Op 0: Machine 0, [3, 5] (durée=2)
  Op 1: Machine 2, [5, 6] (durée=1)
  Op 2: Machine 1, [6, 10] (durée=4)

Job 2:
  Op 0: Machine 1, [0, 4] (durée=4)
  Op 1: Machine 2, [8, 11] (durée=3)

Diagramme de Gantt (ASCII) :
-----------------------
Temps    : 01234567890
Machine 0: 00011......
Machine 1: 2222001111.
Machine 2: .....100222
-----------------------
Légende : chiffre = id du job exécuté, '.' = machine idle.

Interprétation : notre solveur naïf vs OR-Tools CP-SAT

Notre solveur retrouve le makespan optimal = 11 (concordance avec OR-Tools), parce que l’énumération exhaustive des ordonnancements disjonctifs est complète — sur l’exemple OR-Tools (3 jobs × 3 machines, 8 opérations), l’espace est petit. La différence est le coût : OR-Tools résout l’exemple en ~0,009 s (précision consignée dans la sortie de la cell #13 ci-dessous) grâce à sa propagation NoOverlap globale et au lazy clause generation (LCG), tandis que notre backtracking naïf explore toutes les permutations. Sur des instances Job-Shop de la littérature Fisher-Thompson (ft6, ft10, ft20 : 6 à 20 jobs), CP-SAT reste tractable alors que notre solveur explose — c’est toute la valeur d’un moteur industriel : mêmes résultats optimaux, mais à l’échelle.

Transition : du solveur maison au moteur de production

Les Sections 1 a 4 ont assemble un solveur Job-Shop from-scratch en C# pur : modele de donnees (jobs, machines, operations), solveur CP avec propagation + backtracking, exemple OR-Tools « a simple example of a job shop problem » (3 jobs / 3 machines, 8 opérations), diagramme de Gantt ASCII. Cette implementation est necessaire a la comprehension : un solveur CP n’est pas magique, c’est un algorithme de recherche avec contraintes.

Mais notre solveur a une limite evidente : sur ft6 (6 jobs / 6 machines = 6!^6 ordres possibles theoriques), le backtracking naif explose en temps. C’est ici qu’intervient la Tranche 2 : Google.OrTools CP-SAT (le solveur de Google, branche .NET officielle).

Pourquoi CP-SAT plutot qu’un autre solveur ? Trois raisons :

Performance : CP-SAT combine Lazy Clause Generation (la technique de recherche qui a revolutionne SAT-solving), propagation de contraintes globale, et recherche arborescente avec heuristiques sophistiquees. Cas rapportes dans la litterature OR-Tools : instances de plusieurs milliers de variables resolues en secondes ; ce notebook ne re-execute pas ces benchmarks (limite pedagogique du kernel .NET Interactive en temps de cours). La demonstration concrete du notebook reste limitee a l’exemple OR-Tools (cf. Section Tranche 2 ci-dessous).
Branche .NET officielle : le package NuGet Google.OrTools est maintenu par Google, integration native via #r "nuget: ..." en .NET Interactive. Pas de binding hasardeux.
Veridique + Optimal : le plan retourne satisfait toutes les contraintes et minimise l’objectif (makespan par defaut). Pas d’approximation, pas de ‘best effort’.

L’objectif de la Tranche 2 est de montrer l’integration from-scratch -> CP-SAT sur le meme exemple OR-Tools. La comparaison directe revele le saut de performance sans detour par une reformulation du probleme.

Tranche 2 : exemple OR-Tools via Google.OrTools CP-SAT (moteur .NET natif)

La tranche 1 (ci-dessus) résout l’exemple OR-Tools avec un solveur from-scratch (backtracking + propagation au plus tôt). Le jumeau Python, lui, délègue à OR-Tools CP-SAT. Pour que le C# atteigne lui aussi le moteur de production de son écosystème — sans abandonner le from-scratch qui enseigne les mécanismes — cette seconde tranche résout la même exemple OR-Tools via Google.OrTools (CP-SAT natif .NET), déjà en service dans plusieurs notebooks du dépôt (CSP-4/6/8, Sudoku-10/18, Search-9, App-8, App-15b).

Critère owner (#10382) : chaque côté atteint un moteur de production de son écosystème — le from-scratch reste en plus, jamais à la place.

#r "nuget: Google.OrTools"
// Tranche 2 : meme exemple OR-Tools (job shop) que la tranche 1, mais via Google.OrTools CP-SAT .NET.
using Google.OrTools.Sat;
using System.Collections.Generic;
using System.Linq;

// --- Exemple OR-Tools « a simple example of a job shop problem » : (machine, duree) par operation ---
int[][][] example = new int[][][] {
    new int[][] { new int[]{0,3}, new int[]{1,2}, new int[]{2,2} },  // Job 0
    new int[][] { new int[]{0,2}, new int[]{2,1}, new int[]{1,4} },  // Job 1
    new int[][] { new int[]{1,4}, new int[]{2,3} },                  // Job 2
};
int numMachines = 3;
int horizon = example.SelectMany(j => j).Sum(op => op[1]);

Console.WriteLine("Tranche 2 : exemple OR-Tools via Google.OrTools CP-SAT (moteur .NET natif)");
Console.WriteLine(new string('=', 60));
Console.WriteLine($"Jobs: {example.Length} | Machines: {numMachines} | Horizon: {horizon}");

var model = new CpModel();

// Variables de debut/fin + intervalle pour chaque operation.
var starts = new IntVar[example.Length][];
var ends = new IntVar[example.Length][];
var intervals = new IntervalVar[example.Length][];
for (int j = 0; j < example.Length; j++)
{
    starts[j] = new IntVar[example[j].Length];
    ends[j] = new IntVar[example[j].Length];
    intervals[j] = new IntervalVar[example[j].Length];
    for (int k = 0; k < example[j].Length; k++)
    {
        int m = example[j][k][0], dur = example[j][k][1];
        starts[j][k] = model.NewIntVar(0, horizon, $"s_{j}_{k}");
        ends[j][k] = model.NewIntVar(0, horizon, $"e_{j}_{k}");
        intervals[j][k] = model.NewIntervalVar(starts[j][k], dur, ends[j][k], $"iv_{j}_{k}");
    }
}

// (1) Precedence intra-job : op k+1 demarre apres la fin de l'op k.
for (int j = 0; j < example.Length; j++)
    for (int k = 0; k + 1 < example[j].Length; k++)
        model.Add(starts[j][k + 1] >= ends[j][k]);

// (2) Non-chevauchement par machine (AddNoOverlap sur les intervalles de chaque machine).
for (int m = 0; m < numMachines; m++)
{
    var onMachine = new List<IntervalVar>();
    for (int j = 0; j < example.Length; j++)
        for (int k = 0; k < example[j].Length; k++)
            if (example[j][k][0] == m) onMachine.Add(intervals[j][k]);
    model.AddNoOverlap(onMachine);
}

// (3) Objectif : minimiser le makespan = max de tous les ends.
IntVar makespan = model.NewIntVar(0, horizon, "makespan");
var allEnds = new List<IntVar>();
for (int j = 0; j < example.Length; j++)
    for (int k = 0; k < example[j].Length; k++) allEnds.Add(ends[j][k]);
model.AddMaxEquality(makespan, allEnds);
model.Minimize(makespan);

var solver = new CpSolver();
var status = solver.Solve(model);
Console.WriteLine($"Statut CP-SAT : {status}");
Console.WriteLine($"Makespan OPTIMAL = {solver.Value(makespan)}  (reference from-scratch & Python = 11)");
Console.WriteLine($"Wall-clock solve : {solver.WallTime():F3}s | branches: {solver.NumBranches()}");

// Schedule detaille (start -> end sur chaque machine)
Console.WriteLine("\nSchedule CP-SAT (start -> end sur machine) :");
for (int j = 0; j < example.Length; j++)
{
    var parts = new List<string>();
    for (int k = 0; k < example[j].Length; k++)
    {
        int m = example[j][k][0], dur = example[j][k][1];
        parts.Add($"M{m}[{solver.Value(starts[j][k])}-{solver.Value(ends[j][k])}]");
    }
    Console.WriteLine($"  Job {j}: {string.Join(" -> ", parts)}");
}

Console.WriteLine("\nLes deux moteurs convergent vers makespan = 11 : le C# atteint son");
Console.WriteLine("moteur de production (Google.OrTools natif .NET), a egalite avec le Python.");

Installed Packages

Google.OrTools, 9.15.6755

Tranche 2 : exemple OR-Tools via Google.OrTools CP-SAT (moteur .NET natif)
============================================================
Jobs: 3 | Machines: 3 | Horizon: 21
Statut CP-SAT : Optimal
Makespan OPTIMAL = 11  (reference from-scratch & Python = 11)
Wall-clock solve : 0,067s | branches: 9

Schedule CP-SAT (start -> end sur machine) :
  Job 0: M0[2-5] -> M1[5-7] -> M2[7-9]
  Job 1: M0[0-2] -> M2[2-3] -> M1[7-11]
  Job 2: M1[0-4] -> M2[4-7]

Les deux moteurs convergent vers makespan = 11 : le C# atteint son
moteur de production (Google.OrTools natif .NET), a egalite avec le Python.

5. Planning as CP : N-Reines (exemple guide, résolu)

Le notebook Python résout aussi les N-Reines comme CSP CP-SAT (cellule “Exemple guide”). On reproduit la résolution des 4-Reines avec notre backtracking CP from-scratch : une reine par ligne, contraintes de colonne et de diagonales distinctes.


#nullable enable
// --- N-Reines (4) comme CSP : backtracking CP from-scratch ---
// Variable : queens[row] = colonne de la reine sur cette ligne (0..N-1).
// Contraintes : colonnes distinctes + diagonales distinctes.
public static class NQueens
{
    public static int[]? Solve(int n, out int nodes)
    {
        int count = 0;   // local capturable (param out 'nodes' ne l'est pas)
        var queens = new int[n];
        bool Place(int row)
        {
            if (row == n) return true;   // base case : toutes les reines placees
            count++;
            for (int col = 0; col < n; col++)
            {
                bool ok = true;
                for (int r = 0; r < row && ok; r++)
                {
                    int dc = col - queens[r];
                    int dr = row - r;
                    if (queens[r] == col || Math.Abs(dc) == Math.Abs(dr)) ok = false;   // colonne ou diagonale
                }
                if (ok) { queens[row] = col; if (Place(row + 1)) return true; }
            }
            return false;
        }
        var result = Place(0) ? queens : null;
        nodes = count;
        return result;
    }
}

int nodes4;
var sol4 = NQueens.Solve(4, out nodes4);
Console.WriteLine("N-Reines (N=4) — Planning as CP");
Console.WriteLine(new string('=', 40));
if (sol4 != null)
{
    Console.WriteLine($"Solution trouvée (nœuds explorés : {nodes4}) :");
    for (int r = 0; r < 4; r++)
    {
        var line = new char[4];
        for (int c = 0; c < 4; c++) line[c] = c == sol4[r] ? 'Q' : '.';
        Console.WriteLine($"  {new string(line)}   (ligne {r} -> colonne {sol4[r]})");
    }
    Console.WriteLine("\nL'encode CP (colonne/diagonale distinctes) équivaut à MkDistinct en CP-SAT.");
}
else Console.WriteLine("Pas de solution pour N=4.");

N-Reines (N=4) — Planning as CP
========================================
Solution trouvée (nœuds explorés : 8) :
  .Q..   (ligne 0 -> colonne 1)
  ...Q   (ligne 1 -> colonne 3)
  Q...   (ligne 2 -> colonne 0)
  ..Q.   (ligne 3 -> colonne 2)

L'encode CP (colonne/diagonale distinctes) équivaut à MkDistinct en CP-SAT.

Exercices

Trois exercices. Chacun reste en stub (convention C.1 : exécutable sans erreur même non complété).


// Exercice 1 : mesurer l'explosion combinatoire sur l'exemple étendu à 4 jobs.
// Objectif : ajouter un Job 3 [(0,3),(2,2),(1,2)] à INSTANCE (passer de 3 jobs à 4) et relancer le solveur.
// Question d'analyse : par quel facteur NodesExplored augmente-t-il ?
// Indice : avec 4 jobs, chaque machine peut avoir jusqu'à 4 opérations -> 4! permutations par machine.
// Étape 1 : ajouter le job à la liste JOBS.
// Étape 2 : recréer l'instance et appeler Solve.
// Étape 3 : noter NodesExplored et Makespan, comparer à l'exemple à 3 jobs.

Console.WriteLine("Exercice 1 (exemple OR-Tools étendu à 4 jobs) — à compléter par l'étudiant.");
// TODO étudiant : var JOBS4 = new List<Job> { ... 4 jobs ... };
//                 var INSTANCE4 = new JobShopInstance(JOBS4, 3);
//                 new JobShopSolver(INSTANCE4).Solve();

Exercice 1 (exemple OR-Tools étendu à 4 jobs) — à compléter par l'étudiant.


// Exercice 2 : N-Reines (N=8) — compter les solutions.
// Objectif : modifier NQueens.Solve pour ÉNUMÉRER toutes les solutions (pas juste la première).
// Indice : remplacer "return true" par un compteur, et continuer la recherche.
// Question : combien y a-t-il de solutions pour N=8 ? (Réponse connue : 92.)
// Étape 1 : ajouter une surcharge CountSolutions(N) retournant le nombre de solutions.
// Étape 2 : exécuter pour N=4 (2 solutions), N=8 (92 solutions).

Console.WriteLine("Exercice 2 (N-Reines énumération) — à compléter par l'étudiant.");
// TODO étudiant : int count = NQueens.CountSolutions(8);

Exercice 2 (N-Reines énumération) — à compléter par l'étudiant.


// Exercice 3 : optimisation — ajout d'une heuristique (Best-Fit Search).
// Objectif : ordonner les machines par "charge critique" (somme des durées) avant le backtracking.
// Indice : traiter d'abord la machine la plus chargée réduit l'arbre de recherche.
// Étape 1 : calculer la charge par machine.
// Étape 2 : trier machineKeys par charge décroissante dans Backtrack.
// Étape 3 : comparer NodesExplored (avec vs sans heuristique).

Console.WriteLine("Exercice 3 (heuristique Best-Fit) — à compléter par l'étudiant.");
// TODO étudiant : modifier l'ordre de machineKeys dans JobShopSolver.Solve.

Exercice 3 (heuristique Best-Fit) — à compléter par l'étudiant.

Bilan Tranche 2 — naive solver vs production CP-SAT

La comparaison directe sur l’exemple OR-Tools entre notre solveur from-scratch (backtracking + propagation) et Google.OrTools CP-SAT (Section Tranche 2) illustre la frontiere entre pedagogie et production :

Solveur from-scratch (tranche 1) : trouve le makespan optimal sur l’exemple OR-Tools (3 jobs / 3 machines, 8 opérations) en un temps humain-lisible. Implementation simple, code transparent, chaque decision de backtracking est visible. Sur les instances plus grandes (ft6, ft10, ft20 — Fisher-Thompson Job-Shop) l’explosion combinatoire rend le solveur naive inutilisable en pratique.
CP-SAT (moteur .NET natif via #r "nuget: Google.OrTools") : meme exemple OR-Tools resolu en millisecondes (cf. output Section Tranche 2). Sur ft10 ou ft20, la litterature rapporte des temps de l’ordre de la seconde a quelques dizaines de secondes selon l’instance exacte (cf. OR-Tools benchmarks publies, non re-executes dans ce notebook – l’instance n’est pas embarquee ici). Verdict : moteur SOTA, veridique, branchable localement (mais la mesure effective reste a executer par l’enseignant selon ses contraintes).

Regle d’or : la Tranche 1 from-scratch est la fondation pedagogique ; la Tranche 2 est la mise en production. Pour les instances Job-Shop de la litterature Fisher-Thompson (ft6, ft10, ft20 – et au-dela), seul CP-SAT (ou un equivalent : OR-Tools, Gurobi, Choco) est realiste. Pour les instances jouet (3 a 5 jobs), un solveur naif reste un excellent outil d’enseignement.

Ou aller ensuite ? La Tranche 2 de ce notebook utilise Google.OrTools – le meme pipeline est expose en Python (cf. Planners-7-OR-Tools.ipynb, twin Python). Pour des problemes > 100 jobs ou avec des couts non lineaires, basculer sur un solveur MIP (CBC, SCIP) ou une metaheuristique (recuit simule, genetic algorithm).

Conclusion

Ce jumeau C# reconstruit à la main le moteur CP que OR-Tools (notebook Python) délègue à sa bibliothèque cp_model. Les deux approches sont complémentaires :

Le notebook Python apprend à modéliser en CP-SAT (NewIntVar, NewIntervalVar, AddNoOverlap, Minimize) et à appeler un solveur industriel.
Ce jumeau C# apprend comment fonctionne la résolution : propagation de domaines, backtracking disjonctif, énumération des ordonnancements. C’est le moteur interne rendu visible.

Ce que vous avez appris

Un Job-Shop = précédences intra-job + non-chevauchement par machine ; minimiser le makespan.
La propagation de domaines (point fixe) calcule le schedule au plus tôt pour un ordonnancement fixé.
Le backtracking sur les ordonnancements disjonctifs est complet (optimal) mais explose combinatoirement.
OR-Tools CP-SAT obtient le même optimum (makespan = 11 sur l’exemple) mais via LCG + NoOverlap global — tractable à grande échelle.

Prochaines étapes

Planners-8-Temporal : planification temporelle (PDDL 2.1, actions duratives) — son jumeau C# existe (Planners-8-Temporal-Csharp).
Planners-9-HTN : planification hiérarchique — jumeau C# (Planners-9-HTN-Csharp).
Pour la version “moteur réel”, revenir au notebook Python Planners-7-OR-Tools et son appel à cp_model.

Ressources

Fisher, H., & Thompson, G. L. (1963) — « Probabilistic Learning Combinations of Local Job-Shop Scheduling Rules », dans Industrial Scheduling, Prentice-Hall. Référence historique aux instances ft6, ft10, ft20 (Job-Shop scheduling), à ne pas confondre avec l’exemple 3×3 du notebook (qui suit l’exemple canonique d’OR-Tools).
Russell, S., & Norvig, P. — Artificial Intelligence: A Modern Approach (4e éd., 2021), ch. « Constraint Satisfaction Problems ». Backtracking, propagation (AC-3), heuristiques MRV/LCV.
Perron, L., & Furnon, V. — OR-Tools CP-SAT (Google). Propagation par clauses paresseuses (LCG), contrainte globale NoOverlap.

Retour au sommet