Ejecución avanzada 2

Materia: Sistemas de Producción Industrial - Grado en Ingeniería Química USC

Profesora: Pastora M. Bello Bugallo 1

Anexo I – Tema 3

PROGRAMACIÓN DE OPERACIONES

A. Características de los problemas de programación en talleres

1.  El patrón de llegada de los trabajos 2.  Número y variedad de las máquinas en el taller 3.  Número de trabajadores en el taller 4.  Patrones específicos de flujo 5.  Evaluación de las reglas alternas

18/11/13 Sistemas de Producción Industrial - Profa. Pastora M. Bello Bugallo

2



Objetivos de la administración de trabajo en un taller

1.  Cumplir con las fechas de entrega. 2.  Minimizar el inventario del trabajo en proceso (WIP) 3.  Minimizar el tiempo promedio del flujo a través del sistema 4.  Suministrar un elevado tiempo de uso de máquina/trabajador

(minimizar el tiempo muerto de máquina/trabajador.) 5.  Suministrar información exacta del estado de los trabajos. 6.  Reducir los tiempos de preparación. 7.  Minimizar los costes de producción y de los trabajadores.

¡ALGUNOS DE ESTOS OBJETIVOS ENTRAN EN CONFLICTO!


3

Objetivos de la administración de trabajo en un taller

Ejemplo: sistema simple compuesto por dos operaciones en serie

Si hay un inventario de amortiguamiento colocado entre las operaciones, 2 puede continuar operando mientras por ejemplo 1 se somete a una reparación o calibración: encontrar la combinación apropiada de WIP y el tiempo muerto del trabajador equivale a seleccionar un punto en la curva de intercambios de estos objetivos conflictivos.

Insumo Amortiguador Producto (WIP)

1 2


4



B. Terminología de la programación de trabajos por taller

Problema: los n trabajos deben procesarse a través de m máquinas. La complejidad del problema depende de varios factores como las secuencias de trabajo permisibles y qué criterios de optimización se seleccionan.


5

Terminología Taller de flujo o línea de montaje/ensamble: cada uno de los n trabajos debe procesarse a través de las m máquinas en el mismo orden, y cada trabajo se procesa exactamente una vez en cada máquina. Taller: difiere de un taller de flujo, en que no se considera que todos los trabajos necesiten exactamente m operaciones, y algunos trabajos pueden requerir operaciones múltiples en una sola máquina. Procesamiento paralelo: las m máquinas son diferentes, y estas realizan varias operaciones diferentes Procesamiento secuencial: se supone que las máquinas son idénticas y cualquier trabajo puede ser procesado en cualquier máquina. Tiempo de flujo: el tiempo de flujo del trabajo i es el que transcurre desde el inicio del primer trabajo en la primera máquina hasta la terminación del trabajo i. Es el tiempo que el trabajo i reside en el sistema. Tiempo de flujo medio: medida común del rendimiento de un sistema, es el promedio aritmético de los tiempos de flujo para los n trabajos. Terminación: es el tiempo de flujo del último trabajo terminado. Es también el tiempo requerido para terminar los n trabajos. Retardo: diferencia positiva entre el tiempo de terminación (tiempo de flujo) y la fecha de vencimiento de un trabajo. Un trabajo retardado es el que termina después de su fecha de vencimiento. Retraso: diferencia entre el tiempo de terminación del trabajo y su fecha de vencimiento, puede ser positivo o negativo. La minimización del retardo promedio y del retardo máximo es también un objetivo común de la programación


6



C. Una comparación de reglas de secuencia específica

Se considera el taller en un instante fijo en el tiempo y una sola máquina.

Supóngase que existe un grupo de trabajos que deben

procesarse en ésta y que cada trabajo tiene asociado un tiempo de procesado y una fecha de vencimiento.

Se compararán el desempeño de cuatro reglas de

secuenciación.


7

Reglas de secuenciación 1.  Primeras llegadas, primeras salidas (FCFS: First-Come, First-Send).

Los trabajos se procesan en el orden que entran al taller.

2.  Tiempo de procesado más corto primero (SPT: Shortest Processing time). Los trabajos se ordenan de manera ascendente correspondiendo con los tiempos de procesado.

3.  Primera fecha de entrega (EDD: Earliest Due Date). Los trabajos se ordenan de manera ascendente de acuerdo con sus fechas de vencimiento.

4.  Programación basada en la razón crítica (CR: Critical Ratio). Se calcula la relación del tiempo de procesado del trabajo y el tiempo restante hasta la fecha de vencimiento, y se programa el trabajo con la siguiente relación más grande.


8



Ejemplo 1 Un centro de mecanizado en un taller donde se realizan trabajos para una compañía local de fabricación tiene cinco trabajos no procesados que se quedan pendientes para un instante específico en el tiempo. Los trabajos están etiquetados como 1, 2, 3, 4, y 5 en el orden de ingreso al taller. Los tiempos de procesado y las fechas de entrega respectivas se muestran a continuación

Nº de trabajo Tiempo de procesado Fecha de entrega 1 11 61

2 29 45

3 31 31

4 1 33

5 2 32


9

C1. Primeras llegadas, primeras salidas (FCFS)

Nº de trabajo Tiempo de terminación Fecha de entrega Retardo

1 11 61 0 2 40 45 0 3 71 31 40 4 72 33 39 5 74 32 42

Totales 268 121 Tiempo de flujo medio = 268/5 = 53.6

Retardo promedio = 121/5 = 24.2 Nº de trabajos retardados = 3

El retardo de un trabajo es igual a cero si el trabajo se termina antes de su fecha de entrega y es igual al nº de días de retraso si el trabajo se termina después de su fecha de entrega 18/11/13 Sistemas de Producción Industrial - Profa.

Pastora M. Bello Bugallo 10



C2. Tiempo de procesado más corto primero (SPT)

Trabajo Tiempo de procesado Tiempo de terminación Fecha de entrega Retardo

4 1 1 33 0 5 2 3 32 0 1 11 14 61 0 2 29 43 45 0 3 31 74 31 43

Totales 135 43

Tiempo de flujo medio = 135/5 = 27.0 Retardo promedio = 43/5 = 8.6 Nº de trabajos retardados = 1

18/11/13 Sistemas de Producción Industrial - Profa.


C3. Primera fecha de entrega (EDD)


Trabajo Tiempo de procesado Tiempo de terminación Fecha de entrega Retardo

3 31 31 31 0 5 2 33 32 1 4 1 34 33 1 2 29 63 45 18 1 11 74 61 13

Totales 235 33


12



C4. Programación basada en la razón crítica (CR) Tiempo presente: t = 0 Trabajo Tiempo de

procesado Fecha de entrega

RC

1 11 61 61/11 (5.545) 2 29 45 45/29 (1.552) 3 31 31 31/31 (1.000) 4 1 33 33/1 (33.00) 5 2 32 32/2 (16.00

Tiempo presente: t = 31 Trabajo Tiempo de

procesado Fecha de entrega

– tiempo

presente

RC

1 11 30 30/11 (2.727) 2 29 14 14/29 (0.483)

4 1 2 2/1 (2.000) 5 2 1 1/2 (0.500

Valor mínimo de RC

Tiempo presente: t = 60 Trabajo Tiempo de

procesado Fecha de entrega – t presente

RC

1 11 1 1/11 (0.909)

4 1 -27 -27/1 (<0) 5 2 -28 -28/2 (<0)

Trabajos retardados: ¡prioridad!

31 + 29


13


Trabajo Tiempo de procesado Tiempo de terminación Retardo

3 31 31 0 2 29 60 15 4 1 61 28 5 2 63 31 1 11 74 13

Totales 289 87

C4. Programación basada en la razón crítica (CR)


14



Resumen de los resultados de cuatro reglas de programación

Regla Tiempo de flujo medio Retardo promedio Nº trabajos retardados

FCFS 53.6 24.2 3 SPT 27.0 8.6 1 EDD 47.0 6.6 4 CR 57.8 17.4 4

Ejemplo 1


15

D. Objetivos de la administración de trabajo en taller: ejemplo 2

Un controlador de tráfico aéreo se enfrenta al problema de programar el aterrizaje de cinco aeronaves. Basándose en la posición y en los requerimientos de pista de cada aeroplano, estima los siguientes tiempos de aterrizaje: Aeroplano 1 2 3 4 5 Tiempo (min) 26 11 19 16 23 Sólo puede aterrizar un avión a la vez. El problema es esencialmente el mismo que el de programar 5 trabajos para una sola máquina. Los aeroplanos corresponden a los trabajos, los tiempos de aterrizaje a los tiempos de procesado, y la pista a la máquina.


16




1. Objetivos razonables: •  Minimizar el tiempo total requerido, es decir, la terminación. La terminación de cualquier secuencia es 95 min (suma de tiempos de aterrizaje) •  Minimizar el tiempo promedio requerido, es decir, el tiempo de flujo medio. No es independiente de la secuencia y la regla del tiempo de procesado más corto minimiza el tiempo de flujo medio. 2. Objetivo alternativo: aterrizar la mayor cantidad de gente tan rápido como sea posible. Supónganse estos números: Aeroplano 1 2 3 4 5 Tiempo (min) 26 11 19 16 23 Nº pasajeros 180 12 45 75 252 Objetivo adecuado: minimizar la terminación ponderada o la suma ponderada de los tiempos de terminación, donde los pesos corresponderían al número de pasajeros en cada aeroplano. La función objetivo tendría unidades de pasajero-minutos. 18/11/13 Sistemas de Producción Industrial - Profa.



3. Otro aspecto a tratar es el tiempo de programación de la llegada de cada aeroplano. Supóngase: Aeroplano 1 2 3 4 5 Tiempo de aterrizaje (min) 26 11 19 16 23 Hora programada de llegada 5:30 5:45 5:15 6:00 5:40 Las reglas de secuenciación que ignoran las fechas de entrega dan resultados muy pobres en cuanto a satisfacer horas de llegada. Objetivos relacionados con las fechas de entrega: minimización del retardo promedio y del retardo máximo. 4. Hay que tener en cuenta las condiciones especiales que favorecen a un aeroplano sobre otro. Supóngase que el aeroplano 4 tiene un nivel de combustible críticamente bajo. Esto conduciría a que tomase la precedencia. También podrían surgir restricciones de prioridad de otras formas: dar prioridad a los aeroplanos que están programados para continuar los vuelos o los que transportan cargas valiosas o perecederas. 18/11/13 Sistemas de Producción Industrial - Profa.




D. Objetivos de la administración de trabajo en taller

ES DIFÍCIL SELECCIONAR UNA FUNCIÓN OBJETIVO PARA LOS PROBLEMAS DE SECUENCIACIÓN DE

TRABAJOS La secuencia óptima es altamente sensible a la selección del

objetivo El objetivo apropiado no siempre es obvio


19

Problemas 1.  Discútanse los siguientes objetivos y la relación que tiene

cada uno con el desempeño de un taller: a)  Reducir el inventario WIP b)  Suministrar un alto nivel de servicio al cliente. c)  Reducir el tiempo muerto del trabajador. d)  Mejorar el rendimiento de la fábrica.


20



Problemas 2.  En el problema 1, ¿por qué a y c son objetivos

conflictivos, y por qué b y d también?


21

Problemas

3.  Defínanse los siguiente términos: a)  Taller de flujo. b)  Taller. c)  Procesado secuencial vs. Procesado paralelo. d)  Terminación. e)  Retardo.


22



Problemas 4.  Cuatro camiones, 1, 2, 3, y 4, están esperando en una rampa

de carga en la compañía XYZ que sólo tiene una crujía de servicio. Los camiones están rotulados en el orden de llegada a la rampa. Supóngase que la hora presente es 1:00 p.m. En la tabla siguiente se indican los tiempos de descarga requeridos para cada camión y los tiempos de entrega del material en la planta.

Determínese el programa para cada una de las reglas FCFS, SPT, EDD, y CR. En cada caso calcúlese el tiempo de flujo medio, el retardo promedio y el número de trabajos retardados.

Camión Tiempo de descarga (min) Hora de entrega del material 1 20 1:25 p.m.

2 14 1:45 p.m.

3 35 1:50 p.m.

4 10 1:30 p.m.


23

Problemas 5.  Deben programarse 5 trabajos para el procesado por lotes en un

sistema de ordenador central (mainframe). Los tiempos de procesado y la hora prometida para cada uno de los trabajos son los siguientes:

Trabajo 1 2 3 4 5 Tiempo de procesado 40 min 2.5 h 20 min 4 h 1.5 h Hora prometida 11:00am 2:00pm 2:00pm 1:00pm 4:00pm Supóngase que la hora presente es 10:00 a.m. a)  Si los trabajos están programados de acuerdo con SPT, encuéntrese el

retardo de cada trabajo y el retardo promedio de todos los trabajos. b)  Repítase el cálculo del apartado a) para la programación EDD.


24



E. Una introducción a la teoría de secuenciación para una sola máquina

n= número de trabajos que van a procesarse en una misma máquina.Para cada trabajo i:ti = tiempo de procesado para el trabajo idi = fecha de entrega del trabajo i

!"#

ctes incorporadas a la descripción de cada trabajo

Wi = tiempo de espera para el trabajo i (antes de comenzar su procesado). Para los casos queconsideramos es también la suma de los tiempos de procesado de todos los trabajos anterioresFi =Wi +ti (tiempo de flujo para el trabajo i=tiempo de terminación del trabajo i)Li = Fi +di (retraso del trabajo i, valor positivo o negativo)Ti = máx Li,0[ ] (retardo del trabajo i, parte positiva del retraso)

Ei = máx -Li,0[ ] (anticipación del trabajo i, parte negativa del retraso)

Tmáx =máx T1,T2,...,{ Tn} (retardo máximo)

F'= 1n

Fi1

n

$ (tiempo de flujo medio)

Cada calendario para una sola máquina puede representarse por una permutación de losenteros 1,2,...,n.Hay exactamente n! calendarios diferentes


25

Programación del tiempo de procesamiento más corto

Teorema La regla de programación que minimiza el tiempo de flujo medio F’ es SPT Demostración Corolario Las siguientes medidas son equivalentes: 1. Tiempo de flujo medio. 2. Tiempo de espera medio. 3.  Retraso medio.

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


26



Programación de la primera fecha de entrega

Si el objetivo es minimizar el retraso máximo, los trabajos deben ordenarse de acuerdo con sus fechas de entrega.

Seleccionar algún programa que no ordene los trabajos en relación con sus fechas de entrega; eso implica que existe un valor de k tal que

Se demuestra que al intercambiar las posiciones de los trabajos k y k+1, se reduce el retraso máximo

d 1[ ]!d 2[ ]!...!d n[ ]

d k[ ]>d k+1[ ]


27

Minimización del número de trabajos retrasados

Algoritmo de Moore (1968): minimiza el número de trabajos retardados para el problema de una sola máquina: Paso 1. Ordénense los trabajos de acuerdo con la fecha de la primera entrega para obtener la solución inicial Paso 2. Encuéntrese el primer trabajo retardado en la secuencia presente, el trabajo [i]. Si no existe ninguno, vaya al paso 4. Paso 3. Considérense los trabajos [1], [2],…, [i]. Rechácese el trabajo con el mayor tiempo de procesado. Regrésese al paso 2. Paso 4. Fórmese 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.

d 1[ ]!d 2[ ]!...!d n[ ]


28



Ejemplo 3 Un taller de máquinas procesa las órdenes a medida de varios clientes. Una de las máquinas, una esmeriladora, tiene seis trabajos en espera de ser ejecutado. A continuación se indican los tiempos de procesado y las fechas comprometidas de entrega (ambos en horas) para los seis trabajos.

Trabajo 1 2 3 4 5 6

Fecha de entrega 15 6 9 23 20 30

Tiempo de procesado 10 3 4 8 10 6


29

Ejemplo 3 Paso 1. Ordenar los trabajos de acuerdo con la regla EDD Paso 2. Encuentre el primer trabajo retardado en la secuencia presente Paso 3. Rechace el trabajo con el mayor tiempo de procesado. Regrese al paso 2 Paso 4. secuencia presente (2,3,4,6) y adjunte los rechazados

Trabajo 2 3 1 5 4 6 Fecha de entrega 6 9 15 20 23 30

Tiempo de procesado 3 4 10 10 8 6

Tiempo de terminación 3 7 17 27 35 41

Fecha de entrega – tiempo de terminación 3 2 -2 -7 -12 -11

Primer trabajo retardado

Trabajo 2 3 5 4 6 Fecha de entrega 6 9 20 23 30

Tiempo de procesado 3 4 10 8 6

Tiempo de terminación 3 7 27 35 41 Mayor tiempo de procesado

Trabajo 2 3 4 6 Fecha de entrega 6 9 23 30

Tiempo de procesado 3 4 8 6

Tiempo de terminación 3 7 15 21

Fecha de entrega-t terminación 3 2 8 9

Secuencia óptima: 2, 3, 4, 6, 5, 1

Ningún trabajo retardado


30



Restricciones de precedentes: algoritmo de Lawler

Se presentan restricciones de precedencia cuando ciertos trabajos deben terminarse antes de que otros puedan comenzar Ejemplos:

Función objetivo: mín máx1!i!n

gi (Fi )

donde gi es cualquier función no decreciente del tiempo de flujo Fi

gi(Fi )=Fi-di =Li

que corresponde a minimizar el retraso máximo, o seagi(Fi )=máx (Fi-di, 0) que equivle a la minimización del retraso máximo


31

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. Denomínese a este conjunto V. Entre el conjunto V, selecciónese el trabajo k que satisfaga Ahora el trabajo k se programa como el último. Considérense los trabajos restantes y determínense nuevamente el conjunto de trabajos que no se requiere que precedan a ningún otro trabajo restante. Una vez programado el trabajo k, este conjunto pudo haber cambiado. El valor de τ se reduce por tk y ahora se determina el trabajo programado antes del último. El proceso continúa hasta programar todos los trabajos.

gk (! )=míni!V

gi (! )( )

donde ! = tii=1

n" y corresponde al tiempo de procesamiento de la secuencia presente


32



Ejemplo 4 Encarna dirige un taller local que hace trabajos de chapa y pintura. Cierta mañana de lunes tiene 6 automóviles en espera de ser reparados. Tres de ellos (1, 2 y 3) son de una compañía de alquiler de automóviles y ella está de acuerdo en terminar estos automóviles en el orden de las fechas en que comprometidas. Los automóviles 4, 5 y 6 son de un distribuidor minorista que ha solicitado que el automóvil 4 se termine primero porque lo está esperando un cliente. Los tiempos requeridos para reparar cada uno de los automóviles (en días) y las fechas de terminación comprometidas asociadas son: Determínese cómo debe programarse La reparación de los automóviles en el Taller con objeto de minimizar el retardo máximo.

Trabajo 1 2 3 4 5 6 Tiempo de procesado 2 3 4 3 2 1



33

Ejemplo 4 Las restricciones de precedencia resultantes pueden representarse como dos redes inconexas, como se muestra en la figura.

Trabajo 1 2 3 4 5 6 Tiempo de procesado 2 3 4 3 2 1


1 2 3

4

5

6


34



Problemas 6.  Considérese la información del problema 4. Determínese la

secuencia de la descarga de los camiones para minimizar: a)  El tiempo de flujo medio. b)  El retraso máximo. c)  El número de trabajos retardados.


35

Problemas 7.  El 1 de diciembre, Álvaro, estudiante de Ingeniería,

repentinamente se da cuenta de que no ha hecho nada de las tareas y trabajos que le han pedido en 7 materias, y el plazo de entrega está a punto de vencer. Estima que el tiempo requerido para terminar cada trabajo (en días) y también anota sus fechas de entrega:

Como los trabajos 1, 3 y 5 son de la misma materia, decide hacerlos

en la secuencia en que vencen. El trabajo 7 requiere resultados de los trabajos 2 y 3, de modo que debe hacerlo después de terminar 2 y 3. Determínese la secuencia en la que debe realizar los trabajos con objeto de minimizar el retardo máximo

Trabajo 1 2 3 4 5 6 7 Tiempo de procesado 4 8 10 4 3 7 14

Fecha de entrega 4/20 5/17 5/28 5/28 5/12 5/7 5/15


36



Problemas 8.  Deben procesarse 8 trabajos en una sola máquina. Los tiempos

de procesado y la fechas de vencimiento son las siguientes:

Además, supóngase que deben satisfacerse las siguientes relaciones

de precedencia: 2è6è3 1è4è7è8

Determínese la secuencia en que estos trabajos deben realizarse para minimizar el retardo máximo sujeto a las restricciones de precedencia.

Trabajo 1 2 3 4 5 6 7 8 Tiempo de procesado 2 3 2 1 4 3 2 2

Fecha de vencimiento 5 4 13 6 12 10 15 19


37

Problemas 9.  Agustín hornea panes y pasteles en su casa y los vende para

fiestas y otras celebraciones. AB tiene solo un horno. Un lunes por la mañana se da cuenta de que se comprometió a terminar cinco pedidos para ese día. Su hermano Jose hace las entregas; y en cada una tarda aproximadamente 15 minutos. Supóngase que Agustín comienza a hornear a las 8:00 a.m.

Determínese la secuencia en que Agustín debe desempeñar los

trabajos con objeto de minimizar: a)  El tiempo de flujo medio. b)  El número de trabajos retardados. c)  E retraso máximo.

Trabajo Tiempo requerido Hora prometida 1 1.2 h 11:30 a.m.

2 40 min 10:00 a.m.

3 2.2 h 11:00 a.m.

4 30 min 1:00 p.m.

5 3.1 h 12:00 h

6 25 min 2:00 p.m.


38



Problemas 10.  En una sola máquina deben realizarse siete trabajos. Los tiempos

de procesado y las fechas de vencimiento se indican a continuación:

Determínese la secuencia de los trabajos con objeto de minimizar: a)  El tiempo de flujo medio. b)  El número de trabajos retardados. c)  El retraso máximo. d)  ¿Cuál es la terminación de cualquier secuencia?

Trabajo 1 2 3 4 5 6 7 Tiempo de procesado 3 6 8 4 2 1 7

Fecha de vencimiento 4 8 12 15 11 25 21


39

F. Algoritmos de secuencia para máquinas múltiples

N trabajos deben procesarse en m máquinas: • n! Ordenaciones diferentes de los trabajos • (n!)m horarios posibles, si los trabajos pueden procesarse en las máquinas en cualquier orden

¡PRÁCTICAMENTE IMPOSIBLE ENUMERAR TODOS LOS HORARIOS POSIBLES!


40



F.1 Gráfica de Gantt Una manera conveniente de representar un horario Suponga dos trabajos, I y J, que deben programarse en dos máquinas 1 y 2. Los tiempos de procesado son:

Trabajo Máquina 1 Máquina 2 I 4 1

J 1 4

I J I J

Máquina 1

Máquina 2

4 5 9

Supóngase que ambos trabajos deben procesarse primero en la máquina 1 y luego en la máquina 2. Los horarios posibles pueden representarse gráficas de Gantt. Uno de los horarios posibles se indica a continuación. • Dibuje las gráficas de Gantt para el resto de los horarios posibles.

• Calcule para cada horario los parámetros siguientes:

(Terminación/tiempo de flujo total) (Tiempo de flujo medio) (Tiempo muerto)


41



J 1 4

I J I J

J I J I

I J J I

J I I J

Máquina 1

Máquina 2

4 5 9

Supóngase que ambos trabajos deben procesarse primero en la máquina 1 y luego en la máquina 2. Los horarios posibles aparecen en cuatro gráficas de Gantt siguientes

Máquina 1

Máquina 2

1 5 6

Máquina 1

Máquina 2

1 5 6 10 Máquina 1

Máquina 2

4 5 9 10 18/11/13 Sistemas de Producción Industrial - Profa.






J 1 4

I J I J

J I J I

I J J I

J I I J

Máquina 1

Máquina 2

4 5 9

Supóngase que ambos trabajos deben procesarse primero en la máquina 1 y luego en la máquina 2. Los horarios posibles aparecen en cuatro gráficas de Gantt siguientes

Máquina 1

Máquina 2

1 5 6

Máquina 1

Máquina 2

1 5 6 10 Máquina 1

Máquina 2

4 5 9 10

(Terminación/tiempo de flujo total) (Tiempo de flujo medio) (Tiempo muerto)

(5+9)/2=7 (5+6)/2=5.5 (5+10)/2=7.5 (5+10)/2=7.5

(4+4)/2=4 (1+1)/2=1 (5+5)/2=5 (5+5)/2=5

18/11/13 Sistemas de Producción Industrial - Profa.

Pastora M. Bello Bugallo

43

F.2 Programación de n trabajos en 2 máquinas

Supóngase: • n trabajos deben procesarse a través de 2 máquinas • cada trabajo debe procesarse en el orden máquina 1 y luego máquina 2 • criterio de optimización: minimizar la terminación Teorema: La solución óptima para programar n trabajos en dos máquinas siempre es un horario de permutación (número total de horarios de permutación = n!, la determinación de horarios óptimos para dos máquinas tiene aproximadamente el mismo grado de dificultad que para m máquinas)


44



F.2 Programación de n trabajos en 2 máquinas Algoritmo para la solución del problema de 2 máquinas (Jonhson, 1954)

2 máquinas: A y B Los trabajos deben procesarse primero en A y luego en B i =trabajos Ai = Tiempo de procesado del trabajo i en la máquina A Bi = Tiempo de procesado del trabajo i en la máquina B

Regla (óptima para establecer orden de procesado de trabajos en 2 máquinas):

el trabajo i precede al trabajo i+1 si mín (Ai, Bi+1) < mín (Ai+1, Bi) Implementación: 1. Listar los valores Ai y Bi en dos columnas.

2. Encontrar el elemento restante más pequeño en las dos columnas. Si aparece en la columna A, programar ese trabajo como el siguiente. Si aparece en la columna B, programar ese trabajo como el último.

3. Entrecruzar los trabajos tal como están programados. Detenerse cuando todos los trabajos hayan sido programados.


45

Ejemplo 5 Van a programarse 5 trabajos en dos máquinas. Los tiempos de procesado son:

Trabajo 1 2 3 4 5 Máquina A 5 1 9 3 10

Máquina B 2 6 7 8 4

1. Listar los valores Ai y Bi en dos columnas.

2. Encontrar el elemento restante más pequeño en las dos columnas. Si aparece en la columna A, programar ese trabajo como el siguiente. Si aparece en la columna B, programar ese trabajo como el último.

3. Entrecruzar los trabajos tal como están programados. Detenerse cuando todos los trabajos hayan sido programados.


46



Ejemplo 5 1. Listar los valores Ai y Bi en dos columnas.

2. Identificar el tiempo mínimo para el trabajo: 1 para el trabajo 2 en la máquina 1

3. El siguiente t procesado menor es 2 para el trabajo 1 en la máquina B

4. El siguiente t procesado menor es 3 para el trabajo 4 en la máquina A

5. El siguiente t procesado menor es 4 para el trabajo 5 en la máquina B

Trabajo Máquina A Máquina B 1 5 2

2 1 6

3 9 7

4 3 8

5 10 4 El trabajo 2 se programa primero (aparece en la columna A) Se cancela la fila 2 Trabajo Máquina A Máquina B

1 5 2 3 9 7

4 3 8

5 10 4

El trabajo 1 se programa de último (aparece en la columna B) Se cancela la fila 1


4 3 8

5 10 4

El trabajo 4 se programa de segundo (aparece en la columna A) Se cancela la fila 4

El trabajo 5 se programa de penúltimo (aparece en la columna B) Se cancela la fila 5 y se establece la secuencia final


5 10 4

2-4-3-5-1 18/11/13 Sistemas de Producción Industrial - Profa.


Ejemplo 5 Diagrama de Gantt para el horario óptimo

Entrecruce los trabajos tal como están programados

2-4-3-5-1

0 1 2 3 4 5 6 7 8 9 10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

A2

A4 A3 A5 A1

B2 B4 B3 B5 B1


48



F.3 Ampliación a 3 máquinas •  programar los trabajos: problema considerablemente más complejo •  Si se restringe la atención al tiempo de flujo total: un horario de

permutación es óptimo. •  Esto no es necesariamente cierto en el caso del tiempo de flujo

promedio El problema de las tras máquinas puede reducirse a (esencialmente) un

problema de dos máquinas si se satisface la siguiente condición: Mín Ai ≥ máx Bi o mín Ci ≥ máx Bi

De la siguiente manera: -  Defínase A’i = Ai + Bi y B’i = Bi + Ci

-  Resuelva el problema utilizando las reglas para dos máquinas, tratando A’i y B’i como los tiempos de procesado.

-  El horario de permutación resultante será el óptimo para el problema de las tres máquinas.


49

F.3 Ampliación a 3 máquinas

Si no se satisfacen las condiciones para reducir un problema de tres máquinas a un problema de 2 máquinas, generalmente este método va a dar resultados razonables, pero posiblemente por debajo del óptimo.

Siempre que el objetivo sea minimizar la terminación o tiempo de flujo total, un

horario de permutación será el óptimo para programar tres máquinas (no necesariamente cierto para el tiempo de flujo promedio)


50



Ejemplo 6 Considere los siguientes tiempos de trabajo para un problema de tres máquinas. Suponga que los trabajos se procesan en la secuencia A, B, C:

Trabajo Máquina A Máquina B Máquina C 1 4 5 8

2 9 6 10

3 8 2 6

4 6 3 7

5 5 4 11


51

Ejemplo 6 Considere los siguientes tiempos de trabajo para un problema de tres máquinas. Suponga que los trabajos se procesan en la secuencia A, B, C: 1. Se verifican las condiciones: mín Ai = 4; mín Bi = 2; mín Ci = 6

2. Se forman las dos columnas:

3. Se resuelve el problema usando el algoritmo de las dos máquinas y la solución óptima es: 1-4-5-2-3

Trabajo Máquina A Máquina B Máquina C 1 4 5 8

2 9 6 10

3 8 2 6

4 6 3 7

5 5 4 11

Trabajo Máquina A’ Máquina B’ 1 9 13

2 15 16

3 10 8

4 9 10

5 9 15


52



F.4 El problema del taller de flujo de dos trabajos •  Van a procesarse dos trabajos a través de m máquinas •  Cada trabajo debe ser procesado por las máquinas en un orden específico,

pero las secuencias de los dos trabajos no necesariamente son las mismas Procedimiento gráfico (Akers, 1956) 1.  Dibuje un sistema de coordenadas cartesianas con los tiempos de

procesado que corresponden al primer trabajo en el eje x y los tiempos de procesado del segundo trabajo en el eje y. En cada eje, marque los tiempos de operación en el orden de ejecución de las operaciones para ese trabajo.

2.  Forme bloques con las áreas que correspondan a cada máquina en la intersección de los intervalos marcados para esa máquina en los dos ejes.

3.  Determine una trayectoria desde el origen del extremo del bloque final que no intercepte a ninguno de los bloques y que minimice el movimiento vertical. El movimiento está permitido sólo en tres direcciones: horizontal, vertical y una diagonal de 45 grados. La trayectoria con la distancia vertical mínima indicará la solución óptima. Observe que esta será igual que la trayectoria con la distancia horizontal mínima.


53

Ejemplo 7 Una fábrica regional de manufacturas produce varios productos para el hogar. Uno de ellos es una lámpara de madera de mesa. Antes de empacarse, las lámparas deben lijarse, barnizarse y pulirse. Cada operación requiere una máquina diferente. En este momento hay dos fletes de dos modelos que esperan el procesado. Los tiempos que requieren las tres operaciones para cada uno de los dos fletes son:

Trabajo 1 Trabajo 2 Operación Tiempo Operación Tiempo

Lijado (A) 3 A 2

Barnizado (B) 4 B 5

Pulido (C) 5 C 3


54



Ejemplo 8 Los hermanos Jesús y Manuel suele pasar las mañanas leyendo el periódico que comparten. A Jesús le gusta leer primero la sección principal, seguida de la deportiva, luego las tiras cómicas y, finalmente, los anuncios clasificados. Manuel también empieza con la sección principal, pero luego va directamente a los anuncios clasificados, luego la sección deportiva y finalmente las tiras cómicas. Los tiempos requeridos (en décimas de una hora) para que cada quien lea las diferentes secciones son: El objetivo es determinar el orden de lectura de las secciones para que cada quien minimice el tiempo total que se requiere para terminar de leer el periódico. En este problema identificamos a Jesús como el trabajo 1 y a Manuel como el trabajo 2.

Jesús Manuel Secuencia Tiempo Secuencia Tiempo

Sección principal (A) 6 A 4

Deportes (B) 1 D 3

Tiras cómicas (C) 5 B 2

Anuncios clasificados (D) 4 C 5


55

Problemas 11.  Considere el ejemplo 6, que ilustra el uso del algoritmo de

Jonhson para tres máquinas. Liste todas las soluciones óptimas de este ejemplo.

12.  Supóngase que deben procesarse 12 trabajos a través de 6 máquinas. Si los trabajos pueden procesarse en cualquier orden, ¿cuántos horarios posibles diferentes hay? Si VD fuese a correr un programa de ordenador que pudiese evaluar 100 horarios por segundo ¿cuánto tiempo necesitaría el programa para evaluar los horarios factibles?


56



Problemas 13.  Dos estudiantes de derecho, Fernando y Antonio, están planeando

trabajar toda la noche para preparar su examen del día siguiente. Entre los dos tienen un conjunto de materiales sobre los 5 temas siguientes: contratos, juicios civiles por daños y perjuicios que no se originan en un incumplimiento de contrato, ley civil, ley corporativa y patentes. Con base a su experiencia anterior, estiman que necesitarán los siguientes tiempos en horas para cada conjunto de materiales:

Acuerdan que Antonio tendrá oportunidad de ver cada conjunto de notas antes que Fernando. Supóngase que comienzan a estudiar a la 8:00 pm. Determínense los tiempos exactos para que cada uno inicie y termine el estudio de cada materia con objeto de minimizar el tiempo total requerido para que ambos terminen de estudiar las 5 materias.

Contratos Juicios civiles por daños

Derecho civil Derecho corporativo

Patentes

Fernando 1.2 2.2 0.7 0.5 1.5

Antonio 1.8 0.8 3.1 1.1 2.3


57

Problemas 14.  Los siguientes 4 trabajos deben procesarse en un taller de flujo

con tres máquinas:

Encuéntrese la secuencia óptima de los trabajos con objeto de minimizar el tiempo total de ejecución. ¿Cuál es el tiempo total de ejecución para la solución óptima? Dibújese un diagrama de Gantt que ilustre la solución.

Trabajo Máquina A Máquina B Máquina C

1 4 2 6

2 2 3 7

3 6 5 6

4 3 4 8


58



Problemas 15.  Mónica y Colum son dos hermanas que actualmente van juntas a

la Universidad. Cada una requiere tutorías en cinco materias: historia, inglés matemáticas, ciencias y religión. Estiman que el tiempo en minutos que cada una requiere en la tutoría es:

Las hermanas piensan que los 5 tutores van a estar disponibles todo el día. A Mónica le gustaría visitar a los tutores en el orden de la tabla, y Colum preferiría verlos en el orden siguiente: matemáticas, religión, inglés, ciencias e historia. ¿En qué horario debe planear cada una de ellas ver a los tutores con el fin de minimizar el tiempo total para que ambas terminen las tutorías?

Máquina A’ Máquina B’ Matemáticas 40 20

Historia 15 30

Inglés 25 10

Ciencias 15 35

Religión 20 25


59

Problemas 16.  Deben procesarse dos trabajos a través de 4 máquinas en el mismo orden. Los

tiempos de procesado en la secuencia requerida son:

Determínese cómo deben programarse los 2 trabajos con objeto de minimizar el tiempo total de ejecución y dibuje el diagrama de Gantt que indique el horario óptimo.

Trabajo 1 Trabajo 2 Máquina Tiempo Máquina Tiempo

A 5 A 2

B 4 B 4

C 6 C 3

D 3 D 5


60



Problemas 17.  María está planificando ir al departamento de tránsito con el fin de renovar su

permiso de conducir. Su amigo, Nicolás, que la acompaña, quiere solicitar un nuevo permiso. En ambos casos hay 5 pasos requeridos:

(A)  hacerse una fotografía, (B)  hacer una verificación de la firma, (C)  pasar una examen escrito, (D)  pasar un examen visual, y (E)  pasar un examen práctico.

Para las renovaciones los pasos se ejecutan en el orden A, B, C, D, y E con tiempos promedio requeridos, respectivamente, de 0.2, 0.1, 0.3, 0.2, y 0.6 horas. En el caso de solicitudes nuevas, los pasos se ejecutan en la secuencia D, B, C, E, y A, con tiempos promedio requeridos de 0.3, 0.2, 0.7, 1.1, y 0.2 horas, respectivamente. María y Nicolás van en un día en que el departamento está más bien vacío ¿cómo deben planear su horario con objeto de minimizar el tiempo requerido para que ambos terminen los cinco pasos?


61

G. Programación estocástica: análisis estático

Máquina única Incertidumbre de los tiempos de procesamiento: en la práctica es posible y probable que no pueda predecirse el tiempo exacto de terminación de uno o más trabajos. Supóngase • N trabajos deben procesarse a través de una solo máquina • Los tiempos de trabajo t1, t2, …, tn, son variables aleatorias con funciones de distribución conocida. El objetivo es minimizar el tiempo de flujo ponderado promedio esperado: La solución óptima (Rothkopf, 1966) consiste en ordenar los trabajos de modo que el trabajo i preceda al trabajo i + 1 si:

Minimo E 1 uiFii=1

n

!"

#$

%

&' donde ui son los pesos y Fi es el tiempo de flujo

(promedio) del trabajo i

E ti( ) < E ti+1( )ui+1


62



G. Programación estocástica: análisis estático

Máquinas múltiples Hipótesis: la distribución de los tiempos de trabajo es exponencial Porque la distribución exponencial es la única que tiene la propiedad sin memoria (la probabilidad de que un trabajo se termine en el siguiente instante de tiempo es independiente del tiempo que ya transcurrió al procesar el trabajo) • Riguroso en el contexto de la programación. • En la mayoría de los talleres de trabajos, si los t procesado no pueden pronosticarse con exactitud, es poco probable que tengan distribución exponencial.


63

G. Programación estocástica: análisis estático Máquinas múltiples Supóngase: • n trabajos deben procesarse a través de dos máquinas paralelas idénticas. • Cada trabajo necesita ser procesado sólo una vez en cada una de las dos máquinas. • El objetivo es minimizar el tiempo esperado que transcurre desde el tiempo cero hasta que el último trabajo haya terminado su procesado: terminación esperada. • Los n trabajos tienen tiempos de procesado t1, t2, … , tn, que son variables aleatorias exponenciales con tasas µ1, µ2, …, µn. Por lo que el tiempo requerido para terminar el trabajo i, E(ti), es 1/µi

El procesamiento en paralelo es diferente del taller de flujo • Taller de flujo: los trabajos se procesan primero en la máquina 1 y luego en la máquina 2 • Paralelo: se necesita procesar los trabajos sólo en una máquina, y cualquier trabajo puede procesarse en cualquiera de las dos máquinas.

Supóngase que para t=0 la máquina 1 está ocupada con el trabajo anterior (0), y el tiempo de procesado restante del trabajo 0 es t0, que podría ser variable determinista o aleatoria. Los trabajos se programan como sigue: • Sea 1, 2, …, n • Se programa el trabajo 1 para la máquina vacante. • El trabajo 2 sigue, ya sea al trabajo 0 en la máquina 1, o bien al trabajo 1 en la máquina 2, dependiendo de cual termine primero. • Cada trabajo sucesivo se programa para la siguiente máquina disponible.


64



G. Programación estocástica: análisis estático Máquinas múltiples Sean T0≤T1≤…≤Tn los tiempos de terminación de los trabajos sucesivos. La terminación es el tiempo de conclusión del último trabajo, Tn El valor esperado de la terminación se minimiza usando la regla del primer tiempo de procesado esperado más largo (LEPT – Longest Expected Processing Time ) [Si consideramos el tiempo de flujo, el tiempo de procesamiento esperado más corto primero (SEPT -Shortest Expected Processing Time first)] (se opone a la regla SPT para una sola máquina)


65

G. Programación estocástica: análisis estático Máquinas múltiples Se muestra intuitivamente la optimalidad de LEPT para este problema de la siguiente forma: - Considerando el diagrama siguiente que proporciona una ejecución específica de los tiempos de procesado para una secuencia arbitraria de los trabajos:

- La variable aleatoria I es el tiempo muerto de la máquina que no procesa el último trabajo. - Nos gustaría hacer I tan pequeño como sea posible con objeto de minimizar la terminación esperada

Ya que I se minimiza al reducir el tiempo de procesado del último trabajo, programamos los trabajos en orden decreciente con respecto al tiempo de procesamiento esperado.

t0 … tn-1 I t1 … tn

Máquina 1

Máquina 2

T0 T1 Tn-1 Tn

Tn +Tn+1= tii=0

n

!

Tn =Tn-1-I

"

#$

%$

Tn +Tn -I= tii=0

n

! & 2Tn = tii=0

n

! +I Si Σti se fija independientemente de la secuencia de procesado, minimizar E(Tn) equivale a minimizar E(I)


66



G. Programación estocástica: análisis estático El caso del taller de flujo de dos máquinas ¿Existe una analogía estocástica con el algoritmo de Johnson para programar n trabajos en 2 máquina en una instalación de taller? (i.e., cada trabajo debe procesarse primero en la máquina 1 y luego en la 2) [El algoritmo de Johnson dice que el trabajo i precede al i+1 si mín(Ai,Bi+1)<mín(Ai+1,Bi) con el objeto de minimizar la terminación] Supongase que A1, A2, …, An y B1, B2, …, Bn son variables aleatorias exponenciales con tasas respectivas a1, a2, …, an y b1, b2, …, bn. Y queremos minimizar el valor esperado de la terminación. Como el mínimo de dos variables aleatorias exponenciales tiene una tasa igual a la suma de las tasas, se concluye que:

E mín Ai,Bi+1( )!" #$=1

ai+bi+1

E mín Ai+1,Bi( )!" #$=1

ai+1+bi

Por lo tanto, el algoritmo de Johnson se traduce en el caso estocástico a condición de que ai – bi ≥ ai+1 – bi+1, de modo que los trabajos deben programarse en el orden de valores decrecientes de la diferencia de las tasas.


67

Ejemplo 9 Considere el ejemplo 5 que se usa para ilustrar el algoritmo de Johnson, pero supongamos que los tiempos de los trabajos son variables aleatorias que tienen la distribución exponencial con tiempos medios dados en el ejemplo:



Tiempos de espera Tasas Trabajo A B A B

1 5 2 0.20 0.500 2 1 6 1.00 0.170 3 9 7 0.11 0.140 4 3 8 0.33 0.125 5 10 4 0.10 0.250


68



Ejemplo 9 Considere el ejemplo 5 que se usa para ilustrar el algoritmo de Johnson, pero supongamos que los tiempos de los trabajos son variables aleatorias que tienen la distribución exponencial con tiempos medios dados en el ejemplo:



Tiempos de espera Tasas Trabajo A B A B Diferencias

1 5 2 0.20 0.500 -0.30 2 1 6 1.00 0.170 0.83 3 9 7 0.11 0.140 -0.03 4 3 8 0.33 0.125 0.21 5 10 4 0.10 0.250 -0.15

La ordenación de los trabajos de acuerdo con los valores decrecientes de las diferencias de la columna final conduce a la secuencia 2-4-3-5-1, que es la misma que en el caso determinista usando el algoritmo de Johnson


69

Problemas 18.  Considérese el ejemplo 2 para determinar la secuencia óptima de aterrizaje

de los aeroplanos. Supóngase que los tiempos de aterrizaje son variables aleatorias con una deviación estándar igual a 1/3 de la media en cada caso:

a.  ¿Cuál debe ser la secuencia de aterrizaje de los aeroplanos con objeto de

minimizar el tiempo de flujo ponderado promedio que se espera, si los pesos que van a usarse son los recíprocos del número de pasajeros de cada aeroplano?

b.  Para la secuencia encontrada en la parte a ¿Cuál es la probabiidad de que todos los aeroplanos aterricen en menos de 100 min? ¿Supóngase que los tiempos de aterrizaje son variables aleatorias independientes con distribución normal ¿Cambiará su respuesta si los aeroplanos aterrizan en una secuencia diferente?


70



Problemas 19.  Un centro de computación tiene dos ordenadores idénticos para el proceso por

lotes. Éstos se utilizan como procesadores paralelos. El usuario estima los tiempos de trabajo, pero la experiencia ha mostrado que una distribución exponencial brinda una descripción exacta de los tiempos de trabajo reales. Supóngase que para un instante de tiempo hay 8 trabajos pendientes de procesarse con los siguientes tiempos de trabajo esperados (en minutos):

Trabajo 1 2 3 4 5 6 7 8 Tiempo esperado 4 8 1 50 1 30 20 6

a.  ¿Cuál debe ser la secuencia de procesado de los trabajos con objeto de minimizar el tiempo de terminación esperado de los 8 trabajos (i.e, la terminación)?

b.  Si se supone que el ordenador A está ocupado con un trabajo que tiene exactamente dos minutos de tiempo de procesado restante, y que el ordenador B está inactivo. Si los tiempos de trabajo son deterministas, muéstrense los tiempos de inicio y de terminación de cada trabajo en cada ordenador utilizando la secuencia obtenida en la parte A.


71

Problemas 20.  Seis barcos están atracados en una bahía esperando que los descarguen. Los

tiempos requeridos para descargarlos son variables aleatorias con medias respectivas de 0.6, 1.2, 2.5, 3.5, 0.4 y 1.8 horas. A los barcos se les da una ponderación prioritaria basada en el tonelaje. Los tonelajes respectivos son 12, 18, 9, 14, 4 y 10. ¿Cuál debe ser la secuencia en que se descarguen los barcos para minimizar el tiempo ponderado esperado?


72



Problemas 21.  Resuélvase el problema 13 suponiendo que los tiempos requeridos por

Fernando y Antonio son variables aleatorias con distribución exponencial de los tiempos esperados en el problema 13.


73

Problemas 22.  Cinco hermanas planean asistir a un acto social. Cada una de ellas requiere

hacerse un peinado y un probarse un vestido. Supóngase que los tiempos requeridos son variables aleatorias con distribución exponencial con tiempos medios para el probador de 0.6, 1.2, 1.5, 0.8 y 1.1 horas, respectivamente, y tiempos medios para el peinado de 0.8, 1.6, 1.0, 0.7 y 1.3 horas, respectivamente. Supóngase que las pruebas se hacen antes de los peinados y que se dispone solo de un estilista y una modista ¿Con qué secuencia deben programarse si se quiere minimizar el tiempo esperado total que e necesita para las pruebas y los peinados?


74



H. Programación estocástica: análisis dinámico “Dinámico”: los trabajos llegan aleatoriamente con el tiempo y deben tomarse decisiones sobre la marcha en cuanto a cómo programarlos. Para ello se utiliza la teoría de colas.


75

I. Balanceo de la línea de ensamblaje Un conjunto de n tareas diferentes que deben terminarse para cada artículo. ti: tiempo requerido para terminar cada artículo Objetivo: organizar la tareas en grupos, ejecutándose cada grupo en una sola estación de trabajo. • Generalmente, la cantidad de tiempo asignada a cada estación de trabajo se determina con antelación, basándose en la tasa deseada de producción de la línea de ensamblaje. Esto se conoce como el tiempo de ciclo, C.

• Factores que complican : restricciones de precedencia (algunas tareas deben terminarse de acuerdo a cierta secuencia); restricciones de zonificación (algunas tareas no pueden ejecutarse en la misma estación de trabajo), …


76



I. Balanceo de la línea de ensamblaje Sea t1, t2, … , tn: tiempo requerido para terminar las respectivas tareas El contenido total de trabajo asociado con la producción de un artículo, por ejemplo T, viene dado por: Para un tiempo de ciclo de C, el número mínimo posible de estaciones de trabajo es [T/C] (los corchetes indican que el valor T/C debe redondearse al siguiente entero) Generalmente se requieren más estaciones que este valor mínimo ideal.

T= tii=1

n

!


77

Método heurístico de Helgeson y Birnie (1961) o técnica de ordenamiento según el peso posicional Este método coloca un peso en cada tarea basándose en el tiempo total requerido por todas las tareas subsiguientes. Las tareas se asignan en forma secuencial a las estaciones basadas en estos pesos.

I. Balanceo de la línea de ensamblaje


78



Ejemplo 10 El ensamble final de los ordenadores sin marca, un clon genérico de PC que se ordena por correo, requiere un total de 12 tareas. El ensamble se hace en la planta de Lubbock, Texas, usando diferentes componentes importados del extremo Oriente. As tareas requeridas para las operaciones de ensamble son: 1. Taladrar orificios en le gabinete de metal y montar las ménsulas para sostener las un unidades de disco. 2. Fijar la tarjeta madre al gabinete. 3. Montar la fuente de poder y unirla con la tarjeta madre. 4. Colocar el procesador principal y los chips de memoria en la tarjeta madre. 5. Enchufar la tarjeta de gráficos. 6. Montar la unidades de discos flexibles. Unir el controlador de la unidad de discos flexibles y la fuente de poder a las unidades de disco. 7. Montar la unidad del disco duro. Unir el controlador del disco duro y la fuente de poder al disco duro. 8. Se hacen las conexiones apropiadas en la tarjeta madre para la configuración específica del sistema. 9. Unir el monitor a la tarjeta de gráficos antes de correr el diagnóstico del sistema. 10. Correr el diagnóstico del sistema. 11. Sellar el gabinete. 12.  Adherir el logo de la compañía y empacar el sistema para su embarque.


79

Ejemplo 10 Los orificios deben taladrarse y la tarjeta madre conectarse al gabinete antes que cualquier otra operación. Una vez que se ha montado la tarjeta, pueden instalarse la fuente de poder, la memoria, los chips del procesador, la tarjeta de gráficos y los controladores de discos. Las unidades de discos flexibles se colocan en la unidad antes que la unidad de disco duro, y requieren que se coloque en primer lugar la fuente de energía y el controlador. Basándose en la configuración de la memoria y en la selección del adaptador de gráficos, se determinan y se gradúan los valores de los interruptores en la tarjeta madre. El monitor debe conectarse a la tarjeta de gráficos de modo que puedan leerse los resultados de las pruebas de diagnóstico. Finalmente, después de terminar todas las demás tareas, se corren los diagnósticos y el sistema se empaca para su embarque. En la siguiente tabla se resumen los tiempos de los trabajos y las relaciones de precedencia para este problema.

Tarea Predecesores inmediatos

Tiempos

1 - 12 2 1 6 3 2 6 4 2 2 5 2 2 6 2 12 7 3, 4 7 8 7 5 9 5 1

10 9, 6 4 11 8, 10 6 12 11 7

Suponga que la compañía desea contratar suficientes trabajadores para producir una máquina ensamblada cada 15 min


80



Ejemplo 10 • Diagrama de restricciones de precedencia para el ordenador clónico (figura) • Suma de los tiempos de las tareas = 70 • Número mínimo de estaciones de trabajo = 70/15 = 4.67, redondeado al siguiente entero = 5 • Determinación del tiempo posicional: el peso posicional de la tarea i se define como el tiempo requerido para ejecutar la tarea i más los tiempos requeridos para ejecutar todas las tareas. Como la tarea 1 debe preceder a todas las demás, su peso posicional es simplemente la suma de los tiempos de las tareas, que es 70.

Tarea Predecesores inmediatos

Tiempos Peso posicional

1 - 12 70 2 1 6 58 3 2 6 31 4 2 2 27 5 2 2 20 6 2 12 29 7 3, 4 7 25 8 7 5 18 9 5 1 18

10 9, 6 4 17 11 8, 10 6 13 12 11 7 7

1 2

3

4

5

6

7 8

9

10

11 12


81

Ejemplo 10 Tarea Predecesores inmediatos

Tiempos Peso posicional

1 - 12 70 2 1 6 58 3 2 6 31 4 2 2 27 5 2 2 20 6 2 12 29 7 3, 4 7 25 8 7 5 18 9 5 1 18

10 9, 6 4 17 11 8, 10 6 13 12 11 7 7

1 2

3

4

5

6

7 8

9

10

11 12


82

Documents

Ejecución avanzada 2