Jeder Zuschnittoptimierer nennt sich „optimal“. Wir veröffentlichen die Zahlen: drei Sätze von Testaufgaben, ein unabhängiges Orakel für die kleinen, beweisbare untere Schranken für die aus der Werkstatt und das Roh-JSON mit allen Parametern des Laufs. Letzter Lauf: 2026-09-17, Kern 6edd4c42bb6b.
▶ Rechner öffnenKeine einzelne Formel, sondern eine Suche mit mehreren Strategien auf derselben Aufgabe: die schnellen Heuristiken (FFD, BFD, FFI, Sortierung nach Anzahl), dynamische Programmierung über Schnittmuster, gemischtes FFD und GRASP mit festem Seed, Vorausschau (Look-ahead) sowie zwei exakte Suchen mit begrenztem Budget — eine für wenige verschiedene Längen, eine für kurze Listen. Jeder Kandidat durchläuft eine lokale Verbesserung (Leeren von Stäben und Tausche), dann gewinnt die Lösung mit dem wenigsten Material, danach mit den wenigsten Stäben. Die Budgets zählen Operationen, keine Sekunden — das Ergebnis ist auf einem schnellen wie auf einem langsamen Server identisch. Wir zeigen es als „beste gefundene Lösung“; „bewiesen optimal“ sagen wir nur, wenn sie die mathematische untere Schranke der Aufgabe erreicht.
Drei Sätze synthetischer Aufgaben mit festem Seed (20260917), erzeugt von tests/benchmark_optimal.py. (A) Exakt prüfbar: 200 kleine Aufgaben (2–4 Stäbe 60–130, 2–7 Teile 10–65, Sägeblatt 0/1/3) mit unabhängigem Orakel — vollständige Aufzählung aller Zuordnungen. (B) Stahlbau: 300 Schnittlisten — Stäbe 6000 mm (90 davon mit Mix 6000 + 12000), 8–30 verschiedene Längen 250–5800 mm zu je 1–20 Stück, Sägeblatt 3 mm, Min. Rest 300 mm; im Schnitt 204 Teile pro Aufgabe (von 55 bis 393). (C) Skalierung: 50, 200, 500, 1000, 2000 Teile × 3 Aufgaben. Alle Modi laufen in einem Prozess auf einer Maschine; gemessen wird mit time.perf_counter direkt um den Aufruf des Kerns.
Bei den kleinen Aufgaben kennt das Orakel das wahre Optimum. „Volle Übereinstimmung“ verlangt auch dieselbe Verteilung der Reste auf die Stäbe; „Material + Stäbe“ ist das, was Sie tatsächlich bezahlen; „Min. Stäbe“ — ob die kleinstmögliche Stabzahl erreicht wurde.
| Algorithmus | Volle Übereinstimmung mit Orakel | Optimum Material + Stäbe | Min. Stäbe | Medianzeit (s) |
|---|---|---|---|---|
| Optimal | 100 % | 100 % | 100 % | <0,01 |
| FFD | 42,5 % | 74,5 % | 84 % | <0,01 |
| BFD | 42,5 % | 74,5 % | 84 % | <0,01 |
| FFI | 32,5 % | 62,5 % | 76,5 % | <0,01 |
| LOOK | 63 % | 80,5 % | 88,5 % | <0,01 |
| GRASP | 64 % | 79,5 % | 88 % | <0,01 |
| SFFD | 65,5 % | 80,5 % | 88,5 % | <0,01 |
| Seq | 31 % | 59,5 % | 59,5 % | <0,01 |
Hier ist das wahre Optimum unbekannt — wir vergleichen mit einer unteren Schranke: L1 = ⌈Σ(Länge + Sägeblatt) / (6000 + Sägeblatt)⌉ und der stärkeren L2 nach Martello–Toth, die die Teile über 3000 mm zählt, die sich keinen Stab teilen können. „Bewiesen optimal“ = die Lösung erreicht die Schranke. Beim Mix 6000 + 12000 rechnen wir in 6-m-Äquivalenten (ein 12-m-Stab = 2), und es gilt nur L1 — die Schranke ist dort lockerer. „Optimal“ ist bei 38,3 % der Aufgaben strikt besser als FFD, bei 61,7 % gleich und bei 0 % schlechter; gegenüber BFD besser bei 39,3 %. Über den ganzen Satz gegenüber FFD gesparte Stäbe: 973. Nur Aufgaben mit einer Stablänge (210 Stück): bewiesen optimal 31,4 %, mittlerer Abstand zur Schranke 1,67 Stäbe, maximal 8.
| Algorithmus | Ø Stäbe (6-m-Äquiv.) | Ø Verschnitt | Bewiesen optimal | Ø Abstand (Stäbe) | Max. Abstand | Medianzeit (s) | 95. Perzentil (s) |
|---|---|---|---|---|---|---|---|
| Optimal | 110,7 | 7,7 % | 26,3 % | 1,79 | 12 | 3,85 | 11,34 |
| FFD | 114,0 | 10,4 % | 21,3 % | 5,04 | 47 | 0,03 | 0,08 |
| BFD | 114,0 | 10,5 % | 21,3 % | 5,05 | 47 | 0,03 | 0,08 |
| FFI | 114,3 | 10,7 % | 20,7 % | 5,35 | 47 | 0,04 | 0,11 |
| GRASP | 114,0 | 10,4 % | 21,3 % | 5,02 | 47 | 0,23 | 0,66 |
| SFFD | 114,0 | 10,4 % | 20,7 % | 5,06 | 47 | 0,15 | 0,47 |
| Seq | 120,3 | 15,2 % | 6,3 % | 11,35 | 49 | 0,01 | 0,02 |
Medianzeit in Sekunden über 3 Aufgaben je Größe (nur 6000er Stäbe, dieselben Parameter wie in B). Der Kern hat eingebaute Grenzen: die Vorausschau läuft bis 240 Teile, die exakten Suchen bis 600 — deshalb wächst die Zeit nicht linear mit der Größe. Größen, bei denen „Optimal“ 10 s überschreitet: —.
| Teile | Optimal | FFD | BFD | FFI | LOOK | GRASP | SFFD | Seq |
|---|---|---|---|---|---|---|---|---|
| 50 | 0,21 | <0,01 | <0,01 | <0,01 | 0,10 | 0,02 | 0,01 | <0,01 |
| 200 | 6,74 | 0,01 | 0,03 | 0,02 | 2,90 | 0,26 | 0,16 | 0,01 |
| 500 | 4,02 | 0,24 | 0,25 | 0,25 | 0,17 | 1,49 | 0,94 | 0,03 |
| 1000 | 5,86 | 0,28 | 0,24 | 0,30 | 0,31 | 1,52 | 1,42 | 0,08 |
| 2000 | 7,61 | 0,31 | 0,68 | 0,31 | 0,38 | 4,17 | 3,69 | 0,44 |
Die Aufgaben sind zufällig und synthetisch. Gleichverteilte Längen von 250–5800 mm sind härter als eine typische Schnittliste — die meisten Teile über 3 m können sich keinen Stab teilen, daher ist der Verschnitt bei allen Algorithmen hoch; entscheidend ist der Unterschied zwischen ihnen, nicht der Absolutwert. Ein Abstand zur unteren Schranke ist keine bewiesene Suboptimalität — das wahre Optimum liegt irgendwo zwischen Schranke und gefundener Lösung. Die Zeiten stammen von einer Maschine (Python 3.14.0); der Server kann schneller oder langsamer sein. Reale Aufträge sind anders — der sicherste Test ist Ihre eigene Schnittliste.
Das Skript tests/benchmark_optimal.py (nur Standardbibliothek + Kern) ist Teil des Anwendungscodes, der nicht öffentlich ist — den Test führen wir selbst aus. Öffentlich ist das Rohergebnis: benchmark-results.json (backend/benchmark_results.json im Code); die Seite liest ihre Zahlen beim Start aus dieser Datei — nichts wird von Hand eingetragen. Darin stehen Seed 20260917, die Parameter des Aufgabengenerators, die Limits und die SHA-256 des Kerns 6edd4c42bb6b7ba0b5f9ee2f6d1b5f11e054c90d2c972b9a961082d945c91f4c. Der volle Lauf (py -3 tests/benchmark_optimal.py) dauert etwa 30 Minuten. Der Algorithmus „Optimal“ ist in den Plänen Hobby und Pro enthalten; der kostenlose Plan rechnet mit FFD und BFD aus denselben Tabellen.
Weil die untere Schranke nicht das Optimum selbst ist. Bei einer Aufgabe mit vielen Teilen über 3 m unterschätzt die Schranke die nötigen Stäbe, sodass eine Lösung optimal sein kann, ohne dass wir es beweisen können. Im Satz A, wo das Optimum exakt bekannt ist, liegt die Übereinstimmung bei 100 %.
Bei zufälligen Längen füllen sich die meisten Stäbe auf offensichtliche Weise, und jede vernünftige Heuristik findet das. Der Unterschied entsteht bei „knappen“ Aufgaben mit Kombinationen aus 2–3 Teilen, die sequenzielle Algorithmen nie sehen — dort gewinnt „Optimal“ ein bis zwei Stäbe, und pro Tonne Stahl ist das echtes Geld.
Nein — Skript und Kern sind Teil des Anwendungscodes und nicht öffentlich zugänglich. Öffentlich ist das Roh-JSON unter /benchmark-results.json mit Seed, Generatorparametern und den Ergebnissen je Aufgabe; jede Zahl in den Tabellen stammt daraus. Die sicherste Prüfung ist Ihre eigene Schnittliste: Vergleichen Sie „Optimal“ (Hobby/Pro) mit FFD/BFD im Rechner.