Scheduling-Optimierung in der Praxis: Theorie, Fallstricke und Heuristiken aus dem Vortrag von Michael Missethan (evon GmbH)

Warum dieser Talk für Entwicklerinnen und Entwickler relevant ist

Als Redaktion von DevJobs.at hören wir viele Sessions über Optimierung – selten aber so fokussiert und praxisnah wie „Scheduling Optimization in Practice“ von Michael Missethan (evon GmbH). In knappem, klar strukturiertem Vortrag führte er uns durch drei Kernfragen: Was ist Scheduling? Warum ist Scheduling schwierig? Und wie kommen wir in der Praxis dennoch zu guten Lösungen?

Der Vortrag hatte eine wohltuend nüchterne Botschaft: Scheduling ist allgegenwärtig – von Stundenplänen bis zu Fertigungsstraßen – und gleichzeitig theoretisch wie praktisch „hart“. Trotzdem gibt es konkrete, wiederholbare Schritte, um robuste und messbar bessere Pläne zu bauen. Diese Mischung aus Pragmatismus und mathematischer Strenge macht die Session für Engineering-Teams besonders wertvoll.

Kurzporträt: Speaker, Firma, Kontext

Michael Missethan ist Mathematiker und Softwareentwickler bei der evon GmbH – mit starkem Fokus auf algorithmische Optimierungsprobleme. evon arbeitet im Bereich Softwareentwicklung und Services und entwickelt unter anderem die Automatisierungsplattform XamControl. Laut Missethan wurde evon 2009 gegründet; der Hauptsitz befindet sich in St. Trobrecht-an-der-Rab, östlich von Graz, mit rund 95 Mitarbeitenden.

Diese Engineering-Perspektive – Mathematik plus praktische Softwareentwicklung – prägt den gesamten Vortrag: präzise Problemdefinition, saubere Modellierung und methodische Algorithmik statt schneller Ad-hoc-Lösungen.

Was ist Scheduling – und was bedeutet Optimierung dabei?

„Roughly speaking, it’s just planning or deciding what to do, when and where under certain constraints.“ Mit dieser nüchternen Definition setzt Missethan den Rahmen: Scheduling ist das zeitliche und räumliche Anordnen von Aufgaben (Tasks/Jobs) auf Ressourcen (z. B. Maschinen, Räume, Personen) unter Einhaltung vielfältiger Nebenbedingungen.

Typische Ziele (Objectives) sind:

• Minimierung von Kosten oder Durchlaufzeit (Completion Time)
• Ausbalancierte Auslastung, etwa im Stundenplan-Kontext für Lehrkräfte

Die Alltagsnähe unterstreicht der Referent mit einem simplen Beispiel: Wir alle planen täglich – Einkaufen, Training, Mittagessen. Der Unterschied: In der Technik legen wir Ziele und Beschränkungen explizit fest und messen, wie gut eine Lösung diese Anforderungen erfüllt.

Das Fertigungsbeispiel: Vier Tasks, mehrere Maschinen, feste Reihenfolgen

Zur Veranschaulichung stellt Missethan ein klassisches Produktionsszenario vor. Vier Aufgaben (Tasks) bestehen jeweils aus Jobs, die nacheinander auf bestimmten Maschinen ausgeführt werden müssen – mit vorgegebenen Zeitdauern.

Ein exemplarischer Task sieht so aus:

• 3 Stunden auf Maschine 1
• 2 Stunden auf Maschine 2
• 4 Stunden auf Maschine 3

Wichtig: Die Jobs eines Tasks müssen direkt aufeinander folgen. Ziel ist es, alle Tasks zu verplanen, ohne Maschinenkonflikte zu erzeugen, und die Gesamtdauer (Makespan) zu minimieren.

Missethan zeigt eine erste – nicht optimale – Planungsskizze: Start mit Task 3 auf Maschine 2, Wechsel nach 3 Stunden auf Maschine 1, dann weiter mit Task 2 etc. In diesem Plan beginnen Task 1 relativ spät, Task 4 noch später. Der gesamte Ablauf benötigt 22 Stunden.

Schon bei diesem kleinen Beispiel wird klar: Verbesserungen sind nicht trivial, und die beste Lösung (globale Optimalität) zu finden, ist noch schwieriger.

Warum Scheduling hart ist: Theorie und Praxis

Theoretische Gründe

1) Kombinatorische Explosion: Schon bei 13 Tasks existieren 13! mögliche Anordnungen – eine Zahl mit 33 Ziffern. Selbst moderne Rechner würden „billions of years“ benötigen, um das vollständig zu enumerieren.

2) Wechselwirkungen: Eine Änderung an einer Stelle erzeugt Kettenreaktionen. Missethan nutzt den Zugverkehr als Bild: Eine Verspätung propagiert sich und verursacht weitere Verspätungen. Übertragen auf Produktionspläne: Eine lokale Anpassung verschiebt andere Jobs quer über Maschinen.

3) Komplexitätstheorie: „Most of the scheduling problems are so-called NP-hard.“ Das heißt: Es ist kein effizienter Algorithmus bekannt, der in allen Fällen eine optimale Lösung garantiert. Für Engineering-Teams ist diese Erkenntnis entscheidend, weil sie die Erwartungshaltung steuert: Wir brauchen robuste Approximationsverfahren und Heuristiken statt der Suche nach dem einen „perfekten“ Algorithmus.

Praktische Gründe

1) Verdeckte oder komplexe Nebenbedingungen: Nicht alle Constraints sind von Anfang an bekannt. Beispiel aus der Fertigung: Maschinen können überhitzen, wenn sie zu lange am Stück laufen – eine Eigenschaft, die bei „schwachen“ Plänen gar nicht sichtbar war und erst nach Optimierung (mit längeren Laufzeiten) relevant wird.

2) Unsicherheiten und Änderungen: Maschinen können ausfallen, Verfügbarkeiten ändern sich. Planen heißt deshalb auch, mit Störungen zu rechnen – und die Modelle so zu gestalten, dass sie auf Änderungen reagieren können.

3) Unklarheit beim Optimieren: „We don’t know how to optimize.“ Gemeint ist: Ohne sauberes Ziel- und Constraint-Design optimieren Teams schnell am eigentlichen Bedarf vorbei – oder finden Lösungen, die auf dem Papier gut aussehen, aber in der Realität nicht ausführbar sind.

Das Fazit aus Theorie und Praxis: Scheduling ist schwer – im Idealfall wie im Alltag. Und trotzdem: „In practice we can still do something and we can still find some reasonable solutions.“

Der Praxis-Workflow: Von der Problemaufnahme bis zur Evaluation

Missethan beschreibt einen wiederkehrenden Ablauf, den wir in dieser Form aus vielen erfolgreichen Optimierungsprojekten kennen. Besonders bemerkenswert: Er betont die Schritte vor der Algorithmik – und warnt vor einer zu starken Fixierung auf den „coolen“ Teil.

1) Daten und Problem sauber erfassen

• Alle Jobs/Tasks erfassen
• Ziele (Objectives) präzise formulieren
• Nebenbedingungen vollständig sammeln und explizit machen

Hinweis aus dem Talk: Viele Constraints sind „implizit“ im Betrieb akzeptiert, aber nirgends schriftlich fixiert. Wer sie beim Modellieren vergisst, riskiert am Ende eine Lösung, die nicht ausführbar ist.

2) Mathematische Modellierung

• Verbale Beschreibung in Formeln überführen
• Entscheidungsvariablen, Parameter und Datenstrukturen definieren

Hier entsteht das Fundament der späteren Algorithmen. Ein präzises Modell schafft Eindeutigkeit – und macht Kompromisse sichtbar, die in reinen Diskussionen oft untergehen.

3) Algorithmisches Design für Approximationen und Heuristiken

• Da optimale Lösungen häufig unerreichbar sind, braucht es Heuristiken oder Approximationsverfahren
• Ziel: „as close to the optimum as possible“

Je nach Kontext können einfache Heuristiken (siehe Greedy) bereits viel bewirken – oder eine Basis bilden, auf der man iterativ verfeinert.

4) Evaluation: Machbarkeit und Qualität

• Feasibility prüfen (sind alle Constraints eingehalten?)
• Performance messen (werden die Ziele gut erfüllt?)

Die Evaluationsphase dient nicht nur der Erfolgsmessung, sondern auch als Feedback in die Modellierung. In der Praxis ist der Prozess „zyklisch“, nicht linear: Nach der Bewertung justiert man Modell, Daten oder Heuristik.

Warnung vor Schieflage: Nicht nur den Algorithmus optimieren

Missethan beobachtet, dass Teams sich oft auf den dritten Schritt („Algorithmus“) fixieren. Aus mathematischer Sicht ist das reizvoll – aber gefährlich, wenn Problemdefinition und Modellierung schlampig bleiben. Wer Ziele unpräzise definiert, erhält am Ende eine perfekt optimierte Lösung für das falsche Ziel. Wer Constraints vergisst, steht mit einem Plan da, der in der Realität scheitert.

Greedy-Heuristik: Früh starten – und die Grenzen des Lokalen

Als leichtgewichtige Einstiegsmethode zeigt Missethan die Greedy-Heuristik: „We try to schedule each task as early as possible.“ Das Vorgehen:

1) Task 1 möglichst früh planen

2) Task 2 ebenfalls möglichst früh planen

3) Task 3 frühestmöglicher Start (hier erst nach 10 Stunden, da Maschinen zuvor belegt sind)

4) Task 4 ebenfalls so früh wie möglich

Ergebnis: 21 Stunden Gesamtzeit – und damit eine Verbesserung gegenüber dem ersten Plan mit 22 Stunden.

Doch Greedy offenbart eine zentrale Schwäche: Es ist lokal optimal, aber global oft suboptimal. Eine kleine, auf den ersten Blick kontraintuitive Abweichung kann das Gesamtziel deutlich verbessern.

Der Aha-Moment: Eine Stunde Verzögerung spart fünf Stunden Gesamtzeit

Missethan zeigt dieselben Schritte – mit einer kleinen Änderung: Task 2 wird um eine Stunde nach hinten verschoben. Zunächst wirkt das schädlich (Task 2 ist dann eine Stunde später fertig), doch es schafft zwischen 5 und 8 Uhr eine größere Lücke auf Maschine 2. Diese Lücke ermöglicht es, Task 3 viel früher zu starten. Die Folge: Task 4 rutscht ebenfalls nach vorn – und die Gesamtdauer sinkt auf 16 Stunden.

Das Beispiel illustriert zwei Einsichten, die im Engineering-Alltag Gold wert sind:

• Lokale Optimalität garantiert keine globale Optimalität.
• Kleine Änderungen können Kaskadeneffekte auslösen – im Positiven wie im Negativen.

Für uns war das die prägnanteste Stelle der Session: ein klarer, quantitativer Beleg, dass naive Frühstart-Strategien in eng gekoppelten Systemen scheitern können.

Praktische Lehren für Engineering-Teams

Aus dem Vortrag lassen sich handfeste Arbeitsprinzipien ableiten. Keine davon ist „Magie“ – alle sind operationalisierbar:

1) Problemdefinition zuerst: Ziele und Constraints explizit machen. „Unintended objectives“ vermeiden, indem man Messgrößen und Prioritäten schriftlich fixiert.

2) Modell vor Heuristik: Erst wenn Variablen, Abhängigkeiten und Restriktionen mathematisch klar sind, lohnt sich Algorithmik. Das Modell ist die Sprache, in der man Lösungen vergleicht.

3) Rechnen mit Unwissen: Planen Sie ein, dass Nebenbedingungen erst durch Optimierung sichtbar werden (z. B. Überhitzung bei langen Laufzeiten). Iteration ist kein Bug, sondern Feature.

4) Lokale Heuristiken als Startpunkt: Greedy liefert oft schnelle, gute Baselines. Aber: Verteidigen Sie die Greedy-Lösung nicht dogmatisch – prüfen Sie bewusst, wo kleine Verzögerungen große Vorzüge erzeugen.

5) Evaluation als Qualitätsfilter: Jeder Plan durchläuft zwei Checks – Durchführbarkeit und Zielerreichung. Ohne Feasibility keine Auslieferung; ohne Performance kein Fortschritt.

6) Iterativer Zyklus statt Einbahnstraße: Das von Missethan skizzierte Vorgehen ist ein Kreis. Evaluation ändert Modell und Daten; neue Informationen formen die Heuristik.

7) Realistische Erwartung an Optimalität: NP-Härte ist kein akademisches Detail, sondern Produktrealität. Sprechen Sie im Team offen darüber, welche Güteziele erreichbar sind – und welche Rechenzeit/Komplexität dafür investiert wird.

Ein minimales mentales Modell für Scheduling-Projekte

Wir fanden es hilfreich, das Gehörte in ein kompaktes, projekttaugliches Raster zu überführen – als Leitfaden für Kick-offs und Reviews:

• Kontext: Welche Ressourcen, Tasks, Abhängigkeiten? Welche Reihenfolgen sind strikt, welche flexibel?
• Ziele: Hauptziel (z. B. Makespan-Minimierung), Neben-/Weichziele (z. B. Balanced Workload). Prioritäten festlegen.
• Constraints: Harte (physikalisch/vertraglich), weiche (Präferenzen). Dokumentieren, versionieren, prüfen.
• Datenqualität: Vollständigkeit, Aktualität, Quellen. Unsicherheiten markieren.
• Modell: Variablen, Nebenbedingungen, Zielfunktion. Verständlich notieren – referenzierbar für alle Beteiligten.
• Algorithmik: Start mit einer einfachen Heuristik (z. B. Greedy), dann gezielt Varianten testen.
• Evaluation: Feasibility-Checks automatisieren; Metriken für Zielerreichung etablieren.
• Iteration: Feedback in Modell und Daten zurückführen; Änderungen transparent machen.

Dieses Raster spiegelt den Workflow aus dem Talk – und passt gleichzeitig zu den Zwängen realer Softwareteams.

Was der Talk nicht verspricht – und warum das gut ist

Auffällig ist, was Missethan nicht tut: Er verkauft keine „Silberkugel“. Keine Wunderalgorithmen, keine Abkürzungen. Stattdessen eine klare Erwartungshaltung: „Finding the best solution is typically out of range“ – also konzentrieren wir uns auf gute Approximationen und systematisches Vorgehen.

Gerade deshalb ist der Vortrag wertvoll. Er hilft Teams, die richtigen Fragen zu stellen und sorgt dafür, dass Ressourcen dort investiert werden, wo sie Wirkung entfalten: bei guter Problemaufnahme, sauberer Modellierung und iterativer Verbesserung – nicht bei der verfrühten Jagd nach globaler Optimalität.

Konkrete Umsetzungstipps für den Start

Wer nach der Session direkt loslegen will, kann mit diesen Schritten anfangen – sie sind alle durch den Vortrag gedeckt und leichtgewichtig umsetzbar:

• Checkliste für Constraints erstellen: Welche expliziten Regeln gelten bereits? Was ist nur „gelebte Praxis“ und sollte formalisiert werden?
• Ziele priorisieren: Wenn zwei Ziele in Konflikt geraten, welches gewinnt? Das vermeidet spätere Überraschungen.
• Baseline bauen: Mit einer Greedy-Heuristik eine erste Planung erzeugen und den aktuellen Makespan dokumentieren.
• Was-wäre-wenn-Varianten: Einzelne Tasks minimal verschieben (wie im Beispiel +1 Stunde) und die Kaskadeneffekte messen.
• Feasibility-Tests automatisieren: Jeder neue Plan läuft automatisch gegen die bekannten Nebenbedingungen.
• Review-Rhythmus festlegen: Ergebnisse regelmäßig prüfen und Modell/Constraints nachschärfen – der Zyklus ist Teil des Plans.

Fazit: Realistische Strenge statt Wunschdenken

„Scheduling Optimization in Practice“ von Michael Missethan (evon GmbH) liefert genau das, was der Titel verspricht: Praxis. Ein klares Vokabular, ein belastbarer Workflow und ein anschauliches Beispiel, das die Grenzen von Greedy zeigt und gleichzeitig Mut macht: Mit systematischem Vorgehen sind deutliche Verbesserungen möglich – selbst wenn das globale Optimum unerreichbar bleibt.

Der vielleicht wichtigste Satz für Teams, die vor Scheduling-Problemen stehen: Ein kleiner, bewusst gesetzter Eingriff – eine Stunde Verzögerung an der richtigen Stelle – kann fünf Stunden Gesamtzeit sparen. Wer diese Dynamik annimmt, modelliert sauber, bewertet konsequent und iteriert, wird in der Praxis bessere Pläne bauen. Genau das war die stärkste Botschaft dieser Session.

• 

  

  Sahra-Marie Kreidl, Front End Developer bei evon

  Sahra-Marie Kreidl von evon erzählt im Interview darüber, wie sie zum Programmieren gekommen ist, was ihr an der Arbeit im Front End gefällt und gibt Tipps für Anfänger.

  Jetzt ansehen
• 

  

  Lorenz Pretterhofer, Application Engineer bei evon

  Lorenz Pretterhofer von evon gibt im Interview Einblicke in die vielfältigen Tätigkeiten als Application Engineer, wie er zu dem Job gekommen ist und was meiner Meinung nach für Neueinsteiger wichtig ist.

  Jetzt ansehen
• 

  

  Luca Voit, QA Engineer bei evon

  Luca Voit von evon spricht im Interview über seinen Weg zum QA Engineering, wie sein Arbeitsalltag aussieht und was seiner Meinung nach wichtig für den Anfang ist.

  Jetzt ansehen