| |
| Autor |
 Scheduling Problem als stochastic programming Problem formulieren |
|
dvdlly
Aktiv 
Dabei seit: 28.12.2016
Mitteilungen: 288
 |  Themenstart: 2022-07-14
|
Hallo,
Für die, die schon andere Posts von mir gelesen haben - ich grüble immer noch über das Scheduling Problem nach und bin nun bei stochastic programming gelandet.
Ich habe einen gerichteten azyklischen Graphen, wobei ein Knoten eine Aufgabe repräsentiert und eine Kante eine Abhängigkeit. Die Aufgabe, die der ausgehende Knoten repräsentiert, muss erledigt sein, bevor die Aufgabe, die der eingehende Knoten repräsentiert, bearbeitet werden kann. Es gibt eine feste Anzahl von Maschinen, die jeweils alle Aufgaben potenziell in unterschiedlicher Geschwindigkeit bearbeiten können. Die Bearbeitungszeit einer Aufgabe auf einer Maschine ist nicht bekannt, allerdings haben wir einen Schätzer, der für ein (Aufgabe i,Maschine j) Paar eine Schätzung abgeben kann. Die Schätzung sieht folgendermaßen aus: \(X_{i,j} = echteLaufzeit + echteLaufzeit \cdot X\) und \(X\) ist eine reelle Zufallsvariable deren Verteilung und Parameter bekannt sind. Außerdem stehen Schätzungen der Schnelligkeiten der Maschinen zur Verfügung, mithilfe derer man die Bearbeitungsdauer einer Aufgabe auf einer Maschine schätzen kann.
Das Ziel ist es, die Aufgaben so auf Maschinen zuzuweisen, dass die Dauer der gesamten Bearbeitungszeit minimal ist.
Ich versuche, das ganze als stochastic programming Problem zu formulieren
https://web.stanford.edu/class/ee364a/lectures/stoch_prog.pdf
allerdings fällt mir keine "Reduktion" ein, die die Essenz der Problems einfängt.
Ich habe mir z.B. überlegt, das Problem als two-stage Problem zu formulieren https://en.wikipedia.org/wiki/Stochastic_programming#:~:text=In%20the%20field%20of%20mathematical,but%20follow%20known%20probability%20distributions.
aber wie drückt man mit \(c^{T} \cdot x\) aus, dass die Bearbeitungsdauer minimiert werden soll?
Danke für eure Hilfe!
|
 Profil
|
Delastelle
Senior 
Dabei seit: 17.11.2006
Mitteilungen: 2320
 | Beitrag No.1, eingetragen 2022-07-14
|
Hallo dvdlly!
Eine Lösung für Dein Problem habe ich nicht.
Aber vielleicht könnte man mit Robust Scheduling arbeiten.
Ich meine damit folgendes:
Man setzt nach jedem Vorgang eine kurze Ruhezeit ein.
Somit können längere Vorgänge noch bearbeitet werden.
Man könnte versuchen, dass 95% der zeitlich schwankenden Vorgänge in den Gesamtplan passen.
Falls die Zeiten kürzer sind, kann man den Plan eventuell zusammenschieben. (Eben die Ruhezeiten kürzen für einen konkreten Plan.)
Viele Grüße
Ronald
|
Profil
|
dvdlly
Aktiv
Dabei seit: 28.12.2016
Mitteilungen: 288
| Beitrag No.2, vom Themenstarter, eingetragen 2022-07-15
|
Danke für deine Idee.
Ich vermute mit Vorgang meinst du die Ausführung einer Aufgabe auf einer Maschine?
"Man könnte versuchen, dass 95% der zeitlich schwankenden Vorgänge in den Gesamtplan passen." - Wie bestimmst du denn den Gesamtplan, eine Zuordnung von Aufgaben zu Maschinen und dann die gesamte Dauer betrachten?
|
Profil
|
Delastelle
Senior
Dabei seit: 17.11.2006
Mitteilungen: 2320
| Beitrag No.3, eingetragen 2022-07-15
|
Hallo dvdlly!
Bei einem Teilgebiet des Scheduling dem Job Shop Scheduling
gibt es Jobs, zu einer Belegung einen Plan und eine Gesamtzeit (Makespan).
Bsp. MT 10 Problem
Jobs 100, Optimum = 930 Zeiteinheiten
Siehe auch meine beiden Matheplanet-Artikel zu Job Shop Scheduling
https://www.matheplanet.de/matheplanet/nuke/html/article.php?sid=1865
und
https://www.matheplanet.de/matheplanet/nuke/html/article.php?sid=1952
Man kann bei einer zulässigen Lösung eines Scheduling Problems auch
Wartezeiten einplanen um Staus im Produktionsprozess teilweise
verarbeiten zu können.
Dies könnte als Beispiel einem Paketzusteller mit Pakten helfen mit Verkehrsstaus umzugehen.
Momentan ist mir noch nicht so ganz klar wie Dein Scheduling Problem genau aussieht.
Viele Grüße
Ronald
|
Profil
|
dvdlly
Aktiv
Dabei seit: 28.12.2016
Mitteilungen: 288
| Beitrag No.4, vom Themenstarter, eingetragen 2022-07-16
|
Danke für die Links.
Also bei mir handelt es sich um ein Job Shop Problem, bei dem ein Job nur aus einem Vorgang besteht. Die Bearbeitungszeit der Jobs pro Maschine ist unbekannt, es existieren aber gemessene Benchmarks mit denen man die Bearbeitungszeit schätzen kann. Zusätzlich haben wir einen sog. Predictor. Er sagt die Laufzeit von einem Job auf einer Maschine vorher und zwar gemäß der folgenden Regel:
\(X_{i,j} = echteLaufzeit + echteLaufzeit \cdot X\) wobei \(X_{i,j}\) die Laufzeit von Job j auf Maschine i angibt und \(X\) eine reelle Zufallsvariable ist, deren Parameter und Verteilung bekannt sind.
Ich versuche wie beschrieben das ganze als stochastic programming problem zu formulieren, aber das will mir nicht gelingen. https://en.wikipedia.org/wiki/Stochastic_programming#:~:text=In%20the%20field%20of%20mathematical,but%20follow%20known%20probability%20distributions.
Hier steht beispielsweise, dass eine Funktion der Form \(g(x) := c^{T} \cdot x + ...\) minimiert werden soll für \(x \in \mathbb{R}^n\). Ich frage mich schon - was genau soll \(x\) ausdrücken? Die Startzeiten oder Bearbeitungszeiten von einem Job auf einer Maschine? Falls das der Fall wäre - dann sehe ich nicht, wie man \(c\) wählen kann, so dass nur der kritische Pfad betrachtet wird.
|
Profil
|
Delastelle
Senior
Dabei seit: 17.11.2006
Mitteilungen: 2320
| Beitrag No.5, eingetragen 2022-07-16
|
Hallo,
c^T*x ist eine Zielfunktion bei der linearen Optimierung.
Für Scheduling Probleme ist oft eine Lösung eine Permutation oder ähnliches. Bei Job Shop Scheduling ist die Lösung eine Permutation mit Nebenbedingung. Die Nebenbedingung ist, dass z.B. für das 10x10 MT10 Problem die Zahlen 1,2 bis 10 und 11,12 bis 20 jeweils in dieser Reihenfolge auftreten müssen.
Eine Permutation wie 2,1, ... ist unzulässig weil Job 2 auf Job 1 folgt.
Vielleicht solltest Du mal ein kleines Problem aufschreiben.
Dann könnte man mal schauen, was die Lösung dieses kleinen Problems ist!
Für Job Shop Scheduling sind Problem wie 3x3 oder 4x4 oder 5x5 klein und meist von Hand lösbar.
Viele Grüße
Ronald
|
Profil
|
| dvdlly hat die Antworten auf ihre/seine Frage gesehen. | | dvdlly wird per Mail über neue Antworten informiert. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
