Nuevos algoritmos para el problema de secuenciación en máquinas paralelas no relacionadas y generalizaciones

Résumé

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 Cmáx, 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//Cmáx, 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.