Navigation : Index | << OR-Tools C# | HTN C# >> Ce notebook est le jumeau C# (.NET Interactive) du notebook Python Planners-8-Temporal.ipynb. Il réimplémente from-scratch (BCL .NET, 0 NuGet, 0 unified_planning, 0 ortools) les concepts de la planification temporelle : PDDL 2.1 actions duratives, algèbre d’intervalles d’Allen, réseau temporel simple (STN) et ordonnancement avec contraintes de précédence et ressources.
at start, over all, at end, effets).Le notebook Python original s’appuie sur unified_planning (API Python de planification) et ortools CP-SAT (Google) pour exprimer et résoudre le problème temporel. Ces libs ne sont pas mobilisables nativement côté .NET Interactive sans NuGet lourds. Le twin C# reconstruit les concepts — Allen, STN, Floyd-Warshall, scheduling — pour les rendre transparents et exécutables sur toute machine .NET 9+. Le value-add (EPIC #4956 Prong B) est pédagogique : chaque mécanisme (composition d’Allen, propagation de contraintes STN, heuristique de scheduling) est visible dans le code C#.
.NET 9.0+ (kernel csharp). Familiarité avec la planification classique state-space (cf. Planners-3-State-Space-Csharp.ipynb). Aucune librairie externe.
Ce notebook jumeau C# de Planners-8-Temporal.ipynb (Python) couvre la planification temporelle, sous-domaine de la planification automatique ou le temps est une dimension explicite (les actions durent, les fenetres temporelles existent, les conflits d’allocation sont possibles). Quatre piliers sont construits from-scratch en C# avant d’etre compares a un moteur SOTA de production (CP-SAT).
Pourquoi ce notebook maintenant ? La planification temporelle est un probleme fondamental de la recherche operationnelle (ordonnancement de chaines de production, planification de personnel, logistique de livraison). Elle est aussi un terrain fertile pour les outils modernes : solveurs CP-SAT, MIP, metaheuristiques. Comprendre les fondations (from-scratch) permet de lire les sorties des solveurs avec un oeil critique.
Prerequisites :
record, HashSet<T>, LINQ). Les specificites enum, readonly struct, sealed class sont documentees inline.Plan du notebook : 5 parties theoriques (PDDL 2.1, Allen, STN, conflits, RCPSP) + 1 Tranche 2 pratique (CP-SAT via NuGet) + 3 exercices. Chaque partie peut etre lue independamment ; les imports sont groupes dans la cellule Setup qui suit.
Note d’integration : la Tranche 2 utilise le package NuGet Google.OrTools via .NET Interactive (#r "nuget: ..."). Premier tel appel dans la serie Planners C# – le notebook documente pas-a-pas la sortie du dotnet-interactive.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
static void Show(object o) { try { display(o); } catch { Console.WriteLine(o); } }
static void Show(string label, object o) => Show($"{label}: {o}");
Show("Setup", "OK — BCL .NET, 0 NuGet (pas de unified_planning / ortools).");Setup: OK — BCL .NET, 0 NuGet (pas de unified_planning / ortools).En planification classique (STRIPS/PDDL 1), une action est instantanée. PDDL 2.1 (Fox & Long, 2003) introduit les actions duratives : une action s’étend sur un intervalle \([t_{start}, t_{end}]\) de durée \(\delta\), avec des conditions et effets qualifiés temporellement :
at start : condition/effect au début de l’action,over all : condition maintenue pendant toute la durée,at end : condition/effect à la fin.Cela permet la concurrence : deux actions duratives peuvent se chevaucher si elles ne se violent pas mutuellement (exclusion mutuelle temporelle sur une ressource, par exemple).
// --- PDDL 2.1 : action durative from-scratch ---
public enum TemporalQualifier { AtStart, OverAll, AtEnd }
public sealed class TimedCondition
{
public TemporalQualifier When { get; }
public string Predicate { get; } // ex: "robot_at(A)", "battery > 10"
public TimedCondition(TemporalQualifier q, string pred) { When = q; Predicate = pred; }
public override string ToString() => $"{When}({Predicate})";
}
public sealed class DurativeAction
{
public string Name { get; }
public double MinDuration { get; }
public double MaxDuration { get; }
public List<TimedCondition> Conditions { get; } = new();
public List<TimedCondition> Effects { get; } = new();
public DurativeAction(string name, double durMin, double durMax) { Name = name; MinDuration = durMin; MaxDuration = durMax; }
public DurativeAction Cond(TemporalQualifier q, string p) { Conditions.Add(new TimedCondition(q, p)); return this; }
public DurativeAction Eff(TemporalQualifier q, string p) { Effects.Add(new TimedCondition(q, p)); return this; }
public override string ToString()
{
var sb = new StringBuilder();
sb.AppendLine($"durative-action {Name} [duration in [{MinDuration}, {MaxDuration}]]");
sb.AppendLine(" condition:");
foreach (var c in Conditions) sb.AppendLine($" {c}");
sb.AppendLine(" effect:");
foreach (var e in Effects) sb.AppendLine($" {e}");
return sb.ToString();
}
}
// --- Action move(A, B) : deplacement classique avec duree ---
var moveAB = new DurativeAction("move(robot, A, B)", 4.0, 4.0)
.Cond(TemporalQualifier.AtStart, "robot_at(A)")
.Cond(TemporalQualifier.OverAll, "battery > 5")
.Eff(TemporalQualifier.AtStart, "not robot_at(A)")
.Eff(TemporalQualifier.AtEnd, "robot_at(B)")
.Eff(TemporalQualifier.AtEnd, "battery -= 4");
Show("Action durative move(A,B)", moveAB.ToString());
// --- Action charge : recharge la batterie ---
var charge = new DurativeAction("charge(robot)", 3.0, 3.0)
.Cond(TemporalQualifier.AtStart, "robot_at(dock)")
.Eff(TemporalQualifier.AtEnd, "battery = 100");
Show("Action durative charge", charge.ToString());Action durative move(A,B): durative-action move(robot, A, B) [duration in [4, 4]]
condition:
AtStart(robot_at(A))
OverAll(battery > 5)
effect:
AtStart(not robot_at(A))
AtEnd(robot_at(B))
AtEnd(battery -= 4)Action durative charge: durative-action charge(robot) [duration in [3, 3]]
condition:
AtStart(robot_at(dock))
effect:
AtEnd(battery = 100)Allen (1983) définit 13 relations binaires entre deux intervalles temporels \(I_1 = [s_1, e_1]\) et \(I_2 = [s_2, e_2]\) (avec \(s_i < e_i\)) : before, after, meets, met-by, overlaps, overlapped-by, during, contains, starts, started-by, finishes, finished-by, equals.
Elles forment une algèbre de relation avec une table de composition (si \(R_1(I_1,I_2)\) et \(R_2(I_2,I_3)\) alors \(R_1 \circ R_2 \subseteq \{\text{relations possibles}\}(I_1,I_3)\)). On implémente la classification par comparaison des bornes, puis la table de composition pour la propagation de contraintes.
// --- Allen Interval Algebra from-scratch ---
public readonly struct Interval
{
public double Start { get; }
public double End { get; }
public string Name { get; }
public Interval(string name, double s, double e) { Name = name; Start = s; End = e; }
public double Duration => End - Start;
public override string ToString() => $"{Name}[{Start},{End}]";
}
public enum AllenRel
{
Before, After, Meets, MetBy,
Overlaps, OverlappedBy, During, Contains,
Starts, StartedBy, Finishes, FinishedBy, Equal
}
public static class AllenAlgebra
{
public static string RelStr(AllenRel r) => r switch
{
AllenRel.Before => "before", AllenRel.After => "after",
AllenRel.Meets => "meets", AllenRel.MetBy => "met-by",
AllenRel.Overlaps => "overlaps", AllenRel.OverlappedBy => "overlapped-by",
AllenRel.During => "during", AllenRel.Contains => "contains",
AllenRel.Starts => "starts", AllenRel.StartedBy => "started-by",
AllenRel.Finishes => "finishes", AllenRel.FinishedBy => "finished-by",
AllenRel.Equal => "equal", _ => "?"
};
// Classifie la relation entre deux intervalles (bornes strictement comparees).
public static AllenRel Classify(Interval a, Interval b)
{
const double EPS = 1e-9;
double s1=a.Start, e1=a.End, s2=b.Start, e2=b.End;
bool SEq(double x, double y) => Math.Abs(x - y) < EPS;
if (SEq(s1,s2) && SEq(e1,e2)) return AllenRel.Equal;
if (SEq(e1,s2)) return AllenRel.Meets;
if (SEq(s1,e2)) return AllenRel.MetBy;
if (e1 < s2) return AllenRel.Before;
if (s1 > e2) return AllenRel.After;
if (SEq(s1,s2) && e1 < e2) return AllenRel.Starts;
if (SEq(s1,s2) && e1 > e2) return AllenRel.StartedBy;
if (SEq(e1,e2) && s1 > s2) return AllenRel.Finishes;
if (SEq(e1,e2) && s1 < s2) return AllenRel.FinishedBy;
if (s1 > s2 && e1 < e2) return AllenRel.During;
if (s1 < s2 && e1 > e2) return AllenRel.Contains;
if (s1 < s2 && e1 < e2 && e1 > s2) return AllenRel.Overlaps;
if (s1 > s2 && e1 > e2 && s1 < e2) return AllenRel.OverlappedBy;
return AllenRel.Equal;
}
// Inverse d'une relation (symetrie de l'algebre d'Allen).
public static AllenRel Inverse(AllenRel r) => r switch
{
AllenRel.Before => AllenRel.After, AllenRel.After => AllenRel.Before,
AllenRel.Meets => AllenRel.MetBy, AllenRel.MetBy => AllenRel.Meets,
AllenRel.Overlaps => AllenRel.OverlappedBy, AllenRel.OverlappedBy => AllenRel.Overlaps,
AllenRel.During => AllenRel.Contains, AllenRel.Contains => AllenRel.During,
AllenRel.Starts => AllenRel.StartedBy, AllenRel.StartedBy => AllenRel.Starts,
AllenRel.Finishes => AllenRel.FinishedBy, AllenRel.FinishedBy => AllenRel.Finishes,
_ => AllenRel.Equal
};
}
// --- Demonstration : 4 intervalles ---
var I1 = new Interval("I1", 0, 5); // [0,5]
var I2 = new Interval("I2", 5, 8); // meets I1
var I3 = new Interval("I3", 3, 7); // overlaps I1
var I4 = new Interval("I4", 1, 4); // during I1
var ivals = new[] { I1, I2, I3, I4 };
var sb = new StringBuilder();
sb.AppendLine("Matrice des relations d'Allen :");
sb.AppendLine($" {string.Join(" ", ivals.Select(i => i.Name))}");
foreach (var a in ivals)
{
sb.Append($"{a.Name} ");
foreach (var b in ivals)
sb.Append($"{AllenAlgebra.RelStr(AllenAlgebra.Classify(a,b)),-12} ");
sb.AppendLine();
}
Show("Allen", sb.ToString());
Show("Inverse de meets", AllenAlgebra.RelStr(AllenAlgebra.Inverse(AllenRel.Meets)));Allen: Matrice des relations d'Allen :
I1 I2 I3 I4
I1 equal meets overlaps contains
I2 met-by equal overlapped-by after
I3 overlapped-by overlaps equal overlapped-by
I4 during before overlaps equal Inverse de meets: met-byUn Simple Temporal Network (Dechter, Meiri & Pearl, 1991) est un graphe dont les arêtes contraignent la distance temporelle entre deux événements (timepoints). Une arête \(X \xrightarrow{[a,b]} Y\) impose \(a \leq t_Y - t_X \leq b\).
On encode chaque contrainte \([a,b]\) par deux arêtes orientées dans la matrice des distances \(D\) : - \(D[X,Y] \leq b\) (borne supérieure), - \(D[Y,X] \leq -a\) (borne inférieure, retournée).
Le STN est consistant ssi aucun cycle négatif n’apparaît après l’exécution de Floyd-Warshall (all-pairs shortest path). Un cycle négatif \(\Rightarrow\) contradiction temporelle insatisfiable.
// --- STN + Floyd-Warshall from-scratch ---
public sealed class STN
{
public List<string> Nodes { get; } = new();
public double[,] Dist; // matrice des distances
private int n => Nodes.Count;
public STN(IEnumerable<string> nodes)
{
Nodes = nodes.ToList();
int N = Nodes.Count;
Dist = new double[N, N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
Dist[i, j] = i == j ? 0 : double.PositiveInfinity;
}
public int Idx(string node) => Nodes.IndexOf(node);
// Contrainte a <= tY - tX <= b
public void AddConstraint(string x, string y, double a, double b)
{
int X = Idx(x), Y = Idx(y);
Dist[X, Y] = Math.Min(Dist[X, Y], b);
Dist[Y, X] = Math.Min(Dist[Y, X], -a);
}
// Floyd-Warshall : retourne true si consistant (pas de cycle negatif).
public (bool Consistent, double[,] D) FloydWarshall()
{
int N = n;
var D = (double[,])Dist.Clone();
for (int k = 0; k < N; k++)
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (D[i, k] + D[k, j] < D[i, j])
D[i, j] = D[i, k] + D[k, j];
bool consistent = true;
for (int i = 0; i < N; i++) if (D[i, i] < 0) consistent = false;
return (consistent, D);
}
public string Dump()
{
var sb = new StringBuilder();
sb.AppendLine($"STN ({n} nodes): {string.Join(", ", Nodes)}");
return sb.ToString();
}
}
// --- STN consistant : 3 evenements A, B, C ---
var stn1 = new STN(new[] { "X0", "A", "B", "C" });
stn1.AddConstraint("X0", "A", 1, 5); // A se produit entre t=1 et t=5
stn1.AddConstraint("X0", "B", 2, 8); // B entre t=2 et t=8
stn1.AddConstraint("A", "B", 1, 10); // B apres A, au moins 1 unite plus tard
stn1.AddConstraint("B", "C", 0, 4); // C apres B, dans les 4 unites
stn1.AddConstraint("X0", "C", 0, 15); // C avant t=15
var (ok1, D1) = stn1.FloydWarshall();
Show("STN 1", stn1.Dump());
Show("STN 1 consistant ?", ok1);
Show("Bornes X0->C", $"[{-D1[stn1.Idx("C"), stn1.Idx("X0")]}, {D1[stn1.Idx("X0"), stn1.Idx("C")]}]");
// --- STN INCONSISTANT : A avant B, B avant A (cycle negatif) ---
var stn2 = new STN(new[] { "A", "B" });
stn2.AddConstraint("A", "B", 5, 10); // B apres A d'au moins 5
stn2.AddConstraint("B", "A", 5, 10); // A apres B d'au moins 5 => contradiction
var (ok2, D2) = stn2.FloydWarshall();
Show("STN 2 (contradictoire)", stn2.Dump());
Show("STN 2 consistant ?", ok2);
Show("Diagonale (cycle negatif ?)", D2[0,0] < 0 ? $"OUI, D[A,A]={D2[0,0]} (contradiction)" : "non");STN 1: STN (4 nodes): X0, A, B, CSTN 1 consistant ?: TrueBornes X0->C: [2, 12]STN 2 (contradictoire): STN (2 nodes): A, BSTN 2 consistant ?: FalseDiagonale (cycle negatif ?): OUI, D[A,A]=-10 (contradiction)Deux actions duratives sont en exclusion mutuelle temporelle si elles ne peuvent pas se chevaucher (par exemple, deux actions utilisant exclusivement la même ressource). On détecte un conflit en testant si leurs intervalles planifiés sont en relation overlaps / during / contains / etc. (tout sauf before/after/meets/met-by/equal disjoint).
// --- Detection de conflits temporels ---
public static class TemporalMutex
{
// Deux intervalles sont-ils en conflit (chevauchement) ?
public static bool Conflicts(Interval a, Interval b)
{
var rel = AllenAlgebra.Classify(a, b);
// Conflit si les intervalles se chevauchent (pas strictement ordonnes).
return rel != AllenRel.Before && rel != AllenRel.After
&& rel != AllenRel.Meets && rel != AllenRel.MetBy;
}
// Verifie qu'un schedule (liste d'intervalles nommes) n'a pas de conflit 2-a-2.
public static List<(Interval, Interval)> FindConflicts(List<Interval> schedule)
{
var conflicts = new List<(Interval, Interval)>();
for (int i = 0; i < schedule.Count; i++)
for (int j = i + 1; j < schedule.Count; j++)
if (Conflicts(schedule[i], schedule[j]))
conflicts.Add((schedule[i], schedule[j]));
return conflicts;
}
}
// --- Schedule sans conflit ---
var sched1 = new List<Interval>
{
new Interval("weld", 0, 4),
new Interval("paint", 4, 7), // meets weld, pas de conflit
new Interval("inspect", 8, 10), // apres, pas de conflit
};
var conflicts1 = TemporalMutex.FindConflicts(sched1);
Show("Schedule 1 conflits", conflicts1.Count == 0 ? "AUCUN (OK)" : string.Join("; ", conflicts1.Select(c => $"{c.Item1.Name}<->{c.Item2.Name}")));
// --- Schedule avec conflit (meme machine) ---
var sched2 = new List<Interval>
{
new Interval("weld_A", 0, 5),
new Interval("weld_B", 3, 8), // overlaps weld_A => conflit (1 machine)
};
var conflicts2 = TemporalMutex.FindConflicts(sched2);
Show("Schedule 2 conflits", conflicts2.Count == 0 ? "AUCUN" : string.Join("; ", conflicts2.Select(c => $"{c.Item1.Name}<->{c.Item2.Name} [{c.Item1}] vs [{c.Item2}]")));Schedule 1 conflits: AUCUN (OK)Schedule 2 conflits: weld_A<->weld_B [weld_A[0,5]] vs [weld_B[3,8]]On assemble les briques précédentes : étant donné un ensemble de tâches (durée, précédences, demande en ressource) et une capacité de ressource, on calcule un schedule par heuristique gloutonne (liste de priorité + placement au plus tôt sous contraintes de précédence et de capacité). On produit ensuite un diagramme de Gantt ASCII.
Le scénario ci-dessous est construit avec contention de ressource — plus de tâches disponibles à un instant donné que la capacité n’en permet d’exécuter en parallèle. C’est précisément la situation qui justifie le scheduler : sans contrainte de capacité bindante, un simple placement au plus tôt (aveugle aux ressources) donnerait le même schedule, et la logique de vérification de capacité du scheduler ne servirait à rien.
C’est une variante simplifiée du RCPSP (Resource-Constrained Project Scheduling Problem, NP-difficile). L’heuristique gloutonne ne garantit pas l’optimalité (makespan minimal) mais produit un schedule réalisable en temps polynomial — la comparaison avec l’optimum known d’un benchmark (ex: PSPLIB) est laissée en exercice.
// --- Ordonnancement glouton RCPSP-lite + Gantt ASCII ---
public sealed class Task
{
public string Name { get; }
public double Duration { get; }
public double Demand { get; } // demande en ressource
public List<string> Predecessors { get; } = new();
public double Start { get; set; } = -1; // -1 = non planifiee
public double Finish => Start + Duration;
public Task(string name, double dur, double demand, params string[] preds)
{ Name = name; Duration = dur; Demand = demand; Predecessors = preds.ToList(); }
}
public sealed class Scheduler
{
public double Capacity { get; }
public Scheduler(double cap) { Capacity = cap; }
// Heuristique gloutonne : a chaque pas, planifier la tache disponible
// (predecesseurs finis) dont le placement au plus tot respecte la capacite.
// Les evenements temporels = fins de taches deja planifiees (grille discretee).
public void ScheduleAll(List<Task> tasks)
{
var done = new HashSet<string>();
double horizon = tasks.Sum(t => t.Duration) + 1;
// Grille de temps fine
var grid = Enumerable.Range(0, (int)Math.Ceiling(horizon) + 1).Select(i => (double)i).ToList();
while (done.Count < tasks.Count)
{
// Taches disponibles
var ready = tasks.Where(t => !done.Contains(t.Name)
&& t.Predecessors.All(p => done.Contains(p))).ToList();
if (ready.Count == 0) { /* deadlock cyclique */ break; }
// Par priorite : duree la plus longue d'abord (LPT heuristic)
ready = ready.OrderByDescending(t => t.Duration).ToList();
bool placed = false;
foreach (var t in ready)
{
// Trouver le plus tot start >= max(fins predecesseurs) tel que
// pendant [start, start+dur] la capacite est respectee a tout instant.
double earliest = t.Predecessors.Count == 0 ? 0
: t.Predecessors.Max(p => tasks.First(x => x.Name == p).Finish);
for (double s = earliest; s <= horizon; s += 1.0)
{
bool ok = true;
for (double tt = s; tt < s + t.Duration; tt += 1.0)
{
double used = tasks.Where(x => x.Start >= 0
&& tt >= x.Start && tt < x.Start + x.Duration).Sum(x => x.Demand);
if (used + t.Demand > Capacity + 1e-9) { ok = false; break; }
}
if (ok) { t.Start = s; done.Add(t.Name); placed = true; break; }
}
if (placed) break;
if (!placed && t.Start < 0) { /* impossible ce tour */ }
}
if (!placed) break; // aucun placement possible => arreter (evite boucle infinie)
}
}
// Diagramme de Gantt ASCII : lignes = taches, colonnes = unites de temps.
public string Gantt(List<Task> tasks)
{
double makespan = tasks.Max(t => t.Finish);
int W = (int)Math.Ceiling(makespan) + 1;
var sb = new StringBuilder();
sb.AppendLine($"Gantt (makespan = {makespan}, capacite = {Capacity}):");
sb.Append("task".PadRight(12) + " |");
for (int t = 0; t < W; t++) sb.Append((t % 10).ToString());
sb.AppendLine();
sb.AppendLine(new string('-', 14 + W));
foreach (var t in tasks)
{
sb.Append(t.Name.PadRight(12) + " |");
var row = new string('.', W).ToCharArray();
for (int k = 0; k < W; k++)
if (k >= t.Start && k < t.Start + t.Duration) row[k] = '#';
sb.AppendLine(new string(row));
}
// Usage de capacite par unite de temps
sb.Append("load".PadRight(12) + " |");
for (int k = 0; k < W; k++)
{
double used = tasks.Where(x => x.Start >= 0 && k >= x.Start && k < x.Start + x.Duration).Sum(x => x.Demand);
sb.Append(used == 0 ? "." : Math.Floor(used).ToString());
}
sb.AppendLine();
return sb.ToString();
}
}
// --- Scenario : atelier avec 2 machines (capacite = 2) ---
// Prong B (#3801) : 3 decoupes (A, B, C) sont disponibles des t=0 et demandent 1 machine
// chacune => demande initiale 3 > capacite 2. Le scheduler DOIT differer une tache : c'est
// la qu'il justifie son existence (resoudre la contention de ressource), la ou un schedule
// aveugle aux ressources placerait les 3 en parallele et violerait la capacite.
var tasks = new List<Task>
{
new Task("A", 3, 1), // decoupe A (3h, 1 machine)
new Task("B", 3, 1), // decoupe B
new Task("C", 3, 1), // decoupe C -> 3e tache en concurrence a t=0
new Task("D", 2, 1, "A"), // soudure apres A
new Task("E", 4, 2, "B", "C"), // assemblage apres B et C, demande les 2 machines
};
var sched = new Scheduler(2);
sched.ScheduleAll(tasks);
Show("Schedule atelier (contention de ressource)", sched.Gantt(tasks));
// --- Diagnostics : la contrainte de ressource est-elle active ? ---
double makespanRC = tasks.Max(t => t.Finish);
double demandAt0 = tasks.Where(t => t.Predecessors.Count == 0).Sum(t => t.Demand);
// Charge maximale par unite de temps (boucle explicite, evite le lambda imbrique CS9236)
double peakLoad = 0;
for (int kk = 0; kk <= (int)Math.Ceiling(makespanRC); kk++)
{
double loadK = tasks.Where(x => x.Start >= 0 && kk >= x.Start && kk < x.Start + x.Duration).Sum(x => x.Demand);
if (loadK > peakLoad) peakLoad = loadK;
}
// Borne inferieure precedence : plus longue chaine (chemin critique), ressources ignorees.
double CritLB(string name)
{
var tk = tasks.First(x => x.Name == name);
return tk.Predecessors.Count == 0 ? tk.Duration : tk.Duration + tk.Predecessors.Max(CritLB);
}
double lbRC = tasks.Max(t => CritLB(t.Name));
Show("Demande a t=0 (sans predecesseur)", $"{demandAt0} > capacite {sched.Capacity} -> schedule aveugle = INFEASIBLE");
Show("Charge maximale observee", $"{peakLoad} = capacite {sched.Capacity} (contrainte SATUREE)");
Show("Chemin critique (borne inferieure)", $"{lbRC}");
Show("Makespan glouton", $"{makespanRC}");
Show("Surcout resource (makespan - chemin critique)", $"{makespanRC - lbRC}");
Show("Realisable ?", tasks.All(t => t.Start >= 0) ? "OUI (toutes planifiees)" : "NON (certaines non placees)");Schedule atelier (contention de ressource): Gantt (makespan = 10, capacite = 2):
task |01234567890
-------------------------
A |###........
B |###........
C |...###.....
D |...##......
E |......####.
load |2222212222.Demande a t=0 (sans predecesseur): 3 > capacite 2 -> schedule aveugle = INFEASIBLECharge maximale observee: 2 = capacite 2 (contrainte SATUREE)Chemin critique (borne inferieure): 7Makespan glouton: 10Surcout resource (makespan - chemin critique): 3Realisable ?: OUI (toutes planifiees)Le scheduler glouton produit ici un makespan de 10, alors que le chemin critique (la plus longue chaîne de précédence, en ignorant les ressources) ne vaut que 7. Cet écart de 3 unités est entièrement dû à la contention de ressource : c’est la trace, dans la sortie, du travail distinctif du scheduler.
Trois signaux le confirment dans la sortie ci-dessus :
used + demand > capacity a effectivement rejeté des placements (sinon la charge resterait strictement inférieure à la capacité).C’est exactement la situation que le scheduler RCPSP est censé résoudre — niveler la demande sous la capacité en différant des tâches — et qui serait invisible sur une instance sans contention (makespan égal au chemin critique, boucle de capacité jamais rejetante). L’heuristique LPT (Longest Processing Time first) fixe l’ordre de priorité ; elle n’est pas optimale (RCPSP est NP-difficile) — l’exercice 3 propose de comparer au makespan optimal obtenu par énumération des ordres topologiques.
Les Sections 1 à 5 ont assemblé les briques d’un solveur from-scratch : modèle STRIPS duratif (Partie 1), algèbre d’intervalles d’Allen (Partie 2), réseau temporel simple + Floyd-Warshall (Partie 3), détection de conflits (Partie 4), ordonnancement glouton RCPSP-lite (Partie 5). Cette approche est nécessaire à la compréhension : vous savez maintenant ce que fait un solveur temporel et comment chaque pièce s’articule.
Mais le glouton de la Partie 5 a une limite de fond : il ne prouve pas l’optimalité du schedule qu’il produit. Sur l’instance de l’atelier (5 tâches A–E, capacité 2), il atteint ici le meilleur makespan possible — mais il ne le sait pas : aucun certificat n’accompagne le plan. La seule garantie théorique classique du glouton de liste LPT — au plus \(4/3 - 1/(3m)\) fois l’optimum (Graham 1969) — vaut pour P||Cmax (tâches indépendantes sur machines identiques) et ne se transfère pas au RCPSP démontré ici (précédences + demandes variables) : dans ce cadre, le glouton ne porte aucune borne d’approximation propre, et l’écart à l’optimum n’est pas contrôlé.
La Tranche 2 introduit un moteur SOTA : Google.OrTools CP-SAT (le solveur de programmation par contraintes de Google, branche .NET officielle). CP-SAT combine propagation de contraintes (filtre le domaine des variables) et recherche arborescente (branch-and-bound). Il est :
Optimal) atteste que l’objectif atteint ne peut pas être amélioré.Google.OrTools, intégration native via #r "nuget: ..." en .NET Interactive.L’objectif de la Tranche 2 est de passer from-scratch -> CP-SAT sur la même instance, sans reformuler le problème (mêmes tâches, mêmes ressources, mêmes durées). Sur cette instance précise, l’apport du moteur n’est pas un makespan plus court — le glouton était déjà optimal — mais la preuve d’optimalité et l’explication de l’écart à la borne inférieure : la certification, pas l’amélioration.
La Partie 5 ci-dessus résout l’ordonnancement de l’atelier (5 tâches A/B/C/D/E, capacité 2 machines) avec un scheduler glouton (heuristique LPT, placement au plus tôt respectant la capacité). Le jumeau Python, lui, délègue ce type de problème à OR-Tools CP-SAT (cellules 26-29). Pour que le C# atteigne lui aussi le moteur de production de son écosystème — sans abandonner le glouton qui enseigne les mécanismes — cette seconde tranche résout la même instance via Google.OrTools (CP-SAT natif .NET), avec la contrainte de ressource cumulative AddCumulative.
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 instance RCPSP que la Partie 5 (cellule 12), via Google.OrTools CP-SAT .NET.
using Google.OrTools.Sat;
using System.Collections.Generic;
using System.Linq;
// --- Instance : atelier 5 taches, capacite 2 (meme que cellule 12) ---
var jobs = new (string Name, int Dur, int Demand, string[] Preds)[] {
("A", 3, 1, new string[]{}),
("B", 3, 1, new string[]{}),
("C", 3, 1, new string[]{}),
("D", 2, 1, new[]{"A"}),
("E", 4, 2, new[]{"B","C"}),
};
int CAPACITY = 2;
int horizon = jobs.Sum(j => j.Dur);
Console.WriteLine("Tranche 2 : RCPSP via Google.OrTools CP-SAT (moteur .NET natif)");
Console.WriteLine(new string('=', 60));
Console.WriteLine($"Taches: {jobs.Length} | Capacite: {CAPACITY} | Horizon: {horizon}");
Console.WriteLine("Makespan glouton LPT (Partie 5, cellule 12) = 10");
var model = new CpModel();
var starts = new Dictionary<string, IntVar>();
var ends = new Dictionary<string, IntVar>();
// Contrainte de ressource cumulative (AddCumulative builder fluent).
var cum = model.AddCumulative(CAPACITY);
foreach (var j in jobs)
{
starts[j.Name] = model.NewIntVar(0, horizon, $"s_{j.Name}");
ends[j.Name] = model.NewIntVar(0, horizon, $"e_{j.Name}");
var iv = model.NewIntervalVar(starts[j.Name], j.Dur, ends[j.Name], $"iv_{j.Name}");
cum.AddDemand(iv, j.Demand); // chaque tache consomme sa demande sur la capacite
}
// (1) Precedences : une tache demarre apres la fin de ses predecesseurs.
foreach (var j in jobs)
foreach (var p in j.Preds)
model.Add(starts[j.Name] >= ends[p]);
// (2) Objectif : minimiser le makespan = max de tous les ends.
IntVar makespan = model.NewIntVar(0, horizon, "makespan");
model.AddMaxEquality(makespan, jobs.Select(j => (LinearExpr)ends[j.Name]).ToList());
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)} (glouton LPT = 10, chemin critique = 7)");
Console.WriteLine($"Gain vs glouton : {10 - solver.Value(makespan)} unite(s) -> le glouton LPT etait DEJA optimal");
Console.WriteLine($"Wall-clock solve : {solver.WallTime():F3}s | branches: {solver.NumBranches()}");
Console.WriteLine("\nSchedule CP-SAT optimal :");
foreach (var j in jobs)
{
var predStr = j.Preds.Length == 0 ? "-" : string.Join(",", j.Preds);
Console.WriteLine($" {j.Name}: [{solver.Value(starts[j.Name])}-{solver.Value(ends[j.Name])}] dur={j.Dur} dem={j.Demand} apres=[{predStr}]");
}
Console.WriteLine("\nApport du moteur de production :");
Console.WriteLine("- Le glouton LPT (Partie 5) trouvait 10 SANS preuve d'optimalite.");
Console.WriteLine("- CP-SAT PROUVE que 10 est optimal (statut Optimal, branches explorees).");
Console.WriteLine("- Pourquoi le chemin critique (7) est inaccessible : E (demande 2) ne peut");
Console.WriteLine(" demarrer a t=3 apres B et C qu'en occupant toutes les ressources, donc A doit");
Console.WriteLine(" etre differe au-dela de E -> makespan remonte a 10. La borne 7 ignore la ressource.");
Console.WriteLine("Le moteur certifie le resultat du glouton et borne l'ecart a la relaxation.");Tranche 2 : RCPSP via Google.OrTools CP-SAT (moteur .NET natif)
============================================================
Taches: 5 | Capacite: 2 | Horizon: 15
Makespan glouton LPT (Partie 5, cellule 12) = 10
Statut CP-SAT : Optimal
Makespan OPTIMAL = 10 (glouton LPT = 10, chemin critique = 7)
Gain vs glouton : 0 unite(s) -> le glouton LPT etait DEJA optimal
Wall-clock solve : 0,019s | branches: 12
Schedule CP-SAT optimal :
A: [0-3] dur=3 dem=1 apres=[-]
B: [0-3] dur=3 dem=1 apres=[-]
C: [3-6] dur=3 dem=1 apres=[-]
D: [3-5] dur=2 dem=1 apres=[A]
E: [6-10] dur=4 dem=2 apres=[B,C]
Apport du moteur de production :
- Le glouton LPT (Partie 5) trouvait 10 SANS preuve d'optimalite.
- CP-SAT PROUVE que 10 est optimal (statut Optimal, branches explorees).
- Pourquoi le chemin critique (7) est inaccessible : E (demande 2) ne peut
demarrer a t=3 apres B et C qu'en occupant toutes les ressources, donc A doit
etre differe au-dela de E -> makespan remonte a 10. La borne 7 ignore la ressource.
Le moteur certifie le resultat du glouton et borne l'ecart a la relaxation.La comparaison RCPSP-lite glouton (Partie 5) versus Google.OrTools CP-SAT (Tranche 2) porte sur la même instance (5 tâches A–E, une ressource de capacité 2). Lecture honnête de la sortie mesurée ci-dessus :
Optimal (12 branches, 0,019 s) certifie que 10 est le meilleur makespan réalisable — le glouton produisait 10 sans savoir que c’était le mieux. Le moteur explique aussi pourquoi le chemin critique (7) est inatteignable : E mobilise les 2 machines entières, donc la borne inférieure « sans ressource » n’est pas réalisable (voir la sortie détaillée ci-dessus).Règle d’or : la Tranche 1 from-scratch est la fondation pédagogique (comprendre comment marche un solveur avant d’en utiliser un) ; la Tranche 2 est la certification et le passage à l’échelle (prouver l’optimalité, viser les instances réelles).
Où aller ensuite ? Google.OrTools est aussi utilisé en Python (Planners-7-OR-Tools.ipynb) et en C# (Planners-7-OR-Tools-Csharp.ipynb). Pour les très grandes instances ou certains critères continus, les alternatives sont les solveurs MIP (CBC, SCIP) ou les métaheuristiques — voir MyIA.AI.Notebooks/Search/MetaGeneticSharp pour la filière métaheuristique C#.
Ce twin C# a reconstruit from-scratch les 4 piliers de la planification temporelle :
at start/over all/at end, effets (Partie 1).Le notebook Python original atteint ces concepts via unified_planning + ortools CP-SAT ; le twin C# les rend transparents et exécutables sans dépendance externe.
// Exercice 1 : Table de composition d'Allen
// TODO etudiant : implementez la table de composition COMPOSE(R1, R2) retourmant
// l'ENSEMBLE des relations possibles entre I1 et I3 sachant R1(I1,I2) et R2(I2,I3).
// Indice : Allen 1983, Table III. Pour before o before = {before}, etc.
// Etape 1 : representer la table par un dictionnaire (R1,R2) -> HashSet<AllenRel>.
// Etape 2 : remplir au moins before/after/meets/equals (les cas les plus frequents).
public static HashSet<AllenRel> Compose(AllenRel r1, AllenRel r2)
{
// TODO etudiant
var result = new HashSet<AllenRel>();
// Indice : before o before = {before}. Commencez par ce cas.
return result;
}
Show("Compose(before,before)", string.Join(",", Compose(AllenRel.Before, AllenRel.Before).Select(AllenAlgebra.RelStr)) + " (a completer)");Compose(before,before): (a completer)// Exercice 2 : Deadline dans le STN
// TODO etudiant : ajoutez une contrainte de deadline (t_C <= T_max) au STN1
// et verifiez la consistan ce. Indice : AddConstraint("X0", "C", 0, T_max).
// Etape 1 : choisir un T_max (ex: 12). Etape 2 : re-invoquer FloydWarshall.
public static bool DeadlineConsistent(STN stn, string node, double deadline)
{
// TODO etudiant
return true; // retournez vrai si le STN + deadline reste consistant
}
Show("Deadline a 12 (a completer)", DeadlineConsistent(stn1, "C", 12.0));Deadline a 12 (a completer): True// Exercice 3 : Optimalite du makespan (comparaison brute-force)
// TODO etudiant : pour le scenario atelier (5 taches), calculez le makespan OPTIMAL
// par enumeration des permutations valides (precedence-respecting topological orders)
// et comparez avec le makespan glouton ci-dessus.
// Indice : enumerer les ordres topologiques, pour chacun simuler ScheduleAll, garder min.
// Etape 1 : enumerer les ordres topologiques des taches. Etape 2 : evaluer chacun.
public static double OptimalMakespan(List<Task> tasks, double capacity)
{
// TODO etudiant
return double.PositiveInfinity; // retournez le makespan minimal
}
Show("Makespan optimal (a completer)", OptimalMakespan(tasks, 2.0));Makespan optimal (a completer): ∞Twin C# du notebook Python Planners-8-Temporal.ipynb. Marathon parité .NET ⇄ Python (#4956, Prong B). From-scratch BCL .NET, 0 NuGet, 0 unified_planning / ortools.