[List-scheduling] Worst case ratio

[Oscar Mopperkont]

Voor een parallel machine probleem kun je het List-Scheduling algoritme gebruiken.

Het List-scheduling algoritme loopt alle taken in willekeurige volgorde af en wijst de desbetreffende taak toe aan de machine die hem het eerste kan verwerken.

Nu is de wordt case ratio voor dit algoritme gelijk aan:

2-1/m

Waarbij m voor het aantal machines staat.

Nu heb ik nooit begrepen waarom er bij List-Scheduling de taken in willekeurige volgorde worden afgwerkt. Want het lijkt mij veel handiger om de taken af te werken van groot naar klein.

Nu heb ik dit toegepast in een programma, voor een vergelijkbaar probleem, en de oplossingen die gevonden worden zijn eigenlijk altijd een globaal optimu, en als er een afwijking is dan is dat 0,01% ofzo.

Nu vroeg ik mij af wat de theorethische worst case ratio is, als je List-Scheduling toepast op "mijn" manier (die volgens mij voor iedereen logischer is).

Kan iemand mij die geven?

Ikzelf dacht dat dat ongeveer gelijk moest zijn aan:
(grootste taak+kleinste taak) / ((som alle taken)/m)

Er is dan ook een bovengrens die begint bij 2, maar deze bovengrens valt volgens mij wel in 99,9% van de gevallen lager uit dan 2-1/m.


_{Misschien is hetnog ff makkelijk om te vermelden, dat de due-date geen rol speelt in het machine probleem. Verder hebben de taken ook geen gewicht.}

[ Voor 10% gewijzigd door Oscar Mopperkont op 24-06-2003 15:29 . Reden: tiepvautjes ]

[Opi]

Hoe is worst case gedefinieerd in dit geval?

Volgens mij wordt List-scheduling gebruikt omdat niet alle taken evenlang duren en daarom de kortere taken eerst afgehandeld kunnen worden zonder dat er op een gewacht hoeft te worden waar veel tijd voor nodig is. Anderzijds hoeven niet alle taken elke iteratieslag uitgevoerd te worden.

offtopic:
Misschien een beetje gare post, maar dit is omdat ik niet precies in zie wat er met worst case bedoeld wordt in een dergelijk geval.

[Oscar Mopperkont]

OpifexMaximus schreef op 24 June 2003 @ 15:17:
Hoe is worst case gedefinieerd in dit geval?

Gewoon, als in slechter kan het niet.

Misschien is hetnog ff makkelijk om te vermelden, dat de due-date geen rol speelt in het machine probleem. Verder hebben de taken ook geen gewicht.

[ Voor 31% gewijzigd door Oscar Mopperkont op 24-06-2003 15:26 ]

[brokenp]

volgens bij blijft de complexiteit hetzelfde, je geeft aan dat er in een willekeurige volgorde de voldende bepaald wordt. Het bepalen van deze willekeurige volgorde heeft als het goed is geen invloed op de worst case complexiteit. Als jij kiest om de grootste als willekeurige aan te wijzen, dan kan dat. Je krijgt evt wel extra tijdscomplexiteit als je al je taken moet sorteren enzo.

[Oscar Mopperkont]

brokenp schreef op 24 June 2003 @ 15:22:
volgens bij blijft de complexiteit hetzelfde, je geeft aan dat er in een willekeurige volgorde de voldende bepaald wordt. Het bepalen van deze willekeurige volgorde heeft als het goed is geen invloed op de worst case complexiteit. Als jij kiest om de grootste als willekeurige aan te wijzen, dan kan dat. Je krijgt evt wel extra tijdscomplexiteit als je al je taken moet sorteren enzo.

Shit! Idd daar een ge-ordende volgorde ook een willekeurige volgorde is Dat ik daar nog niet aan gedacht had

De bovengrens verandert volgens mij toch wel. Doordat de taken in volgorde gezet worden, wordt het aantal toewijzingsmogelijkheden beperkt tot 1, waar dat bij willekeurig vele malen groter is, in de orde van N!/2.

En er vallen dus heel wat worst cases af. Bij de eerste worst-case ga je uit van de slechtst mogelijke volgorde waarin je toewijst. Ik zeg nu dat als je ordent van groot naar klein, dat dit eigenlijk nooit de slechtst mogelijk volgorde is (is wel mogelijk), en je wordt-case ratio dus beter wordt. In ieder geval kun je volgens mij een andere formule hangen aan de worst-case ratio.

Ik wil die formule weten. De bovengrens is iig al bepaald door die 2-1/m, slechter kan het nooi worden, geordend is immers 1 van de mogelijkheden van willekeurig.

[ Voor 35% gewijzigd door Oscar Mopperkont op 24-06-2003 15:40 . Reden: Ik ben van gedachten veranderd ]

[Verwijderd]

Volgens mij is de worst-case scenario als de input van een taak afhankelijk is van de vorige.
In dat geval maakt het niet uit met hoeveel machines/processoren er wordt gewerkt. Het gebeurd in de zelfde tijd als dat er met 1 gewerkt zou worden. (plus wat tijd voor de sceduler om daar achter te komen natuurlijk)

(je zou het maar zo parallel geprogrammeerd hebben, maar het is mogelijk natuurlijk... )

Als ik de vraagstelling niet snap, kom dan maar eventjes met wat voorbeeldjes als je wilt.

[Verwijderd]

Ik kon het even niet laten:

De powerpoint presentatie op csiam.edu.cn/scm/scheduling.ppt
laat een aantal formules zien die ik niet wil analyseren.. maar doe je best zou ik zeggen.

Ik snap alleen de ratio formule 2-1/m niet... wat zegt dat?
en hoewel ik er dus geen idee van heb, zal je worstcase antwoord wel 3-1/m zijn.
(misschien wel 4-1/m... maar dat moet je zelf maar lezen)

[ Voor 8% gewijzigd door Verwijderd op 25-06-2003 02:01 ]

[Oscar Mopperkont]

Verwijderd schreef op 25 June 2003 @ 01:58:
Ik kon het even niet laten:

De powerpoint presentatie op csiam.edu.cn/scm/scheduling.ppt
laat een aantal formules zien die ik niet wil analyseren.. maar doe je best zou ik zeggen.

Ik snap alleen de ratio formule 2-1/m niet... wat zegt dat?
en hoewel ik er dus geen idee van heb, zal je worstcase antwoord wel 3-1/m zijn.
(misschien wel 4-1/m... maar dat moet je zelf maar lezen)

Dat wil zeggen dat de oplossing gevonden met List-Scheduling in het slechtste geval 2-1/m slechter is (op M machines) als de beste oplossing.

Dus stel je hebt 10 machines en de beste oplossing is 20, dan is je met list scheduling gevonden oplossing nooit slechter dan (2-1/m)*20 --> (2-1/10)*20=38

Snappie?

[Oscar Mopperkont]

Subtiel schopje! *kick*