Tema: PLANEAMIENTO Y
CONTROL DE OPERACIONES
Docente: Mg. SUGEY QUEA
Escuela Profesional Período académico: 2020-2
Ingeniería Industrial Semestre: VII
Unidad: III
Unidad III
Planeación de producción, capacidad y materiales,
programación de operaciones, planeamiento y
control de la producción integrados
Sesión 11
Programación de
operaciones
MÁQUINAS PARALELAS
Con frecuencia, los problemas de programación consideran varias máquinas. Las máquinas múltiples pueden
estar colocadas en paralelo o en serie. En esta sección se estudiarán varios modelos para sistemas paralelos.
La figura en la siguiente presentación, describe máquinas paralelas. Cuando se usan máquinas múltiples en
paralelo, se supone que cualquier trabajo se puede procesar en cualquiera de las máquinas, y que el
tiempo para procesar un trabajo es el mismo en cualquiera de ellas, es decir, son máquinas idénticas. Además,
los trabajos consisten en una sola operación; una vez que comienza el procesado de un trabajo en una de las
máquinas, debe terminarse. La decisión de programación comprende dos aspectos: qué máquina procesa el
trabajo y en qué orden.
Aunque es difícil obtener una solución óptima para los problemas de máquinas idénticas en paralelo, se
sabe que para una medida normal la solución óptima se puede ver como una lista programada. Una lista es una
secuencia de todos los trabajos. Para crear un programa, se asigna el siguiente trabajó en la lista a la máquina
con la menor cantidad de trabajo asignado, y se continúa hasta que todos los trabajos en la lista se asignan.
MÁQUINAS PARALELAS
El algoritmo es.
Máquinas paralelas
Paso 0. Sea i/f = 0, i = 1,2, >.., m la carga de trabajo asignada
a la máquina i, L = ([1], [2],
..., [/i]) la lista ordenada de la secuencia, Cj = 0* j = 1,2,..., n Máquina 1
y k = 1.
Máquina 2
Se examinará una implantación específica de listas programadas; de Máquina 3
nuevo los modelos se jerarquizan según la medida de desempeño.
Tiempo de flujo
Del análisis de los problemas de una sola máquina, se sabe que TPC minimiza el tiempo de flujo en una
máquina, de manera que es probable que la lista TPC sea un buen punto de partida. Se programa el
trabajo con el menor tiempo de procesado en Cualquier procesador, después el trabajo con el
siguiente tiempo de procesado más pequeño, para que comience en cuanto sea posible en la máquina
con el menor tiempo total de procesado. Se continúa hasta que todos los trabajos están programados;
una prueba directa muestra que este procedimiento minimiza el tiempo de flujo.
Ejemplo
Tiempo de flujo mínimo en procesadores paralelos. Gerry Pratt es propietario de Pratt Plastics, una pequeña planta
de moldeo de plástico por inyección. En este momento, Pratt tiene tres máquinas de moldeo idénticas y tiene 15
trabajos. Todos los clientes quieren sus trabajos ahora mismo, de manera que se quiere minimizar el tiempo tota!
que todos los trabajos pasan esperando ser procesados. Los tiempos de procesamiento se muestran en la tabla.
Los trabajos se numeraron en el orden TPC.
Tiempos de procesado para Pratt Plastics
Ejemplo
Solución. Minimizar el tiempo de espera es equivalente a minimizar el tiempo de flujo.
Al inicio no hay trabajos asignados a las máquinas, el primer trabajo de la lista se puede asignar a cualquier
procesador. Los empates se rompen arbitrariamente, asignando el trabajo a la máquina con el menor número de
identificación; entonces, el trabajo 1 se asigna a la máquina 1, y su tiempo de procesado (j\ = 1) se suma al tiempo de
procesado total de la máquina 1 (Hi = 0 + 1 = 1). El segundo trabajo se asigna a la máquina 2 (H2 = 3) y el tercero en la
máquina 3 (H3 = 4). Se asigna el cuarto trabajo a la máquina con menor carga, que es la máquina 1 {Hx = min {1,3,4}).
Se suma el tiempo de procesamiento del trabajo 4 (PA = 6) a la carga total de la máquina 1 (H, = 1), lo que da 7
periodos de tiempo de procesado en la máquina 1 (Hx = 1+6 = 7).
Gráfica de Gantt para
el tiempo de flujo en
procesadores paralelos
Ejemplo
Programa de tiempo de flujo mínimo para Praít
Se continúa de esta manera para llegar al programa óptimo que se resume en la tabla La figura (Gráfica
de Gantt para el tiempo de flujo en procesadores paralelos) contiene una representación pictórica
mediante la gráfica de Gantt. Este programa tiene tiempo de flujo total de 372 unidades de tiempo.
Lapso de producción
Suponga que se quiere minimizar el lapso en lugar del tiempo de flujo. Desafortunadamente, no se cuenta con un
algoritmo eficiente para minimizar el lapso, ni siquiera cuando se trata de sólo dos máquinas. Sin embargo, la lista del
programa proporciona un buen heurístico.
Si alguna vez ha ayudado a alguien a cargar un camión, tal vez haya colocado los artículos más grandes primero y
usado los más pequeños para llenar los espacios libres. La misma filosofía se aplica a la construcción de los programas
que minimizan el lapso. Se usa primero una lista del tiempo de procesado más largo (TPL) y se asigna el siguiente
trabajo en la lista a la máquina con el menor tiempo de procesado total asignado. Como antes, los empates se pueden
romper de manera arbitraria, ya sea para los trabajos en lista o para las asignaciones en las máquinas.
Para el ejemplo anterior, la lista TPL es sólo la opuesta de la lista TPC. Primero se asigna el trabajo 15 a cualquiera
de las tres máquinas, digamos a la máquina 1. Después se asigna el trabajo 14 a la máquina 2 y el 13 a la 3. Las tres
máquinas tienen cargas de trabajo respectivas de 19, 18 y 16. El trabajo 12 es el siguiente en la lista y se asigna a la
máquina 3, que tiene el menor tiempo de procesado. Está máquina tiene ahora 30 unidades de tiempo de procesado
asignado. Se continúa de esta manera hasta asignar el resto de los trabajos.
Los resultados se dan en la tabla y la gráfica de Gantt correspondiente:
Lapso de producción
Solución con lapso de producción mínimo para Pratt'
Diagrama de Gantt para el lapso de producción en procesadores
paralelos
Ejemplo
donde m es el número de máquinas (Graham, 1969). Así, para el problema de tres máquinas, no importa cuáles
sean los datos, el algoritmo de la lista TPL nunca produjo un lapso mayor que 23% arriba del lapso óptimo. Éste es
un resultado sorprendente, significa una garantía para el heurístico.
Si se permite la interrupción (es decir, que los trabajos se separen y se haga una parte en una máquina y el resto en
otra), es sencillo obtener el programa de lapso mínimo. McNaughton (1959) demuestra que el lapso mínimo cuando
se permite interrupción es
De manera intuitiva los trabajos se asignan a las máquinas tan parejo como se
pueda. Para construir un programa con este lapso, se asignan trabajos de manera arbitraria a la máquina
1, hasta que el tiempo de procesado total es mayor que Cmáx. Se interrumpe el último trabajo, moviendo
a la máquina 2 la parte que excede a Cmáx. Se continúa asignando trabajos a cada máquina de esta
forma; al final se obtiene un programa sin tiempo ocioso y con lapso se
programa el trabajo más largo en una máquina, se eliminan el trabajo y la máquina del problema y se
procede como antes.
Ejemplo
Para garantizar un programa con lapso mínimo sin interrupciones, se debe recurrir a algoritmos enumerativos como ramificación y
acotamiento o programación dinámica. Sin embargo, el lapso proporciona una cota inferior sobre el lapso sin interrupciones. Para el
ejemplo, Cmiac = máx{19, 53}. Como el algoritmo de la lista TPL construyó un programa con lapso de 54, quedó dentro del 2%
alejado del óptimo, que es lo suficientemente cercano para la mayor parte de las aplicaciones. Existe un programa mejor:
intercambiar el trabajo 11 en la máquina 2 con el trabajo 9 en la 3, con esto todas las máquinas tienen 53 unidades de procesado,
que es igual a la cota inferior y, por lo tanto, debe ser óptima.
En la figura se ve que el lapso para el programa de tiempo de flujo mínimo era 59, mientras que en la figura (Diagrama de Gantt para el lapso de
producción en procesadores paralelos) se observa que el tiempo de flujo para el programa TPL es 582. Si ambas medidas son importantes, ¿qué
programa debe elegirse? De hecho, se puede mejorar mucho el tiempo de flujo del lapso mínimo con sólo invertir el orden de los trabajos en
cada máquina, es decir, poniéndolos en el orden TPC. Esto no es lo mismo que el algoritmo de la lista TPC; todavía se hace la asignación según el
TPL y se obtienen diferentes asignaciones de los trabajos a las máquinas. Para el ejemplo, al invertir el orden de los trabajos en las máquinas se
reduce el tiempo de flujo a 372, que es igual al tiempo de flujo de la lista TPC. Para este ejemplo se puede tener el pastel y también comerlo, ya
que se obtienen un buen lapso (54) y el tiempo de flujo óptimo (372) en el mismo programa. Esto sucedió por suerte y no necesariamente
ocurrirá en otros problemas.
Otros modelos
Si la medida no es el lapso o el tiempo de flujo, el problema de programar máquinas paralelas idénticas es mucho más difícil.
Si la medida es Tmáx, la lista FEC parecería adecuada; para tiempo de flujo ponderado se usa TPPC. Es sencillo aplicar una
extensión del algoritmo de Hodgson para tratar de minimizar el número de trabajos tardíos. Si lo que interesa es la tardanza,
puede ser razonable una lista formada con el heurístico de R&M. Desafortunadamente, ninguno de ellos garantizan programas
óptimos. El intercambio adyacente por pares puede mejorar la solución. Los procedimientos de búsqueda en una simulación de
recocido pueden adaptarse para resolver estos problemas. Los algoritmos especializados para otros problemas de máquinas
paralelas se encuentran en Arkin y Roundy (1991), en Cheng y Chen (1994) y en So (1990).
Si los procesadores no son idénticos, el problema puede complicarse todavía más. Algunos sistemas paralelos tienen
procesadores proporcionales o uniformes. En ese caso, el tiempo para hacer el trabajo j en la máquina k e spik = sk p’j, donde sk
refleja la velocidad del procesador k y pfj es el tamaño del trabajo/ Así, si el trabajo i toma más tiempo en la máquina k que el
trabajo j, tomará más tiempo que el trabajo j en cualquier máquina. Los procesadores no relacionados tienen tiempos de
procesado pJk que varían por trabajo y máquina sin patrón aparente. Es difícil obtener soluciones óptimas para estos modelos,
pero existen buenos heurísticos.
TALLERES DE PRODUCCIÓN CONTINUA
El procesado de trabajos de manera secuencial en varias máquinas, recibe el nombre de producción continua. Todos los trabajos
se procesan en el mismo orden, por lo que se pueden numerar las máquinas de manera que la máquina 1 hace la primera
operación y así sucesivamente.
Taller de producción continua
La figura describe un taller de producción continua. Las células dedicadas son buenos ejemplos de producción continua. Una
familia, o un grupo, de partes se produce en una célula. Cada parte visita, en el mismo orden, las máquinas que componen una
célula. Se supone que cada parte debe procesarse en todas las máquinas; si no es así, el tiempo de procesado en una máquina que
no es necesaria para un trabajo se iguala a cero. Sólo unos cuantos de estos modelos tienen una solución sencilla. Se comienza con
el modelo del lapso de producción para dos máquinas.
PRODUCCIÓN INTERMITENTE
Las plantas de producción continua tienen rutas idénticas para todos los trabajos, de no ser así, se trata de producción
intermitente. La producción en muchas plantas fabricantes de metales es intermitente. Existe cierto número de productos que usan
las mismas máquinas, pero tal vez en diferente orden. La figura en la siguiente presentación muestra tres trabajos procesados en un
taller de cuatro máquinas. E1 trabajo 1 consiste en tres operaciones, la primera en la máquina B, la segunda en la A y la última en la
C. Estas operaciones deben realizarse en este orden (la operación y precede a la operación j+ l)por razones técnicas, como roscar un
agujero después de haberlo perforado. El trabajo 2 se procesa en el orden A-B-D y el trabajo 3 sigue la ruta A-C-B-D.
Sin pérdida de generalidad, suponga que cada trabajo se procesa en cada máquina; si no, el tiempo de procesado en esa
máquina es cero. Entonces, se tienen m máquinas, cada trabajo consiste en m operaciones, donde la operación j del trabajo i tiene
tiempo de procesado pu. Una lista de ruta especifica la máquina que debe procesar cada operación para cada trabajo. Para
simplificar los datos de la producción intermitente, se da una tabla de tiempos de procesado para los trabajos y las operaciones. El
tiempo de la operación va seguido de una diagonal y la máquina en la que ocurre. Por ejemplo, si la operación 2 del trabajo 6 tiene
un elemento 5/C, la segunda operación del trabajo 6 se hace en la máquina C y requiere 5 minutos.
PRODUCCIÓN INTERMITENTE
Es difícil programar la producción Taller de producción intermitente
intermitente. Existen (n\)m programas posibles
para una planta con n trabajos y m máquinas.
Aun para valores pequeños de n y m, este
número es enorme. Incluso el problema
mencionado de tres trabajos y cuatro máquinas
tiene más de 1000 programas; un problema de
10 trabajos tendría más de 1026. Se comienza
con un caso que se puede resolver,
minimizando el lapso en dos máquinas. Se
estudiarán dos enfoques heurísticos: los
procedimientos de despacho y de búsqueda. Se
regresará al problema de programación de la
producción intermitente, cuando se analicen
los heurísticos de cuellos de botella.
SISTEMAS DE PROGRAMACIÓN CON CAPACIDAD FINITA
Los modelos de programación estudiados en este capítulo son una parte integral de un sistema de programación de capacidad
finita. Estos sistemas estrechan la relación entre los planes de capacidad de MRP y los programas detallados para la planta. Como
muy pocos sistemas MRP toman en cuenta la preparación y la mayoría supone tiempos de entrega constantes, sus metas de
producción pueden ser poco realistas. La manufactura moderna requiere diversidad en los productos, producción en lotes pequeños,
entrega rápida y cumplimiento de las fechas de entrega prometidas. Más aún, es necesario tener flexibilidad para responder a los
cambios en las órdenes de los clientes y disponibilidad de materiales o de capacidad. Por tradición, los inventarios y el exceso de
capacidad han ocultado problemas asociados con estos requerimientos. La disminución de los niveles de inventario y capacidad han
hecho que la programación de la capacidad finita sea una paso importante en la planeación y control de la producción.
Existe una relación fundamental entre la capacidad y el tiempo de entrega. En muchas plantas tradicionales, los estudios
muestran que alrededor del 5% del tiempo de entrega de la manufactura de un trabajo es un proceso con valor agregado real. El
resto es tiempo de espera y de movimiento. El tiempo de espera puede ser consecuencia de otros trabajos en proceso, de la falta de
materiales o herramientas o de la preparación. Tener un exceso en la capacidad es una manera de aliviar el problema. Si se tienen
máquinas dedicadas para cada trabajo, entonces no es necesario esperar que otros trabajos sean procesados, ni que se lleve a cabo
la preparación. Por otro lado, el inventario puede permitir un abastecimiento instantáneo y disminuir el número de preparaciones
necesarias; separa las operaciones sucesivas y se puede planear y programar a nivel local, que es mucho más sencillo.
Desafortunadamente, esto requiere una alta inversión en capacidad e inventario.
SISTEMAS DE PROGRAMACIÓN CON CAPACIDAD FINITA
Un enfoque es simplificar el sistema de producción. La fabricación en células convierte a los talleres de producción intermitente en talleres dedicados de
producción continua para cada producto.
La reducción de preparaciones puede eliminar el tiempo perdido por el cambio de un trabajo a otro.
Aunque estos conceptos son racionales, existen situaciones en las que el costo de la capacidad prohibe dedicar equipo, o para las que ya no es posible
reducir más las preparaciones. En tales casos, una programación adecuada puede ayudar a reducir el tiempo de entrega y, en consecuencia, se podrá
cumplir mejor con las fechas prometidas y se podrá crear capacidad al dedicar menos tiempo a las preparaciones o las esperas por material. La
programación puede también suavizar el flujo del producto. La programación asistida por computadora libera a los gerentes para que se dediquen a
aspectos más importantes en lugar de generar los programas.
Muchas compañías tienen un manual del programador o un comité que crea los programas El programa que resulta determina el orden de distribución de
las órdenes y se usa para el control de la planta. Con frecuencia, el cambio requiere colocar algunos trabajos en una lista especial que especifica aquellos
que son importantes, cuáles tienen prioridad sobre otros. Algunas personas se dedican a acelerar los trabajos en esta lista especial; el personal de ventas,
los representantes del servicio a clientes y los gerentes de producción pueden también hacerlo. Estas prácticas pueden hacer más daño que bien. Los
sistemas de programación de capacidad finita asistidos por computadora vencen muchos de estos problemas. Se usan insumos de bases de datos
existentes para generar uno o más programas a partir de un modelo apropiado, por ejemplo, un modelo de programación de un cuello de botella. Un
programador revisa el programa y lo acepta como está o lo modifica. Se puede modificar en forma manual o puede cambiar las prioridades, los tiempos o
las capacidades y dejar que la computadora genere un nuevo programa. El programa se implanta y se da seguimiento a los trabajos en la planta. Si
ocurren cambios en la producción, el programa se modifica para tomarlos en cuenta. En la sección de software (sección 8) se estudiarán varios detalles de
este proceso.
Beneficios
• Mayor número de entregas a tiempo
• Tiempos de entrega reducidos
• Incremento de la capacidad
• Producción más suave
• Más tiempo del administrador dedicado a problemas importantes
Un sistema de programación de la planta en una compañía incrementó el ingreso en $844 000; otra compañía
redujo sus faltantes de 60% a 13%; una tercera disminuyó 70% su trabajo en proceso; una cuarta firma
recuperó el costo del sistema en 21 días, y otras han reducido sus entregas tarde de manera significativa.
Aunque no es sencillo desarrollar estos sistemas, las ganancias valen la pena el esfuerzo.
GRACIAS
