Algoritmo voraz iterativo con mecanismo de destrucción mixto semi aleatorio para la programación a gran escala de máquinas heterogéneas en paralelo

Abstract

La investigación trata el tema de la programación de máquinas en paralelo, conocido como Parallel Machine Scheduling (PMS). Se enfoca en el problema de la programación a gran escala, donde el número de trabajos es muy grande y mucho mayor que el número de recursos. La solución consiste en asignar y secuenciar los trabajos en los recursos, de modo tal, que se logren terminar a tiempo o con el menor atraso posible. PMS es un problema clásico, tanto de la ingeniería industrial por su relación con la optimización de recursos, y de la matemática computacional de análisis combinatorio. Casos de pocos trabajos y recursos, han sido resueltos satisfactoriamente por modelos de optimización, los casos de mayor tamaño se abordan con métodos heurísticos y se logran soluciones aceptables. La programación a gran escala es un problema relativamente nuevo, pero cuya presencia aumenta debido a la tendencia de fabricación de lotes de producción más pequeños para lograr una oferta más variada de productos. La literatura sobre casos de gran escala es aún escaza. La tesis incluye dos papers, uno con una revisión de métodos para PMS y otro donde se compara el desempeño de algoritmos heurísticos para casos de gran escala. Finalmente se desarrolla una modificación del algoritmo voraz iterativo y se comprueba empíricamente que su desempeño aumenta considerablemente.

The research deals with the topic of Parallel Machine Programming (PMS). It focuses on the problem of large-scale scheduling, where the number of jobs is very large and much greater than the number of resources. The solution is to allocate and sequence the jobs on the resources, such that they can be completed on time or with the least possible delay. PMS is a classic problem, both in industrial engineering due to its relation to resource optimization, and in computational mathematics of combinatorial analysis. Cases with few jobs and resources, have been satisfactorily solved by optimization models, larger cases are addressed with heuristic methods and acceptable solutions are achieved. Large-scale scheduling is a relatively new problem, but its presence is growing due to the trend towards smaller production batches for a more diverse product offering. The literature on large-scale cases is still scarce. The thesis includes two papers, one with a review of methods for PMS and another where the performance of heuristic algorithms for large-scale cases is compared. Finally, a modification of the greedy iterative algorithm is developed and it is empirically verified that its performance increases considerably.