Siegfried-Angel Gevatter Pujals                A                        14 d’octubre de 2011 | FIB

Donat el següent problema:

Un servidor té n processos que triguen  temps cadascun. En quin ordre s’han d’executar per minimitzar el temps d’espera acumulat?

És a dir, donats  on , volem minimitzar  on  és el temps d’espera del procés .

Demostra que la solució òptima és executar els processos per ordre creixent.

Suposem, sense pèrdua de generalitat, que els processos estan ordenats en ordre creixent (és a dir, ). Podem expressar la solució com una permutació  on cada element  identifica l’-èssim procés.

Està clar que  es pot definir de la forma següent:

I que podem simplificar aquesta equació de la següent manera:

Representem la solució de l’algorisme golafre d’ordenar els processos per temps d’execució amb la permutació identitat . Anomenem la solució òptima .

Hi ha dues possibilitats:

Procedim a demostrar que la segona possibilitat no resulta en una solució millor que la de .

Si , hi ha com a mínim dos elements  tals que . Tornem a escriure la 2a l’equació de  descomposant-la de la següent forma:

on .

Així l’efecte dels dos elements  queda limitat a la component .

Amb  hi ha dues possibilitats:

Q.E.D.