FACULTAD DE INGENIERÍA Y

CIENCIAS BÁSICAS

PROYECTO GRUPAL
SCHEDULING E INVENTARIOS Institución Universitaria Politécnico Grancolombiano

OPTIMIZACIÓN DE UN PROBLEMA DE SECUENCIACIÓN CON DOS

MÁQUINAS

CASO LITOGRAFIA

INTEGRANTES:

Julio Ferney Linares Barrera: 1821980108

Eucarin Morales Agudelo: 1711981501

Néstor Germán Palacios Diaz: 1821980584

Fredy Apolonio Rojas Rojas: 1821981686

TUTOR:

Stevenson Bolivar Atuesta

INSTITUCIÓN UNIVERSITARIA POLITÉCNICO GRANCOLOMBIANO

FACULTAD DE INGENIERÍA Y CIENCIAS BÁSICAS

INGENIERIA INDUSTRIAL

2020
 FACULTAD DE INGENIERÍA Y
CIENCIAS BÁSICAS

PROYECTO GRUPAL
SCHEDULING E INVENTARIOS Institución Universitaria Politécnico Grancolombiano

Tabla Contenido

1. Introducción...................................................................................................................3
1.1. Objetivo principal...................................................................................................4
1.2. Objetivos secundarios............................................................................................4
1.3. Cronograma de actividades...................................................................................5
2. Marco teórico – Secuenciación de máquinas...............................................................6
2.1. Tipos principales de problemas en secuenciación de máquinas.........................6
2.2. Algoritmos principales para secuenciación en problemas mono-máquina.......6
2.3. Algoritmos principales para secuenciación en problemas multi-máquina.....10
3. Solución del estudio de caso........................................................................................20
4. Conclusiones y Recomendaciones..............................................................................20
4.1. Conclusiones..........................................................................................................20
4.2. Recomendaciones..................................................................................................20
bibliografía...........................................................................................................................22
anexos...................................................................................................................................24
 FACULTAD DE INGENIERÍA Y
CIENCIAS BÁSICAS

PROYECTO GRUPAL
SCHEDULING E INVENTARIOS Institución Universitaria Politécnico Grancolombiano

1. Introducción
El Scheduling también conocido como programación de operaciones o programación de
tareas, es el proceso mediante el cual se asignan recursos a diferentes tareas determinado
inicio y final.
En el presente proyecto se investigará, analizara y definirán una serie de estrategias o tareas
en secuencias con el fin de minimizar el makespan de la compañía, analizando dos
máquinas que aportan a la elaboración de la producción.
El Makespan nos ayuda a definir el tiempo usado para completar un grupo de actividades,
es la distancia en el tiempo que transcurre desde el inicio del trabajo hasta el final
 FACULTAD DE INGENIERÍA Y
CIENCIAS BÁSICAS

PROYECTO GRUPAL
SCHEDULING E INVENTARIOS Institución Universitaria Politécnico Grancolombiano

1.1. Objetivo principal

Analizar y desarrollar una secuencia de trabajo que nos permitan implementar alternativas
para minimizar el Makespan (la duración de un proyecto es la distancia en el tiempo que
transcurre desde el inicio del trabajo hasta el final) comparando las diferentes variables que
intervienen en la ejecución de este como lo son factores de tiempo y maquinaria.

1.2. Objetivos secundarios

 Investigar e implementar estrategias con el fin de minimizar los tiempos de
ejecución.

 Establecer algoritmos que faciliten la programación con eficiencias.

 Lograr resultados mediante la comprensión de la teoría de programación, y así

aplicarlo al estudio de sistemas múltiples.

 Minimizar el makespan para equilibrar la carga de las maquinas

 Minimizar el tiempo total en la producción con el desarrollo de algoritmos para el

mejor desempeño de las máquinas.
1.3. Cronograma de actividades

ACTIVIDAD

INVESTIGAR Y ESTUDIAR EL MATERIALES DE APOYO SOBRE ALGORITMOS BÁSICOS

ESTUDIAMOS Y ANALIZAMOS LOS MATERIALES DE APOYO. DIVIDIR ROLES Y FUNCIONES EN EL
GRUPO
DESARROLLAMOS LA PRIMERA ENTREGA MEDIANTE LA INVESTIGACIÓN INDIVIDUAL DEL TEMA
APORTANDO OPINIONES Y LA SOCIALIZACIÓN GRUPAL
IDENTIFICAMOS Y DEFINIMOS ASPECTOS A CONSIDERAR PARA LA RESOLUCIÓN DEL
PROBLEMÁTICA DEL PROYECTO.
DESARROLLAREMOS LA SEGUNDA ENTREGA MEDIANTE LA INVESTIGACIÓN INDIVIDUAL DEL
TEMA APORTANDO OPINIONES Y LA SOCIALIZACIÓN GRUPAL
ESTUDIAREMOS Y ANALIZAREMOS EL ESTUDIO DE CASO PROPUESTO EN EL PROYECTO
IDENTIFICAREMOS QUE ALGORITMO DE SECUENCIA CORRESPONDE Y BAJO CUAL ES LA REGLA
DE DESPACHO QUE APLICA.
DESARROLLAMOS LA TERCERA ENTREGA MEDIANTE LA INVESTIGACIÓN INDIVIDUAL DEL TEMA
APORTANDO OPINIONES Y LA SOCIALIZACIÓN GRUPAL.
2. Marco teórico – Secuenciación de máquinas

2.1. Tipos principales de problemas en secuenciación de máquinas

El proceso de determinar el pedido en una máquina o en un centro de trabajo se llama
secuenciación o también secuenciación por prioridades. Las reglas de prioridad son reglas
usadas para obtener una secuenciación de los trabajos. Las reglas pueden ser muy simples y
pedir únicamente que los trabajos se ordenen de acuerdo con un dato, como el tiempo de
procesamiento, plazo u orden de llegada. Otras reglas, aunque también simples, requieren
más datos, casi siempre para obtener un número indicador, como la regla del menor margen
de tiempo y la regla de la proporción crítica (que se definen más abajo). Otras más, como la
regla de Johnson (que también se estudia después), se aplican a la programación de trabajos
en una secuencia de máquinas y requieren un procedimiento de cómputo para especificar el
orden de desempeño.
Las siguientes medidas de desempeño de los programas se usan para evaluar las reglas de
prioridad.
Cumplir las fechas de los clientes o de las operaciones posteriores.
1. Minimizar el tiempo de tránsito (el tiempo que pasa un trabajo en el proceso).
2. Minimizar el inventario de trabajos sin terminar.
3. Minimizar el tiempo ocioso de máquinas y trabajadores

2.2. Algoritmos principales para secuenciación en problemas mono-máquina

Suponga que n trabajos van a procesarse a través de una máquina. Para cada trabajo i,
defina las siguientes cantidades:
ti: Tiempo de procesamiento para el trabajo i,
di: Fecha de entrega del trabajo i,
Wi: Tiempo de espera para el trabajo i,
Fi: Tiempo de flujo para el trabajo i,
Li: Retraso del trabajo i,
Ti: Retardo del trabajo i,
Ei: Anticipación del trabajo i.
El tiempo de procesamiento y la fecha de entrega son constantes que están incorporadas a
la descripción de cada trabajo. El tiempo de espera de un trabajo es el que debe esperar
antes de que pueda comenzar su procesamiento. Para los casos que consideramos, es
también la suma de los tiempos de procesamiento de todos los trabajos anteriores. El
tiempo de flujo es simplemente el tiempo de espera más el de procesamiento del trabajo (Fi
= Wi + ti). El tiempo de flujo del trabajo i y el de terminación del trabajo i son los mismos.
Definiremos el retraso del trabajo i como Li = Fi - di, y supondremos que el retraso puede
ser una cantidad positiva o bien, una negativa. El retardo es la parte positiva del retraso (Ti
= máx[Li,0]), y la anticipación es la parte negativa del retraso (Ei = máx[-Li, 0]).

Otras cantidades relacionadas son el retardo máximo Tmáx, dado por la fórmula
Tmáx = máx {T1, T2, . . . , Tn}, y el tiempo de flujo medio F´, dado por la fórmula
n
´
F =1 ∑ F i
i =1

Como solamente estamos considerando una sola máquina, cada calendario puede
representarse por una permutación (es decir, ordenamiento) de los enteros 1, 2, . . . , n. ¡Hay
exactamente n! calendarios de permutación diferentes [n! =n(n - 1) …(2)(1)].

Programación del tiempo de procesamiento más cortó

La regla de programación que minimiza el tiempo de flujo medio F´es SPT.
Sea [1], [2], . . . , [ n] cualquier permutación de los enteros 1, 2, 3, . . . , n. El tiempo de
flujo del trabajo que se programa en la posición k está dado por
k
F [ K ] =∑ t [ i ]
i=1

SE concluye que el tiempo de flujo esta dado por

n n k
F ´ =1 ∑ F [ K ] =1 ∑ ∑ t [ i ]
k=1 k=1 i=1

El término de doble sumatoria puede escribirse de forma diferente. Al expandir la doble

sumatoria, obtenemos
k =1: t[1]
k =2: t[1] + t[2]
k =n: t[1] + t[2] +…+ t[n].
que claramente se minimiza al establecer
t[1]≤ t[2]≤…≤t[n],
que es exactamente la regla de secuenciación SPT
Las siguientes medidas son equivalentes:
1. Tiempo de flujo medio
2. Tiempo de espera medio
3. Retraso medio
En conjunto, se establece que SPT minimiza el tiempo de flujo medio, el tiempo de espera
medio y el retraso medio para la secuenciación de una sola máquina.

Programación de la primera fecha de entrega

Si el objetivo es minimizar el retraso máximo, entonces los trabajos deben ordenarse de
acuerdo con sus fechas de entrega. Es decir, d[1]≤d[2]≤…≤d[n]. No presentaremos una
prueba de este resultado. La idea que fundamenta la prueba es seleccionar algún programa
que no ordene los trabajos en relación con sus fechas de entrega; eso implica que existe un
valor k tal que d[k]>d[k+1]. Se demuestra que al intercambiar las posiciones de los trabajos
k y k +1, se reduce el retraso máximo.
Minimización del número de trabajos retrasados
Hay muchos ejemplos en los cuales la penalización por un trabajo atrasado (retardado)
permanece igual sin importar qué tan grande sea el retraso. Por ejemplo, cualquier atraso en
la terminación de todas las tareas que se requieren para la preparación de un lanzamiento al
espacio podría causar el aborto del lanzamiento, independientemente de la magnitud del
atraso. Vamos a describir el algoritmo de Moore (1968), que minimiza el número de
trabajos retardados para el problema de una sola máquina.
Paso 1. Ordene los trabajos de acuerdo con la fecha de la primera entrega para obtener la
solución inicial. Es decir d[1]≤d[2]≤...≤d[n].
Paso 2. Encuentre el primer trabajo retardado en la secuencia presente, digamos el trabajo
[i]. Si no existe ninguno, vaya al paso 4.
Paso 3. Considere los trabajos [1], [2], . . . , [i]. Rechace el trabajo con el mayor tiempo de
procesamiento. Regrese al paso 2.
Paso 4. Forme una secuencia óptima tomando la secuencia presente y adjuntándole los
trabajos rechazados. Los trabajos adjuntos a la secuencia presente pueden programarse en
cualquier orden porque constituyen los trabajos retardados.

Restricciones de precedentes: Algoritmo de Lawler

El algoritmo de Lawler (Lawler, 1973) es una técnica poderosa para la solución de varios
problemas restringidos de programación. Se supone que la función objetivo es de la forma
min max gi ( Fi )
1 ≤i ≤n
donde gi es cualquier función no decreciente del tiempo de flujo Fi. Además, el algoritmo
maneja cuales quiera restricciones de precedencia. Se presentan restricciones de
precedencia cuando ciertos trabajos deben terminarse antes de que otros trabajos puedan
comenzar; son muy comunes en los problemas de programación. Algunos ejemplos de
funciones gi que pueden considerarse son gi(Fi) =Fi - di = Li, que corresponde a minimizar
el retraso máximo, o sea
gi(Fi) = máx (Fi - di,0), que equivale a la minimización del retraso máximo.
El Algoritmo El algoritmo de Lawler programa primero el trabajo que debe terminarse en
último lugar, luego el siguiente trabajo que debe terminarse después del último, etc. En
cada etapa se determina el conjunto de trabajos que no se requiere que precedan a ningún
otro. Denominemos a este conjunto V. Entre el conjunto V, seleccione el trabajo k que
satisfaga

gi ( τ )= min( gi( τ )) ,
i∈ V
n
Donde τ =∑ t i y corresponde al tiempo de procesamiento de la secuencia presente. Ahora
i=1
el trabajo k se programa como el último. Considere los trabajos restantes y determine
nuevamente el conjunto de trabajos que no se requiere que precedan a ningún otro trabajo
restante. Tras programar el trabajo k, este conjunto pudo haber cambiado. El valor de τ se
reduce por tk y ahora se determina el trabajo programado enseguida del último. El proceso
se continúa hasta que se programan todos los trabajos. Observe que a medida que se
programan los trabajos, pueden relajarse algunas de las restricciones de precedencia, de
modo que es probable que el conjunto V cambie para cada iteración.

2.3. Algoritmos principales para secuenciación en problemas multi-máquina

Programación de n trabajos en dos máquinas
El siguiente esquema, por complejidad, es el caso del tránsito n/2, en el que dos o más
trabajos deben procesarse en dos máquinas según un orden común. Como en el caso n/1,
hay un método que lleva a una solución óptima siguiendo determinados criterios. El
objetivo de este método, llamado regla de Johnson o método de Johnson (por el apellido de
quien lo concibió) es minimizar el tiempo de tránsito desde el comienzo del primer trabajo
hasta el final del último. La regla de Johnson consta de los pasos siguientes:
Se anota el tiempo de operación de cada trabajo en ambas máquinas.
 Se elige el tiempo más breve
Si el tiempo breve es para la primera máquina, se hace el primer trabajo si es para la
segunda, se hace el trabajo al último. En caso de empate, se hace el trabajo en la primera
máquina.
Repita los pasos 2 y 3 con los restantes trabajos hasta completar la programación
Un algoritmo muy enciente para la solución del problema de dos máquinas fue descubierto
por Johnson (1954). Éste denota a las maquinas como Ay B. Se supone que los trabajos
deben procesarse primero en la máquina A y luego en la máquina B. Suponga que los
trabajos están rotulados i, para1≤i≤n; defina
Ai =Tiempo de procesamiento del trabajo i en la máquina A.
Bi = Tiempo de procesamiento del trabajo i en la máquina B.
El resultado de Johnson es que la siguiente regla es óptima para el establecimiento de un
orden para procesar los trabajos en las dos máquinas.
Regla: El trabajo i precede al trabajo i+1 si min⁡(A_i,B_(i+1) )<min⁡(A_(i+1),B_i )

Una manera fácil de implementar esta regla se indica a continuación:

1. Liste los valores de Ai y Bi en dos columnas.
2. Encuentre el elemento restante más pequeño en las dos columnas. Si aparece en la
columna A, entonces programe a ese trabajo como el siguiente. Si aparece en la columna B,
entonces programe ese trabajo como el último.
3. Entrecruce los trabajos tal como están programados. Deténgase cuando todos los trabajos
hayan sido programados.
Ampliación a tres máquinas El problema de programar trabajos es considerablemente más
complejo. Si restringimos nuestra atención solamente al tiempo de flujo total, todavía es
verdad que un horario de permutación es óptimo (éste no es necesariamente el caso para el
tiempo de flujo promedio). Rotule las máquinas como A, B, y C. El problema de las tres
máquinas puede reducirse a (esencialmente) un problema de dos máquinas si se satisface la
siguiente condición:

Programación de un conjunto de trabajos en el mismo número de máquinas.

Algunos centros de trabajo tienen suficientes máquinas correctas para iniciar todos los
trabajos al mismo tiempo. Aquí el problema no es qué trabajo hacer primero, sino qué
asignación de trabajos a cuáles máquinas dará el mejor programa general. En estos casos, se
aplica el método de asignación. El método de asignación es un caso especial del método de
transporte de programación lineal. Puede aplicarse a situaciones en las que hay n fuentes de
oferta y n usos de la demanda (como cinco trabajos en cinco máquinas) y el objetivo es
minimizar o maximizar alguna medida de eficacia. La técnica es conveniente en
aplicaciones que comprenden asignación de trabajos a los centros de trabajo, personas a los
puestos, etc. El método de asignación es apropiado para resolver problemas que tienen las
características siguientes:
Hay n “cosas” que se distribuyen a n “destinos”
Cada cosa debe asignarse a un, y sólo un, destino.
Sólo puede aplicarse un criterio (por ejemplo, costo mínimo, utilidad máxima o
tiempo mínimo de terminación).
Si solo se puede asignar un trabajo a una máquina, se puede utilizar el método Húngaro, el
cual es un método de optimización de problemas de asignación, conocido como tal gracias
a que los primeros aportes al método clásico definitivo fueron de Dénes König y Jenő
Egerváry dos matemáticos húngaros. El algoritmo tal como se detallará a continuación está
diseñado para la resolución de problemas de minimización únicamente, será entonces
cuestión de agregar un paso adicional para abordar ejercicios de maximización.

Algoritmo húngaro, paso 1

Antes que nada, cabe recordar que el método húngaro trabaja en una matriz de costos n*m
(en este caso conocida como matriz m*m, dado que el número de filas es igual al número
de columnas n = m), una vez construida esta se debe encontrar el elemento más pequeño en
cada fila de la matriz.
Algoritmo húngaro, paso 2
Una vez se cumple el procedimiento anterior se debe construir una nueva matriz n*m, en la
cual se consignarán los valores resultantes de la diferencia entre cada costo y el valor
mínimo de la fila a la cual cada costo corresponde (valor mínimo hallado en el primer
paso).
Algoritmo húngaro, paso 3
Este paso consiste en realizar el mismo procedimiento de los dos pasos anteriores referidos
ahora a las columnas, es decir, se halla el valor mínimo de cada columna, con la diferencia
que este se halla de la matriz resultante en el segundo paso, luego se construirá una nueva
matriz en la cual se consignarán los valores resultantes de la diferencia entre cada costo y el
valor mínimo de la columna a la cual cada costo corresponde, matriz llamada "Matriz de
Costos Reducidos".
Algoritmo húngaro, paso 4
A continuación, se deben de trazar líneas horizontales o verticales o ambas (únicamente de
esos tipos) con el objetivo de cubrir todos los ceros de la matriz de costos reducidos con el
menor número de líneas posibles, si el número de líneas es igual al número de filas o
columnas se ha logrado obtener la solución óptima (la mejor asignación según el contexto
de optimización), si el número de líneas es inferior al número de filas o columnas se debe
de proceder con el paso 5.
Algoritmo húngaro, paso 5
Este paso consiste en encontrar el menor elemento de aquellos valores que no se encuentran
cubiertos por las líneas del paso 4, ahora se restará del restante de elementos que no se
encuentran cubiertos por las líneas a continuación, este mismo valor se sumará a los valores
que se encuentren en las intersecciones de las líneas horizontales y verticales, una vez
finalizado este paso se debe volver al paso 4.

Programación de n trabajos en m máquinas

Los centros de trabajo complejos se caracterizan por numerosos centros de máquinas que
procesan trabajos diferentes que llegan intermitentemente a lo largo del día. Si hay que
procesar n trabajos en m máquinas y todos los trabajos se procesan en todas las máquinas,
entonces hay (n!) m programas alternativos para este grupo de trabajos. En virtud del gran
número de programas que hay incluso para centros de trabajo pequeños, la simulación por
computadora (véase el capítulo 19A) es la única manera práctica de determinar las
bondades relativas de las reglas de prioridad en esas situaciones.
¿Qué regla de prioridad debe usarse? Los autores piensan que las necesidades de la mayor
parte de los fabricantes quedan cubiertas razonablemente con un esquema simple de
prioridades que incorpore los principios siguientes:
 Debe ser dinámico, es decir, que se calcule a menudo durante un trabajo para
que dé cuenta de los cambios de las condiciones.
 Debe basarse, en un sentido o en otro, en el margen de tiempo (la diferencia
entre lo que falta por 2. hacer de un trabajo y el tiempo que queda para
hacerlo).
 La secuenciación tiene distintos niveles de complejidad, ya veíamos como se
aplicaban principios de prioridad para elegir el mejor orden para procesar
distintas operaciones que pasaban por un centro de trabajo; el siguiente nivel
corresponde en determinar la secuencia para efectuar el mismo proceso pero
esta vez para dos centros de trabajo.
En la industria, y por muchos años la regla de Johnson se ha aplicado con gran éxito para
minimizar el tiempo de procesamiento global.
¿En qué consiste la Regla de Johnson?
La regla de Johnson es un algoritmo heurístico utilizado para resolver situaciones de
secuenciación de procesos que operan dos o más órdenes (operaciones) que pasan a través
de dos máquinas o centros de trabajo. Su principal objetivo es minimizar el tiempo de
procesamiento total del grupo de trabajos. Este algoritmo consiste en la aplicación de cuatro
sencillos pasos:
 El primer paso consiste en listar todos los trabajos u operaciones junto con su
tiempo de procesamiento por cada centro de trabajo o máquina.
 El segundo paso consiste en seleccionar el tiempo de procesamiento más corto.
Recuerde que como resultado de la aplicación del paso 1 obtenemos dos columnas
de tiempos (tiempos del centro de trabajo 1 y 2); Sí el tiempo más corto se
encuentra en la columna correspondiente al centro de trabajo (máquina) 1, este
trabajo se programa primero, en caso contrario y de estar en la columna
correspondiente al centro de trabajo 2, este trabajo se programa al final. Cualquier
empate puede romperse de forma arbitraria.
 Una vez se programa un trabajo, sea al inicio o sea al final, este se elimina de la lista
inicial.
 Se deben repetir los pasos 2 y 3 para los trabajos restantes, trabajando hacia el
centro de la secuencia.
Ejemplo de la aplicación de la Regla de Johnson
El taller de metalmecánica «Abelito» tiene para su programación 5 órdenes de trabajo; se
trata de piezas de acero inoxidable de geometrías distintas, para ello la materia prima
(bloques de acero inoxidable) debe ser primero torneada, según especificaciones
particulares de cada pieza; luego son pasadas al centro de fresado, en el cual adquieren
geometrías diversas según las precisiones del plano que la acompañan.
El orden de trabajo no es conmutativo, por lo cual es imperativo que antes de que cada
pieza sea fresada deberá haber pasado por el proceso de torneado. Los tiempos de torneado
y fresado de cada pieza se especificarán en el siguiente tabulado:

Orden Torneado (horas) Fresado (horas)

Pieza A 1,2 1,8

Pieza B 2,2 0,8

Pieza C 0,7 3,1

Pieza D 0,5 1,1

Pieza E 1,5 2,3

Con base en lo anterior, debemos efectuar una secuenciación que minimice el tiempo total
de programación, para ello utilizaremos la regla de Johnson.

Solución
El primer paso consiste entonces en listar los trabajos junto a sus respectivos tiempos de
procesamiento en los centros de trabajo, para lo cual hacemos uso del tabulado del
enunciado del problema:

Orden Torneado (horas) Fresado (horas)

Pieza A 1,2 1,8

Pieza B 2,2 0,8

Pieza C 0,7 3,1

Pieza D 0,5 1,1

Pieza E 1,5 2,3

El segundo paso consiste en seleccionar el tiempo de procesamiento más corto, como este
se encuentra en el centro de trabajo 1 (torneado, primera columna), se programa de
primero:
El tercer paso consiste en eliminar de la lista la orden que fue asignada:

El último paso indica la repetición de los pasos 2 y 3 hasta asignar la totalidad de órdenes:

En la asignación del orden del siguiente trabajo podemos observar que el tiempo menor se
encuentra en la segunda columna, correspondiente al proceso de fresado, razón por la cual
este trabajo se programará de último:

El último trabajo se asignará por lógica en el orden que queda disponible, por lo cual la
secuencia obtenida mediante la aplicación de la regla de Johnson es la siguiente:
Es práctica común luego de determinar la secuencia, diagramar el orden y los tiempos de
cada trabajo y para cada máquina en una gráfica de Gantt, esta herramienta permite
observar de una manera sencilla el tiempo de programación global, y por cada centro de
trabajo, así como los tiempos ociosos de los mismos.

Podemos observar como el centro de fresado debe esperar 0,5 horas para recibir la pieza D
proveniente del centro de torneado; además, podemos observar como el tiempo total de
programación es igual a 9,6 horas.
Regla de Johnson, n Trabajos, dos centros de trabajo La regla de Johnson es una heurística
simple que proporciona un tiempo de procesado mínimo para secuenciar n trabajos
mediante dos máquinas o centros de trabajo donde la misma secuencia de proceso debe ser
seguida por todos los trabajos. Los trabajos con menores tiempos de proceso son colocados
al principio si el tiempo de procesado es en la primera máquina, y al final si es en la
segunda máquina. Este procedimiento maximiza el tiempo de operación de ambos centros
de trabajo.
Ejemplo 6-4: Industrias Metálicas "ABC" tiene órdenes de cinco trabajos específicos (A, B,
C, D y E) que deben ser procesados secuencialmente a través de dos centros de trabajo
(horneado y decorado). La cantidad de tiempo (en horas) requerido para los trabajos es
mostrada en la tabla inferior. Determínese la secuencia de programación que minimiza el
tiempo total para los cinco trabajos y preséntese en la forma de una gráfica de Gannt.
Tiempo que requiere el trabajo (h)
Centros de trabajo A B C D E
1 Torneado 8 7 11 10 9
2 Pintura 6 12 5 7 13
La regla de Johnson dice cómo identificar el tiempo de procesado más corto. Si esto es en
el primer centro de trabajo, colóquese tan al final como sea posible. Elimínese ese trabajo
para consideraciones posteriores y aplíquese la regla de decisión a los trabajos restantes.
Rómpase cualquier empate entre trabajos secuenciando el trabajo en el primer centro
tempranamente y en el segundo centro al último.
Los trabajos que tienen el mismo tiempo en ambos centros de trabajo pueden ser asignados
al final de la secuencia.

a) El menor tiempo es para C en el centro 2 (2 horas). Colóquese la C al final. C

b) El siguiente menor es A en el centro 2. Colóquese A tan tarde como sea posible. A

C

c) El siguiente es un empate entre B y D. Secuénciese el trabajo en el primer centro

(trabajo B) tan pronto como sea posible. B A C

d) El siguiente es D en el centro 2. Colóquese tan tarde como sea posible. B D A C

 e) Colóquese el trabajo B en el cuadro restante. B E D A C

Los tiempos secuenciales son los siguientes:

BEDAC
Centro 1 4 8 7 5 8
Centro 2 9 10 4 3 2

Figura 6.2 Gráfica Regla de Johnson nx2

3. Solución del estudio de caso

La solución estudio de caso que se presenta para la Litografía, se da cuando se relacionan
20 trabajos que se tienen programados para el próximo periodo divididos en dos procesos,
uno el de preparación de planchas y tintas, limpieza de rodillos y el segundo proceso de
impresión offset, que para el análisis efectuado se definen como dos puestos de trabajo y/o
maquinas bajo el modelo seleccionado.
La consecución de trabajos en máquinas, se refiere a la asignación de tiempos para los
recursos disponibles a partir de un determinado criterio, estableciendo la secuencia óptima
para la ejecución de los trabajos sobre un conjunto de máquinas con el menor tiempo de
ocio o perdido posible en el proceso.
Unos de los procesos de gran importancia en los sistemas de producción debido a los
múltiples beneficios que aporta a la empresa es una correcta programación en el área de
producción que involucre una asignación de máquinas para distintas operaciones y la
secuenciación de estas con el objetivo de disminuir costos, optimizar recursos y mejora el
servicio al cliente.
Con base en lo anterior, para la solución de este caso hemos analizado y estudiado el
algoritmo O regla de JOHNSON, pues este nos permite establecer secuencias optimas en
procesos con varias operaciones, tal como sucede en el caso litografía, adicional a esto
como ya contamos con el tiempo que dura cada actividad o tarea y la cantidad de tareas que
se deben realizar, podemos empezar a ordenar de forma ascendente, es decir, de menor a
mayor los tiempos de tarea para definir los más cortos con el objetivo de minimizar el
tiempo requerido para finalizar los trabajos (MAKESPAN).

4. Conclusiones y Recomendaciones
Analizando y estudiando el Algoritmo Johnson podemos concluir que este método nos
permite resolver de manera eficaz el problema de secuenciación de 2 máquinas con el fin
minimizar el tiempo de entrega de un trabajo.
La aplicación del Scheduling da mejores soluciones para la toma de decisiones, de modo tal
que al ejecutar dentro de cada proceso productivo pueda finalmente generar disminución en
los tiempos entre el cambio de cada trabajo realizado.
La secuenciación de máquinas permite desarrollar una seria de estrategias que ayudan
finalmente a la minimización del Makespan dentro de una compañía.
Uno de los retos que hoy en día afrontan las organizaciones es la optimización y
minimización de tiempos en el desarrollo de su proceso productivo siendo fundamentos
esenciales para la búsqueda de rentabilidad y sostenibilidad dentro del mercado.

Bibliografía
Autor: August Casanoves

Fuente bibliográfica: Dirección de operaciones, © Universidad de Barcelona Virtual, 2003

Referencia bibliográfica: Código documento: 1059987

Autores: David Burgués i Estebanell ( Ingeniero técnico industrial por la upc. Master en

dirección y administración de empresas por la ub/uab/upc. ), Ricard Rocosa
Alsina ( Ingeniero industrial por la universidad politécnica de cataluña (etseib). Consultor
en organización y mejora de procesos. ) y August Casanoves
Fuente bibliográfica: E-business, © Universidad de Barcelona Virtual, 2003 Referencia
bibliográfica: Código documento: 1060050

Cortés Rodríguez, C. J., Delgado, E., Duarte Velasco, Ó. G. (2005).

Aplicación de algoritmos genéticos para la programación de tareas en una celda de
manufactura. Ingeniería e Investigación, 25 (2), 24-31. Recuperado de
[Link]

YouTube. 2018. Programación Multiobjetivo [Video]. YouTube.

Consultado el 10 de Noviembre de 2020 en [Link]

CHASE, R. B., F. ROBERT JACOBS, & NICHOLAS J. AQUILANO. (2009).

ADMINISTRACIÓN DE OPERACIONES Producción y cadena de suministros
(Duodécima Edición ed.). McGraw-Hill Nahmias, S. (2007).

Análisis de la producción y las operaciones (5ta edición ed.). McGraw-Hill

[Link]

Gestión de la Producción y Operaciones Naim Caba Villalobos Oswaldo Chamorro

Altahona Tomás José Fontalvo Herrera

[Link]