Gupta

Scientia et Technica Año XVI, No 49, Diciembre de 2011. Universidad Tecnológica de Pereira. ISSN 0122-1701

69

Aplicación de la heuristica de gupta en la secuenciación de n tareas en m máquinas: un caso de estudio
Application gupta´s heuristic for sequencing n jobs trough m machines: a study case
Jorge Hernán Restrepo C.
Ingeniería Industrial, Universidad Tecnológica de Pereira, Pereira,Colombia
jhrestrepoco@utp.edu.co Resumen— Este documento presenta como es aplicada la heurística de Gupta para resolver un problema 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. Palabrasclave— Heurística, programación de tareas. Abstract— This paper shows how is applied the Gupta´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. Key Word — Heuristic, jobs programming.

disponibles para iniciar su procesotendremos un problema de 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. 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 de proceso de las tareas a través de las máquinasdebe 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 los diferentes tipos de flujos de producción, los de seriecon 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 trabajos tardíos entre otras.

I.

INTRODUCCIÓN

Losmodelos de secuenciales 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 como las 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. 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. Existencuatro 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 quedan
Fecha de Recepción: 25 de Enero de 2011 Fecha de Aceptación: 11 de Agosto de 2011

II.

REGLAS Y NOTACIÓN

En todos los problemas de programación considerados en número de tareasy maquinas son finitos. En número de trabajos es denotado por 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 siguientes piezas de datos son asociadas con el trabajo j. 1. Tiempo de proceso p i,j :...