03_Scheduling

• Is The Task of allocating resources to tasks over given time periods in order to optimize one or more objectives

Variable:

• Repräsentiert einen Wert oder eine Menge von Werten

• Speichert Informationen

• Kann verschiedene Datentypen haben

Performance-Metrik:

• Misst die Leistung eines Modells, Systems oder Algorithmus

• Spezifische Funktionen oder Maße

• Quantifiziert Genauigkeit, Effizienz oder andere Leistungsaspekte

• Verwendet zur Bewertung von Vorhersagegenauigkeit im maschinellen Lernen

Difference:

• Flowshop:

  • equential processing of orders in a predetermined sequence at each workstation.

  • Orders follow the same order of operations at each workstation.

  • Example: Assembly line with a fixed sequence of tasks.

    • Production line for assembling smartphones.

    • All smartphones go through the same sequence of manufacturing steps, such as component assembly, testing, and packaging.

  Job Shop:

  • Each order may have a unique sequence of operations.

  • Orders have varying routing and processing requirements.

  • Flexibility and customization are key characteristics.

  • Example: Custom printing shop.

    • Each printing order may require different processes, such as design, printing, cutting, and binding.

    • The order of operations and the equipment used can vary for each order.

• Während im Job Shop die Reihenfolge der Operationen je nach Auftrag variiert, gibt es im Open Shop keine festgelegte Reihenfolge der Operationen, und die Flexibilität der Arbeitsstationen steht im Vordergrund.

• Permutation:

  • Permutation im Scheduling bezieht sich auf die Beibehaltung der ursprünglichen Reihenfolge der Jobs an der ersten Maschine.

  • Es ermöglicht die Einhaltung von Prioritäten und logistischen Anforderungen.

  • An den folgenden Maschinen können die Jobs in beliebiger Reihenfolge bearbeitet werden.

Schedule (Terminplan):

• Legt fest, wann jede Aktivität beginnen und enden soll.

• Fokussiert sich auf die zeitliche Anordnung der Aktivitäten.

• Berücksichtigt die geplanten Start- und Endtermine.

Sequence (Reihenfolge/Permutation):

• Bestimmt die richtige Abfolge der Aktivitäten.

• Konzentriert sich auf die logische und technische Abhängigkeit zwischen den Aktivitäten.

• Gibt an, in welcher Reihenfolge die Aktivitäten durchgeführt werden müssen.

Der Schedule definiert die Zeitpunkte, wann die Aktivitäten stattfinden sollen, während die Sequence die korrekte Abfolge der Aktivitäten angibt, um ein Projekt erfolgreich durchzuführen. Der Schedule beantwortet die Frage "Wann?", während die Sequence die Frage "In welcher Reihenfolge?" beantwortet.

• Non-delay schedule (Verzögerungsfreier Terminplan): Alle Maschinen sind kontinuierlich ausgelastet, es gibt keine Leerlaufzeiten zwischen den Operationen.

  • Beispiel: Alle Maschinen im Produktionsprozess sind während des gesamten Zeitraums vollständig ausgelastet, es gibt keine Wartezeiten zwischen den Operationen.

• Active schedule (Aktiver Terminplan): Keine Operation kann in eine leere Zeitlücke eingefügt werden, ohne die geplante Fertigstellungszeit zu ändern. —> Optimaler Plan

  • Beispiel: Der Terminplan für eine Bauarbeitsstelle ist so strukturiert, dass keine neuen Arbeiten in die Zeitpläne der vorhandenen Arbeiten aufgenommen werden können, ohne die geplante Fertigstellungszeit des Projekts zu beeinflussen.

• Semi-active schedule (Halbaktiver Terminplan): Es ist möglich, Verbesserungen zu erzielen, indem die Reihenfolge der Operationen geändert wird, um eine bessere Durchführung zu ermöglichen.

  • Beispiel: In einem Fließbandproduktionssystem kann die Reihenfolge der Montageschritte optimiert werden, um die Gesamtdurchlaufzeit zu reduzieren oder bestimmte Engpässe in der Produktion zu beseitigen.

• Ein "Non-delay Schedule" ist nicht immer optimal, da er die Ressourcenverteilung, Prioritäten und Flexibilität möglicherweise nicht optimal berücksichtigt. Es kann Situationen geben, in denen ein alternativer Terminplan mit leicht längerer Durchlaufzeit, aber besserer Ressourcenauslastung oder Prioritätenerfüllung, insgesamt optimaler ist.

• Most simple but fundamental machine environment

• n jobs are scheduled on a single machine

• Every schedule is a permutation of the n jobs

• Number of different schedules: n!

Unlimited: products are physically small, large buffer capacities

limited: products are physically large

• Für 2 Maschinen und n Aufträge.

• Cmax (Makespan) is independent of the schedule and is named proportional flow shop. That means that every schedule equals

• Cmax =

• Slope Herusitic

• Every Job has a (different) route of machines to visit

• machine sequence of each job is given

• Highly compley problem —> use heuristics

Kommentar: Disjunktive (gestrichelte) Kanten 𝐵: Sie verbinden Operationen, die zu verschiedenen Jobs gehören, aber auf derselben Maschine durchgeführt werden müssen.

• we have a lot of binary variables which complicates solving this problem

• Kommentar: conjunctiv !!! formulation !!

• 2 Machines (J2IICmax)