Informatiker Board | Druckvorschau: progressive filling Algorithmus für max-min faire Ratenallokation

Geschrieben von deppensido am 16.09.2015 um 15:16:

progressive filling Algorithmus für max-min faire Ratenallokation

hallo,

ich versuche momentan den progressive filling Algorithmus zur Berechnung einer max-min fairen Ratenallokation anhand einer Beispiel Aufgabe zu verstehen (siehe Anhang). Allerdings kann ich die Lösung überhaupt nicht nachvollziehen. So wie ich den Algorithmus bisher verstanden habe, setzt man zunächst R (für Ratenallokation) auf 0, hier also R = [0,0,0] da man drei Nutzer hat und dann füllt man die Rate gleichmäßig an, bis die Ressource verbraucht ist. In diesem Fall hat man 50 Stunden für die Zentrifuge und 30 Stunden für das Massenspektrometer. In der Lösung geht man jetzt nur auf die 30 Stunden ein, warum nicht auch auf die 50 ? Desweiteren versteh ich nicht, was überhaupt mit VA1, VB1, VC1 und Rneu gemeint ist. Das man in der Lösung nun auf Rneu = [4,4,4] kommt und danach auf 16 versteh ich auch nicht. Auf Rneu = [4,4,4] vielleicht weil Nutzer VB ein Ressourcenverbrauchsverhältnis von [1,4] hat? Ich hoffe mir kann jemand erläutern was genau in der Lösung gemacht wurde. Vielen Dank im voraus.

Geschrieben von eulerscheZahl am 16.09.2015 um 15:43:

Ich habe zwar noch nie etwas von dem Algorithmus gehört, denke aber ich kann mir denken, was die Lösung tut:
Wenn wir als Zeitbasis Stunden nehmen (also Anton 3 Studen mit der Zentrifuge und eine mit dem Massenspektrometer verbringt), dann gibt das in Summe: [4, 7].
Es ist 50/4 = 12 Rest 2 und 30/7=4 Rest 2 (von minutenweiser Zuteilung hält deine Lösung scheinbar nichts).
Folglich darf Anton 4 mal in der Woche seine gewünschten Stunden arbeiten.
Und die Auslastung der Zentrifuge ist 4(Anteil der Zentrifuge in []4,7]) * 4 (Ergebnis der Division) = 16. In deiner Lösung ist das noch anteilig auf die einzelnen Personen aufgeteilt.

Geschrieben von deppensido am 16.09.2015 um 17:01:

hallo,

danke, ich glaub ich hab es versanden. Also die Zentrifuge darf 50 Stunden genutzt werden und wird tatsächlich 50/7 = 12,5 Stunden benötigt und das Massenspektometer darf 30 Stunden genutzt werden und wird tatsächlich 30/7 = 4,2857 Stunden benötigt. Für Rneu wird dann das niedrigere Ergebnis genutzt um die Raten aufzufüllen also 4. Und da jeder das Massenspektometer benötigt werden die Nutzer alle eingefroren, womit R = [4,4,4] das Ergebnis ist. Und von der Zentrifuge bleiben 50 - (4*3+4*1+4*0) = 34 Stunden ungenutzt, womit diese: 50 - 34 = 16 Stunden genutzt wird. Hab ich das alles so richtig erläutert?

Geschrieben von eulerscheZahl am 16.09.2015 um 18:57:

Zitat:

Original von deppensido
Also die Zentrifuge darf 50 Stunden genutzt werden und wird tatsächlich 50/7 = 12,5 Stunden benötigt
[...]
Hab ich das alles so richtig erläutert?

Nein. Das sind keine Stunden, das ist ein möglicher Multiplikator: [3,1]*12.5 + [1,4]*12.5] + [0,2]*12.5 = [50, 87.5]
Mit diesem Multiplikator wird aber die Auslastung für das Massenspektrometer zu hoch.