Resumen

Para iniciar esta Tesis Doctoral se buscó un problema de producción sencillo
pero de amplia aplicación práctica que permitiera adaptarlo para llegar
a problemas más generales y de más amplia aplicación. Por este motivo, nos
centramos en las máquinas paralelas, y dentro de ellas, en las no relacionadas
dado que son una generalización de los casos de máquinas idénticas y de las
uniformemente relacionadas. Escogimos el objetivo de minimizar el tiempo
máximo de finalización o Cmax, uno de los más comunes de la literatura. Este
problema tiene la facultad de que, a pesar de su carácter teórico, tiene una
amplia aplicación práctica, como el caso de secuenciar las tareas de los hornos
de cocción cerámicos. Por otra parte se quería ampliar el problema para el
caso en que no se usaran todas las máquinas o no se hicieran todos los trabajos
necesariamente.
Las metas perseguidas son el presentar unos algoritmos sencillos y potentes
para la resolución del problema R//Cmax, capaces de constituirse en el estado
del arte. Dado que los modernos ordenadores montan casi en su totalidad varios
núcleos en su CPU y los algoritmos se van adaptando a este hecho, también se
ha buscado realizar una adaptación de los algoritmos para su uso en paralelo.
Finalmente, se pone como meta el encontrar métodos eficaces y sencillos para
la resolución de problemas de este tipo en donde no se emplearan todas las
máquinas o no se realizaran todos los trabajos.
En la presente Tesis Doctoral se realizó un amplio estudio de la literatura
existente respecto al problema de máquinas paralelas no relacionadas y se
extrajo el estado del arte, así como un estudio del posible tipo de instancias a
emplear, dado que no existía una grupo de instancias tipo para este problema.
Se presentan cuatro algoritmos iniciales sencillos que mejoran los resultados
del estado del arte en algunos casos y dan mejores resultados de media en el
conjunto total de instancias tratadas. Dichos algoritmos se basan en métodos
iterativos en los que se realiza una búsqueda local de inserción seguida de
una búsqueda local de intercambio hasta óptimo local de ambas, seguidas de
diversos métodos de modificación parcial de la solución para volver de nuevo
con esta solución modificada a las búsquedas locales.
Se introducen métodos que buscan disminuir el grado de aleatoriedad de los
primeros algoritmos, donde se llega a desarrollar tres nuevos algoritmos que
mejoran los anteriores y que destacan con mejores resultados que el estado del
arte en prácticamente todos los casos. Un nuevo algoritmo híbrido donde se
aúnan todas las características de los métodos desarrollados hasta ese momento
nos lleva a mejorar significativamente los resultados obtenidos.
No obstante los buenos resultados, se proponen nuevos métodos basados en
una disminución del número de variables a tener en cuenta en la resolución
del problema que acaban derivando en cinco nuevos algoritmos que nos llevan
a mejorar aún más los valores ya obtenidos por los anteriores métodos propuestos.
Es de destacar que los algoritmos propuestos no solo obtienen buenos
resultados, si no que van mejorando estos resultados a medida que se les da
más tiempo de ejecución.
Se realizan las modificaciones pertinentes a los mejores algoritmos desarrollados
en aras de paralelizar parte de las tareas que realizan y esto nos permite
compararlos con el estado del arte. Los resultados muestran como el mejor
algoritmo desarrollado es capaz de superar al método representativo del estado
del arte también en el ambiente paralelo.
Finalmente, se presenta el problema de máquinas opcionales y selección de
trabajos, realizando primeramente su formulación matemática para posteriormente
mostrar los métodos más favorables para la solución de este tipo de
problemas, basados, en el caso de la selección de máquinas, en un elaboración
de un ranking de máquinas, seguidos de una selección iterativa de ellas y una
resolución final por distintos métodos.
Por último hacemos una reflexión sobre todo lo estudiado y una discusión
sobre las posibles líneas de investigación que deja abiertas la presente Tesis
Doctoral.