Die SPT-Regel verständlich erklärt

Arbeitet eine einzelne Maschine Aufträge nacheinander ab, lassen sich alle im Durchschnitt am schnellsten fertigstellen, wenn die kürzesten zuerst drankommen. Das gilt, solange alle Aufträge von Anfang an bereitliegen und nur die durchschnittliche Fertigstellung zählt; ein einfacher Tauschbeweis zeigt, dass es dann keine bessere Reihenfolge gibt. Diese Seite erklärt das zuerst ohne Formeln und danach für Fachleute mit Modell, Beweis, Messwerten und Grenzen. Die zugehörige Demo eröffnet eine Reihe über klassische Reihenfolgeplanung.

Zuletzt aktualisiert: 28. Oktober 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Eine Maschine, viele Aufträge

Stellen Sie sich eine kleine Druckerei vor, in der alle Aufträge über eine einzige Maschine laufen. Jeder Auftrag braucht eine bestimmte Zeit, die Bearbeitungszeit: Ein Aushang ist schnell gedruckt, ein dicker Katalog dauert lange. Die Maschine bearbeitet immer nur einen Auftrag auf einmal, die anderen warten. Wer in der Reihenfolge hinten steht, muss abwarten, bis alle vor ihm fertig sind.

Die Frage lautet: In welcher Reihenfolge sollte man die Aufträge abarbeiten? Solche Fragen der Reihenfolgeplanung heißen im Englischen Scheduling. Gemessen wird hier, wie lange es im Durchschnitt dauert, bis ein Auftrag fertig ist, gerechnet ab dem Start der ersten Arbeit. Diese Zeit bis zur Fertigstellung besteht aus der Wartezeit plus der eigenen Bearbeitungszeit. Die eigene Bearbeitungszeit ändert sich mit der Reihenfolge nicht, also kommt es allein auf das Warten an. Im Folgenden gilt: nur eine Maschine, alle Aufträge liegen von Anfang an bereit, und es zählt allein diese durchschnittliche Zeit bis zur Fertigstellung.

Kurze zuerst, und warum nichts Besseres geht

Die einfache Regel heißt SPT, nach dem englischen „Shortest Processing Time first“: Als Nächstes kommt immer der Auftrag mit der kürzesten Bearbeitungszeit dran. Das Bild dazu kennen Sie von der Supermarktkasse. Wer nur eine Packung Milch hat, wird gern vorgelassen, denn das kostet den Wartenden mit dem vollen Wagen nur die kurze Zeit, die das Kassieren der Milch dauert, erspart dem anderen aber das Warten auf den ganzen vollen Wagen.

Dass keine andere Reihenfolge besser sein kann, zeigt ein Tauschargument. Nehmen Sie irgendeine Reihenfolge, in der ein langer Auftrag unmittelbar vor einem kurzen steht, und vertauschen Sie genau diese beiden. Für alle anderen Aufträge ändert sich nichts, denn die beiden belegen zusammen dieselbe Zeit wie vorher, und alles davor und danach beginnt und endet zur selben Zeit.

Ein Beispiel in Worten: Ein Katalog dauert lange, ein Aushang ist schnell gedruckt. Läuft zuerst der Katalog, wartet der Aushang die ganze lange Zeit mit. Läuft zuerst der Aushang, wartet der Katalog nur die kurze Zeit des Aushangs. Allgemein gilt: Der kurze Auftrag ist nach dem Tausch früher fertig, und zwar um die Dauer des langen. Der lange Auftrag ist später fertig, aber nur um die Dauer des kurzen. Weil der lange Auftrag länger dauert als der kurze, überwiegt der Gewinn.

Das gilt für jedes solche Paar. Solange irgendwo ein langer Auftrag vor einem kürzeren steht, lässt sich die Reihenfolge also verbessern. Die beste Reihenfolge gibt es sicher, denn es sind nur endlich viele, und sie kann keinen solchen Fall enthalten. Also sind in ihr die Aufträge nach Dauer aufsteigend geordnet. Man nennt die Regel deshalb beweisbar optimal: Unter den genannten Annahmen ist sie nicht nur meistens gut, sondern nachweislich die beste.

Wo die Regel aufhört

Der Beweis stützt sich auf Annahmen, die bisher stillschweigend galten: Es gibt nur eine Maschine, alle Aufträge sind gleich wichtig, es gibt keine Abgabefristen, und die Bearbeitungszeit hängt nicht davon ab, was vorher lief. Die Demo prüft die letzte dieser Annahmen.

Ein Beispiel aus der Werkstatt: Die Aufträge gehören zu Familien, etwa gleiche Werkstoffe oder Formate. Wechselt die Maschine von einer Familie zur nächsten, muss sie umgerüstet werden. Diese Rüstzeit steckt in keiner Bearbeitungszeit. SPT kennt sie nicht und sortiert nur nach der Dauer. Dann trägt der Tauschbeweis nicht mehr, denn ein Tausch ändert auch, wie oft umgerüstet wird. In der Demo liegt SPT dadurch messbar schlechter als die tatsächlich beste Reihenfolge, und der Abstand wächst, je länger das Umrüsten dauert. Wie groß er ist, steht im Fachteil.

Zählt etwas anderes als die durchschnittliche Fertigstellung, braucht es andere Regeln. Geht es um Abgabefristen und darum, die größte Verspätung klein zu halten oder möglichst wenige Aufträge zu verspäten, sortiert man nach der Frist und nicht nach der Dauer, denn sonst käme ein kurzer Auftrag mit fernem Termin vor einem langen mit nahem Termin dran, und der lange würde zu spät fertig. Sind manche Aufträge wichtiger als andere, muss man Wichtigkeit und Dauer gemeinsam betrachten. Mit mehreren Maschinen kommt die Frage dazu, welcher Auftrag auf welche Maschine gehört. Für jede dieser Änderungen gibt es eine eigene Regel, die in den weiteren Demos dieser Reihe behandelt wird.

Wie ernst ist das Modell zu nehmen?

Die Aufträge der Demo sind künstlich erzeugt: Bearbeitungszeiten, Familien und Rüstzeiten sind zufällig oder frei gewählt, keine Messung an einer echten Werkstatt. Die Demo zeigt, wie das Tauschargument wirkt und wo es endet, nicht wie eine bestimmte Druckerei arbeitet. Als Gegenprobe probiert sie bei kleinen Aufgaben alle denkbaren Reihenfolgen durch und vergleicht. Bei größeren Aufgaben ist das nicht mehr machbar, weil jeder weitere Auftrag die Zahl der Reihenfolgen vervielfacht; dort verlässt sie sich auf den Beweis.

Was Sie mitnehmen: Arbeitet eine einzelne Maschine oder Person Aufträge nacheinander ab und kommt es nur darauf an, dass im Durchschnitt alle schnell fertig werden, ordnen Sie nach Dauer, kurze zuerst. Sobald Umrüsten, Fristen oder unterschiedliche Wichtigkeit ins Spiel kommen, prüfen Sie, ob diese Regel noch passt. Bedenken Sie auch die Gerechtigkeit: Die langen Aufträge kommen zwangsläufig zuletzt dran, und in einem laufenden Betrieb, den die Demo nicht abbildet, könnten sie bei ständig neuen kurzen Aufträgen sehr lange warten.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst die formale Beschreibung der Demo zusammen; die vollständige Fassung steht im Expander „📐 Mathematische Formulierung“ der Demo.

• Problem: \(n\) Aufträge mit Bearbeitungszeit \(p_j\) auf einer Maschine, Ziel ist die Summe der Fertigstellungszeiten \(\sum_j C_j\). In der α|β|γ-Notation der Scheduling-Literatur ist das \(1||\sum C_j\) (α: eine Maschine, β: keine Nebenbedingungen, γ: das Ziel). Keine Präzedenzen, ein Auftrag ist eine Operation.
• Vehikel Neutral: Bearbeitungszeiten \(p_j \sim U(1, 100)\). Fälligkeiten (TF/RDD-Schema) und Gewichte sind für Folgestücke erzeugt, in diesem Stück aber unbenutzt.
• Vehikel Werkstatt/Logistik: dieselben Aufträge, aber jeder gehört zu einer Familie, und ein Familienwechsel kostet eine feste Rüstzeit. Rüstzeit 0 fällt exakt auf das neutrale Vehikel zurück (per Test belegt). Die Demo führt dafür einen zweiten, unabhängigen Instanzgenerator ein, damit die Annahme „Bearbeitungszeit unabhängig von der Reihenfolge“ wirklich verletzt wird und nicht nur ein Regler sie abschaltet.
• Regler: Zahl der Aufträge (2 bis 60), Vehikel, bei Werkstatt/Logistik zusätzlich Rüstzeit und Zahl der Familien, Zufalls-Seed der Instanz und Zufalls-Seed der Kette. Der Zufalls-Seed der Kette steuert nur die zufällige Vergleichsreihenfolge; SPT selbst ist deterministisch.

Die Formeln

Eine Reihenfolge \(\pi\) legt die Fertigstellungszeit jedes Auftrags fest, nämlich die Summe der Bearbeitungszeiten aller Aufträge, die nicht später als er an der Reihe sind:

\[C_j = \sum_{k: \pi(k) \le \pi(j)} p_k\]

Satz. SPT (aufsteigend nach \(p_j\) sortieren, \(O(n \log n)\)) minimiert \(\sum_j C_j\). Beweis (Vertauschungsargument). Stehen in einer Reihenfolge zwei benachbarte Aufträge \(i\) vor \(j\) mit \(p_i > p_j\), und ist \(t\) die Summe der Bearbeitungszeiten davor, so gilt vorher \(C_i = t + p_i\) und \(C_j = t + p_i + p_j\), nachher \(C_j' = t + p_j\) und \(C_i' = t + p_j + p_i\). Alle anderen Fertigstellungszeiten bleiben gleich. Die Summe sinkt um genau

\[(C_i + C_j) - (C_i' + C_j') = p_i - p_j\]

und das ist positiv. Durch wiederholtes Vertauschen solcher Paare (wie beim Blasensortieren) erreicht man in endlich vielen Schritten eine aufsteigende Reihenfolge, und jeder Schritt senkt die Summe streng. Eine Reihenfolge mit einem solchen Paar ist also nicht optimal. Da es nur endlich viele Reihenfolgen gibt, existiert ein Optimum, und es ist aufsteigend sortiert. Aufträge gleicher Dauer lassen sich vertauschen, ohne den Wert zu ändern, deshalb sind alle aufsteigenden Reihenfolgen gleich gut.

Als Kennzahl nutzt die Demo den Abstand einer Reihenfolge zu SPT in Prozent, also \(100 \cdot (\text{Summe} - \text{Summe}_{\text{SPT}}) / \text{Summe}_{\text{SPT}}\). Eine gleichwertige Sicht, die die Demo nicht zeigt (elementare Umformung): Der Auftrag an Position \(k\) zählt in \(n-k+1\) Fertigstellungszeiten mit, nämlich in seiner eigenen und in denen aller späteren. SPT gibt den kleinen Bearbeitungszeiten damit die großen Gewichte.

Gegenprobe und Umsetzung

Als unabhängige Gegenprobe zählt die Demo für kleine \(n\) alle \(n!\) Reihenfolgen durch (Vollaufzählung, nur bis \(n \approx 9\) nutzbar). Darüber vertraut sie dem Beweis, nicht einer weiteren Aufzählung. Dasselbe gibt es für die Rüstzeit-Variante: eine Vollaufzählung des echten Optimums mit Rüstzeiten. Weitere Absicherungen laut README: ein Konsistenztest (Rüstzeit 0 liefert dieselbe Zielfunktion wie das neutrale Vehikel), eine von Hand nachgerechnete Instanz mit drei Aufträgen, und alle Zahlen der App-Texte sind als Tests hinterlegt.

Befunde

Alle Zahlen stammen aus der README der Demo. Die Mittelwerte beziehen sich auf feste Instanzen mit den Zufalls-Seeds 100000–100004, bei den Vergleichsreihenfolgen mit je 3 Ketten-Seeds, der Bezug steht jeweils in der Zeile. Rechenzeiten hängen vom Rechner ab.

Frage	Befund
Wie viel schlechter sind andere Reihenfolgen als SPT?	Standardfall mit 20 Aufträgen: Die längste-zuerst-Reihenfolge (LPT) liegt im Mittel 97,6 % und eine zufällige Reihenfolge 49,7 % über SPT.
Trifft SPT das Minimum der Vollaufzählung?	Ja, 100 % Trefferquote bei n = 2 bis 9 auf den 5 festen Instanzen je Größe; kein einziger Fall, in dem SPT das Minimum verfehlt.
Wie teuer ist die Vollaufzählung?	Einmal gemessen auf einer Instanz (Zufalls-Seed 35), rechnerabhängig: Bei n = 9 braucht die Vollaufzählung über 1000 ms, SPT rund 0,005 ms, also über 200.000-mal schneller; dieser Faktor ist keine allgemeine Größenordnung. Der Test belegt nur, dass die Vollaufzählung bei neun Aufträgen mehr als zwei Zehntelsekunden dauert. \(n!\) wächst schneller als jede Potenz von \(n\), \(n \log n\) ist dagegen praktisch flach.
Wie weit liegt SPT mit Rüstzeiten über dem echten Optimum?	Bei Rüstzeit 0 / 5 / 15 / 30 / 60 Minuten je Familienwechsel: 0 / 1,6 / 6,6 / 14,3 / 28,9 % (Mittel über 5 feste Instanzen mit 8 Aufträgen und 3 Auftragsfamilien, ohne Ketten-Seeds; Optimum mit Rüstzeiten per Vollaufzählung).
Gilt das auch für jede einzelne Instanz?	Nein: einzelne Instanzen liegen bei hoher Rüstlast noch höher, laut README bis über 50 % im Einzelfall.

Die Vorab-Vermutung, SPT bleibe auch ohne Beweis eine gute Heuristik, hat sich teilweise bestätigt, aber nicht garantiert: Bei kleiner Rüstzeit ist der Abstand klein, wächst aber deutlich mit der Rüstzeit. SPT ersetzt also kein Verfahren, das Rüstzeiten selbst mit optimiert.

Grenzen

• Voraussetzungen des Beweises: eine Maschine, gleich gewichtete Aufträge, keine Fristen, Bearbeitungszeiten unabhängig von der Reihenfolge. Gewichte (WSPT), Fristen (EDD, Moore-Hodgson) und mehrere Maschinen (Johnson-Regel, LPT, Job Shop) hebt je ein Folgestück der Reihe auf; die Demo zeigt sie nicht.
• Rüstzeit-Befunde: Sie gelten für das Werkstatt/Logistik-Vehikel mit seinen erzeugten Familien und Rüstzeiten, gemittelt über die 5 festen Instanzen und mit einer Vollaufzählung nur auf kleinen Instanzen. Wie groß der Abstand in einer echten Werkstatt wäre, sagt die Demo nicht.
• Vollaufzählung: Sie ist die einzige echte Gegenprobe und praktisch nur bis \(n \approx 9\) nutzbar. Darüber stützt sich die Aussage auf den Beweis, nicht auf eine Messung.
• Gerechtigkeit: Das Ziel \(\sum_j C_j\) misst nur den Durchschnitt. Dass lange Aufträge zuletzt drankommen, bewertet die Demo nicht; sie betrachtet feste Aufträge, keinen laufenden Zufluss neuer Aufträge.
• Synthetische Instanzen: Gleichverteilte Bearbeitungszeiten, Fälligkeiten nach dem TF/RDD-Schema, keine Präzedenzen, ein Auftrag ist eine Operation. Die Rechenzeiten sind rechnerabhängig.
• Live-Werte: Die Demo rechnet die Rüstzeit-Reihe auf Wunsch live auf einer kleinen Instanz nach; die Werte können dort von den Mittelwerten der README abweichen.

Quellen

• Smith, W. E. (1956): Various optimizers for single-stage production. Naval Research Logistics Quarterly 3(1–2), 59–66 (die SPT-Regel).
• Graham, R. L., Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G. (1979): Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics 5, 287–326 (α|β|γ-Notation).
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/spt-scheduling-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen; die Jahreszahl der SPT-Regel stammt aus der README der Demo, die Angaben zu Zeitschrift und Seiten sowie die zweite Arbeit aus dem Gedächtnis.