Resum

Per iniciar aquesta tesi doctoral es va buscar un problema de producció
senzill però de gran aplicació pràctica que permetés adaptar per arribar a
problemes més generals i de més àmplia aplicació. Per aquest motiu, ens
centrem en les màquines paral.leles, i dins d’elles, en les no relacionades donat
que són una generalització dels casos de màquines idèntiques i de les uniformement
relacionades. Vam escollir l’objectiu de minimitzar el temps màxim
de finalització o Cmax, un dels més comuns de la literatura. Aquest problema
té la facultat que, tot i el seu caràcter teòric, té una àmplia aplicació pràctica,
com per al cas de seqüenciar les tasques dels forns de cocció ceràmics. D’altra
banda es volia ampliar el problema per al cas en que no fan falta totes les
màquines o no es fessin tots els treballs necessàriament.
Les metes perseguides són el presentar uns algoritmes senzills i potents per
a la resolució del problema R//Cmax, capaços de constituir-se en l’estat de
l’art. Atès que els moderns ordinadors munten quasi totalment diversos nuclis
a la seva CPU i els algorismes es van adaptant a aquest fet, també s’ha buscat
realitzar una adaptació dels algorismes per al seu ús en paral.lel. Finalment,
es posa com a meta el trobar mètodes eficaços i senzills per a la resolució
de problemes d’aquest tipus on no s’utilitzaran totes les màquines o no es
realitzaran tots els treballs.
En la present tesi doctoral es va realitzar un ampli estudi de la literatura existent
respecte al problema de màquines paral.leles no relacionades i es va extraure
l’estat de l’art, així com un estudi del possible tipus d’instàncies a utilitzar, ja
que no existia una grup d’instàncies tipus per aquest problema.
Es presenten quatre algoritmes inicials senzills que milloren els resultats de
l’estat de l’art en alguns casos i donen millors resultats de mitjana en el conjunt
total de instàncies tractades. Aquests algorismes es basen en mètodes iteratius
en què es realitza una cerca local d’inserció seguida d’una cerca local d’intercanvi
fins òptim local de les dues, seguides de diversos mètodes de modificació
parcial de la solució per tornar de nou amb aquesta solució modificació a les
recerques locals.
S’introdueixen mètodes que busquen disminuir el grau d’aleatorietat dels primers
algoritmes, on s’arriba a desenvolupar tres nous algoritmes que milloren
els anteriors i que destaquen amb millors resultats que l’estat de l’art en pràcticament
tots els casos. Un nou algorisme híbrid a on es reuneixen totes les
característiques dels mètodes desenvolupats fins aquell moment ens porta a
millorar significativament els resultats obtinguts.
No obstant els bons resultats, es proposen nous mètodes basats en una disminució
del nombre de variables a tenir en compte en la resolució del problema que
acaben derivant en cinc nous algoritmes que ens porten a millorar encara més
els valors obtinguts pels anteriors mètodes proposats. És de destacar que els
algorismes proposats no només obtenen bons resultats, sinó que van millorant
aquests resultats a mesura que se’ls dóna més temps d’execució.
Es realitzen les modificacions pertinents als millors algorismes desenvolupats
en nom de parallelitzar part de les tasques que realitzen i això ens permet
comparar-los amb l’estat de l’art. Els resultats mostren com el millor algorisme
desenvolupat és capaç de superar el mètode representatiu de l’estat de l’art
també en l’ambient paral.lel.
Finalment, es presenta el problema de màquines opcionals i selecció de treballs,
realitzant primerament la seva formulació matemàtica per a posteriorment
mostrar els mètodes més favorables per a la solució d’aquest tipus de
problemes, basats, en el cas de la selecció de màquines, en un elaboració de un
rànquing de màquines, seguits d’una selecció iterativa d’elles i una resolució
final per diferents mètodes.
Per últim fem una reflexió sobre tot el estudiat i una discussió sobre les possibles
línies d’investigació que deixa obertes aquesta tesi doctoral.