Sortier Algorithmus

  • VB.NET

Es gibt 21 Antworten in diesem Thema. Der letzte Beitrag () ist von vico255.

    Sortier Algorithmus

    Ich bin hier jetzt schon eine Weile am grübeln und komme nicht wirklich zu einem Nenner. ?(

    Folgendes Problem einfach dargestellte.
    Ich habe 3 Kisten und einen Stein. Lege ich jetzt den Stein in jede Kiste, habe ich 3 Möglichkeiten.
    Benutze ich 2 Steine, komme ich auf 9 Möglichkeiten (3^2).

    Ich suche nach einer Function(anz Steine) - Die jede Möglichkeit durchgeht und 3 Kisten füllt (Listboxen)

    ZB. für 2 Steine soll das dann so aussehen.
    Stein 1 = 1
    Stein 2 = 2
    0 = Kein Stein

    K1...K2...K3
    ___________
    1/2...0...0
    1....2....0
    1....0....2
    2....1....0
    0...1/2...0
    0...1.....2
    2...0.....1
    0...2.....1
    0...0...1/2

    Vlt kann man da jemand n Tipp zu geben. Danke
    In Arbeit...

    vico255 schrieb:

    Lege ich jetzt den Stein in jede Kiste
    Das musst Du mir zeigen, wie das geht. ;)

    vico255 schrieb:

    Benutze ich 2 Steine
    Sund die unterscheidbar (numeriert oder verschieden farbig)?
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Ja der eine ist blau und der andere rot ;)

    Sollte nur zur einfachen Erklärung sein :)
    Die Function soll halt für n Steine möglich sein.

    Hintergrund ist, die Steine sind Auftragsnummern, die abhängig ihres Gewichts und Material unterschiedliche Bearbeitsungdszeiten haben.
    Habe ich alle Möglichkeiten, kann ich mir die beste ausrechnen und somit laufen die 3 Anlagen am effektivsten.
    In Arbeit...

    RodFromGermany schrieb:

    Sund die unterscheidbar

    Anhand der Testdaten schon, da man für

    Quellcode

    1. 1 0 2
    2. 2 0 1


    offenbar 2 Möglichkeiten loggt.

    (1 == "Stein 1")
    (2 == "Stein 2")

    Lg, Acr0most
    Wenn das Leben wirklich nur aus Nullen und Einsen besteht, dann laufen sicherlich genügen Nullen frei herum. :D
    Signature-Move 8o
    kein Problem mit privaten Konversationen zu Thema XY :thumbup:

    vico255 schrieb:

    Die Function soll halt für n Steine möglich sein.
    Poste bitte eine belastbare und vollständige Aufgabenstellung / Problembveschreibung, dass nicht nach jedem Vorschlag von Dir kommt: Dieses und jenes soll es auch noch können.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Hi
    so wie ich das verstehe, versuchst du Aufgaben so zu parallelisieren, dass die benötigte Zeit insgesamt minimal wird, oder?

    Falls ja, beantworte bitte folgende Fragen:
    1. Um wieviele Aufgaben handelt es sich grob?
    2. Um wieviele parallele Prozesse handelt es sich? (grober Schätzwert, mehr als z.B. 1000 oder weniger?)
    3. Genügt eine Schätzung oder muss es exakt sein?
    4. Kommen weitere Aufgaben hinzu oder ist die Aufgabenliste statisch (während des Verarbeitungsintervalls)?

    Viele Grüße
    ~blaze~

    Vollzitat entfernt. ~Trade
    @RodFromGermany OK.
    Mir geht es um das Auflisten jeder möglichen Konstellation siehe Post 1#
    Da es mir jetzt nicht bekannt ist wieviele Aufträge geplant sind. Habe ich mir gedacht, jede Mögliche Abfolge durchzuspielen und mir die kürzeste Bearbeitsungszeit,
    anhand der x Möglichkeiten auszurechnen.
    Mein Problem ist momentan, das es an Auflistung hapert.

    @~blaze~
    1) Im Schnitt zwischen 10 und 50 Aufträge
    2) müssen auf 3 Anlagen verteilt werden
    3) Sollte bei der Stückzahl exakt zu lösen sein?
    4) Das ist ein laufender Prozess, fertige Aufträge verschwinden aus der Auflistung, neue kommen hinzu. Aber das ist nicht das Problem, denk ich.
    In Arbeit...

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Trade“ ()

    Punkt 4 ist ein Problem. Wenn ein neuer Auftrag eingeht, ändert sich ja ggf. die effizienteste Lösung für das gesamte Problem.

    Ich garantiere dir zwar nicht die effizienteste Lösung, aber wie wäre es damit? Immer der nächst freie Thread nimmt sich der nächsten Aufgabe an:
    - Erstelle eine Klasse, die IDisposable implementiert
    - Verwende eine Queue, die von allen Threads verwendet wird (SyncLock auf ein gemeinsames Objekt (New Object()), sobald auf die Queue zugegriffen wird)
    - Solange kein Element in der Queue ist, wartet der Thread über Monitor.Wait auf dem Synchronisationsobjekt
    - Wenn ein neues Element in die Queue gegeben wird, wird Monitor.PulseAll für das Synchronisationsobjekt aufgerufen (einer der freien Threads nimmt sich dieser Aufgabe an) (Verbiete dies, falls die Instanz über Dispose freigegeben wurde)
    - Zähle die Anzahl der aktiven Threads (d.h. Inkrementiere über Threading.Interlocked, sobald ein Thread aktiv wird, dekrementiere mit selbigem, sobald der Thread in den Zustand "wartend" übergeht)
    - Wenn ein Thread in den Zustand wartend übergehen würde, überprüfe, ob die Instanz über Dispose freigegeben wurde
    - Bei Dispose rufe ebenfalls Monitor.PulseAll auf und warte anschließend über Monitor.Wait darauf, dass obiger Zähler 0 erreicht

    Innerhalb der Abarbeitungsschleife (einfach Do-Loop ohne Bedingung):
    - Beginne einen Synchronisationsblock über SyncLock auf dem Synchronisationsobjekt
    - Wiederhole: Überprüfe, ob die Queue leer ist, falls ja, überprüfe, ob _disposed. Wenn _disposed, rufe Exit Do auf - sonst warte über Monitor.Wait auf dem Synchronisationsobjekt (Zähler entsprechend inkrementieren oder dekrementieren)
    - Sobald ein Auftrag drin ist (--> Count > 0), rufe diesen ab und speichere ihn zwischen
    - Verlasse den Synchronisationsblock
    - Arbeite den Auftrag ab

    Nach der Schleife:
    Rufe Monitor.PulseAll auf, damit Dispose abbrechen kann (welches ja auf Zähler = 0 wartet).


    Obige Prozedur sollte hinreichend optimieren und alle Aufträge vollständig abarbeiten (damit das passiert, ist die Dispose-Routine so umständlich implementiert). Das funktioniert übrigens für eine beliebige Anzahl an Threads, nicht nur für 3. Eine gute Wahl ist z.B. Environment.ProcessorCount.
    Aufträge kannst du als Action implementieren, wodurch du beliebige Aufträge abarbeiten kannst.

    Viele Grüße
    ~blaze~

    vico255 schrieb:

    Im Schnitt zwischen 10 und 50 Aufträge


    Mal angenommen du hast nur 2 Maschinen. Für die 10 Aufträge gibt es dann 2^10 = 1024 verschiedene Kombinationen, sie an die zwei Maschinen zuzuweisen. Bei 50 Aufträgen ist es dann schon 2^50, was grob so um die 10^16 ist. Das ist eine Eins mit sechzehn Nullen.
    Bei 3 Maschinen wird's noch schlimmer: 3^10 = 59049, 3^50 = ~ 10^23.
    Sowas lässt sich nicht wirklich ohne Strategie lösen. Du hast geschriben, es sind "Auftragsnummern, die abhängig ihres Gewichts und Material unterschiedliche Bearbeitsungdszeiten haben". Welche Eigenschaften haben die genau und wie stellst Du fest, welcher Auftrag am besten für welche Maschine geeignet ist? Da lässt sich sicher eine effiziente Lösung finden.

    Edit: War als Antwort auf Post #8 gedacht.
    Ich hatte das jetzt eher so verstanden, dass hier modelliert werden soll, wie Aufträge in der realen Welt auf Anlagen (irgendwelche Fertigungsmaschinen?) verteilt werden sollen.
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Niko Ortner“ ()

    Das ist nicht sonderlich kompliziert. Versuche einfach mal, mehrere Threads aus einer Queue Aufträge entnehmen zu lassen
    Zulässiges Werkzeug sind SyncLock und Queue(Of T).

    Die Threads arbeiten dabei endlos.

    Anschließend arbeite ein "Warten bis ein Auftrag vorhanden ist" ein.

    Und danach mache dich an das Abbruchkriterium über Dispose.

    Der signifikante Unterschied zur optimalen Lösung zeigt sich übrigens erst am Schluss. Wenn ein eingehender Auftrag länger benötigt, als die anderen, wäre es unter Umständen geschickter, den kürzeren auf einem anderen Thread zu verarbeiten.

    Optimalität erreichst du, indem du alle Möglichkeiten durchgehst und dir jene herauspickst, die die geringste Zeit benötigt.
    Dazu musst du halt alle Permutationen aller Aufträge und Behälter wählen und jene weglassen, die. definitiv nicht zu einer optimalen Lösung führen. Beachte, dass die Behälter nicht unterscheidbar sind.

    Viele Grüße
    ~blaze~

    Ich hatte das jetzt eher so verstanden, dass hier modelliert werden soll, wie Aufträge in der realen Welt auf Anlagen (irgendwelche Fertigungsmaschinen?) verteilt werden sollen.


    Ja es handelt sich um 3 Linien wo Werkstoffe vergütet werden. Jeder Werkstoff hat einen andere Anlasstemperatur und dementsprechend gibt es ab gewissen Temperatur Unterschieden zwischen den Aufträgen unterschiedliche Pausenzeiten. Haben wir jetzt x Aufträge, so werden die anhand der Erfahrung den Linien zugeteilt. Das ist aber mit Sicherheit nicht der optimale Wert. Deshalb wollte ich: Jede möglichkeit durchspielen und mir die beste Aufteilung merken und verwenden.
    Über das Wochenende können bei vielen kleinen Aufträgen durchaus 15 auf einer Linie geplant sein.

    Viele Grüße
    In Arbeit...

    Also geht es nicht um das Programmieren eines parallelen Ablaufs, sondern tatsächlich um die Berechnung der optimalen Verteilung? Mit dem Modell vom Anfang hast du mich da wohl auf die falsche Fährte geführt, sorry.

    Zu dem Punkt von Niko Ortner: Vergiss nicht, dass du über gut gewählte Kriterien bereits einige der Lösungen filtern kannst. So fallen bereits jene Fälle weg, die eine der Linien leer lässt oder ein starkes Ungleichgewicht schafft. Ebenso können die Wiederholungen weggelassen werden - zumindest, wenn es keine Rolle spielt, welcher Job auf welcher Linie durchgeführt wird.
    Wenn man die Aufträge in ihrer Dauer sortiert und zuerst die großen immer an die kürzeste Schlange anhängt, erhält man zumindest schon mal eine gute Näherung.

    Mit meinem überfüllten Kopf kriege ich auf jeden Fall gerade keine schöne Lösung für dieses eigentlich nicht mal so (nicht bzgl. der Komplexität bzgl. Laufzeit) schwere Problem mehr hin.

    Viele Grüße
    ~blaze~

    Nein @~blaze~, meine Schuld, hätte früher mit der Sprache rauskommen oder es besser erklären koennen.

    Ich versuche es nochmal besser.

    Angenommen ich hätte 20 Aufträge zwischen 300 und 500 Grad. Das Gewicht spielt nur eine Rolle, weil die Linien über einen Einwaage befüllt werden.
    Sagen wir 30 kg im 120 sec Takt sind das 900kg/h, ergo ein 9t Auftrag läuft 10h und danach kommt der nächste. Wenn der nächste Auftrag 15 Grad (Temperatur +-) nicht überschreitet, beträgt die Pause zwischen dem Auftrag 20 Minuten (15-30 Grad = 50 Min, 30-60 Grad = 120 Min, >60 Grad = 180 Min).

    Das wird momentan wirklich nur aus Erfahrung aufgeteilt. ( logisch manchmal steht eine Linie auch wegen Rep.)
    Deshalb ist es momentan so das eine Linie hohe Temp. und eine niedrige fährt um die Pausenzeiten gering zu halten, aber bei der doch großen Anzahl an Möglichkeiten, kann man das durchaus verbessern.

    Danke trotzdem für deine ausführliche Antwort :)
    In Arbeit...

    RodFromGermany schrieb:

    Poste bitte eine belastbare und vollständige Aufgabenstellung / Problembveschreibung, dass nicht nach jedem Vorschlag von Dir kommt: Dieses und jenes soll es auch noch können.

    vico255 schrieb:

    hätte früher mit der Sprache rauskommen oder es besser erklären koennen.
    Nächster Versuch, ich habs noch nicht ganz verstanden.
    Probier mal, Dein Problem sowohl ohne programmiertechnische als auch ohne physikalische Details zu erläutern.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Ich suche die optimale Verteilung der Aufträge anhand des Gewichts und der Temperatur.

    - Jeder Auftrag kann nur über eine Anlage laufen (also nicht aufgeteilt werden)
    - zwischen jedem Auftrag ist eine Lücke (abhängig der Temperatur < +- 15 Grad 20 Minuten , siehe Post #15)
    - Die laufzeit der einzelnen Aufträge durch die Anlage werden über die Einwaage gesteuert. Ein faktor der sich aber ändert. Zb 30 kg in 120 Sec = 900kg/h ( Ein 1200 kg Auftrag wäre dann in 80 Min in der Anlage.


    Mein Ziel war es alle möglichen Konstellationen zu simulieren und das beste Ergebnis dann auch zu nehmen. (Schnellstmögliche Abarbeitung der Aufträge)


    zb: Auftrag 1-3
    4000 kg (30kg in 120 sec) -> 267 min
    Lücke (20 Grad unterschied = 50 Min) -> 50 min
    1500 kg (29kg in 120 sec) -> 104 min
    Lücke (90 Grad unterschied = 180 Min) -> 180 min
    6000 kg (31kg in 120 sec) -> 387 min
    _________________________________
    Laufzeit über eine Anlage = 988 min ( 16 Stunden und 28 Minuten)



    Bilder

    • test1818.png

      22,62 kB, 1.601×935, 86 mal angesehen
    In Arbeit...

    Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „vico255“ ()

    K1...K2...K3
    ___________
    1/2...0...0
    1....2....0
    1....0....2
    2....1....0
    0...1/2...0
    0...1.....2
    2...0.....1
    0...2.....1
    0...0...1/2


    Es scheitert gerade schon daran eine Function zu schreiben die mir das liefert, ohne dafür x Schleifen verschachteln zu müssen.
    Bei 2 Aufträgen ist das noch übersichtlich aber bei 10 oder mehr. ?( pro run soll er mir halt jede möglichkeit ausspucken.
    Wüsste jemand wie man das am elegantesten löst?
    In Arbeit...

Facebook
Telefonspende