Algoritmo Gupta

UNICAH
Nuestra Señora Reina De La Paz

Campus San Pedro San Pablo
Asignatura
Ingeniería en sistemas de producción 1.
Catedrático
Ing. Alirio Núñez.
Trabajo
Investigación sobre el Algoritmo Gupta
Integrantes:
Dulce María Galeas 0806200000316
Fecha
03 de marzo del año 2024.
INDICE
INTRODUCCIÓN
El algoritmo Gupta es una técnica utilizada en el diseño de algoritmos para la

programación de horarios, particularmente en el contexto de sistemas de transporte
público. Fue desarrollado por Amit Gupta y se centra en la optimización de la
asignación de recursos, como vehículos y conductores, para minimizar los costos
operativos y mejorar la eficiencia del sistema. Este algoritmo es fundamental para la
planificación y gestión efectiva de los horarios en redes de transporte público, ayudando
a maximizar la satisfacción de los usuarios y la rentabilidad del servicio.
OBJETIVO GENERAL
El algoritmo Gupta es optimizar la asignación de recursos en sistemas de
transporte público, como vehículos y conductores, para minimizar los costos
operativos y mejorar la eficiencia del sistema en términos de puntualidad,
frecuencia y cobertura de rutas.
OBJETIVOS ESPECIFICOS
Minimización de costos operativos: El algoritmo Gupta busca asignar
eficientemente recursos como vehículos y conductores para minimizar los costos
asociados con la operación del sistema de transporte público.
Maximización de la cobertura de rutas: Busca optimizar la asignación de

recursos para garantizar una cobertura óptima de las rutas, asegurando que se
atienda a la mayor cantidad posible de pasajeros y áreas de servicio.
Mejora de la calidad del servicio: El algoritmo Gupta tiene como objetivo

mejorar la calidad del servicio al garantizar la puntualidad, reducir la congestión
y ofrecer una frecuencia adecuada de vehículos, lo que se traduce en una
experiencia más satisfactoria para los usuarios del transporte público.
MARCO TEORICO
El algoritmo de Gupta, desarrollado en 1969 por J. N. D. Gupta, es un método
heurístico para la secuenciación de tareas en talleres de tipo "flow shop". Este tipo de
talleres se caracterizan por tener un flujo de producción lineal, donde las tareas se
procesan en una secuencia fija a través de un conjunto de máquinas. El objetivo del
algoritmo de Gupta es encontrar la secuencia de tareas que minimice el tiempo total de
procesamiento, también conocido como "makespan".
Funcionamiento del Algoritmo:
El algoritmo de Gupta se basa en la siguiente lógica:
Calcular el tiempo de procesamiento total para cada tarea en cada máquina.

Calcular un índice de prioridad para cada tarea. Este índice se calcula como la
suma de los tiempos de procesamiento de la tarea en todas las máquinas.
Ordenar las tareas en orden descendente de acuerdo a su índice de prioridad.
Asignar las tareas a las máquinas en la secuencia ordenada.
Ventajas del Algoritmo:
o Es un método simple y fácil de implementar.

o Es relativamente eficiente en la búsqueda de soluciones de buena calidad.
o Es flexible y se puede adaptar a diferentes tipos de problemas de secuenciación.
Desventajas del Algoritmo:
o No siempre encuentra la solución óptima.

o Puede ser sensible a la elección del índice de prioridad.
o No es adecuado para problemas de secuenciación con restricciones complejas.
Recomendaciones:
 Se recomienda comparar la solución obtenida con el método de Gupta con

otras heurísticas o algoritmos exactos para verificar su calidad.
 Se puede ajustar el método de Gupta para mejorar la calidad de la solución,
como por ejemplo, utilizando diferentes métodos para calcular los tiempos de
holgura.
 Para problemas complejos, se recomienda utilizar algoritmos más sofisticados
que consideren la simultaneidad de operaciones y otras restricciones.
Aplicaciones del Algoritmo:
El algoritmo de Gupta se ha utilizado en una amplia variedad de aplicaciones,

incluyendo:
o Planificación de la producción en talleres

o Programación de trabajos en máquinas herramienta
o Secuenciación de operaciones en procesos de fabricación
o Optimización del flujo de tráfico en redes.
PASOS PARA APLICAR EL ALGORITMO GUPTA
1. Definir el problema:
 Identificar el tipo de taller: flujo lineal (flow shop) o taller por lotes (job shop).
 Determinar el número de máquinas (m) y el número de trabajos (n).
 Especificar el tiempo de procesamiento de cada trabajo en cada máquina (tij).
2. Calcular el tiempo total de procesamiento (TP):
TP = Σ(tij) para todos los trabajos i y máquinas j.
3. Calcular el índice de Gupta (GI) para cada trabajo:
GIi = TP / tii
4. Ordenar los trabajos en orden ascendente de GI.
5. Programar los trabajos en la secuencia ordenada.
Reglas de programación:
 Un trabajo no puede comenzar a procesarse en una máquina hasta que la máquina esté
disponible.
 Un trabajo solo puede procesarse en una máquina a la vez.
 Se debe respetar la secuencia de procesamiento de cada trabajo.
6. Calcular el tiempo de finalización (Cmax) del último trabajo.
7. Evaluar la solución:
 Comparar el Cmax con otros métodos de programación.

 Analizar la eficiencia y la equidad de la solución.
Consideraciones adicionales:
 El algoritmo de Gupta es un método heurístico, por lo que no siempre ofrece la solución

óptima.
 El algoritmo se puede adaptar para diferentes tipos de talleres y objetivos de
programación.
 Existen diferentes variantes del algoritmo de Gupta que pueden mejorar la eficiencia del
método.
Problema resuelto de Algoritmo Gupta
Consideremos el siguiente problema de taller de flujo:
 Tenemos 3 máquinas (M1, M2, M3).

 Hay 4 trabajos (T1, T2, T3, T4) que se deben procesar en las 3 máquinas en orden
específico.
 La siguiente tabla muestra el tiempo de procesamiento (en minutos) de cada trabajo en
cada máquina:
Objetivo: Encontrar la secuencia óptima de trabajos que minimice el tiempo total de

procesamiento (Makespan) en el taller.
Solución paso a paso usando el Algoritmo Gupta:
1. Calcular el tiempo de holgura:
El tiempo de holgura (H) para cada trabajo i en la máquina j se calcula como:
H_ij = T_ij - (M_j - ΣT_ki)
Donde:
 T_ij: Tiempo de procesamiento del trabajo i en la máquina j.

 M_j: Tiempo de procesamiento total en la máquina j (suma de los tiempos de
procesamiento de todos los trabajos en la máquina j).
 ΣT_ki: Suma de los tiempos de procesamiento de todos los trabajos anteriores a i en la
máquina j.
Aplicando la fórmula a nuestro problema, obtenemos la siguiente tabla de
holguras:
2. Calcular el índice de Gupta (GI):
El índice de Gupta (GI) para cada trabajo se calcula como:
GI_i = ΣH_ij
Donde:
 H_ij: Tiempo de holgura del trabajo i en la máquina j.
Sumando las holguras de cada trabajo en todas las máquinas, obtenemos la siguiente
tabla de índices de Gupta:
3. Seleccionar la secuencia de trabajos:
Se ordenan los trabajos en orden descendente según su índice de Gupta. La secuencia

de trabajos con el índice de Gupta más alto será la primera en procesarse, y así
sucesivamente.
En este caso, la secuencia de trabajos ordenada por índice de Gupta es:
T4 - T2 - T3 - T1
4. Calcular el tiempo total de procesamiento (Makespan):
El Makespan se calcula como la suma del tiempo de procesamiento de cada trabajo en

la máquina más lenta. En este caso, la máquina más lenta es M3 con un tiempo total de
procesamiento de 23 minutos.
Makespan = 23 minutos
5. Conclusión:
La secuencia de trabajos T4 - T2 - T3 - T1 minimiza el tiempo total de procesamiento

(Makespan) en el taller con un valor de 23 minutos.
RECUERSO ADICIONAL
Resolución del problema de taller de flujo mediante el algoritmo de

Gupta
Planteamiento del problema:
Se presenta un taller de flujo con las siguientes características:
 Número de máquinas: 3 (M1, M2, M3).

 Número de trabajos: 4 (T1, T2, T3, T4).
 Ruta de procesamiento: Cada trabajo debe procesarse en las 3 máquinas en orden
específico.
 Matriz de tiempos de procesamiento: Se proporciona una matriz que indica el tiempo
de procesamiento (en minutos) de cada trabajo en cada máquina.
Objetivo:
Encontrar la secuencia óptima de trabajos que minimice el tiempo total de

procesamiento (Makespan) en el taller.
Metodología:
Se aplica el algoritmo de Gupta para la secuenciación de trabajos en talleres de flujo. El
algoritmo se basa en dos pasos principales:
1. Cálculo del índice de Gupta (GI):
 Se calcula el tiempo de holgura (H) para cada trabajo i en cada máquina j.

 Se calcula el índice de Gupta (GI) para cada trabajo como la suma de sus tiempos de
holgura en todas las máquinas.
2. Secuenciación de trabajos:
 Se ordenan los trabajos en orden descendente según su índice de Gupta.

 La secuencia de trabajos con el índice de Gupta más alto será la primera en procesarse,
y así sucesivamente.
Resultados:
 Secuencia de trabajos: T4 - T2 - T3 - T1
 Makespan: 23 minutos
Conclusiones:
La secuencia de trabajos T4 - T2 - T3 - T1 obtenida mediante el algoritmo de Gupta

permite minimizar el tiempo total de procesamiento (Makespan) en el taller con un
valor de 23 minutos.
Consideraciones adicionales:
 El algoritmo de Gupta es una heurística, por lo que no se garantiza que siempre

encuentre la solución óptima.
 La complejidad computacional del algoritmo aumenta con el número de trabajos y
máquinas.
 Existen otras heurísticas y algoritmos exactos para la secuenciación de trabajos en
talleres de flujo.
CONCLUSIONES
 El algoritmo GUPTA es más rápido que otros algoritmos de

agrupamiento jerárquico ascendente, como el algoritmo de Ward o el
algoritmo de Lance-Williams. Esto se debe a su estrategia de "poda"
que evita calcular distancias entre pares de puntos poco probables de
agruparse.
 El algoritmo GUPTA produce agrupamientos de alta calidad, con

cohesión intra-grupo y baja cohesión inter-grupo. Esto se debe a su
medida de distancia robusta, que considera la distribución de los
puntos en el espacio de características.
 El algoritmo GUPTA es escalable para conjuntos de datos grandes,

gracias a su estructura de datos eficiente para almacenar la
información de agrupamiento.
BIBLIOGRAFIA
(S/f-b). Researchgate.net. Recuperado el 4 de marzo de 2024, de
https://www.researchgate.net/publication/327159824_Programacion_d
e_Taller_Tipo_Flow_Shops_siguiendo_el_Modelo_Gupta
Palmer y Gupta - Apuntes de Ingeniería Mecánica. (s/f). Docsity.com.
Recuperado el 4 de marzo de 2024, de
https://www.docsity.com/es/palmer-y-gupta/3174412/
(S/f-a). Uson.mx. Recuperado el 4 de marzo de 2024, de
http://tesis.uson.mx/digital/tesis/docs/3092/Capitulo5.pdf

Algoritmo Gupta

Cargado por

Copyright:

Formatos disponibles

Algoritmo Gupta

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Algoritmo Gupta

Cargado por

Copyright:

Formatos disponibles

UNICAH

Nuestra Señora Reina De La Paz

El algoritmo Gupta es una técnica utilizada en el diseño de algoritmos para la

Maximización de la cobertura de rutas: Busca optimizar la asignación de

Mejora de la calidad del servicio: El algoritmo Gupta tiene como objetivo

Funcionamiento del Algoritmo:

El algoritmo de Gupta se basa en la siguiente lógica:

Calcular el tiempo de procesamiento total para cada tarea en cada máquina.

Ventajas del Algoritmo:

o Es un método simple y fácil de implementar.

Desventajas del Algoritmo:

o No siempre encuentra la solución óptima.

 Se recomienda comparar la solución obtenida con el método de Gupta con

Aplicaciones del Algoritmo:

El algoritmo de Gupta se ha utilizado en una amplia variedad de aplicaciones,

o Planificación de la producción en talleres

2. Calcular el tiempo total de procesamiento (TP):

TP = Σ(tij) para todos los trabajos i y máquinas j.

3. Calcular el índice de Gupta (GI) para cada trabajo:

4. Ordenar los trabajos en orden ascendente de GI.

5. Programar los trabajos en la secuencia ordenada.

6. Calcular el tiempo de finalización (Cmax) del último trabajo.

 Comparar el Cmax con otros métodos de programación.

 El algoritmo de Gupta es un método heurístico, por lo que no siempre ofrece la solución

 Tenemos 3 máquinas (M1, M2, M3).

Objetivo: Encontrar la secuencia óptima de trabajos que minimice el tiempo total de

Solución paso a paso usando el Algoritmo Gupta:

1. Calcular el tiempo de holgura:

El tiempo de holgura (H) para cada trabajo i en la máquina j se calcula como:

H_ij = T_ij - (M_j - ΣT_ki)

 T_ij: Tiempo de procesamiento del trabajo i en la máquina j.

2. Calcular el índice de Gupta (GI):

El índice de Gupta (GI) para cada trabajo se calcula como:

 H_ij: Tiempo de holgura del trabajo i en la máquina j.

Se ordenan los trabajos en orden descendente según su índice de Gupta. La secuencia

En este caso, la secuencia de trabajos ordenada por índice de Gupta es:

4. Calcular el tiempo total de procesamiento (Makespan):

El Makespan se calcula como la suma del tiempo de procesamiento de cada trabajo en

La secuencia de trabajos T4 - T2 - T3 - T1 minimiza el tiempo total de procesamiento

Resolución del problema de taller de flujo mediante el algoritmo de

Planteamiento del problema:

Se presenta un taller de flujo con las siguientes características:

 Número de máquinas: 3 (M1, M2, M3).

Encontrar la secuencia óptima de trabajos que minimice el tiempo total de

1. Cálculo del índice de Gupta (GI):

 Se calcula el tiempo de holgura (H) para cada trabajo i en cada máquina j.

 Se ordenan los trabajos en orden descendente según su índice de Gupta.

La secuencia de trabajos T4 - T2 - T3 - T1 obtenida mediante el algoritmo de Gupta

 El algoritmo de Gupta es una heurística, por lo que no se garantiza que siempre

 El algoritmo GUPTA es más rápido que otros algoritmos de

 El algoritmo GUPTA produce agrupamientos de alta calidad, con

 El algoritmo GUPTA es escalable para conjuntos de datos grandes,

(S/f-b). Researchgate.net. Recuperado el 4 de marzo de 2024, de

Palmer y Gupta - Apuntes de Ingeniería Mecánica. (s/f). Docsity.com.

Recuperado el 4 de marzo de 2024, de

(S/f-a). Uson.mx. Recuperado el 4 de marzo de 2024, de

También podría gustarte