AplicacionDeLaHeuristicaDePalmerEnLaSecuenciacionD 4530379
Páginas: 7 (1581 palabras)
Publicado: 5 de mayo de 2015
Scientia et Technica Año XVII, No 46, Diciembre 2010. Universidad Tecnológica de Pereira. ISSN 0122-1701
175
APLICACIÓN DE LA HEURISTICA DE PALMER EN LA SECUENCIACIÓN DE N TAREAS EN M
MÁQUINAS: UN CASO DE ESTUDIO
APPLICATION THE PALMER´S HEURISTIC FOR SEQUENCING N JOBS TROUGH M MACHINES:
A STUDY CASE.
RESUMEN
Este documento presenta como es aplicada la heurística de Palmer para resolver
uproblema de programación de n tareas a través de m maquinas. El documento
hace de forma breve una introducción al problema del Flow Shop, el modelo
matemático, los pasos para resolver el problema, la solución con base en una
medida de desempeño y las conclusiones.
JORGE HERNÁN RESTREPO C
Ingeniero Industrial, M. Sc.
Profesor Asociado
Universidad Tecnológica de Pereira
jhrestrepoco@utp.edu.coPALABRAS CLAVES: Heurística, programación de tareas.
ABSTRACT
This paper shows how is applied the Palmer´s heuristic to solve a programming
problem of n jobs through m machines. The document explains a short
introduction of Flow shop problem, the mathematical model, the steps to solve
the problem, problem solution and conclusions.
KEYWORDS: Heuristic, jobs programming
1. INTRODUCCIÓN1
Los modelos desecuenciales tienen aplicaciones
principalmente en un taller de tareas, donde un conjunto
de máquinas, de propósito general, ejecutan una serie de
operaciones sobre órdenes de trabajos o tareas de
producción. Las tareas son a menudo únicas y ordenadas
por un determinado cliente. El proceso en el taller de
tareas es un modelo fundamental para un considerable
número de sistemas operacionales, tales comolas
actividades de mantenimiento, asignación de aulas de
clase a un grupo de materias, la programación de llegada
y salida de buses, la programación de n tareas en m
máquinas en un taller de fabricación intermitente, etc.
2.
El número de máquinas que integran el taller.:
Existe un problema de secuenciación cuando n
trabajos son programados en m maquinas.
3.
El flujo de producción: el flujo deproceso de las
tareas a través de las máquinas debe ser
especificado, si todas las tareas siguen la misma
ruta el flujo de producción es continuo o en
serie. En el extremo opuesto, donde no existe
una ruta preconcebida de procesos se tiene un
taller cuyo flujo de producción es aleatorio. Los
trabajos pueden ser independientes unos de
otros, o bien interdependientes. Cuando se
mezclan losdiferentes tipos de flujos de
producción, los de serie con los aleatorios,
existen rutas generales de proceso.
4.
El objetivo que se desea optimizar: la medida de
desempeño que frecuentemente se utiliza es la
optimización del tiempo total de proceso de
todas las tareas o trabajos en todas las máquinas,
pero se puede pensar también en la tardanza
máxima, tardanza promedio o mínimo número
de trabajostardíos entre otras.
La programación de un taller de tareas consiste en
determinar el orden o la secuencia de las tareas en las
máquinas para optimizar alguna medida de ejecución.
Existen cuatro factores que describen y clasifican un
problema específico de programación de un taller de
tareas de acuerdo a:
1.
El patrón de llegada de los trabajos: si n tareas
llegan simultáneamente al taller y quedandisponibles para iniciar su proceso tendremos un
problema d e programación estática. Si las tareas
llegan intermitentemente, posiblemente de
acuerdo a un proceso estocástico, el problema
de programación es dinámico.
Fecha Recepción: 9 de Septiembre de 2010
Fecha aceptación: 15 de Noviembre de 2010
Scientia et Technica Año XVII, No 46, Diciembre 2010. Universidad Tecnológica de Pereira.
176
2.REGLAS Y NOTACIÓN2
En todos los problemas de programación considerados en
numero de tareas y maquinas son finitos. En número de
trabajos es denotado mor n y el número de máquinas por
m. normalmente j se refiere a la tarea e i para la máquina.
Si una tarea requiere un número de pasos de proceso u
operaciones, entonces el par (i,j) significa el paso del
proceso del trabajo j en la máquina i. las...
175
APLICACIÓN DE LA HEURISTICA DE PALMER EN LA SECUENCIACIÓN DE N TAREAS EN M
MÁQUINAS: UN CASO DE ESTUDIO
APPLICATION THE PALMER´S HEURISTIC FOR SEQUENCING N JOBS TROUGH M MACHINES:
A STUDY CASE.
RESUMEN
Este documento presenta como es aplicada la heurística de Palmer para resolver
uproblema de programación de n tareas a través de m maquinas. El documento
hace de forma breve una introducción al problema del Flow Shop, el modelo
matemático, los pasos para resolver el problema, la solución con base en una
medida de desempeño y las conclusiones.
JORGE HERNÁN RESTREPO C
Ingeniero Industrial, M. Sc.
Profesor Asociado
Universidad Tecnológica de Pereira
jhrestrepoco@utp.edu.coPALABRAS CLAVES: Heurística, programación de tareas.
ABSTRACT
This paper shows how is applied the Palmer´s heuristic to solve a programming
problem of n jobs through m machines. The document explains a short
introduction of Flow shop problem, the mathematical model, the steps to solve
the problem, problem solution and conclusions.
KEYWORDS: Heuristic, jobs programming
1. INTRODUCCIÓN1
Los modelos desecuenciales tienen aplicaciones
principalmente en un taller de tareas, donde un conjunto
de máquinas, de propósito general, ejecutan una serie de
operaciones sobre órdenes de trabajos o tareas de
producción. Las tareas son a menudo únicas y ordenadas
por un determinado cliente. El proceso en el taller de
tareas es un modelo fundamental para un considerable
número de sistemas operacionales, tales comolas
actividades de mantenimiento, asignación de aulas de
clase a un grupo de materias, la programación de llegada
y salida de buses, la programación de n tareas en m
máquinas en un taller de fabricación intermitente, etc.
2.
El número de máquinas que integran el taller.:
Existe un problema de secuenciación cuando n
trabajos son programados en m maquinas.
3.
El flujo de producción: el flujo deproceso de las
tareas a través de las máquinas debe ser
especificado, si todas las tareas siguen la misma
ruta el flujo de producción es continuo o en
serie. En el extremo opuesto, donde no existe
una ruta preconcebida de procesos se tiene un
taller cuyo flujo de producción es aleatorio. Los
trabajos pueden ser independientes unos de
otros, o bien interdependientes. Cuando se
mezclan losdiferentes tipos de flujos de
producción, los de serie con los aleatorios,
existen rutas generales de proceso.
4.
El objetivo que se desea optimizar: la medida de
desempeño que frecuentemente se utiliza es la
optimización del tiempo total de proceso de
todas las tareas o trabajos en todas las máquinas,
pero se puede pensar también en la tardanza
máxima, tardanza promedio o mínimo número
de trabajostardíos entre otras.
La programación de un taller de tareas consiste en
determinar el orden o la secuencia de las tareas en las
máquinas para optimizar alguna medida de ejecución.
Existen cuatro factores que describen y clasifican un
problema específico de programación de un taller de
tareas de acuerdo a:
1.
El patrón de llegada de los trabajos: si n tareas
llegan simultáneamente al taller y quedandisponibles para iniciar su proceso tendremos un
problema d e programación estática. Si las tareas
llegan intermitentemente, posiblemente de
acuerdo a un proceso estocástico, el problema
de programación es dinámico.
Fecha Recepción: 9 de Septiembre de 2010
Fecha aceptación: 15 de Noviembre de 2010
Scientia et Technica Año XVII, No 46, Diciembre 2010. Universidad Tecnológica de Pereira.
176
2.REGLAS Y NOTACIÓN2
En todos los problemas de programación considerados en
numero de tareas y maquinas son finitos. En número de
trabajos es denotado mor n y el número de máquinas por
m. normalmente j se refiere a la tarea e i para la máquina.
Si una tarea requiere un número de pasos de proceso u
operaciones, entonces el par (i,j) significa el paso del
proceso del trabajo j en la máquina i. las...
Leer documento completo
Regístrate para leer el documento completo.