Scheduling: Reihenfolgebeziehung - maximale Wartezeit

[Malou]

Hallo allerseits,

Ich habe mich gerade mit dem Scheduling Problem der maximalen Wartezeit zwischen zwei Jobs auseinandergesetzt und verstehe folgende Formel nicht ganz: delta[k,i] = -(d[_i]+l[i,k]) # Folie 306.

In der Vorlesungsaufzeichnung vom 14.07.2016 (https://www.youtube.com/watch?v=aTYbcfO ... qgNTiT13U6) wird erklärt, wie man auf diese Formel kommt. Dass die Differenz zwischen der Startzeit vom Job k und der Startzeit vom Job i kleiner als die Summe des Dauer von i und die maximale Wartezeit sein muss, verstehe ich. Das ist ja nur die Definition von der maximalen Wartezeit. Wie die ganze Ungleichung mit (-1) multipliziert wird, verstehe ich auch. Jedoch verstehe ich nicht, warum es gemacht wird. Und wie T(i) - T(k) >= -(d[_i] + l[i,k] in delta[k,i] = -(d[_i] + l[i,k]) umgewandelt wird, verstehe ich auch nicht. Warum ist es nicht
delta[k,i] >= -(d[_i] + l[i,k])?

Wenn ich folgendes Beispiel habe: Ein Job i mit Dauer 1, ein Job k mit Dauer 2 und l[i,k] = 2
Dann müsste laut Definition gelten: delta[k,i] = -1 - 2 = -3 bzw. delta[i,k] = 1. Ich will aber so schnell wie möglich mit dem nächsten Job anfangen. Angenommen ich habe keine andere Einschränkung, dann könnte ich direkt nach Job i mit Job j anfangen. Dann würde gelten delta[k,i] = -1. Und das widerspricht die Definition...

Was habe ich mir falsch überlegt?

Kann mir jemand damit helfen?

Vielen Dank im Voraus,

Malou

[steffen.maus]

Hi,

ich versuch mich mal, kann aber nichts garantieren

Die Multiplikation mit (-1) wird gemacht, weil wir auf der linken Seite den Term T(i)-T(k) brauchen. Damit können wir es in unsere Delta-Matrix hineinbringen.
Dass daraufhin >= zu = wird könnte daran liegen, da Semantisch die obere Schranke angegeben wird. Der Algorithmus wird später ohnehin versuchen einen geringeren Wert zu nutzen. Wir machen also aus "Wartezeit: höchstens 5h" ein "Zeit: 5h. Wenn möglich aber kleiner, soll ja optimal werden...".

Bei deinem Beispiel blicke ich leider nicht ganz durch, wo kommt das j her?

Gruß,
Steffen