Guía de

Ejercicios
Propuestos

(Gestión de
Operaciones l)

14217

Semana 13 a 15

1
INDUSTRIA VIRTUAL 2020 2
La empresa Computín S.A se especializa en la reparación de discos duros dañados, los cuales pueden requerir sólo la
reconfiguración de su sistema de archivos, mientras que otros requieren la sustitución de partes defectuosas. Actualmente
están en espera del servicio cinco discos duros con diversas averías. Las estimaciones más aproximadas acerca de los tiempos
de trabajo y los datos de entrega prometidos a los clientes (el número de días para la entrega a partir de hoy) se presentan en
la siguiente tabla:

Tiempo estimado de trabajo Fecha de entrega prometida

Disco Duro
(días) (días desde hoy)
HP 1000 5 8
Kingston X-230 4 15
Samsung 200-Z 10 12
Kingston 9000 1 20
Dell 2K Series 3 10

a) Desarrolle programas por separado aplicando las reglas SPT, EDD y mínima holgura.
b) Compare los tres programas considerando el tiempo promedio de flujo, el inventario promedio, la utilización de la
máquina y la tardanza promedio. ¿Cuál secuencia es mejor según cada una de las anteriores medidas de eficiencia?

Solución:

a) Se tiene:

Trabajo Disco Duro ti di Holgura: Hi = di – ti

A HP 1000 5 8 3
B Kingston X-230 4 15 11
C Samsung 200-Z 10 12 2
D Kingston 9000 1 20 19
E Dell 2K Series 3 10 7

Secuencia SPT: D – E – B – A – C

Tiempo de Flujo Tardanza

Trabajo ti di
Fi Ti
D 1 1 20 0
E 3 4 10 0
B 4 8 15 0
A 5 13 8 5
C 10 23 12 11
Suma 23 49 ---- 16
Secuencia EDD: A – E – C – B – D

Tiempo de Flujo Tardanza

Trabajo ti di
Fi Ti
A 5 5 8 0
E 3 8 10 0
C 10 18 12 6
B 4 22 15 7
D 1 23 20 3
Suma 23 76 ---- 16

Secuencia Mínima Holgura: C – A – E – B – D

Tiempo de Flujo Tardanza

Trabajo ti di
Fi Ti
C 10 10 12 0
A 5 15 8 7
E 3 18 10 8
B 4 22 15 7
D 1 23 20 3
Suma 23 88 ---- 25

b)

Secuencia
MEJOR
SPT EDD Mínima Holgura
MÉTODO
Medida
Tiempo
49 76 88
promedio de = 9,8 = 15,2 = 17,6 SPT
flujo: F (días) 5 5 5

Inventario WIP 49 76 88
= 2,130 = 3,304 = 3,826 SPT
promedio 23 23 23

23 23 23
Utilización = 0,4694 = 46,94% = 0,3026 = 30,26% = 0,2614 = 26,14% SPT
49 76 88
Tardanza
16 16 25 SPT o
promedio: = 3,2 = 3,2 =5
5 5 5 EDD
T (días)
Andrés Arturson es un consultor de software independiente. Después de terminar su más reciente proyecto, él tiene cinco
trabajos esperándolos para su término. El estima los siguientes tiempos de procesos para completar cada trabajo y además los
tiempos de entrega.
En la Tabla siguiente se presenta dicha información:

Fecha de entrega (días a partir del

Trabajo N° Tiempo de Procesamiento (días)
presente)
A 12 52
B 16 37
C 08 28
D 20 57
E 06 31

Andrés que tomo recientemente un curso de Gestión de Operaciones desea saber que política tomar para realizar los
trabajos. Para ello desea aplicar las siguientes reglas SPT (menor tiempo de procesamiento), EDD (fecha de terminación más
temprana); CR (índice crítico) y STR (menor tiempo de holgura).
Para cada caso calcule el tiempo promedio del flujo por trabajo, Makespan, número de trabajos promedio en el sistema,
tardanza a promedio por trabajo y la cantidad de trabajos tardíos al aplicar cada una de las políticas anteriores y decida cual
política es más conveniente para él.
NOTA: Para el cálculo del Makespan use la fórmula a lo menos en dos políticas.

Solución:

a) Regla SPT

Fecha Tiempo de Días Días

Secuencia Trabajo
entrega flujo anticipados retrasados
1 E(6) 31 6 25 -
2 C(8) 28 14 14 -
3 A(12) 52 26 26 -
4 B(16) 37 42 - 5
5 D(20) 57 62 - 5
Suma = 150 Suma = 10

- Tiempo promedio de flujo=150/5=30 días

- Makespan:

C ( J1 ,1) = 6
C ( J 2 ,1) = C ( J1 ,1) + T ( J 2 ,1) = 6 + 8 = 14
C ( J 3 ,1) = C ( J 2 ,1) + T ( J 3 ,1) = 14 + 12 = 26
C ( J 4 ,1) = C ( J 3 ,1) + T ( J 4 ,1) = 26 + 16 = 42
C ( J 5 ,1) = C ( J 4 ,1) + T ( J 5 ,1) = 42 + 20 = 62
 - Número de trabajos promedio: 150/62=2.42 trabajos
- Tardanza promedio (por trabajo):10/5=2 días
- Número de trabajos retrasados: 2 trabajos

b) Regla EDD

Fecha Tiempo de Días Días

Secuencia Trabajo
entrega flujo anticipados retrasados
1 C(8) 28 8 20 -
2 E(6) 31 14 17 -
3 B(16) 37 30 7 -
4 A(12) 52 42 10 -
5 D(20) 57 62 - 5
Suma = 156 Suma = 5

- Tiempo promedio de flujo=156/5= 31.2 días

- Makespan:

C ( J1 ,1) = 8
C ( J 2 ,1) = C ( J1 ,1) + T ( J 2 ,1) = 6 + 8 = 14
C ( J 3 ,1) = C ( J 2 ,1) + T ( J 3 ,1) = 14 + 12 = 26
C ( J 4 ,1) = C ( J 3 ,1) + T ( J 4 ,1) = 26 + 16 = 42
C ( J 5 ,1) = C ( J 4 ,1) + T ( J 5 ,1) = 42 + 20 = 62
- Número de trabajos promedio: 156/62= 2.52 trabajos
- Tardanza promedio (por trabajo): 5/5= 1 días
- Número de trabajos retrasados: 1 trabajos

c) Regla CR(índice crítico)

Tiempo de Días Días

Secuencia Trabajo Índice crítico
flujo anticipados retrasados
1 B(16) 37/16=2.31 16 22 -
2 D(20) 57/20=2.87 36 21 -
3 C(8) 29/8=3.5 44 - 16
4 A(12) 52/12=4.33 56 - 4
5 E(6) 31/6=5.17 62 - 31
Suma = 214 Suma = 51

- Tiempo promedio de flujo= 214/5= 42.8 días

- Makespan: 62
- Número de trabajos promedio: 214/62= 3.45 trabajos
- Tardanza promedio (por trabajo): 51/5= 10.2 días
- Número de trabajos retrasados: 3 trabajos
d) Regla STR

Tiempo de Días Días

Secuencia Trabajo Holgura
flujo anticipados retrasados
1 C(8) 28-8=20 8 20 -
2 B(16) 37-16=21 24 13 -
3 E(6) 31-6=25 30 1 -
4 D(20) 57-20=37 50 7 -
5 A(12) 52-12=40 62 - 10
Suma = 174 Suma = 10

- Tiempo promedio de flujo = 174/5= 34.8 días

- Makespan: 62
- Número de trabajos promedio: 174/62= 2.8 trabajos
- Tardanza promedio (por trabajo):10/5= 2 días
- Número de trabajos retrasados: 1 trabajos

Tabla resumen:

N° Trabajos Tardanza N° Trabajos

Tiempo Flujo Makespan
Promedio Promedio Retrasados
SPT 30 62 2.42 2 2
EDD 31.2 62 2.52 1 1
CR 42.8 62 3.45 10.2 3
STR 34.8 62 2.81 2 1

Dada la tabla anterior se puede apreciar que la política más adecuada es la EDD dado que tiene el menor número de retraso y
el menor tiempo de retraso.

3) Considere los siguientes trabajos y sus tiempos de procesamiento en las tres máquinas. No se permite pasar los trabajos.

Duración (horas)
Máquina 1 Máquina 2 Máquina 3
TRABAJO Ti1 Ti2 Ti3
A 6 4 7
B 5 2 4
C 9 3 10
D 7 4 5
E 11 5 2

Con esta información calcule:

a) Las secuencias, empleando el algoritmo de CDS
b) Cuál de las secuencias anteriores es la mejor, empleando para ello el concepto de Makespan (utilice la fórmula para ello)
Solución:
a)
Solución 1:
Trabajos M1 M2
A 6 7
B 5 4
C 9 10
D 7 5
E 11 2
Secuencia aplicando Johnson: A, C, D, B, E.

Solución 2:
Trabajos M1 M2
A 10 11
B 7 6
C 12 13
D 11 9
E 16 7
Secuencia aplicando Jonson: A, C, D, E, B.
b) Secuencia A, C, D, B, E:

c( j1,1) = t ( j1,1) = 6
c ( j2 ,1) = c ( j1 ,1) + t ( j2 ,1) = 6 + 9 = 15
c ( j3 ,1) = c ( j2 ,1) + t ( j3 ,1) = 15 + 7 = 22
c ( j4 ,1) = c ( j3 ,1) + t ( j4 ,1) = 22 + 5 = 27
c ( j5 ,1) = c ( j4 ,1) + t ( j5 ,1) = 27 + 11 = 38
c ( j1 ,2) = c ( j1 ,1) + t ( j1 , 2) = 6 + 4 = 10
c ( j1 ,3) = c ( j1 , 2) + t ( j1 ,3) = 10 + 7 = 17
c( j2 ,2) = max c( j2 ,1) + c( j1 ,2)+ t ( j2 ,2) = 15 + 3 = 18
c( j2 ,3) = max c( j2 ,2) + c( j1 ,3)+ t ( j2 ,3) = 18 + 10 = 28
c( j3 ,2) = max c( j3 ,1) + c( j2 ,2)+ t ( j3 ,2) = 22 + 4 = 26
c( j3 ,3) = max c( j3 ,2) + c( j2 ,3)+ t ( j3 ,3) = 28 + 5 = 33
c( j 4 ,2) = maxc( j 4 ,1) + c( j 3 ,2)+ t ( j 4 ,2) = 27 + 2 = 29
c( j 4 ,3) = maxc( j 2 ,2) + c( j 3 ,3)+ t ( j 4 ,3) = 33 + 4 = 37
c( j 5 ,2) = maxc( j 5 ,1) + c( j 4 ,2)+ t ( j 5 ,2) = 38 + 5 = 43
c( j 5 ,3) = maxc( j 5 ,2) + c( j 4 ,3)+ t ( j 5 ,3) = 43 + 2 = 45
Secuencia A, C, D, E, B:

c ( j1 ,1) = t ( j1 ,1) = 6
c ( j 2 ,1) = c ( j1 ,1) + t ( j 2 ,1) = 6 + 9 = 15
c ( j3 ,1) = c ( j 2 ,1) + t ( j3 ,1) = 15 + 7 = 22
c ( j 4 ,1) = c ( j3 ,1) + t ( j 4 ,1) = 22 + 11 = 33
c ( j5 ,1) = c ( j 4 ,1) + t ( j5 ,1) = 33 + 5 = 38
c ( j1 , 2) = c ( j1 ,1) + t ( j1 , 2) = 6 + 4 = 10
c ( j1 ,3) = c ( j1 , 2) + t ( j1 ,3) = 10 + 7 = 17
c( j2 ,2) = max c( j2 ,1) + c( j1 ,2) + t ( j2 ,2) = 15 + 3 = 18
c( j2 ,3) = max c( j2 ,2) + c( j1 ,3) + t ( j2 ,3) = 18 + 10 = 28
c( j3 ,2) = max c( j3 ,1) + c( j2 ,2) + t ( j3 ,2) = 22 + 4 = 26
c( j3 ,3) = max c( j3 ,2) + c( j2 ,3) + t ( j3 ,3) = 28 + 5 = 33
c( j4 ,2) = max c( j4 ,1) + c( j3 ,2) + t ( j4 ,2) = 33 + 5 = 38
c( j4 ,3) = max c( j4 ,2) + c( j3 ,3) + t ( j4 ,3) = 38 + 2 = 40
c( j5 ,2) = max c( j5 ,1) + c( j4 ,3) + t ( j5 ,2) = 38 + 2 = 40
c( j5 ,3) = max c( j5 ,2) + c( j4 ,3) + t ( j5 ,3) = 40 + 4 = 44
La mejor solución es A, C, D, E, B; pues el Makespan es el menor.

4) Las órdenes A, B y C llegan en orden alfabético y reciben su prioridad sobre la base del primero en llegar y primero en
salir. Las rutas y los tiempos de operación se muestran a continuación:

Hoja de ruta: Hoja de ruta: Hoja de ruta:

Orden A Orden B Orden C
Secuencia de Tiempo Tiempo Tiempo
Máquina Máquina Máquina
operaciones (horas) (horas) (horas)
1 I 3 II 3 I 4
2 II 3 III 2 III 4
3 III 2 I 2 II 2

a) ¿Cómo programaría las máquinas, según la información entregada? Haga un esquema, tabla, gráfico u otro elemento de
apoyo para justificar su respuesta. Cabe señalar que los tiempos límites para las ordenes son de 10 horas para A, de 16 horas
para B y 14 horas para la orden C. ¿Qué tanto retraso resulta en el procesamiento de las órdenes? ¿Cuál es el exceso del
inventario resultante?
b) Es posible proponer otra secuencia, que sea más eficiente. Discútala y evalúela.
Solución:

a) Secuencia A-B-C
Opción no fraccionable:
Horas I II III
1 A B
2 A B
3 A B
4 A B
5 A B
6 B A
7 B A
8 C A
9 C
10 C
11 C
12 C
13 C
14 C
15 C
16 C
17 C

Opción Fraccionable:
Horas I II III
1 A B
2 A B
3 A B
4 C A B
5 C A B
6 B A
7 B A
8 C A
9 C
10 C
11 C
12 C
13 C
14 C
15 C
16
17
Existe retraso en C dado que la fecha límite es 14 horas, en consecuencia (15-17) 3 horas de retraso para la orden C. El
retraso es de 1 hora, en el caso fraccionable para C.

Inventario en sistema = (8+5+17)/17=1.88 órdenes.

Si entrega a tiempo, inventario en sistema = 3/17 = 0.176 órdenes.

La fracción de atraso =1/15 = 0.06.

b) Secuencia ACB:
No fraccionada:

Horas I II III
1 A B
2 A B
3 A B
4 C A B
5 C A B
6 C A
7 C A
8 B A
9 B C
10 C
11 C
12 C
13 C
14 C
15

El tiempo total es de 14 horas para el total de los 3 trabajos, ajustándolos a los tiempos límites.

5) Los últimos pasos del proceso de producción requieren dos operaciones. En algunos trabajos es necesario completar el
procesamiento en M1 antes de iniciarlo en M3. Otros trabajos requieren que el procesamiento en M2 se realice antes que en
M3. Actualmente, seis trabajos están en espera de ser procesados en M1 y cuatro trabajos en espera de ser procesados en M2.
Los siguientes datos han sido generados por el sistema de control del taller de producción:
 Tiempos de procesamientos (horas)
Fecha de
Trabajo M1 M2 M3
vencimiento (h)
1 6 - 4 13
2 2 - 1 18
3 4 - 7 22
4 5 - 3 16
5 7 - 4 30
6 3 - 1 29
7 - 4 6 42
8 - 2 10 31
9 - 6 9 48
10 - 8 2 40

a) Desarrolle el programa para este taller, aplicando la CR, calcule además el tiempo promedio de flujo, las horas promedio
de tardanza y de demora, así como el inventario promedio.

Solución:

Dado el orden en que se debe realizar cada trabajo, para calcular el índice crítico podemos tomar los datos como parte de un
solo gran sistema:

Tiempo de Fecha de
Trabajo Índice Crítico
procesamiento vencimiento
1 10 13 1.3
2 3 18 6
3 11 22 2
4 8 16 2
5 11 30 2.72
6 4 29 7.25
7 10 42 4.2
8 12 31 2.58
9 15 48 3.2
10 10 40 4

3 − 4 − 8 − 5 − 9 − 10 − 7 − 2 − 6
Secuencia : 1 −
4 − 3 − 8 − 5 − 9 − 10 − 7 − 2 − 6
Utilizando la primera secuencia:

Tiempo de Tiempo de Fecha de

Trabajo Demora Tardanza
Procesamiento Flujo Vencimiento
1 10 10 13 -3 0
3 11 21 22 -1 0
4 8 29 16 13 13
8 12 41 31 10 10
5 11 52 30 22 22
9 15 67 48 19 19
10 10 77 40 37 37
7 10 87 42 45 45
2 3 90 19 72 72
6 4 94 29 65 65
Suma 94 568 ––– 279 283

Finalmente:

568 279
Tiempo de Flujo = = 56,8 horas Demora = = 27,9 horas
10 10
568 283
Inventario = = 6,04 trabajos Tardanza = = 28,3 horas
94 10

6) La Quix Company, ha desarrollado un nuevo líquido para lavar platos, y está preparándose para una campaña
promocional en televisión. La empresa ha decidido programar una serie de anuncios de un minuto durante las
puntas de audiencia de dueñas de casa, de 1:00 a 5:00 P.M. Para abarcar la mayor audiencia posible. Quix
Company desea programar un anuncio en cada una de las cuatro cadenas y tener un anuncio durante cada uno de
los cuatro bloques de una hora. Los índices de exposición por cada hora representan el número de televidentes por
cada 1.000 dólares gastados y se presentan en la siguiente Tabla.

CADENAS
HORA A B C Independiente
1:00-2:00 P.M. 2,71 1,81 1,13 0,95
2:00-3:00 P.M. 1,89 1,55 1,71 1,06
3:00-4:00 P.M. 1,92 1,85 0,99 0,77
4:00-5:00 P.M. 1,15 2,14 1,68 1,28

a) ¿Qué cadena debería ser programada a cada hora para ofrecer una máxima exposición a la audiencia?
b) Plantee el modelo como un problema de Programación Lineal
Solución:

a) Para maximizar cambiaremos la estructura de los datos, usando (10 − xij ) = yij , y a partir de este cambio
minimizamos:

A B C IND
1 7.29 8.19 8.87 9.05
2 8.11 8.45 8.29 8.94
3 8.08 8.15 9.01 9.23
4 8.85 7.85 8.32 8.72

Restando el menor de cada fila:

A B C IND
1 0 0.9 1.58 1.76
2 0 0.34 0.18 0.83
3 0 0.07 0.93 1.15
4 1 0 0.47 0.87

Restando el menor de cada columna:

A B C IND
1 0 0.9 1.1 0.93
2 0 0.34 0 0
3 0 0.07 0.25 0.32
4 1 0 0.19 0.04

Se tienen sólo 3 líneas, por lo cual es infactible. Luego, restamos el menor de los no cubiertos, sumándoselo a las
intersecciones:
A B C IND
1 0 0.9 1.26 0.89
2 0.04 0.38 0 0
3 0 0.07 0.71 0.28
4 1 0 0.25 0

Nuevamente se tienen sólo 3 líneas, por lo cual es infactible. Luego, restamos el menor de los no cubiertos,
sumándoselo a las intersecciones:
A B C IND
1 0 0.83 1.29 0.82
2 0.11 0.38 0 0
3 0 0 0.64 0.21
4 1.07 0 0.25 0

Se tienen 4 líneas = rango, luego estamos en el óptimo.

Asignación:
Período 1, cadena A
Período 2, cadena C-D
Período 3, cadena A-B
Período 4, cadena B-IND

Entones, finalmente:
Período 1, cadena A
Período 2, cadena C
Período 3, cadena B
Período 4, cadena IND

b) F.O.:
4 4
MaxZ =  P X
i =1 j =1
ij ij

MaxZ = 2.71X11 + 1.31X 12 + 1.13 X 13 + 0.95 X14 + 1.89 X 21 + 1.55 X 22

+ 1.71X 23 + 1.06 X 24 + 1.92 X 31 + 1.85 X 32 + 0.99 X 33 + 0.77 X 34 + 1.15 X 41
+ 2.14 X 42 + 1.68 X 43 + 1.28 X 44

Alternativamente:
4 4
MinZ =  Pij X ij
i =1 j =1

MinZ = 7.29 X 11 + 8.19 X 12 + 8.87 X 13 + 9.05 X 14 + 8.11X 21 + 8.45 X 22

+ 8.29 X 23 + 8.94 X 24 + 8.08 X 31 + 8.15 X 32 + 9.01X 33 + 9.23 X 34 + 8.85 X 41
+ 7.85 X 42 + 8.32 X 43 + 8.72 X 44
S.A.:
4

X
j =1
ij = 1 _ i = 1..4
4

X
i =1
ij = 1 _ j = 1..4

1
X ij =  , donde las X ij son variables binarias.
0

7) Un operario de la fábrica LookOut Inc., ubicada al sur de California, tiene cinco trabajos que se pueden procesar en
cualquiera de las seis máquinas, con sus respectivos tiempos (en horas), las cuales se presentan a continuación:
 Trabajo
A-52 E-23 I-56 O-42 U-84
Máquina
1 60 22 29 42 30
2 22 52 16 32 18
3 34 16 58 28 25
4 42 32 28 46 15
5 30 18 22 15 45
6 60 48 55 30 42

a) Determine la asignación óptima de los trabajos a las máquinas, que dé cómo resultado la minimización del tiempo total de
procesamiento.
b) Aplique una heurística “golosa” por columnas para hacer la asignación

Solución:

a) Por el Método Húngaro:

Como hay una máquina demás, creamos un trabajo ficticio asignándole altos tiempos de procesamiento, para que una
máquina que tenga un bajo tiempo de procesamiento en el resto de los trabajos no sea asignada a este trabajo ficticio.

De esta manera, se tiene:

 60 22 29 42 30 100  38 0 7 20 8 78 
 22 52 16 32 18 100   6 36 0 16 2 84 
  
 34 16 58 28 25 100  18 0 42 12 9 84 
   
 42 32 28 46 15 100  Menor de cada 27 17 13 31 0 85 
 30 18 22 15 45 100  columna sin ceros 15 3 7 0 30 85 
Menor de   →  
cada fila  60 48 55 30 42 100  30 18 25 0 12 70 

32 0 7 20 8 8 25 0 0 20 8 8 
 0 36 0 16 2 14   0 43 0 23 9 21
  
12 0 42 12 9 14   5 0 35 12 9 14 
   
 21 17 13 31 0 15  14 17 6 31 0 15 
Menor de  9 3 7 0 30 15   2 3 0 0 30 15 
los no   Iteración final  
cubiertos 24 18 25 0 12 0  → 17 18 18 0 12 0 
→
Asignación:

M1 → E-23 o I-56 ⇒ M1 → I-56

M2 → A-52 o I-56 ⇒ M2 → A-52
M3 → E-23 ⇒ M3 → E-23
M4 → U-84 ⇒ M4 → U-84
M5 → I-56 o O-42 ⇒ M5 → O-42
M6 → O-42 o Ficticio ⇒ M6 → Ficticio

Tiempo Total Procesamiento = 29 + 22 + 16 + 15 + 15 = 97 horas

b) Una solución puede ser:

60 22 29 42 30 
22 52 16 32 18 

34 16 58 28 25
 
42 32 28 46 15 
30 18 22 15 45
 
60 48 55 30 42 

Tiempo total de procesamiento = 22 + 16 + 22 + 30 + 15 = 105 horas

8) Gerald Glynn administra el Michaels Distruibution Center. Después de examinar cuidadosamente la información de su
base de datos, ha determinado los requisitos diarios para el personal de tiempo parcial que atiende la plataforma de carga. El
centro de distribución funciona los siete días a la semana, y los requisitos diarios de personal de tiempo parcial son los
siguientes:

Día L M M J V S D
Requisitos 6 3 5 3 7 2 3

a) Encuentre el número mínimo de trabajadores que Glynn necesita contratar. Prepare un programa de trabajo para esos
individuos, de manera que cada uno disponga de dos días libres consecutivos por semana y que todos los requisitos de
personal sean satisfechos. En caso de empate, conceda preferencia a la pareja S-D.
b) Plantee el problema anterior como un problema P.L., sin la consideración del requisito de empate.
Solución:
a)

Número mínimo de trabajadores:

Luego, el número mínimo de trabajadores que se necesitan contratar es 7.

Programa de Trabajo:

Trabajador L M W J V S D
1 X X X X X Libre Libre
2 X X X X X Libre Libre
3 X Libre Libre X X X X
4 X X X X X Libre Libre
5 X X Libre Libre X X X
6 X X X X X Libre Libre
7 Libre Libre X X X X X
Disponible 6 5 5 6 7 3 3
Demanda 6 3 5 3 7 2 3
Holgura 0 2 0 3 0 1 0

Holgura Total = 8

b) Sabiendo que, para nuestro caso, el número mínimo de trabajadores es 7 (equivalente al requisito de personal máximo),
comenzamos probando el modelo con un valor de n = 7, luego 8, 9 y así sucesivamente, hasta el primer n en que se
obtenga una solución factible. Ese valor de n es el número mínimo de trabajadores que se necesitan contratar.
De esta manera tenemos:

Variables:

1 si el trabajador i trabaja el día j

Xi j =  i = 1,2, …,n j = 1,2, …,7
0 si el trabajador i está libre el día j
Parámetros:

Rj = Requisitos diarios de personal durante el día j (j = 1,2, …,7)

Modelo:

7
 n  
min H Total =    X ij  − R j 
j =1  i =1  

Sujeto a:

n
i) X
i =1
ij  Rj  j = 1,2,...,7

7
ii) X
j =1
ij =5  i = 1,2,..., n

 6 
iii)   X i , j − X i , j +1  + X i , 7 − X i ,1 = 2  i = 1,2,..., n
 
 j =1 

Otra forma de expresar esta restricción, de manera no lineal es:

 (X  X i , j +1 ) + X i ,1  X i ,7 = 4
6

i, j  i = 1,2,..., n
j =1

Con n7

9) La regla de Jonson se puede utilizar para minimizar el tiempo de procesamiento para colocar en secuencia un grupo de
trabajos a través de dos instalaciones o máquinas. También minimiza el tiempo ocioso total en las máquinas. Explique el
porqué.

Solución:

La idea de la regla de Jonson es hacer que unas cuantas tareas pasen por el procesador 1 con rapidez (trabajos de
menor tiempo) para dar al procesador 2 para que tenga algo que hacer (disminuir ocio del procesador 2). Al final del
programa el propósito es que queden tareas que requieran poco tiempo para los últimos procesadores de modo que una vez
que este completo el procesador 1, el ultimo procesador pueda terminar rápidamente.
10) Cuando se programan n tareas en un solo procesador, el tiempo medio del flujo se minimiza secuenciando primero la
tarea con el tiempo más corto de procesamiento, o sea t1 ≤ t2≤ …≤ tn.
Demuestre que cuando se programan n tareas en un sólo procesador, la demora media se minimiza por la secuencia de t 1 ≤
t2 ≤ ... ≤ tn.

Nota: Si se supone que todas las tareas están disponibles cuando se inicia el programa, el tiempo de flujo de cada tarea es
igual a su tiempo de terminación (Fi,s = Ci,s)

Solución:

Supongamos que el programa S’, una secuencia que no es SPT, minimiza el tiempo medio de flujo. Entonces debe
existir un par de trabajos en S’, digamos i y j, tales que j está programado inmediatamente antes de i, y tj > ti. Ahora
consideremos el programa S, que es el mismo que S’ excepto que los trabajos i y j se intercambiaron, de manera que i está
programado inmediatamente antes de j. Las tareas anteriores a i y j se definen dentro del conjunto A y las posteriores
pertenecen al conjunto B, los cuales están en la misma posición en los dos programas. Las dos secuencias se pueden ver en la
figura a continuación. Obsérvese que las tareas en los conjuntos A y B se inician y completan en los mismos tiempos en
ambas secuencias; por tanto, sus tiempos de flujo son los mismos. La única diferencia en los tiempos de flujo de las dos
secuencias se presenta en las tareas i y j.

El tiempo medio de flujo para cada secuencia está dado por:

1    
FS =   Fk , S  + Fi , S + F j , S +   Fk ,S 
n   k en A    k en B 
1    
=   Fk , S  + (t A + ti ) + (t A + ti + t j ) +   Fk , S 
n   k en A    k en B 
1    
F S' =   Fk , S '  + F j , S ' + Fi , S ' +   Fk , S ' 
n   k en A    k en B 
1    
=   Fk , S '  + (t A + t j ) + (t A + t j + t i ) +   Fk , S ' 
n   k en A    k en B 
Sustrayendo el flujo medio de S’ del de S se obtiene:

F S − F S' =
1
n
 
ti − t j  0

Esto implica que el tiempo medio de flujo de S es menor que el de S’, lo que contradice la suposición de que S’ es
óptimo. Este mismo intercambio de dos a dos de tareas adyacentes se puede repetir siempre que el cambio coloque la tarea
más corta adelante de la más larga y que cada intercambio reduzca el tiempo medio de flujo. Estas mejoras se pueden hacer
hasta que t[1]  t[2]  …  t[n], lo cual representa el tiempo medio mínimo de flujo. Por lo tanto, un programa óptimo debe estar
en el orden SPT.

11) Si se tiene un sistema constituido por 2 máquinas A y B, ¿cuál sería el orden de procesamiento de los siguientes
conjuntos de tareas {a}, {b}, {ab} y {ba}? Fundamente su respuesta.

Solución:

Los trabajos en {ab} deben programarse antes en la máquina A que los trabajos en {ba}, porque no se quiere que la
máquina A esté ociosa mientras espera que termine la primera operación de un trabajo {ba} en la máquina B antes de poder
procesarlo en la máquina A. Por el mismo argumento, se quiere programar, en la máquina A, todos los trabajos de {a} antes
que los trabajos {ba}. Por otro lado, ningún trabajo de {a} debe ir antes que los trabajos {ab} en la máquina A, ya que podría
retrasar el proceso de un trabajo {ab} en la máquina B. Esto implica un orden de los conjuntos de trabajos en la máquina A:
{ab} {a} {ba}. De la misma manera, el orden en B debe ser {ba} {b} {ab}.

En cuanto al orden de los trabajos dentro de los conjuntos, si sólo se tuvieran trabajos {ab}, se podría usar el
algoritmo de Johnson para programarlos. También se podría usar para programar los trabajos en {ba}, pero con la máquina B
primero y la A después. El orden de los trabajos dentro de {a} y {b} no importa, de manera que el programa de lapso mínimo
para un taller de producción intermitente con 2 máquinas es:

• Máquina A: trabajos {ab} ordenados según el algoritmo de Johnson, después los trabajos {a} en cualquier orden,
seguidos de los {ba} en orden inverso al algoritmo de Johnson.
• Máquina B: trabajos {ba} en orden inverso de Johnson, trabajos {b} en cualquier orden y trabajos {ab} en el orden
de Johnson.

INDUSTRIA VIRTUAL 2020 21