Matroids Matheplanet Forum Index
Moderiert von Kleine_Meerjungfrau Monkfish epsilonkugel
Mathematik » Stochastik und Statistik » Normalverteilung in eine Rangfolgeberechnung einbeziehen
Autor
Universität/Hochschule Normalverteilung in eine Rangfolgeberechnung einbeziehen
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 266
  Themenstart: 2022-05-19

Hallo, Ich habe schon ein paar verwandte Fragen gestellt, aber hier ist eine neues Version meines Anliegens. Ich habe einen gerichteten azyklischen Graphen \(G=(V,E)\), die Kante \((a,b) a,b \in V\) steht für eine Abhängigkeit von b nach a. Die Knoten repräsentieren Aufgaben, die von verschiedenen Arbeitern ausgeführt werden können die unterschiedlich schnell arbeiten und zur gleichen Zeit maximal eine Aufgabe ausführen können. Damit eine Aufgabe ausgeführt werden kann müssen alle Aufgaben, von denen diese abhängig ist, ausgeführt worden sein. Ich habe als Information: die \(\textbf{geschätzte}\) Ausführungszeit einer Aufgabe für jeden Arbeiter \(est_{a,Arbeiter_j}\)sowie den Schätzungsfehler \(err_{a,Arbeiter_j}\), von dem ich annehme, dass er Normalverteilt ist mit Parametern, die mir bekannt sind. Ich möchte nun eine Zuordnungsfunktion bestimmen, die Aufgaben zu Arbeitern zuweißt und benutze dafür die Formel: \(Rang(a) := \sum_{j,a}{}f(est_{a,Arbeiter_j},err_{a,Arbeiter_j}) + \max_{b}(Rang(b)\) wobei \(\max_{b}\) über die Menge der Kinder von \(a\) läuft. Dann läuft ein Algorithmus ab: 1. sortiere die Aufgaben nach monoton fallendem Rang 2. wähle die Aufgabe mit höchstem Rang, die noch nicht zugewiesen wurde 3. für jeden Arbeiter: bestimme den erwarteten Beendigungszeitpunkt der Aufgabe auf dem Arbeiter. Lege dann die Reihenfolge zur Abarbeitung der Aufgaben für alle "Kinder" von der in (2) ausgewählten Aufgabe fest und speichere den Zeitpunkt, zu dem die letzte Aufgabe gemäß den Schätzungen beendet wird 4. weise die Aufgabe dem Arbeiter zu, der die Beendigungszeit aus (3) minimiert 5. gehe zu (2) falls noch nicht alle Aufgaben zugewiesen wurden Meine Frage: Ich bin mir unsicher, wie ich \(f\) wählen soll - in welchem Verhältnis die geschätzte Ausführzeit und der Fehler stehen sollen. Man könnte z.B. die geschätzte Zeit mit dem unteren und oberen Wert im \(2-\sigma\) Intervall des Fehlers addieren, aber ich frage mich ob es geschickter geht. Danke, dass ihr das bis zum Ende gelesen habt :)


   Profil
Bozzo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.04.2011
Mitteilungen: 2228
Wohnort: Franken
  Beitrag No.1, eingetragen 2022-05-22

Hallo, mir ist noch nicht ganz klar, wie der Algorithmus funktioniert. Was waere denn, wenn alle err = 0 waeren, wie wuerde dann f ausschauen? Wenn z. B. f = est waere, wie wuerde dann Schritt 3 ablaufen? Fuer eine "isolierte" Aufgabe (die von keiner anderer Aufgabe abhaengt und von der auch keine andere Aufgabe abhaengt) waere der Rang dann die Summe der Arbeitszeiten, die alle Arbeiter zusammen haetten, wenn jeder die Aufgabe (nacheinander) erledigen wuerde. D. h. Aufgaben, fuer die viele Arbeiter lange braeuchten bekaemen einen hohen Rang, was auch Sinn machen wuerde, da man solche Aufgaben gerne moeglichst frueh an einen Arbeiter geben wuerde, der sie evtl. etwas schneller erledigen koennte (solange der noch "frei" ist). Wenn ich nur isolierte Aufgaben im Graph habe und jetzt die mit dem hoechsten Rang nehme, die noch nicht zugewiesen ist; wenn ich jetzt in Schritt 3 den "Endzeitpunkt" fuer jeden Arbeiter bestimme, beruecksichtige ich dabei Aufgaben, die schon in Bearbeitung und/oder schon zugewiesen sind? D. h. wenn Arbeiter 2 Aufgabe 5 in 10 Min erledigen koennte, allerdings schon Aufgabe 6 zugewiesen hat, fuer die er vorraussichtlich noch 5 Min brauchen wird, waere dann der erwartete Endzeitpunkt fuer Aufgabe 5 in 15 Min? Gehe ich recht in der Annahme, dass es nicht nur darum geht, die Aufgaben den einzelnen Arbeitern zuzuweisen, sondern auch um die Reihenfolge, in der jeder Arbeiter seine zugewiesenen Aufgaben abarbeiten soll? Gehe ich des Weiteren Recht in der Annahme, dass es darum geht, die Gesamtzeit, die fuer alle Aufgaben gebraucht wird zu minimieren? Im stochastischen Fall, soll die erwartete Gesamtzeit minimiert werden oder z. B. die Median-Zeit oder die des 95% Quantils? Wird die ganze Planung durchgefuehrt, bevor der erste Arbeiter mit der Arbeit startet, oder wird im laufenden Prozess immer wieder "nachgeplant", wenn mehr Informationen darueber verfuegbar sind, wie lange die Arbeiter nun tatsaechlich an welcher Aufgabe gesessen sind, und wie weit sie ihr Pensum tatsaechlich schon abgearbeitet haben? Wie genau geht deine Abhangigkeitsstruktur? "Abhangigkeit von b nach a" verstehe ich nicht. Wenn (a,b) eine Kante im DAG ist, kann dann b erst erledigt werden, wenn a erledigt worden ist oder muss b erledigt worden sein, damit a gestartet werden kann? Sind die "Kinder" von a also Aufgaben, die erst nach a erledigt werden koennen, oder welche, die schon vor a erledigt worden sein muessen? Ich nehme mal an, b kann erst gestartet werden, nachdem a beendet wurde. Das bedeutet, Rang(a) ist der Gesamtrang der "laengsten Kette" von Aufgaben, die von a abhaengen. Was wird jetzt in Schritt 3 genau geprueft? Geht es nur darum, die laengste Kette ausgehend von a zu "verteilen" oder darum den gesamten Baum an Aufgaben, die von a abhaengen? Andere Abhaengigkeiten der von a abhaengenden Aufgaben werden dabei nicht beruecksichtigt, oder? D. h. ich mache nun fuer jeden Arbeter ein "Paralleluniversum" auf und ueberlege mir, wie ich die Abaengigkeiten verteilen koennte, wenn der entsprechende Arbeiter die Aufgabe a zugewiesen bekommen wuerde. Was muss ich mir dazu jetzt im naechsten Schritt in jedem Paralleluniversum ueberlegen? Lege ich nun direkt die nachste Aufgabe aus der laengsten Kette auf den Arbeiter, der damit am fruehesten fertig wird, oder eroeffne ich wieder fuer jeden Arbeiter ein neues Paralleluniversum und pruefe alle Moeglichkeiten? Oder bestimme ich erst mal wieder den Rang aller Kinder und verteile dann alle Untergraphen der Reihe nach (in "Tiefensuche")?


   Profil
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 266
  Beitrag No.2, vom Themenstarter, eingetragen 2022-05-22

Hey, Danke für deine (ausführliche) Antwort. :D Wenn err = 0, wäre, dann würden wir in (3) nur \(est_{a,Arbeiter_j}\) benutzen, um den erwarteten Beendigungszeitpunkt der Aufgabe auf dem Arbeiter zu bestimmen. Das muss dann die früheste Zeit, zu welcher der Arbeiter anfangen kann die Aufgabe zu bearbeiten + \(est_{a,Arbeiter_j}\). Wenn ein Knoten isoliert ist, dann wäre sein Rang \(\sum_{a,j} f(est_{a,Arbeiter_j},err_{a,Arbeiter_j}\) wobei f ja noch nicht spezifiziert ist. Man kann f so wählen, dass die Summe z.B. die mittlere gewichtete Bearbeitungszeit ergibt + den mittleren Fehler. Zur Ermittlung des Endzeitpunktes werden alle Aufgaben berücksichtigt die schon zugewiesen wurden. Deine Vermutung mit dem Beispiel ist also richtig. Ja, du liegst mit beiden Vermutungen richtig, es geht um die Reihenfolge der Zuweisung der Aufgaben auf die Arbeiter und es geht darum die gesamte Bearbeitungsdauer zu minimieren. Im stochastischen Fall geht es darum die erwartete Gesamtzeit zu minimieren. Die Entscheidung, ob man einmal im Vorhinein alles plant oder "nachplant", wenn man mehr Informationen über die tatsächliche Ausführzeit hat, steht noch aus. Mir fällt keine geschickte Methode ein, um die neu gewonnenen Informationen "gewinnbringend" in den Algorithmus einzubringen. \((a,b)\) bedeutet a muss vor b bearbeitet werden, damit b bearbeitet werden kann. Die Abhängigkeit von b nach a ist etwas verwirrend, sorry. In (3) versuchen wir, die ausgewählte Aufgabe so auf einen Arbeiter zu verteilen, dass der späteste Zeitpunkt, zu dem eine ihrer Kindesaufgaben fertig wird, minimiert wird. Das machen wir, damit der Algorithmus nicht nur lokal gute Reihenfolgen festlegt, sondern ein wenig in die Zukunft schauen kann. Sorry für die Metapher, vielleicht ist das hilfreich. Ich mache für jeden Arbeiter ein Paralleluniversum auf und das besteht aus dem Arbeiter, allen seinen Kindern, deren jeweiligen bereits berechneten Rängen und den Endzeiten der Aufgaben, die jeweils als letztes auf jedem Arbeiter ausgeführt wurden (damit ich weiß, wann jeder Arbeiter frühestmöglich wieder arbeiten kann). Ich nehme die Aufgabe A, und mache für jeden Arbeiter R das folgende: Ich weise A zu R zu. Dann teile ich die Kinder von A den Arbeitern zu, indem die Kinder, welche absteigend nach ihrem Rang sortiert werden, einzeln ausgewählt werden und dann für jedes Kind geguckt wird, auf welchem Arbeiter es frühestmöglich fertig wird. Das Kind wird dann diesem Arbeiter (aber vorerst nur im Paralleluniversum) zugewiesen. Jetzt weiß ich, dass wenn ich A auf R zuweise, wie lange es dauert bis alle Kinder von A fertig sind (nach diesem Verfahren natürlich). Da ich das ganze für alle Arbeiter mache, habe ich am Ende den Arbeiter R', auf dem die Beendigungszeit von allen Kindern von A kleinstmöglich ist. Die Aufgabe A weise ich dann diesem Arbeiter R' zu.


   Profil
Bozzo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.04.2011
Mitteilungen: 2228
Wohnort: Franken
  Beitrag No.3, eingetragen 2022-05-23

Mir scheint das Basisverfahren, bei dem die Bearbeitungszeiten vorab bekannt sind (also err = 0) schon nur eine Heuristik zu sein und nicht unbedingt optimale Loesungen zu liefern. Wenn ich z. B. zwei isolierte Jobs (1, 2) und zwei Arbeiter (A, B) habe und die folgenden Arbeitszeiten fuer die Aufgabe habe: A1=10, B1=11, A2=8, B2=12 habe, hatte Job 1 mit 21 den hoeheren Rang als Job 2 mit 20, daher wuerde Arbeiter A zuerst den Job 1 zugewiesen bekommen, da er ihn schneller erledigen kann und Arbeiter B im naechsten Schritt Job 2. Dadurch betraegt die Gesamtbearbeitungszeit 12, da Arbeiter B fuer Job 2 zwoelf Zeiteinheiten benoetigt. Haette man dagegen die Jobs getauscht, waere man schon nach 11 Minuten fertig geworden. Ich finde es nun schwierig darueber nachzudenken, wie man einen Algorithmus, der im einfachen Fall schon nicht zuverlaessig arbeitet in einem komplexeren Fall so anpassen soll, dass er dann ... -- ja, ... ich bin unsicher, was ich dann von dem "verbesserten" dann Algorithmus ueberhaupt erwarten koennen darf ... Um aber die Heuristik noch etwas besser zu verstehen haette ich noch ein paar Fragen, mit welchen Situationen ueblicherweise zu rechnen ist: Wie haeufig kommen Wartezeiten vor? Passiert es regelmaessig, dass Arbeiter auf eine Aufgabe warten muessen, bis andere Arbeiter die Abhaengigkeiten erledigt haben? Oder spielen die eine untergeordnete Rolle und koennen erst mal vernachlaessigt werden? Wie sind die "Faehigkeiten" der Arbeiter verteilt? Gibt es "bessere" Arbeiter, die im Wesentlichen alle Aufgaben schneller erledigen koennen als andere (z. B. aufgrund ihrer laengeren Erfahrung), bzw. "langsamere" (z. B. "Anfaenger"), die tendentiell fuer alles laenger brauchen? Oder gibt es "Experten", die jeweils einen bestimmten Typ Aufgabe besonders gut koennen und die anderen Aufgaben mehr oder weniger in "normaler" Zeit bearbeiten. Bzw. gibt es Arbeiter, denen bestimmte Aufgaben "nicht liegen" und die uebermaessig lange fuer diesen Typ Aufgabe benoetigen, aber die uebrigen Aufgabentypen in "normaler" Zeit bearbeiten koennen? Von wie vielen anderen Aufgaben ist eine Aufgabe typischerweise Abhaengig? Ist das nur i.d.R. max. eine oder mal zwei, oder sind Aufgaben haeufig von vielen anderen Aufgaben abhaengig? Wie viele andere Aufgaben haengen von einer Aufgabe ab? Ist das i.d.R. auch nur max. eine oder mal zwei oder sind auch hier haefig viele andere Aufgaben von einer anderen Aufgabe ab? Und wie "separiert" ist der DAG? Besteht er im Wesentlichen aus vielen unabhaengigen "Produktgruppen" die nur untereinander "vernetzt" sind, oder ist er ein grosses Netz in dem fast alles ueber Umwege irgendwie voneinander abhaengig ist? Grundsaetzlich wuerde ich mir erst mal anschauen, wo grosses Einsparpotential liegt. Aufgaben, die von einem Arbeiter viel schneller bearbeitet werden koennen als von den anderen wuerde ich gerne irgendwie versuchen, diesem zuzuweisen und umgekehrt wuerde ich gerne vermeiden, dass ein Arbeiter eine Aufgabe zugewiesen bekommt, die er nur viel langsamer bearbeiten kann als die uebrigen Arbeiter. Zum anderen wuerde ich Wartezeiten (und Leerlauf) versuchen wollen zu vermeiden. Dadurch ergbit sich insgesamt eine hohe Auslastung mit Aufgaben, die die Arbeiter jeweils einigermassen gut bearbeiten koennen, wodurch die Gesamtzeit automatisch relativ gering werden sollte. Ich denke, dass das aktuelle Ranking diese beiden Aspekte noch zu wenig beruecksichtigt.


   Profil
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 266
  Beitrag No.4, vom Themenstarter, eingetragen 2022-05-23

Hallo, Die Anzahl der Wartezeiten hängt von der Struktur des DAG ab und die kann sehr unterschiedlich ausfallen, im allgemeinen gibt es aber in jedem DAG Abhängigkeiten, ein vollends isolierter Graph kommt nicht vor. Abhängig davon, wie Aufgaben zu Arbeitern zugeteilt werden kann die Wartezeit für Aufgaben natürlich im selben DAG auch variieren. Das einzige Ziel ist es, die gesamte Zeitspanne, in der Aufgaben bearbeitet werden, zu minimieren. Man kann dafür in Kauf nehmen, einen Arbeiter eine Zeit lang unbeschäftigt zu lassen. Die Arbeiter sind meistens entweder "besser" oder eben nicht, sie können dann die meisten Aufgaben ähnlich viel schneller oder langsamer ausführen. Allerdings kann es auch sein, dass ein Beispiel wie du es angegeben hast eintritt. Es kann also Experten geben. Im allgemeinen ist aber nicht bekannt, ob ein Arbeiter ein Experte ist, oder einfach besser. Die DAG Struktur kann sehr stark variieren, aber da der DAG im Allgemeinen relativ groß ist (>1000 Aufgaben) ist eine Aufgabe von vielen anderen abhängig, mehr als 1 oder 2. Da die DAG Struktur variiert, kann sowohl der Fall der einzelnen Produktgruppen als auch der Fall des fast vollständig über Umwege vernetzten DAGs auftreten. Ich versuche in erster Linie einen Weg zu finden, den Fehler in der geschätzten Bearbeitungszeit klug auszunutzen, hast du da vielleicht eine Idee? Es ist meiner Erfahrung nach nicht so leicht den Algorithmus zu verbessern.


   Profil
Bozzo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.04.2011
Mitteilungen: 2228
Wohnort: Franken
  Beitrag No.5, eingetragen 2022-05-23

Rein gefühlsmäßig würde ich "f(est, err) = est + c * err" setzen, wobei ich für c Werte im Bereich zwischen 0.5 und 2.0 ausprobieren würde. Aus meiner Sicht kann man da nicht viel anderes machen, als einfach zu testen, was in der Praxis gute Ergebnisse liefert, ohne den ganzen Algorithmus von Grund auf auf den Kopf zu stellen. Grundsätzlich noch ein paar Überlegungen dazu: 1. Das Problem kann Abhängigkeits- oder Arbeitsbeschränkt sein. D. h. die Gesamtarbeitszeit kann sich im Wesentlichen durch die "längste Kette" ergeben (dann gibt es i.d.R. rel. viele Warte- und/oder Leerlaufzeiten), -- dann muss die optimale Lösung "um diese herum" gebaut werden. Oder es kann sich einfach durch das gesamte Arbeitspensum ergeben, in dem Fall arbeiten alle Arbeiter fast pausenlos und die Abhängigkeitsstruktur spielt nur eine untergeordnete Rolle weil es eh immer irgendwas zutun gibt -- dann ist das wichtigste, keine "doofen" Zuteilungen zu machen, bei denen Arbeiter konträr zu ihren Fähigkeiten eingesetzt werden. 2. Nehmen wir mal an, wir hätten zwei "Aufgabenketten" (a1, a2, a3) und (b1, b2, b3) und zwei Arbeiter A und B, von denen Arbeiter A im Mittel bei jeder Aufgabe etwas schneller als B ist, dafür jedoch eine deutliche höhere Unsicherheit in der Ausführungszeit aufweist. Konkret sagen wir einfach mal dass für alle Aufgaben est(A) = 10, err(A) = 5, est(B) = 12, err(B) = 1 sei (ich schreibe das ab jetzt als 10(5) und 12(1), wobei vor der Klammer "est" steht und in der Klammer "err"). Rein gefühlsmäßig würde ich mal behaupten, dass es keine bessere (a-priori) Lösung gibt, als einfach Arbeiter A die Aufgaben (a1, a2, a3) der Reihe nach abarbeiten zu lassen und gleichzeitig Arbeiter B die Aufgaben (b1, b2, b3). Arbeiter A braucht für seine Aufgaben insgesamt dann 30(8.7) und Arbeiter B 36(1.7), wenn man die Arbeitszeiten für die einzelnen Aufgaben als unabhängig voneinander annehmen kann. Die Arbeitszeitdifferenz beträgt dann 6(8.8) und ist mit etwa 25% W'kt negativ, d. h. in etwa 1/4 der Fälle ist Arbeiter B vor Arbeiter A fertig. Wenn du rein nach dem Erwartungswert gehst, kannst du die Unsicherheiten wahrscheinlich komplett vernachlässigen. Diese werden allerdings dann interessant, wenn du "auf Nummer sicher" gehen willst, und z. B. an der "Lösung" interessiert bist, die auch im "95%-Worst-Case" immer noch am besten ist ("Worst-Case" der 95% "besten" Fälle). Die Kunst dabei ist das "Risiko" abzuschätzen, dass durch die Verzögerungen entstehen kann und sich zu überlegen, wie viel "erwartete Bearbeitungszeit" man bereit ist dafür zu "bezahlen" etwas "eventuelle Bearbeitungszeit" einsparen zu können.


   Profil
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 266
  Beitrag No.6, vom Themenstarter, eingetragen 2022-05-27

Danke für die Tipps. Wenn du den ursprünglichen Algorithmus abändern solltest und statt der Normalverteilung eine Exponentialverteilung für den Fehler gegeben wäre mitsamt Parametern, welche Änderungen würdest du vornehmen? Ich habe mir gedacht man kann den DAG weiter "untersuchen" und in isolierte Untergraphen aufteilen, falls das möglich ist. Aber das ist ja auch nicht so oft der Fall.


   Profil
Bozzo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.04.2011
Mitteilungen: 2228
Wohnort: Franken
  Beitrag No.7, eingetragen 2022-05-29

Exponentialverteilte Bearbeitungszeten klingt deutlich einfacher, weil die Situation dadurch gedaechtnislos wird und sich Markow-Theorie leichter einsetzen laesst. "Warteschlangentheorie" untersucht aehnliche Situationen, vlt. gibt es dort ein Modell, das nahe genug dran ist, um die Situation von dort startend zu modellieren. Leider habe ich aber gerade keine Zeit, mich da tiefer reinzudenken.


   Profil
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 266
  Beitrag No.8, vom Themenstarter, eingetragen 2022-05-29

Danke ich recherchiere gerade. Und wenn der Fehler nun doch Normalverteilt wäre und du den Algorithmus verbessern würdest, was würdest du ausprobieren?


   Profil
Bozzo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.04.2011
Mitteilungen: 2228
Wohnort: Franken
  Beitrag No.9, eingetragen 2022-05-29

Zunächst mal ist mir noch gar nicht so richtig klar, wie überhaupt das Ergebnis des Algorithmus aussehen sollte. Z. B. könnte man eine Liste von Aufgaben pro Arbeiter generieren, die dieser in der entsprechenden Reihenfolge abarbeite soll, wobei er wartet, wenn die Voraussetzungen für seine nächste Aufgabe noch nicht erfüllt sind. Das würde eine Reihe von disjunkten Listen ergeben und zu jeder dieser "Lösungen" könnte man nun die erwartete Bearbeitungszeit und deren Varianz berechnen oder ein passendes Quantil. Man könnte auch jedem Arbeiter eine Menge aus Paaren mit Aufgaben und Prioritäten zuordnen und ihn immer wenn er mit einer Aufgabe fertig ist diejenige "verfügbare" Aufgabe aus der Liste mit der höchsten Priorität zuordnen oder ihn warten lassen, wenn gerade keine weitere Aufgabe verfügbar ist. In dem Fall können Aufgaben (ggf. mit unterschiedlicher Priorität) verschiedenen Arbeitern "gleichzeitig" zugewiesen werden und es ist am Ende vom Zufall abhängig, wer welche Aufgabe konkret bearbeitet. Bei der Art der Lösung würde ich versuchen, etwas möglichst "Allgemeines" zu finden, mit dem sich jeder Typ Strategie gut abbilden lässt (z. B. sowohl solche, bei denen ich am Anfang einen festen Plan mache, der dann stupide abgearbeitet wird, als auch solche, bei denen ich abhängig davon wie es bisher gelaufen ist ggf. neue Entscheidungen treffen kann), dabei aber schon versuchen "unsinnige" Handlungen möglichst von vorne herein auszuschließen (man könnte sich z. B. fragen, ob es Sinn machen kann, dass ein Arbeiter eine Aufgabe noch nicht bearbeitet, obwohl deren Voraussetzungen schon erfüllt sind, und erst noch abwartet, ob ein anderer Arbeiter rechtzeitig mit einer bestimmten Aufgabe fertig wird, oder ob der Arbeiter auch immer schon gleich mit der Aufgabe begonnen haben könnte, wenn sie ihm schlussendlich auch zugeteilt wird -- das ist denke ich nicht offensichtlich). In jedem Fall würde ich zunächst versuchen, jeder möglichen "Lösung" einen Wert zuzuteilen, wie "gut" diese ist um dann irgendwas zum optimieren zu haben um überhaupt nach einer "idealen" Lösung suchen zu können. Ich denke aber, die Aufgabenstellung mit der exponentialverteilten Bearbeitungszeit ist deutlich einfacher und könnte mir gut vorstellen, dass sich aus deren Untersuchung auch ein besseres Verständnis für den normalverteilten Fall ergeben könnte, weswegen ich tatsächlich mit dem Fall anfangen würde. Z. B. bei vier Aufgaben 1, 2, 3, 4 mit zwei Abhängigkeiten (1,2) und (3,4) und zwei Arbeitern A und B, die für die Aufgaben im Schnitt jeweils a1, a2, a3, a4, b1, b2, b3, b4 benötigen kann man eine Markow-Prozess mit Zuständen der Form (T|A,B|S) aufstellen, wobei T die bereits erledigten Aufgaben, A die Aufgabe die gerade von A erledigt wird, BM die Aufgabe, die gerade von B erledigt wird und S die noch nicht zugeteilten Aufgaben bezeichnet, wobei T, A, B, S disjunkte Mengen von Aufgaben sind, die zusammen alle Aufgaben enthalten (eine "Partititon") und A und B maximal je eine Aufgabe enthalten. Der Prozess startet mit s = ({},{},{},{1,2,3,4}) und endet in t = ({1,2,3,4},{},{},{}). Es gibt z. B. Übergänge von (T|{i},{j}|S) zu (T+{i}|{},{j}|S) mit "Rate" 1/ai und zu (T+{j}|{i},{}|S) mit Rate 1/bj. Von (T|{i},{}|S) kann man entweder mit Rate 1/ai zu (T+{i}|{},{}|S) gehen, wenn man "nichts" tut, oder direkt mit Rate rj zu (T|{i},{j}|S\{j}) wenn man Aufgabe j an Arbeiter B zuweist. Die Übergansraten, die entstehen, wenn eine Aufgabe abgearbeitet wird, ergeben sich aus den Bearbeitungszeiten der einzelnen Arbeiter für die einzelnen Aufgaben. Nach den Raten rj (in jedem Zustand unterschiedlich), mit der in den einzelnen Situationen neue Aufgaben zugewiesen werden, sollte optimiert werden. In Abhängigkeit von diesen Parametern kann die "Intensitätmatrix" Q für den Markow-Prozess aufgestellt werden aus der berechnet werden kann, wie lange sie im Schnitt von s nach t benötigt und diese Dauer sollte relativ einfach nach den Übergangsraten zur Jobzuteilung optimierbar sein. Dabei würde ich erwarten, dass je ein rj gegen undendlich geht (z. B. bei einem iterativen Algorithmus immer größer wird), was bedeutet, dass das der entsprechende nächste Job ist, der in der Situation zugeteilt werden sollte. Ob das so durch geht, bin ich nicht ganz sicher, würde das aber mal als ersten Ansatz so versuchen.


   Profil
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 266
  Beitrag No.10, vom Themenstarter, eingetragen 2022-05-29

Das Ziel ist es, eine Bearbeitungsreihenfolge zu finden, also eine Zuordnung von Aufgaben zu Arbeitern, welche die Gesamtdauer vom Start der ersten Aufgabe bis zum Ende der letzten Aufgabe minimiert. Sorry, das ist untergegangen ich dachte ich hätte es am Anfang erwähnt.


   Profil
Bozzo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.04.2011
Mitteilungen: 2228
Wohnort: Franken
  Beitrag No.11, eingetragen 2022-05-30

Das ist nicht untergegangen, aber mir ist nicht so ganz klar, was das nun genau bedeutet. Darum habe ich zwei verschiedene Beispiele gemacht, "was" eine Lösung sein könnte (eine Liste pro Arbeiter, mit Jobs in bestimmter Reihenfolge oder alternativ eine Prioritätslist, aus der der Reihe nach Jobs gezogen werden). Mit beiden Varianten sind verschiedene Strategietypen abbildbar und wenn man sich hier von vorneherein ungünstig einschränkt, kann sich das am Ende auf die "Effektivität" des Lösungsalgorithmus auswirken. Idealerweise sollte man jedem Arbeiter immer nach Beendigung seiner aktuellen Aufgabe eine neue Aufgabe auf Basis des aktuellen Wissenstands (welche Aufgaben schon abgearbeitet sind und wie lange die Arbeiter schon an ihrer aktuellen Aufgabe sitzen) zuteilen. Wahrscheinlich braucht man dazu auch "virtuelle Warteaufgaben", wie z. B. "Neue Aufgabe: Warte bis Arbeiter X mit Aufgabe Y fertig ist oder schon Zeit Z daran gesessen ist". Wie beschreibt man aber eine "Strategie" die so eine "Just-in-Time"-Zuweisung durchführt, damit man ihre Gesamtbearbeitungszeit berechnen kann und ihr so einen "Wert" zum Optimieren zuordnen kann?


   Profil
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 266
  Beitrag No.12, vom Themenstarter, eingetragen 2022-05-30

Bisher habe ich es mit einer einzigen Prioritätsliste versucht. Ja die virtuellen Warteaufgaben sind nötig, eine optimale Lösung kann beinhalten, dass man einen Arbeiter eine Zeit lang unbeschäftigt lässt obwohl Aufgaben zur Verfügung stehen. Was deine letzte Frage angeht habe ich keinen guten Einfall. Edit: Eine Partition in Form von Listen, die jedem Arbeiter zugeteilt werden habe ich nicht gewählt weil das wie du schon erwähnt hast in Richtung JIT geht.


   Profil
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 266
  Beitrag No.13, vom Themenstarter, eingetragen 2022-05-31

Wenn man den urspünglichen Algorithmus ohne die Fehlerverteilung benutzt kommt man auf passable Ergebnisse, auch wenn man Fälle konstruieren kann, in denen er nicht optimal ist. Hast du eine Vermutung woran das liegen könnte?


   Profil
Bozzo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.04.2011
Mitteilungen: 2228
Wohnort: Franken
  Beitrag No.14, eingetragen 2022-06-01

Der Algorithmus schaut ja ein wenig voraus und versucht zumindest mal nicht die duemmsten Entscheidungen zu treffen. Da kann schon was ganz passables bei herauskommen. In den meisten Faellen wuerde man es ja aber auch gar nicht merken, wenn es noch eine bessere Loesung gaebe, solange einen da niemand draufstoesst.


   Profil
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 266
  Beitrag No.15, vom Themenstarter, eingetragen 2022-06-01

Ich meinte - hast du eine Vermutung woher die Diskrepanz kommt. Ich kann mir nicht erklären warum der Algorithmus so schlecht wird, wenn man den Fehler einführt.


   Profil
Bozzo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.04.2011
Mitteilungen: 2228
Wohnort: Franken
  Beitrag No.16, eingetragen 2022-06-02

Vermutlich wird er Lösungen bevorzugen, bei denen er sich sicher ist, dass sie auch im Worst-Case nicht allzulange dauern, auch wenn diese im Mittel nicht so gut sind, gegenüber Lösungen, die zwar im Mittel schnell gehen, aber im Worst-Case etwas länger dauern. Wahrscheinlich ist es besser, im Algorithmus nur mit den Erwartungswerten zu rechnen und nach jeder Aufgabe, die beendet wurde, mit der aktuellen Information einen neun Planungsschritt durchzuführen, um herauszufinden, welche Aufgabe als nächstes zugeteilt werden sollte. Wenn ein Arbeiter dabei eine Aufgabe bereits seit Zeit t bearbeitet, für die er μ(σ) erwartete Zeit benötigt, sollte damit gerechnet werden, dass er im Mittel noch $\sigma \cdot (\frac{\varphi(\tau)}{1-\Phi(\tau)} - \tau)$ benötigt (Erwartungswert der abgeschnittenen Normalverteilung), wobei $\tau = \frac{t-\mu}{\sigma}$ ist und $\varphi$ und $\Phi$ die Dichte und Verteilungsfunktion der Standardnormalverteilung sind.


   Profil
dvdlly hat die Antworten auf ihre/seine Frage gesehen.
dvdlly hatte hier bereits selbst das Ok-Häkchen gesetzt.
dvdlly wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 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]