Un algoritmo GRASP para resolver el problema de la programacion de tareas dependientes en maquinas diferentes
Manuel Tupia (1), David Mauricio Sánchez (2)
e-mails: tupia.mf@pucp.edu.pe, dms@terra.com
(1) Pontificia Universidad Católica del Perú - Dep. de Ingenieria 32 Lima Perú
(2) Universidad Nacional Mayor de San Marcos - UPG-FISI 1 Lima Perú
The industrial planning has experienced notable advances from his
origins around the middle of the century XX not only a meal in the
efficiency in application importance inside all the industries
where it is used, and sophistication of the algorithms that try to
resolve the problems that generate all its existent variants. The
interest for the heuristic- methods application in front of to
give answers to the problems of the area of planning need has
taken us to develop new algorithms to resolve one of the problem
variants of the planning from the Artificial Intelligence's point
of view: The programming of tasks or task scheduling: once an
tasks set was given to be programmed in determined machines group,
finding an order once was made suitable of execution that minimize
the time once was accumulated total of processing of the machines
or makespan. The present work GRASP to resolve programming the
problem of dependent tasks in different machines shows a heuristic
goal.
La planificación industrial ha experimentado notables avances
desde sus orígenes a mediados del siglo XX tanto en importancia de
aplicación dentro de todas las industrias en donde es usada, como
en la eficiencia y sofisticación de los algoritmos que buscan
resolver los problemas que generan todas sus variantes existentes.
El interés por la aplicación de métodos heurísticos ante la
necesidad de dar respuestas a los problemas del área de
planificación nos ha llevado a desarrollar nuevos algoritmos para
resolver una de las variantes del problema de la planificación
desde el punto de vista de la Inteligencia Artificial: la
programación de tareas o task scheduling: dado un conjunto de
tareas dependientes de una línea de producción a ser programadas
en un determinado grupo de máquinas diferentes, encontrar un orden
adecuado de ejecución que minimice el tiempo total de trabajo de
las máquinas o makespan. El presente trabajo muestra una meta
heurística GRASP para resolver dicha variante del problema del
task scheduling.
Keywords:GRASP Algorithm, Task Sheduling, Combinatorial Optimization, Meta Heuristic, Artificial Intelligence
Palabras Clave/Palavras Chave: Algoritmos GRASP, Programación de tareas, Optimización combinatoria, Meta heurísticas, Inteligencia Artificial
BibTex
@INPROCEEDINGS{tupia04:51,
AUTHOR = {Manuel Tupia and David Mauricio Sánchez},
TITLE = {Un algoritmo GRASP para resolver el problema de la programacion de tareas dependientes en maquinas diferentes},
BOOKTITLE = {30ma Conferencia Latinoamericana de Informática (CLEI2004)},
YEAR = {2004},
editor = {Mauricio Solar and David Fernández-Baca and Ernesto Cuadros-Vargas},
pages = {129--139},
address = {},
month = Sep,
organization = {Sociedad Peruana de Computación},
note = {ISBN 9972-9876-2-0},
file = {http://clei2004.spc.org.pe/es/html/pdfs/51.pdf}
}
PDF de este artículo
PDF de CLEI2004 (incluye todos los artículos)
Página principal CLEI 2004
Generado por Sociedad Peruana de Computación