[Eff. Alg] Makespan mit Longest Processing Time

[hingiswiss]

Hallo zusammen,

ich darf mal zum Punkt gehen. Beim Beweis wird angenommen, dass p1, p2, p3, ..., pn eine Eingabesequenz minimaler Länge ist, und somit gilt dass der zuletzt fertig werdende Job pn ist.

Was ist eigentlich damit gemeint?

Gruss aus Stolberg.

[mara]

Da gabs imho ne ordnung auf den jobs (p1 <= p2 <= ... < pn). Dann folgt die Aussage, da die Sequenz bzgl. des Makespans minimal ist.

[hingiswiss]

Hallo mara,

danke für die Antwort erstmal. Die Ordnung ist:

p1 >= p2 >= p3 ... >= pn

Es steht, dass der letzte Job, der zuletzt fertig wird, ist pn, also der Job mit der geringsten Laufzeit. Zuletzt fertiger Job = pn.
Ich weiss nicht warum, ich könnte ein Gegenbeispiel anbieten.

Angenommen, n = 5
p1 = 1000
p2, p3, p4, p5 = 2

Bei dem Beispiel wäre p1 ja derjenige Job, der zuletzt fertig wird.

Nun, ich glaube, das hat mit dieser kürzesten Eingabelänge zu tun, sodass der zuletzt fertige Job immer pn (Job mit geringster Laufzeit) ist. Ich weiss nur nicht, was dieser Satz mit Eingabelänge bedeutet.

Vielen Dank..

Gruss aus Stolberg

[mara]

Ich glaube, dein Beispiel ist falsch in diesem Zusammenhang. Es geht um eine Sequenz p1 >=p2 >= ... >=pn, die zum einen die kürzeste solche Sequenz ist UND zum anderen folgendes erfüllt

Makespan der Sequenz > 4/3 opt (meine ich zumindest- hab das skript nicht hier liegen und prüfung is schon länger her)

Geht ja um einen Widerspruchsbeweis afaik.

Dein Beispiel erfüllt die Ordnung, berücksichtigt aber nicht diese Schranke (denn dein Shedule haette in LPT einen MS von - im schlechtesten Fall - 1008 und opt 1000. Benötigt würde aber ein MS von > 1333 ).

Hoffe, dass ich nicht völlig daneben liege.

[hingiswiss]

Ich glaube, dein Beispiel ist falsch in diesem Zusammenhang. Es geht um eine Sequenz p1 >=p2 >= ... >=pn, die zum einen die kürzeste solche Sequenz ist UND zum anderen folgendes erfüllt

Makespan der Sequenz > 4/3 opt (meine ich zumindest- hab das skript nicht hier liegen und prüfung is schon länger her)

Geht ja um einen Widerspruchsbeweis afaik.

Dein Beispiel erfüllt die Ordnung, berücksichtigt aber nicht diese Schranke (denn dein Shedule haette in LPT einen MS von - im schlechtesten Fall - 1008 und opt 1000. Benötigt würde aber ein MS von > 1333 ).

Hoffe, dass ich nicht völlig daneben liege.

Was heißt hier die kürzeste solche Sequenz?

Danke

[mara]

Das es keine Sequenz mit weniger als n Jobs gibt, welche den genannten Makespan von mind. 4/3 macht. Was ist daran schwer zu verstehen