| Revue: | Computación y sistemas |
| Base de datos: | PERIÓDICA |
| Número de sistema: | 000383407 |
| ISSN: | 1405-5546 |
| Autores: | Selley Rojas, Héctor J1 García Díaz, Jesús1 Soto Ramos, Manuel A1 Menchaca García, Felipe R2 Menchaca Mendez, Rolando1 |
| Instituciones: | 1Instituto Politécnico Nacional, Centro de Investigación en Computación, México, Distrito Federal. México 2Instituto Politécnico Nacional, Escuela Superior de Ingeniería Mecánica y Eléctrica, México, Distrito Federal. México |
| Año: | 2015 |
| Periodo: | Ene-Mar |
| Volumen: | 19 |
| Número: | 1 |
| Paginación: | 47-68 |
| País: | México |
| Idioma: | Español |
| Tipo de documento: | Artículo |
| Enfoque: | Analítico, descriptivo |
| Resumen en español | En este artículo se presenta un algoritmo aleatorizado para el problema de planificación de tareas compuestas por procesos con restricciones de precedencia en ambientes distribuidos tipo Grid. El algoritmo aleatorizado propuesto esta basado en una nueva técnica que hemos denominado como de distribuciones deslizantes, la cual busca combinar las ventajas de los algoritmos de aproximación deterministas y de los algoritmos aleatorizados tipo Montecarlo. El objetivo es proveer un algoritmo que con alta probabilidad entregue soluciones p-aproximadas, pero que al mismo tiempo tenga la capacidad de analizar el vecindario extendido de dichas soluciones para escapar de máximos o mínimos locales. En el artículo se demuestra que el algoritmo propuesto es correcto y se caracteriza de manera formal su complejidad temporal. Así mismo, se evalúa el desempeño del algoritmo por medio de una serie de experimentos basados en simulaciones. Los experimentos muestran que el algoritmo propuesto logra en general un desempeño superior al de los algoritmos que componen el estado del arte en planificación en sistemas Grid. Las métricas de desempeño utilizadas son retardo promedio, retardo máximo y utilización de la Grid |
| Resumen en inglés | In this paper we present a randomized algorithm for the online version of the Job Shop problem where jobs are composed of processes with precedence constraints and processors are organized in a Grid topology. The proposed randomized algorithm is based on a new technique that we have denominated as sliding distributions, which aims at combining the advantages of the deterministic approximation algorithms with those of the Montecarlo randomized algorithms. The objective is to provide an algorithm that delivers p-approximated solutions with high probability, but at the same time, is able to investigate an extended neighborhood of such solutions so that it can escape from local extrema. We formally characterize the temporal complexity of the proposed algorithm and show that it is correct. We also evaluate the performance of the proposed algorithm by means of a series of simulation-based experiments. The results show that the proposed algorithm outperforms the traditional state of the art algorithms for scheduling in Grid systems. The performance metrics are average delay, maximum delay, and Grid utilization |
| Disciplinas: | Ciencias de la computación |
| Palabras clave: | Programación, Planificación de tareas, Optimización combinatoria, Red de suminstro, Algoritmo aleatorio |
| Keyword: | Computer science, Programming, Task scheduling, Combinatorial optimization, Grid system, Randomized algorithm |
| Texte intégral: | Texto completo (Ver HTML) |
