Ein-Maschinen-Problem

aus Wikipedia, der freien Enzyklopädie

Ein-Maschinen-Probleme sind in der Maschinenbelegungsplanung spezielle Modelle mit einer einzigen Maschine und n verschiedenen zu fertigenden Aufträgen. Obwohl die Modelle relativ einfach sind, verglichen mit Job-Shop-, Open Shop- oder Flow-Shop-Problemen, gehören manche zu den NP-schweren Problemen.[1] Viele lassen sich jedoch in polynomialer Zeit lösen, also vergleichsweise schnell. Die Lösung der Modelle hängt von der angestrebten Zielsetzung ab. Beispiele sind die Minimierung der Zykluszeit, der Durchlaufzeit oder der Verspätungen. In der bei Maschinenbelegungsproblemen üblichen Notation handelt es sich um [1| | ]-Probleme. (Für Details zur Notation siehe Klassifikation von Maschinenbelegungsmodellen.) Die meisten Probleme lassen sich auch als Scheduling-Probleme in der Informatik betrachten: Die Maschine entspricht dann einem Prozessor und die Aufträge entsprechen den Prozessen. Analog lässt sich ein Maschinenbelegungsproblem mit parallelen Maschinen als Modell interpretieren mit mehreren Prozessoren.

Minimierung der maximalen Terminabweichung

Das Problem [1| |Tmax] lässt sich optimal lösen mit der Prioritätsregel der Earliest Due Date-Regel (EDD-Regel). Bei [1|prec|Tmax] liegt ein Graph vor mit einer Reihenfolge der einzuhaltenden Arbeitsgänge. Es lässt sich mit dem Algorithmus von Lawler lösen.[2]

Die Probleme [1|aj|Tmax] und [1|aj|Vmax] sind NP-schwer.[3] Wenn die Bearbeitung der Aufträge unterbrochen werden kann ([1|pmnt, aj|Tmax] und [1|pmnt, aj|Vmax]) lassen sich mit einer modifizierten (sogenannten dynamischen) EDD-Regel lösen. Eingeplant werden dann die Aufträge mit dem zum Planungszeitpunkt kleinsten Fertigstellungstermin (sofern sie bereits zur Verfügung stehen). Dies kann dazu führen, die Bearbeitung eines Auftrags zu unterbrechen, falls ein weiterer Auftrag einplanbar wird der einen kleineren Fertigstellungstermin hat.

Minimierung der Zykluszeit

Für das Problem [1| |Z] stellt jede Belegung ohne Leerzeiten eine optimale Lösung dar. Falls ein Vorranggraph für die Aufträge vorliegt ([1|prec|Z]), so muss man die Aufträge in der Entsprechenden Reihenfolge einplanen. Werden die Aufträge zu unterschiedlichen Zeitpunkten verfügbar, handelt es sich um [1|aj|Z]. Die optimale Lösung ergibt sich durch Sortierung nach absteigenden Bereitstellungsterminen und entsprechender Einplanung. Bei [1|nj|Z] muss man die Aufträge nach monoton fallenden Nachlaufzeiten sortieren und einplanen.[4]

Um ein NP-schweres Problem handelt es sich bei [1|aj, nj|Z]. Es kann bei dreistufiger Fertigung entstehen wenn die mittlere Stufe mit nur einer Maschine einen Engpass darstellt. Die Bereitstellungstermine entsprechen dann den Fertigstellungszeiten der ersten Stufe und die Nachlaufzeiten den Bearbeitungszeiten der dritten Stufe. Es spielt auch als Relaxation komplexerer Job Shop-Probleme eine Rolle. Gelöst wird es mit dem Branch and Bound Verfahren von Carlier.[5] Die obere Grenze wird mit dem Algorithmus von Schrage (eine Heuristik) bestimmt, die untere mit einer Abwandlung davon.[6]

Liegen reihenfolgeabhängige Rüstzeiten vor, lässt sich das Problem [1||Z] mit den Rüstzeiten von Auftrag j auf Auftrag k als Rundreiseproblem formulieren. Die Aufträge entsprechen dabei den zu besuchenden Städten und die Rüstzeiten den Entfernungen zwischen ihnen.[7]

Minimierung der Durchlaufzeit

Das allgemeine Modell [1| |D] lässt sich mit dem Aufwand O(n log n) mit der Smith-Regel:[8] Man sortiert die Aufträge nach steigender Bearbeitungszeit und plant sie in dieser Reihenfolge ein. Werden die einzelnen Aufträge mit Gewichten multipliziert, ergibt sich die optimale Reihenfolge durch Sortierung nach steigender Bearbeitungszeit je Gewicht .[9]

[1|pmnt, aj|D] lässt sich mit der dynamischen Shortest Remaining Processing Time Regel lösen.

Minimierung der Anzahl der Verspätungen

[1| |V#] lässt sich mit dem Algorithmus von Hodgson lösen.[10]

Siehe auch

Einzelnachweise

  1. ↑ Domschke, Scholl, Voß: Produktionsplanung: Ablauforganisatorische Aspekte. 2. Auflage, Springer, 1997, S. 307.
  2. ↑ Domschke, Scholl, Voß: Produktionsplanung: Ablauforganisatorische Aspekte. 2. Auflage, Springer, 1997, S. 308f.
  3. ↑ Domschke, Scholl, Voß: Produktionsplanung: Ablauforganisatorische Aspekte. 2. Auflage, Springer, 1997, S. 310.
  4. ↑ Domschke, Scholl, Voß: Produktionsplanung: Ablauforganisatorische Aspekte. 2. Auflage, Springer, 1997, S. 313f.
  5. ↑ J. Carlier: The one-machine sequencing problem. European Journal of Operations Research 11, 1982, S. 164–176.
  6. ↑ Domschke, Scholl, Voß: Produktionsplanung: Ablauforganisatorische Aspekte. 2. Auflage, Springer, 1997, S. 314
  7. ↑ Domschke, Scholl, Voß: Produktionsplanung: Ablauforganisatorische Aspekte. 2. Auflage, Springer, 1997, S. 326f.
  8. ↑ W. E. Smith: Various optimizers for single-stage production. Naval Research Logistics Quarterly 3, S. 59–66.
  9. ↑ Domschke, Scholl, Voß: Produktionsplanung: Ablauforganisatorische Aspekte. 2. Auflage, Springer, 1997, S.
  10. ↑ Domschke, Scholl, Voß: Produktionsplanung: Ablauforganisatorische Aspekte. 2. Auflage, Springer, 1997, S. 327
Abgerufen von „https://de.wikiup.org/index.php?title=Ein-Maschinen-Problem&oldid=203497244“