À la fin de ce notebook, vous saurez : 1. Modéliser le Job-Shop Scheduling Problem (JSSP) : opérations ordonnées par job, une machine par opération, minimisation du makespan 2. Dérouler des heuristiques de dispatching from-scratch (SPT, LPT, MOR, MWKR, FIFO) et comprendre leurs biais 3. Implémenter un branch-and-bound par énumération d’emplois du temps actifs avec élagage par borne inférieure 4. Comparer ces moteurs explicites au solveur industriel OR-Tools CP-SAT du twin Python
Twin C# du marathon #4956 (parité .NET ⇄ Python). Le notebook Python App-4-JobShopScheduling invoque OR-Tools CP-SAT (IntervalVar, AddNoOverlap, minimisation du makespan). Ce twin déroule les algorithmes à la main (BCL .NET 9, 0 NuGet) : ce que CP-SAT cache (propagation de précédences, gestion des ressources partagées, recherche arborescente) devient explicite. Verdict axe-2 SOTA #3801 Prong B.
1. Contexte — le Job-Shop Scheduling Problem
Le JSSP est l’un des problèmes combinatoires les plus étudiés en recherche opérationnelle. On a n jobs, chacun composé d’une séquence ordonnée d’opérations ; chaque opération doit être exécutée sur une machine donnée pendant une durée donnée. Une machine ne traite qu’une opération à la fois (no-overlap), et les opérations d’un même job respectent leur ordre (précédence). L’objectif est de minimiser le makespan — la date de fin de la dernière opération.
C’est un problème NP-difficile au sens fort : même de petites instances (6×6) sont non-triviales, et l’explosion combinatoire est brutale.
Deux familles d’algorithmes
Famille
Idée
Ce qu’on voit ici
Heuristiques de dispatching
À chaque pas, planifier l’opération « la plus prioritaire » (glouton)
SPT, LPT, MOR, MWKR, FIFO
Branch-and-bound
Énumérer les emplois du temps actifs en élaguant par borne inférieure
Optimum garanti sur petites instances
Le twin Python (CP-SAT) fusionne propagation + recherche + optimisation dans un solveur « boîte noire ». Ici on sépare pour voir ce que chaque stratégie capture — et ce qu’elle rate.
The below script needs to be able to find the current output cell; this is an easy method to get it.
Instance ft03 : 3 jobs x 3 machines = 9 operations, horizon <= 22
Job 0 : M0(3) -> M1(2) -> M2(2) [total = 7]
Job 1 : M0(2) -> M2(1) -> M1(4) [total = 7]
Job 2 : M1(4) -> M2(3) -> M0(1) [total = 8]
2. Modèle — opération planifiée et makespan
Une solution = une affectation (début, fin) à chaque opération (job, op_idx). Le makespan est le maximum des fins. Les contraintes à respecter : - Précédence : l’opération k+1 du job j commence après la fin de k. - No-overlap : sur une machine, deux opérations ne se chevauchent pas.
// --- Modele d'une solution + validateur + makespan ---// schedule[(j,k)] = (start, end) pour l'operation k du job j.// Type Dictionary explicite partout (pas d'alias 'using' : les tuples nommes en cle sont rejetes par l'aliasing C#).Dictionary<(int j,int k),(int start,int end)>EmptySched()=>new();intMakespan(Dictionary<(int j,int k),(int start,int end)> sched){int m =0;foreach(var v in sched.Values)if(v.end> m) m = v.end;return m;}// Valide une solution complete contre les contraintes (retourne nb de violations)(int prec,int overlap)Validate((int machine,int dur)[][] jobs, Dictionary<(int j,int k),(int start,int end)> sched){int prec =0, overlap =0;for(int j =0; j < jobs.Length; j++)for(int k =0; k < jobs[j].Length-1; k++)if(sched[(j, k +1)].start< sched[(j, k)].end) prec++;var byMachine =new Dictionary<int, List<(int s,int e)>>();for(int j =0; j < jobs.Length; j++)for(int k =0; k < jobs[j].Length; k++){int m = jobs[j][k].machine;var iv =(sched[(j, k)].start, sched[(j, k)].end);if(!byMachine.ContainsKey(m)) byMachine[m]=new List<(int,int)>(); byMachine[m].Add(iv);}foreach(var kv in byMachine){var sorted = kv.Value.OrderBy(x => x.s).ToList();for(int i =1; i < sorted.Count; i++)if(sorted[i].s< sorted[i -1].e) overlap++;}return(prec, overlap);}// Diagramme de Gantt ASCII (lignes = machines)stringGantt((int machine,int dur)[][] jobs, Dictionary<(int j,int k),(int start,int end)> sched,int makespan,int nm){var byMachine =new Dictionary<int, List<(int s,int e,int j,int k)>>();for(int j =0; j < jobs.Length; j++)for(int k =0; k < jobs[j].Length; k++){int m = jobs[j][k].machine;if(!byMachine.ContainsKey(m)) byMachine[m]=new List<(int,int,int,int)>(); byMachine[m].Add((sched[(j, k)].start, sched[(j, k)].end, j, k));}var sb =new System.Text.StringBuilder();for(int m =0; m < nm; m++){ sb.Append("M"+ m +" ");char[] row =newstring(' ', makespan +2).ToCharArray();if(byMachine.ContainsKey(m))foreach(var(s, e, j, k)in byMachine[m].OrderBy(x => x.s))for(int t = s; t < e; t++) row[t]=(char)('0'+ j); sb.AppendLine(newstring(row).TrimEnd());} sb.AppendLine("Makespan = "+ makespan +" (chiffre = index du job sur la machine)");return sb.ToString();}"Modele + Validate + Gantt prets.".Display();
Modele + Validate + Gantt prets.
3. Heuristiques de dispatching — le glouton actif
On simule l’atelier : à chaque itération, on regarde les opérations prêtes (opérateur suivant d’un job dont la précédence est satisfaite), on calcule leur date de début au plus tôt = max(fin précédente du job, libération de la machine), puis on planifie en priorité selon la règle. C’est l’algorithme explicite derrière les règles de priorité industrielles.
Règle
Priorité
Biais
SPT
durée la plus courte
favorise la fluidité, risque sur les longues
LPT
durée la plus longue
sécurise les goulets
MOR
travail restant maximal dans le job
finit les jobs longs en priorité
MWKR
travail restant total (somme)
variante plus fine de MOR
FIFO
ordre d’arrivée
baseline neutre
// --- Ordonnanceur par regle de dispatching (glouton actif) ---Dictionary<(int j,int k),(int start,int end)>Dispatch((int machine,int dur)[][] jobs,string rule,int nm){int nj = jobs.Length;var nextOp =newint[nj];var jobEnd =newint[nj];var machEnd =newint[nm];var sched =new Dictionary<(int j,int k),(int start,int end)>();int total = jobs.Sum(j => j.Length), done =0;while(done < total){// Operations pretes : op = nextOp[j] si < longueur du jobvar ready =new List<(int j,int k,int m,int d,int es)>();for(int j =0; j < nj; j++){int k = nextOp[j];if(k < jobs[j].Length){int m = jobs[j][k].machine, d = jobs[j][k].dur;int es = Math.Max(jobEnd[j], machEnd[m]); ready.Add((j, k, m, d, es));}}if(ready.Count==0)break;// Choix de la priorite(int j,int k,int m,int d,int es) pick = ready[0]; System.Func<(int j,int k,int m,int d,int es),double> key = rule switch{"SPT"=> x => x.d,// duree courte d'abord"LPT"=> x =>-x.d,// duree longue d'abord"MOR"=> x =>-(jobs[x.j].Length- x.k),// ops restantes dans le job (max d'abord)"MWKR"=> x =>-jobs[x.j].Skip(x.k).Sum(o => o.dur),// travail restant total"FIFO"=> x => x.es,// debut au plus tot _ => x => x.d,}; pick = ready.OrderBy(x =>key(x)).First();int start = pick.es, end = start + pick.d; sched[(pick.j, pick.k)]=(start, end); jobEnd[pick.j]= end; machEnd[pick.m]= end; nextOp[pick.j]++; done++;}return sched;}var spt =Dispatch(ft03,"SPT", NM);var(p, ov)=Validate(ft03, spt);"=== ft03 - regle SPT ===".Display();Gantt(ft03, spt,Makespan(spt), NM).Display();$"Violations : precedence={p}, overlap={ov} (attendu 0/0)".Display();
=== ft03 - regle SPT ===
M0 11000 2
M1 0011112222
M2 1 00 222
Makespan = 19 (chiffre = index du job sur la machine)
Les heuristiques donnent une solution rapide mais sans garantie. Pour prouver l’optimum sur une petite instance, on énumère les emplois du temps actifs : à chaque conflit (plusieurs opérations prêtes au même instant), on branche sur l’ordre, et on élague toute branche dont la borne inférieure dépasse la meilleure solution connue.
La borne inférieure est simple : max(fins actuelles) augmenté du travail restant minimal. C’est l’équivalent explicite de la propagation + recherche de CP-SAT, sans son ingénierie.
// --- Branch-and-bound : enumere les emplois du temps actifs, elague par borne ---int bestMakespan =int.MaxValue;Dictionary<(int j,int k),(int start,int end)> bestSched =null;long nodes =0, pruned =0;// Borne inferieure : max des (fin job + travail restant du job), et max liberation machine + travail restant sur machineintLowerBound((int machine,int dur)[][] jobs,int[] jobEnd,int[] machEnd,int[] nextOp){int lb =0;for(int j =0; j < jobs.Length; j++){int rem = jobs[j].Skip(nextOp[j]).Sum(o => o.dur); lb = Math.Max(lb, jobEnd[j]+ rem);}return lb;}voidBB((int machine,int dur)[][] jobs,int[] jobEnd,int[] machEnd,int[] nextOp, Dictionary<(int j,int k),(int start,int end)> sched,int done,int total){if(done == total){int mk =Makespan(sched);if(mk < bestMakespan){ bestMakespan = mk; bestSched =new Dictionary<(int j,int k),(int start,int end)>(sched);}return;} nodes++;// Elagage : si la borne depasse deja le meilleur connu, on coupeif(LowerBound(jobs, jobEnd, machEnd, nextOp)>= bestMakespan){ pruned++;return;}// Operations pretes : on branche sur TOUTES (enumeration complete des ordres topologiques).// Limiter aux "actives" (es==tmin) donnerait les emplois non-delay, un sous-ensemble strict// qui peut rater l'optimum -- d'ou la recherche complete ici, elaguee par la borne.var ready =new List<(int j,int k,int m,int d,int es)>();for(int j =0; j < jobs.Length; j++){int k = nextOp[j];if(k < jobs[j].Length){int m = jobs[j][k].machine, d = jobs[j][k].dur; ready.Add((j, k, m, d, Math.Max(jobEnd[j], machEnd[m])));}}foreach(var op in ready){var jb =(int[])jobEnd.Clone();var mb =(int[])machEnd.Clone();var nb =(int[])nextOp.Clone();var sb2 =new Dictionary<(int j,int k),(int start,int end)>(sched);int end = op.es+ op.d; sb2[(op.j, op.k)]=(op.es, end); jb[op.j]= end; mb[op.m]= end; nb[op.j]++;BB(jobs, jb, mb, nb, sb2, done +1, total);}}bestMakespan =int.MaxValue; bestSched =null; nodes =0; pruned =0;BB(ft03,newint[NJ],newint[NM],newint[NJ],new Dictionary<(int j,int k),(int start,int end)>(),0, totalOps);"=== ft03 - Branch-and-bound (optimal) ===".Display();Gantt(ft03, bestSched, bestMakespan, NM).Display();$"Optimum prouve : makespan = {bestMakespan} | noeuds explores = {nodes} | branches elaguees = {pruned}".Display();
=== ft03 - Branch-and-bound (optimal) ===
M0 00011 2
M1 2222001111
M2 122200
Makespan = 11 (chiffre = index du job sur la machine)
L’instance ft06 de Fisher & Thompson (6 jobs × 6 machines, 36 opérations) est un classique plus exigeant. Le branch-and-bound devient trop lent pour la prouver in-notebook, mais les heuristiques de dispatching restent instantanées et donnent un encadrement. Le twin Python (CP-SAT) prouve ici son avantage : il trouve l’optimum (littérature : makespan = 55) en quelques secondes.
// --- Instance ft06 (Fisher & Thompson, 6x6) + heuristiques ---// Instance ft06 canonique (6 jobs x 6 machines, 36 operations)(int machine,int dur)[][] ft06 =new[]{new[]{(2,1),(0,3),(1,6),(3,7),(5,3),(4,6)},new[]{(1,8),(2,5),(4,10),(3,10),(0,10),(5,4)},new[]{(2,5),(3,4),(4,8),(0,9),(1,1),(5,7)},new[]{(1,5),(0,5),(2,5),(3,3),(4,8),(5,9)},new[]{(2,9),(1,3),(4,5),(5,4),(0,3),(3,1)},new[]{(1,3),(3,3),(5,9),(0,10),(4,4),(2,1)},};int NM6 =6;var sb6 =new System.Text.StringBuilder();sb6.AppendLine("Regle | Makespan");sb6.AppendLine(newstring('-',20));foreach(var r innew[]{"SPT","LPT","MOR","MWKR","FIFO"}){var s =Dispatch(ft06, r, NM6); sb6.AppendLine(r +newstring(' ',7- r.Length)+" | "+Makespan(s));}sb6.ToString().Display();$"Litterature ft06 : makespan optimal = 55 (OR-Tools CP-SAT le prouve en secondes dans le twin Python).".Display();$"Nos heuristiques donnent une borne superieure rapide ; le B&B serait trop lent sur 36 operations pour ce notebook.".Display();
★ Ce twin ne remplace pas CP-SAT (qui reste l’outil SOTA, capable de prouver ft06=55). Il rend visibles les briques que CP-SAT orchestre : la génération d’emploi du temps actif, le rôle des règles de priorité, et la mécanique du branch-and-bound. C’est le cœur pédagogique du Prong B — l’intérieur de la boîte noire exposé.
Tranche 2 : parité lib-vs-lib via Google.OrTools CP-SAT
La Tranche 1 ci-dessus (sections 3–4) réimplémente from-scratch deux moteurs — 5 règles de dispatching glouton (SPT, LPT, MOR, MWR, etc.) et un branch-and-bound — en BCL pure, 0 NuGet. C’est ce que la §6 « Complémentarité » décrit : rendre visibles la génération d’emploi du temps actif et l’élagage du B&B que CP-SAT orchestre en boîte noire. La §6 annonçait CP-SAT comme l’outil SOTA capable de « prouver ft06 = 55 ».
La Tranche 2 franchit le même cap que le jumeau Python : invoquer ce moteur de production plutôt que de le laisser de l’autre côté du miroir. Le jumeau Python appelle ortools.sat.python.cp_model ; côté .NET, Google publie le même solveur CP-SAT sous le package NuGet Google.OrTools. La parité est lib-vs-lib : le même moteur (intervalles, NoOverlap, propagation de bornes) des deux côtés.
Le job-shop est la famille d’ordonnancement qui exerce le plus distinctement CP-SAT, car il mobilise une brique que les N-Reines et le Nurse-Rostering n’utilisaient pas : les variables d’intervalle (IntervalVar) et la contrainte globale AddNoOverlap (une machine ne traite qu’une opération à la fois). Le modèle tient en quatre éléments — c’est la formulation canonique reconnue, identique à celle du jumeau Python (App-4-JobShopScheduling.ipynb, fonction solve_jssp_cpsat) :
Élément
Construction CP-SAT
Sens
Variables d’intervalle
NewIntervalVar(start, durée, end, …) par opération
chaque opération occupe [start, end] sur sa machine
Précédence (chaîne de job)
Add(end[j,k] <= start[j,k+1])
opérations d’un même job en séquence
Non-chevauchement machine
AddNoOverlap(intervalles d'une machine)
une machine = une opération à la fois
Objectif makespan
AddMaxEquality(makespan, toutes les fins) + Minimize(makespan)
minimiser la date de fin totale
sur la même instance ft03 que la Tranche 1 (3 jobs × 3 machines, déclarée en §1 et réutilisée telle quelle — la parité est sur le même problème).
#r "nuget: Google.OrTools"using Google.OrTools.Sat;using System.Diagnostics;using System.Collections.Generic;// Instance ft03 REUTILISEE de la cellule §1 (cellule code ec=1) : ft03, NJ, NM, horizon.// Meme instance que le jumeau Python solve_jssp_cpsat(instance).var model =newCpModel();// --- Etape 1 : variables d'intervalle par operation ---var starts =new IntVar[NJ][];var ends =new IntVar[NJ][];var intervals=new IntervalVar[NJ][];var machineIntervals =new List<IntervalVar>[NM];for(int m =0; m < NM; m++) machineIntervals[m]=new List<IntervalVar>();for(int j =0; j < NJ; j++){int nOps = ft03[j].Length; starts[j]=new IntVar[nOps]; ends[j]=new IntVar[nOps]; intervals[j]=new IntervalVar[nOps];for(int k =0; k < nOps; k++){int mac = ft03[j][k].machine, dur = ft03[j][k].dur;var s = model.NewIntVar(0, horizon, $"s_j{j}_o{k}");var e = model.NewIntVar(0, horizon, $"e_j{j}_o{k}");var iv = model.NewIntervalVar(s, dur, e, $"iv_j{j}_o{k}"); starts[j][k]= s; ends[j][k]= e; intervals[j][k]= iv; machineIntervals[mac].Add(iv);}}Console.WriteLine($"Variables : {ft03.Sum(j => j.Length)} operations, horizon = {horizon}");// --- Etape 2 : contraintes de precedence (operations d'un job en sequence) ---int nPrec =0;for(int j =0; j < NJ; j++)for(int k =0; k < ft03[j].Length-1; k++){ model.Add(ends[j][k]<= starts[j][k +1]); nPrec++;}Console.WriteLine($"Contraintes de precedence : {nPrec}");// --- Etape 3 : non-chevauchement par machine (AddNoOverlap) ---for(int m =0; m < NM; m++) model.AddNoOverlap(machineIntervals[m]);Console.WriteLine($"Contraintes NoOverlap : {NM} machines");// --- Etape 4 : objectif = minimiser le makespan (max des fins) ---var allEnds =new List<IntVar>();for(int j =0; j < NJ; j++)for(int k =0; k < ft03[j].Length; k++) allEnds.Add(ends[j][k]);var makespan = model.NewIntVar(0, horizon,"makespan");model.AddMaxEquality(makespan, allEnds);model.Minimize(makespan);// --- Resolution ---var solver =newCpSolver();solver.StringParameters="max_time_in_seconds:30";var sw = Stopwatch.StartNew();var st = solver.Solve(model);sw.Stop();Console.WriteLine($"\nCP-SAT JSSP ft03 : status={st}, makespan={solver.Value(makespan)}, temps={sw.Elapsed.TotalMilliseconds:F1} ms");// --- Emploi du temps solution (par job, par operation) ---if(st is CpSolverStatus.Feasible or CpSolverStatus.Optimal){ Console.WriteLine("\nEmploi du temps CP-SAT (makespan optimal prouve) :");for(int j =0; j < NJ; j++){var ligne = $" Job {j} : ";for(int k =0; k < ft03[j].Length; k++){int s =(int)solver.Value(starts[j][k]);int e =(int)solver.Value(ends[j][k]);int mac = ft03[j][k].machine; ligne += $"[M{mac} @{s}-{e}] ";} Console.WriteLine(ligne);} Console.WriteLine($"\n=> makespan = {solver.Value(makespan)} (= jumeau Python OPTIMAL 11 ; LB = 10, le moteur prouve qu'aucun ordonnancement a 10 n'existe).");}
Interprétation : lib-vs-lib, non-chevauchement et preuve d’optimalité
Parité de statut et de makespan avec le jumeau Python. Le solveur CP-SAT .NET atteint OPTIMAL avec makespan = 11 sur ft03 — exactement le résultat que produit le jumeau Python (solve_jssp_cpsat → OPTIMAL, makespan 11). La parité est chiffre-à-chiffre sur l’optimum : non seulement une solution faisable, mais la même preuve d’optimalité. La borne inférieure (10 = max du plus long job et de la machine la plus chargée) n’est pas atteignable ; le moteur démontre qu’aucun ordonnancement de makespan 10 n’existe, et que 11 est l’optimum global.
Tranche 1 vs Tranche 2 = pédagogie vs production. La Tranche 1 (§3–4) rend visible la mécanique : les règles de dispatching ordonnancent gloutonnement, le branch-and-bound énumère les emplois du temps actifs en élaguant. La Tranche 2 délègre tout cela au moteur CP-SAT, qui apporte la contrainte globale NoOverlap (propagation énergique sur les intervalles) et la preuve d’optimalité — le même rôle que ortools.sat.python.cp_model joue côté Python. C’est le pont que la §6 « Complémentarité » réservait au twin Python : il est désormais matérialisé côté C#.
Pourquoi les intervalles changent tout. Les N-Reines (App-1) et le Nurse-Rostering (App-3) se modélisent en booléens (AddAllDifferent, sommes linéaires). Le job-shop, lui, modélise le temps : chaque opération est un intervalle [start, end], et la contrainte « une machine à la fois » devient la contrainte globale AddNoOverlap, qui propage bien plus efficacement qu’une paire de disjonctions (a ≤ b) ∨ (b ≤ a) explicites. C’est précisément la capacité de CP-SAT que ce notebook met en valeur (Prong B de #3801) : le moteur excelle là où la structure temporelle se prête aux intervalles.
Preuve vs heuristique. La Tranche 1 §3 montrait que les meilleures règles de dispatching atteignent ft03 ≈ 12 ; CP-SAT prouve l’optimum 11. Sur ft06 (6×6, §5), le B&B from-scratch peinerait ; CP-SAT prouve 55 — c’est le saut de échelle que le moteur de production autorise, et que la §6 annonçait.
C’est exactement la parité demandée par l’EPIC #10382 : les deux jumeaux atteignent désormais un moteur de production de leur écosystème (ortools.sat côté Python, Google.OrTools côté .NET), la réimplémentation pédagogique étant conservée en plus, jamais à la place.
7. Exercices
Exercice 1 — Implémenter la règle MWKR sur ft06
La règle MWKR (Most Work Remaining) priorise l’opération dont le job a le plus de travail restant. Elle est déjà dans le dispatcher ci-dessus — observez son makespan vs SPT sur ft06. Votre tâche : ajoutez une variante AWKR (Average Work Remaining = travail restant / nb d’opérations restantes) et comparez.
// --- Exercice 1 : regle AWKR (travail restant moyen) ---// TODO etudiant : ajouter une regle "AWKR" au dispatcher (cle = -(somme restante / nb ops restantes))// Indice : modifier le 'switch' dans Dispatch(), ajouter "AWKR" => x => -(jobs[x.j].Skip(x.k).Sum(o => o.dur) / (double)(jobs[x.j].Length - x.k))// Puis comparer AWKR vs MWKR vs SPT sur ft06."Exercice 1 a completer : implémenter AWKR dans le dispatcher et comparer.".Display();
Exercice 1 a completer : implémenter AWKR dans le dispatcher et comparer.
Exercice 2 — JSSP avec temps de setup
Dans la réalité, changer de job sur une machine coûte un temps de setup. Ajoutez un coût de setup setup[m][jobA][jobB] lorsqu’une machine enchaîne deux jobs différents, et modifiez le dispatcher pour l’inclure dans es.
// --- Exercice 2 : temps de setup (STUB) ---// TODO etudiant : etendre le modele pour qu'un enchainement (jobA -> jobB) sur une machine// ajoute un delai setup. Indice : memoriser le dernier job traite par machine, ajouter le setup a 'es'."Exercice 2 a completer : integrer les temps de setup inter-job.".Display();
Exercice 2 a completer : integrer les temps de setup inter-job.
Exercice 3 — Flexible Job-Shop
En flexible job-shop, chaque opération peut aller sur un ensemble de machines (pas une seule). C’est strictement plus dur. Proposez comment étendre le dispatcher pour choisir la machine la moins chargée parmi les candidates.
// --- Exercice 3 : Flexible Job-Shop (STUB) ---// TODO etudiant : operations = (HashSet<int> machines, duree). Le dispatcher choisit// la machine candidate dont machEnd est minimale. Indice : ready.Add(..., candidates.Min(m => machEnd[m]))."Exercice 3 a completer : Flexible Job-Shop (choix de machine par operation).".Display();
Exercice 3 a completer : Flexible Job-Shop (choix de machine par operation).
Conclusion
Ce twin C# a déroulé deux familles d’algorithmes from-scratch sur le Job-Shop Scheduling :
Les heuristiques de dispatching (SPT, LPT, MOR, MWKR, FIFO) donnent des solutions rapides mais sans garantie, et leurs biais se voient dans le makespan.
Le branch-and-bound prouve l’optimum sur petites instances (ft03) en énumérant les emplois du temps actifs avec élagage — c’est l’équivalent explicite de la propagation + recherche de CP-SAT.
La frontière est nette : au-delà de quelques opérations, seul un solveur industriel comme CP-SAT (twin Python) reste praticable. Ce twin rend lisible ce que CP-SAT encapsule — c’est tout l’enjeu du Prong B du marathon #4956.