28-102-1-PB

Vista previa del material en texto

See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/285244333
Programacion de Sistemas de Produccion con SPS Optimizer
Article · January 2010
CITATIONS
16
READS
3,346
1 author:
Eduardo Salazar
University of Concepción
15 PUBLICATIONS   60 CITATIONS   
SEE PROFILE
All content following this page was uploaded by Eduardo Salazar on 12 January 2016.
The user has requested enhancement of the downloaded file.
https://www.researchgate.net/publication/285244333_Programacion_de_Sistemas_de_Produccion_con_SPS_Optimizer?enrichId=rgreq-6663488daa03bda693b597b56fe36ca1-XXX&enrichSource=Y292ZXJQYWdlOzI4NTI0NDMzMztBUzozMTcwMzI1MjcwMDc3NDZAMTQ1MjU5Nzg1Mjc1MA%3D%3D&el=1_x_2&_esc=publicationCoverPdf
https://www.researchgate.net/publication/285244333_Programacion_de_Sistemas_de_Produccion_con_SPS_Optimizer?enrichId=rgreq-6663488daa03bda693b597b56fe36ca1-XXX&enrichSource=Y292ZXJQYWdlOzI4NTI0NDMzMztBUzozMTcwMzI1MjcwMDc3NDZAMTQ1MjU5Nzg1Mjc1MA%3D%3D&el=1_x_3&_esc=publicationCoverPdf
https://www.researchgate.net/?enrichId=rgreq-6663488daa03bda693b597b56fe36ca1-XXX&enrichSource=Y292ZXJQYWdlOzI4NTI0NDMzMztBUzozMTcwMzI1MjcwMDc3NDZAMTQ1MjU5Nzg1Mjc1MA%3D%3D&el=1_x_1&_esc=publicationCoverPdf
https://www.researchgate.net/profile/Eduardo-Salazar-5?enrichId=rgreq-6663488daa03bda693b597b56fe36ca1-XXX&enrichSource=Y292ZXJQYWdlOzI4NTI0NDMzMztBUzozMTcwMzI1MjcwMDc3NDZAMTQ1MjU5Nzg1Mjc1MA%3D%3D&el=1_x_4&_esc=publicationCoverPdf
https://www.researchgate.net/profile/Eduardo-Salazar-5?enrichId=rgreq-6663488daa03bda693b597b56fe36ca1-XXX&enrichSource=Y292ZXJQYWdlOzI4NTI0NDMzMztBUzozMTcwMzI1MjcwMDc3NDZAMTQ1MjU5Nzg1Mjc1MA%3D%3D&el=1_x_5&_esc=publicationCoverPdf
https://www.researchgate.net/institution/University-of-Concepcion?enrichId=rgreq-6663488daa03bda693b597b56fe36ca1-XXX&enrichSource=Y292ZXJQYWdlOzI4NTI0NDMzMztBUzozMTcwMzI1MjcwMDc3NDZAMTQ1MjU5Nzg1Mjc1MA%3D%3D&el=1_x_6&_esc=publicationCoverPdf
https://www.researchgate.net/profile/Eduardo-Salazar-5?enrichId=rgreq-6663488daa03bda693b597b56fe36ca1-XXX&enrichSource=Y292ZXJQYWdlOzI4NTI0NDMzMztBUzozMTcwMzI1MjcwMDc3NDZAMTQ1MjU5Nzg1Mjc1MA%3D%3D&el=1_x_7&_esc=publicationCoverPdf
https://www.researchgate.net/profile/Eduardo-Salazar-5?enrichId=rgreq-6663488daa03bda693b597b56fe36ca1-XXX&enrichSource=Y292ZXJQYWdlOzI4NTI0NDMzMztBUzozMTcwMzI1MjcwMDc3NDZAMTQ1MjU5Nzg1Mjc1MA%3D%3D&el=1_x_10&_esc=publicationCoverPdf
 
 
REVISTA ICHIO 
ISSN 718-9605 
Vol. 1 / Nº 2, pp. 33 – 46, Diciembre 2010 
33 
 
 
 
Programación de Sistemas de Producción con SPS_Optimizer 
 
 
Eduardo Salazar H. 
Departamento de Ingeniería Industrial 
Facultad de Ingeniería – Universidad de Concepción 
esalazar@udec.cl 
Casilla 160-C / Correo 3 
Concepción / Chile 
 
 
 
Resumen 
 
Se presenta el problema de la programación de producción en sistemas productivos a través del sistema 
SPS Optimizer / Job Shop Scheduler desarrollado por el autor. Este sistema permite resolver la 
programación de un conjunto de órdenes en sistemas de producción tipo taller (flexible job shop), 
configuración que incluye los conceptos de multicapacidad, tiempos de preparación y recirculación. Como 
casos particulares se desprenden los sistemas de una máquina, máquinas paralelas y taller de flujo. Los 
algoritmos disponibles abarcan un amplio espectro de métodos de programación, que van desde las 
clásicas reglas de despacho y métodos orientados al problema en sistemas clásicos de una máquina, 
máquinas paralelas, taller de flujo y job shop, a métodos basados en simulación y metaheurísticas de 
búsqueda local. Se ilustra el uso del sistema SPS_Optimizer resolviendo un problema de programación de 
producción en un sistema tipo flowshop con flujos reentrantes. 
 
Palabras Claves: Sistemas de producción, Programación de producción, Métodos de programación. 
 
 
 
Abstract 
 
The production scheduling problem for manufacturing systems is presented through the SPS Optimizer / 
Job Shop Scheduler system developed by the author. This system solve the problem of scheduling a set of 
production orders in a job shop (flexible job shop) like configuration, which includes concepts of 
multicapacity, setups and recirculation. Special cases of machine configurations as the single machine 
shop, parallel machine shop and flow shop are also considered. The available scheduling methods includes 
from clasical dispatching rules and problem oriented methods to simulation based methods and local 
search metaheuristics. The use of SPS_Optimizer is illustrated through a production scheduling problem 
in a flowshop with reentrant flows. 
 
Keywords: Production systems, Production scheduling, Scheduling methods. 
 
 
REVISTA ICHIO 
ISSN 718-9605 
Vol. 1 / Nº 2, pp. 33 – 46, Diciembre 2010 
34 
 
1. Introducción 
 
Se analiza la programación de sistemas productivos utilizando SPS_Optimizer / Job Shop Scheduler, sistema 
prototipo para la programación de sistemas de producción desarrollado por el autor. El sistema considera ambientes 
productivos tipo taller con multicapacidad, tiempos de preparación (setups) y recirculación (flexible job shop with 
setups and recirculation), que incluye como casos particulares los sistemas de una máquina (single machine shop), 
taller paralelo (parallel shop), taller de flujo fexible (flexible flow shop) y taller general (flexible job shop). Permite 
además modelar la disponibilidad y estado inicial de las capacidades productivas, y considerar la liberación de 
órdenes de producción en diferentes instantes de tiempo. El concepto de recirculación se entiende como la opción de 
múltiples procesos de una orden de producción en un mismo centro de trabajo. 
 
La programación de producción es un problema fundamental para todo sistema productivo, la forma de programar la 
producción influye, entre otros, en los inventarios en proceso, utilización de máquinas y cumplimiento de fechas de 
entrega. Variados métodos se han aplicado al problema de la programación de producción en también variadas 
configuraciones productivas (Jain & Meeran (1999)). El problema de encontrar un buen programa de producción ha 
despertado el interés tanto académico (desarrollo algorítmico) como industrial (secuenciar órdenes de producción en 
entornos complejos que permitan cumplir a tiempo los compromisos con los clientes, reducir tiempos improductivos 
por falta de coordinación, etc.). Como método de programación, el concepto de regla de despacho y sus 
combinaciones, ha sido ampliamente utilizado a través del tiempo (ver Panwalkar & Iskander (1977), Haupt (1989) y 
Jayamohan & Rajendran (2000)). Métodos heurísticos de búsqueda local como algoritmos genéticos han encontrado 
aplicación para este problema en las últimas décadas (ver Davis (1985), Dorndorf & Pesh (1995), Gonçalvez et al. 
(2005)). 
 
2. El Problema de la Programación de Producción 
 
El problema de la programación de producción consiste en asignar los recursos productivos 
(máquinas, operarios, herramientas, etc.) a un conjunto de actividades productivas en un 
horizonte de tiempo (generalmente de corto plazo), de manera que se satisfagan relaciones 
técnicas de precedencia y de capacidad de máquinas (para mayor detalle ver Baker (1974), Heizer 
y Render (2007), Pinedo (2005), Pinedo (2008)). 
Una orden de producción (OP) se considera como una secuencia de operaciones, cada una a 
procesar en un centro de trabajo (CT). La secuencia de operaciones define la ruta de proceso de 
cada orden. Las principales características de una OP son su secuencia de proceso, tiempo de 
proceso, fecha de liberación (release date), fecha de entrega comprometida (due date) y tipo de 
operación (ver sección 3). Las principales características de un CT son su capacidad (número de 
máquinas idénticas del CT), disponibilidad de máquinas y tiempos de preparación. 
 
La Tabla 1 muestra los datos para un ejemplo de programación de 4 OPs en un sistema 
productivo de 3 CTs de capacidad 2,3 y 1. 
 
 
CT Capacidad OP Liberación Fecha de Entrega Ruta: CT (Tiempo de Proceso) 
1 2 1 0 7 3 (4) – 2 (4) 
2 3 2 0 12 2 (5) – 1 (3) – 3 (4) – 2 (3) 
3 1 3 1 8 2 (8) 
 4 3 15 1 (3) – 2 (4) – 3 (2) 
Tabla 1 Programación de 4 OPs en un Sistema de 3 CTs 
 
 
 
REVISTA ICHIO 
ISSN 718-9605 
Vol. 1 / Nº 2, pp. 33 – 46, Diciembre 2010 
35 
 
En la Tabla 1, la ruta de una OP se indica como una secuencia de operaciones procesadas en CTs 
con los respectivos tiempos de proceso de la operación entre paréntesis. Por ejemplo, la OP2 
consiste en 4 operaciones (la primera operación se realiza en el CT2 con tiempo de proceso 5, la 
segunda operación se realiza en el CT1 con tiempo de proceso 3, la tercera operación se realiza en 
el CT3 con tiempo de proceso 4 y la cuarta operación se realiza en el CT2 con tiempo de proceso 
3 unidades de tiempo). El concepto de recirculación se aprecia en la ruta de proceso de la OP2, en 
la que tanto la operación 1 como la operación 4 se procesan en el CT2. También, de la Tabla 1 se 
desprende que la fecha de liberación (release date) de la OP2 es 0 (la orden se libera en el tiempo 
0), y su fecha de entrega comprometida (due date) es 12. 
Las diferentes operaciones se asignan a máquinas del correspondiente CT en un horizonte de 
tiempo, indicando fecha de inicio y término de cada operación. Esta asignación debe respetar la 
secuencia de proceso (una operación de una OP no puede ejecutarse antes de que termine la 
operación precedente de la misma OP) y restricciones de capacidad en cada CT (una máquina no 
puede procesar dos operaciones en forma simultánea). 
Las operaciones de una OP se identifican con un correlativo dentro de la secuencia de proceso de 
la orden. Por ejemplo, la tercera operación de la OP2 se identifica como la operación 2.3. La 
Figura 1 muestra la estructura de precedencia soportada por SPS_Optimizer, ejemplificada para la 
OP2, la que corresponde a la estructura clásica de proceso en un job shop. 
 
 
 
Figura 1 Estructura de Proceso de OPs 
 
La Figura 2 muestra la ruta de proceso de la OP2 a través de los CTs del sistema productivo. Los 
cuadrados de color negro representan las máquinas del respectivo CT. 
 
 
 
 
 
 
 
 
 
Figura 2 Sistema de Producción y Flujo de OP2 
 
El proceso de programación requiere de un procedimiento (algoritmo) que permita realizar la 
asignación de operaciones productivas a recursos, generando un programa de producción factible, 
orientado por la medida de desempeño (objetivo) a optimizar. 
Entre las medidas de desempeño frecuentemente utilizadas se encuentran el lapso o makespan 
(M), tiempo de flujo (F) y tardanza (T). La primera mide el lapso de tiempo en el que un sistema 
productivo procesa completamente un conjunto de OPs, la segunda es la suma de los tiempos de 
flujo, es decir, la suma de los tiempos que las OPs permanecen en el sistema. La tercera medida 
corresponde a la suma de las tardanzas, es decir, la suma de los atrasos efectivos de las OPs 
(revisar Baker (1974), Pinedo (2005). 
Si ri, di y Ci corresponden respectivamente a las fechas de liberación (release dates), 
comprometidas para entrega (due dates) y finalización (completion dates) de la OPi, entonces: 
2.1 2.2 2.3 2.4 
CT1 
CT2 
CT3 
 
2.1 
 
2.3 
 
2.4 
 
OP2 
2.2 
OP2 
 
 
REVISTA ICHIO 
ISSN 718-9605 
Vol. 1 / Nº 2, pp. 33 – 46, Diciembre 2010 
36 
 
)C(maxM i
n,...,i 1=
=
 (1) 
iii
n
i
i rCFconFF −=∑=
=1 (2) 
),dC(maxTconTT iii
n
i
i 0
1
−=∑=
= (3) 
 
donde n, Fi y Ti corresponden respectivamente al número de OPs a programar, tiempo de flujo y 
tardanza de la OPi. La fórmula (1) es válida si al menos una fecha de liberación es 0. 
 
3. Tipos de Operación 
 
Cada operación puede asociarse a un tipo de operación, por ejemplo, en un CT de perforación se 
realizan operaciones de perforación de diferente diámetro con brocas para diferentes materiales; 
la Tabla 2 ilustra este concepto para el CT2. La operación tipo 1 de la Tabla 2 ejemplifica una 
operación de perforación utilizando una broca de 10 mm de diámetro para madera, mientras que 
la operación tipo 4 se refiere a una operación de perforación utilizando una broca de 12 mm de 
diámetro para metal. La operación tipo 3, que siendo una perforación de igual diámetro que la 
operación tipo 1, es diferente a esta ya que se realiza con una broca diferente. 
 
Tipo Diámetro [mm] Material 
1 10 Madera 
2 12 Madera 
3 10 Metal 
4 12 Metal 
5 14 Metal 
Tabla 2 Tipos de Operación de Perforación en CT2 
 
Procesar un lote de producto que requiere una perforación tipo 1 y luego procesar otro lote de 
producto que requiere de una perforación tipo 4, origina una preparación de la máquina (cambio 
de broca, limpieza, etc.). 
La Tabla 3 complementa la información de la Tabla 1 con respecto a la identificación de 
operaciones y del tipo de operación. 
 
OP Operación CT Tiempo de Proceso Tipo 
1 1.1 3 4 0 
 1.2 2 6 3 
2 2.1 2 5 5 
 2.2 1 3 0 
 2.3 3 4 0 
 2.4 2 7 3 
3 3.1 2 5 1 
4 4.1 3 2 0 
 4.2 2 3 4 
 4.3 1 4 0 
Tabla 3 Operaciones de Ordenes de Producción 
 
 
 
REVISTA ICHIO 
ISSN 718-9605 
Vol. 1 / Nº 2, pp. 33 – 46, Diciembre 2010 
37 
 
El tipo de operación 0 corresponde a un tipo de operación neutro, que no origina preparación de 
la máquina que procesa una operación de este tipo. De la Tabla 3, se deduce que sólo en el CT2 
existen tiempos de preparación, ya que sólo a las operaciones que se procesan en el CT2 se les 
asigna un tipo diferente a 0. 
 
4. Disponibilidad y Estado Inicial de Máquinas 
 
Cada capacidad productiva (máquina) de un CT puede ser modelada con una determinada 
disponibilidad y estado inicial. La disponibilidad de una máquina indica a partir de qué instante 
ésta se encuentra disponible para ser utilizada, lo que permite modelar la inserción de nuevas OPs 
a un programa en ejecución. El estado inicial de una máquina indica el estado en que ésta se 
encuentra, reflejado a través del tipo de la última operación procesada en la máquina. 
 
La Tabla 1 indica que el CT1 tiene 2 máquinas, el CT2 tiene 3 máquinas y el CT3 tiene 1 máquina. 
Las máquinas en un CT se identifican por medio de un correlativo. Por ejemplo, las máquinas del 
CT1 se identifican como las máquinas 1.1 y 1.2, las máquinas del CT2 se identifican como las 
máquinas 2.1, 2.2 y 2.3, y la máquina del CT3 se identifica como la máquina 3.1. 
 
 
CT Máquina Disponibilidad Estado 
1 1.1 0 0 
 1.2 0 0 
2 2.1 2 2 
 2.2 4 1 
 2.3 0 3 
3 3.1 0 0 
Tabla 4 Máquinas del Sistema 
 
La Tabla 4 complementa la información de la Tabla 1 con respecto de la disponibilidad y estado 
inicial de las máquinas. Por ejemplo, la máquina 1.1 está disponible a partir del instante 0 (tiempo 
de referencia de inicio de la programación) e inicialmente está en estado 0 (estado neutro), 
mientras que la máquina 2.2 estará disponible a partir del tiempo 4 y quedará en estado 1. Esto 
significa que el tipo de la última operación que procesó la máquina 1.1 no influye en la 
preparación de esta para procesar un siguiente trabajo; el caso de la máquina 2.2 es diferente, ya 
que actualmente procesa una operación tipo 1, es decir, una perforación de diámetro 10 mm sobre 
madera. 
 
 
 
5. Tiempos de Preparación (Setups) 
 
El problema de programar operaciones productivas con tiempos de preparación dependientes de 
la secuencia se produce cuando el tiempo de preparación de una máquina para procesar una 
operación depende de cuál fue la última operación procesada en la máquina. La Tabla 5 
complementa la información de la Tabla 1, mostrando los tiempos de preparación en el CT2. Se 
considera que si la siguiente operación a procesar en una máquina es del mismo tipo que la última 
 
 
REVISTA ICHIO 
ISSN 718-9605 
Vol. 1 / Nº 2, pp. 33 – 46, Diciembre 2010 
38 
 
operación procesada, no es necesario preparar la máquina.Por ejemplo, si una operación tipo 2 se 
programa como primer trabajo en la máquina 2.1 la preparación inicial es 0, ya que la última 
operación procesada por la máquina 2.1 fue tipo 2 (ver columna Estado para la máquina 2.1 en la 
Tabla 4) y por lo tanto no se requiere preparación. 
 
 
Tipo 1 2 3 4 5 
1 - 3 7 4 7 
2 2 - 5 3 2 
3 3 6 - 1 8 
4 1 3 2 - 11 
5 5 1 2 7 - 
Tabla 5 Tiempos de Setup en CT2 
 
De la Tabla 5 se desprende que, si a continuación de una operación tipo 3 se procesa una 
operación tipo 2, el tiempo de preparación de la máquina es 6. Posterior a la preparación de la 
máquina corresponde el proceso de la operación propiamente tal. Por ejemplo, si se supone que la 
operación 2.1 (operación tipo 5) se programa como primera operación en la máquina 2.3 (que 
inicialmente se encuentra en estado 3), se incurrirá en un tiempo de preparación de 8. Por lo 
tanto, el programa de producción reflejará que la máquina 2.3 estará en preparación desde el 
instante 0 al instante 8, y dado que el tiempo de proceso de la operación 2.1 es 5 (ver Tabla 1), 
desde el instante 8 al instante 13 la máquina 2.3 estará procesando la operación 2.1. 
Es claro que en este caso el tiempo de preparación total será dependiente de la secuencia de 
operaciones procesadas en una máquina. 
 
 
6. El Sistema SPS_Optimizer 
 
El sistema SPS_Optimizer fue desarrollado por el autor en VisualBasic y Lenguaje C/C++, y 
provee de un ambiente autónomo de trabajo. En las secciones 1 a 5 se detallan las 
configuraciones productivas y características de los procesos productivos soportadas en 
SPS_Optimizer. El sistema productivo se modela como un conjunto de CTs de multicapacidad 
(una o más máquinas). 
 
6.1 Visualización de la Funcionalidad del Sistema SPS_Optimizer 
El problema a resolver se ingresa al sistema SPS_Optimizer identificando las características de 
los CTs y de las OPs. La información relativa a CTs y OPs puede ser visualizada en forma tabular 
o con estructura de árbol (en la Figura 3, los CTs se visualizan en forma tabular, mientras que las 
OPs con estructura de árbol). Es posible almacenar la definición del sistema en un archivo, lo que 
permite la posterior visualización y edición de un problema. 
 
 
 
REVISTA ICHIO 
ISSN 718-9605 
Vol. 1 / Nº 2, pp. 33 – 46, Diciembre 2010 
39 
 
 
 
Figura 3 Shortcut Despliegue de Información del Sistema SPS_Optimizer 
 
La Figura 3. muestra un shortcut de la funcionalidad y despliegue de información del sistema 
SPS_Optimizer, basado en el sistema definido en la sección 2 y posteriores (ver Tabla 1 a 5), 
mostrando resultados del problema aplicando un algoritmo genético (GA). El cursor indica la 
operación 2.4 en la carta Gantt, que corresponde a la última operación en finalizar. 
 
Una vez ingresado (o seleccionado) un problema, la programación se realiza seleccionando el 
método deseado. El resultado de la programación se presenta en formato tabular (conjunto de 
tablas) y gráfico (carta Gantt) con la programación de cada CT. 
 
6.2 Algoritmos de Programación 
Los algoritmos disponibles en el sistema SPS_Optimizer abarcan un amplio espectro de métodos 
de programación, que van desde la utilización de las clásicas reglas de despacho (SPT – shortest 
processing time, FCFS – first come first served ó FIFO, EDD – earliest due date, Slack – 
minimum slack, SST – shortest setup time, LWKR – least work remaining, WSPT – weighted 
SPT, etc.) y métodos clásicos orientados al problema (Heurística de Mínimo Setup – Mejor 
Vecino y Heurística ATCS para el problema de una máquina, Algoritmo SPT y Heurísticas LPT, 
MultiFit y ATCS para máquinas paralelas, algoritmo de Johnson para taller de flujo de 2 
máquinas y heurísticas de Palmer, CDS, Gupta, RA, MPS y NEH para taller de flujo, algoritmo 
de Jackson para jobshop de 2 máquinas, etc.), a métodos que utilizan técnicas de simulación 
(SRB: Simulation Rule Based Scheduling – permite aplicar reglas de despacho por CT con dos 
reglas adicionales como criterios de desempate, Montecarlo Simulation – realiza un muestreo 
aleatorio de secuencias y Manual Entry – permite definir una prioridad arbitraria) y 
metaheurísticas de búsqueda local como algoritmos evolutivos (algoritmos genéticos y 
estrategias evolutivas). 
Métodos de programación para problemas clásicos de una máquina, máquinas paralelas, 
flowshop y jobshop pueden revisarse en Baker (1974), Johnson (1974) y Pinedo (2008). 
 
 
 
REVISTA ICHIO 
ISSN 718-9605 
Vol. 1 / Nº 2, pp. 33 – 46, Diciembre 2010 
40 
 
6.3 Medidas de Desempeño 
Las medidas de desempeño que orientan el proceso de optimización de los métodos de búsqueda 
local son makespan (M), tiempo de flujo (F) y tardanza (T). Sin embargo, al aplicar cualquiera de 
los métodos de programación se calculan en forma estándar, además de las mencionadas, una 
serie de medidas como espera total (W), Fmax, Tmax, Wmax, utilización promedio del sistema (Ut 
%), setup total, número de trabajos tardíos (NT ), entre otras. 
La información estadística de CTs y OPs se visualiza en forma tabular. Para cada CT se presenta 
información relativa a: setup total, tiempo total de proceso, % utilización, etc.; y para cada OP 
información relativa a: tiempo de inicio y finalización, tiempo de flujo, tardanza, espera, etc. 
Se presenta una tabla resumen con diferentes medidas de desempeño como: makespan, tiempo de 
flujo, tardanza, flujo y tardanza máxima, setup total, % utilización del sistema, número de OPs 
atrasadas, etc. En la Figura 3, los shortcuts Estadísticas CT y Estadísticas OP resumen las 
estadísticas generadas por la programación para CTs y OPs respectivamente. 
Es posible repetir el proceso de programación utilizando diferentes métodos, cuyos resultados 
(resumen de medidas de desempeño) se mantienen durante la sesión de trabajo para efectos de 
comparación (ver Figura 4). 
La Figura 4 resume los resultados para las medidas de desempeño M, F y T obtenidos al aplicar 
la regla de despacho SPT, algoritmos genéticos (con 2 seg de tiempo CPU) minimizando las 
medidas M, F y T respectivamente, para el problema definido en la sección 2. Notar que cuando 
el objetivo es minimizar M, F y T (resultados en columnas GA(2)/M, GA(2)/F y GA(2)/T en la 
Figura 4), se obtiene el menor valor para M, F y T respectivamente. Utilizando la regla de 
despacho SPT se obtienen los peores resultados para las 3 medidas. Este resultado no es de 
extrañar, dada la naturaleza de una metaheurística que realiza un proceso de búsqueda en un 
espacio amplio de soluciones con un criterio de optimización, mientras que SPT como regla de 
despacho entrega y evalúa sólo una solución. 
 
 
 
Figura 4 Resumen de Medidas de Desempeño 
 
 
 
El resultado de la programación presentado en forma gráfica (ver Figura 3) permite visualizar la 
no disponibilidad inicial de máquinas (achurado de malla), los tiempos de setup (barra achurada 
con líneas diagonales) previo al proceso de la operación propiamente tal (barra sólida). 
Operaciones de una misma OP se visualizan en el mismo color. 
 
 
 
 
 
 
REVISTA ICHIO 
ISSN 718-9605 
Vol. 1 / Nº 2, pp. 33 – 46, Diciembre 2010 
41 
 
7. Aplicación – Flowshop con Flujos Reentrantes 
 
Se ilustra la resolución de un problema de programación de producción de mayor complejidad 
que el problema definido en las secciones 2 a 5, adaptado de Morton y Pentico (1993, p 353 – 
356), identificado como un flowshop con flujos reentrantes. 
 
7.1 Definición del Sistema de Producción 
El proceso productivo de una familia de productos requiere sucesivas operaciones de reducción, 
limpieza y templado de los lotes en proceso, las que se denominan etapas. La Figura 5 muestra 
las operaciones de las 4 etapas del proceso, que se realizan sobre cada lote de producto. 
Las operaciones de reducción R1, R2 y R3 se realizan en diferentes Centros de Reducción de 2, 1 
y 1 máquinas respectivamente. Las operaciones de limpiezaL1, L2 y L3 se realizan todas en la 
única Estación de Limpieza de capacidad 3, mientras que las operaciones de templado T1, T2 y T3 
se realizan todas en un Horno de capacidad 1. La operación de terminación F se realiza en el 
Centro de Terminado de capacidad 1. 
 
 
 
Figura 5 Secuencia de Operaciones 
 
Se requiere producir 5 lotes (órdenes de producción), correspondiente a 5 productos diferentes, 
cuyos tiempos de proceso se presentan en la Tabla 6. El objetivo para el sistema de producción es 
entregar lo antes posible la totalidad de las órdenes. 
 
OP R1 L1 T1 R2 L2 T2 R3 L3 T3 F 
1 8 7 5 6 2 3 4 5 4 12 
2 11 5 6 8 4 2 5 4 5 15 
3 5 4 4 5 6 4 8 3 5 14 
4 6 3 6 7 8 2 9 2 2 10 
5 4 5 7 9 10 2 6 1 2 9 
Tabla 6 Tiempos de Proceso 
 
Las máquinas de reducción deben ser preparadas cada vez que se utilizan. Los tiempos de 
preparación son dependientes de la secuencia (para simplificación se supone que son iguales en 
todos los Centros de Reducción). 
En la Tabla 7 se presentan los tiempos de preparación para las operaciones de reducción en todos 
los Centros de Reducción. Por ejemplo, y de acuerdo al estado actual de las máquinas de 
reducción, si la primera orden procesada es la OP5 (operación R1, R2 ó R3 de OP5), entonces se 
requiere un setup inicial de 2. Si después de realizada una reducción de la OP2 (operación R1, R2 
ó R3 de OP2) se realiza una reducción de la OP1 (operación R1, R2 ó R3 de OP1) se requiere un 
setup de 7. 
OP Setup Inicial 1 2 3 4 5 
1 2 - 4 5 3 4 
2 1 7 - 2 1 2 
3 4 2 3 - 4 4 
4 3 3 4 2 - 5 
5 2 4 2 1 3 - 
Tabla 7 Tiempos de Setup en Centros de Reducción 
T3 F R1 L1 T1 R2 L2 T2 R3 L3 
 
 
REVISTA ICHIO 
ISSN 718-9605 
Vol. 1 / Nº 2, pp. 33 – 46, Diciembre 2010 
42 
 
 
La especificación de setups iniciales, refleja que la última operación de los Centros de Reducción 
ha sido una reducción de un lote de un producto que no pertenece a la familia a procesar. 
 
7.2 Programación con SPS_Optimizer 
Se identifican 6 CTs, los que se muestran en la Tabla 8. Todas las capacidades productivas están 
disponibles a partir del tiempo 0 (tiempo de referencia para el inicio de la programación) y se 
encuentran en estado neutro, salvo las máquinas de reducción de los CT1, CT2 y CT3 (se explica 
más adelante). 
CT Descripción Capacidad 
1 Reducción 1 2 
2 Reducción 2 1 
3 Reducción 3 1 
4 Limpieza 3 
5 Horno de Templado 1 
6 Terminación 1 
Tabla 8. Definición de CTs 
 
Las 5 OPs tienen igual secuencia de proceso (y por ende igual número de operaciones), las que se 
presentan en la Tabla 9; en esta las operaciones indicadas en la Tabla 6 se asocian a las 
operaciones 1 a 10. Los tiempos de proceso para las operaciones de cada OP son los que se 
indican en la Tabla 6. Todas las OPs se liberan en el tiempo 0. 
 
Operación R1 L1 T1 R2 L2 T2 R3 L3 T3 F 
Operación (id) 1 2 3 4 5 6 7 8 9 10 
CT 1 4 5 2 4 5 3 4 5 6 
Tabla 9. Tiempos de Proceso 
 
La estructura de proceso del sistema se muestra en la Figura 6. Dado que en CT1, CT2 y CT3 
(Centros de Reducción) existen setups, las operaciones que allí se realizan (operaciones 1, 4 y 7 
para cada OP), deben asociarse a un tipo de operación. Como en este caso los setups dependen de 
la OP, el tipo de operación se identifica con el número de OP para las operaciones 1, 4 y 7. Así, 
las operaciones 1, 4 y 7 de la OPi se les asigna el tipo i (ver Figura 7). 
 
 
 
 
 
 
 
 
 
Figura 6 Sistema de Producción y Flujo de OPs 
 
CT2 CT5 CT3 CT6 
CT4 
CT1 
 
 
REVISTA ICHIO 
ISSN 718-9605 
Vol. 1 / Nº 2, pp. 33 – 46, Diciembre 2010 
43 
 
 
Figura 7 Tipos de Operación 
 
 
Las operaciones 1, 4 y 7 de cada OP se realizan en los CT1, CT2 y CT3 respectivamente. La 
matriz de setup en CT1 se muestra en la Figura 8 de acuerdo a la información de la Tabla 7. El 
estado inicial de la máquina del CT1 (Máquina Reductora) se define como 6, lo que permite 
modelar el setup inicial. Análogamente se procede para CT2 y CT3. 
 
 
 
 
 
Figura 8 Estado y Tiempos de Setup en CT1 (análogo para CT2 y CT3) 
 
 
Dado el objetivo planteado en la sección 7.1, se debe realizar la programación de las 5 OPs 
minimizando el makespan (M). Para realizar la programación se exploran 5 métodos (ver sección 
6.2). Se utiliza la regla de despacho SPT, método de simulación basado en reglas de despacho 
(SRB) priorizando los centros de trabajo CT4, CT5 y CT6 con las reglas SPT (1
er
 criterio) / 
LWKR (1er criterio de desempate) / FCFS (2do criterio de desempate) y CT1, CT2 y CT3 con las 
reglas SST / SPT / LWKR, simulación montecarlo (MC) con una muestra de tamaño 1000, y 
estrategia evolutiva (ES) con 10 segundos de tiempo CPU, cuyos resultados se resumen en la 
Figura 9. 
 
El menor valor para el makespan (115) se obtuvo con ES, sería por lo tanto la programación 
generada con este método la solución escogida, aunque es posible que ante 2 soluciones con 
similar valor de M se analicen otras medidas calculadas como las presentadas en la Figura 9. 
 
 
 
 
 
REVISTA ICHIO 
ISSN 718-9605 
Vol. 1 / Nº 2, pp. 33 – 46, Diciembre 2010 
44 
 
 
 
Figura 9 Medidas de Desempeño 
 
La Figura 10 muestra la carta Gantt de la programación obtenida con el método ES(10)/M, y en 
la Figura 11 se muestran las estadísticas por CT y OP. 
 
 
 
Figura 10 Programación obtenida con método ES 
 
La utilización (%Ut) de CT corresponde al uso productivo del CT (no considera los tiempos de 
setup). Si para los CT1, CT2 y CT3 se incluye los tiempos de setup (7, 10 y 14 respectivamente) se 
obtiene una ocupación de máquina del 17.83%, 39.13% y 40.00% respectivamente. 
 
 
 
Figura 11 Estadísticas por CT y OP 
 
 
 
REVISTA ICHIO 
ISSN 718-9605 
Vol. 1 / Nº 2, pp. 33 – 46, Diciembre 2010 
45 
 
8. Conclusiones 
 
El sistema SPS_Optimizer es un sistema prototipo que permite apoyar el proceso de la 
programación de producción de sistemas productivos tipo job shop (incluyendo los conceptos de 
multicapacidad, setups y recirculación) a través de la aplicación de variados métodos de 
programación, lo que permite obtener y comparar diferentes soluciones para un mismo problema. 
La combinación de métodos de programación que incluye el sistema, permite resolver tanto 
problemas de carácter académico como industrial. 
Los resultados de la programación se entregan por medio de tablas y carta gantt. La información 
de salida permite analizar la solución (programa de producción) obtenida, en relación al efecto 
que se produce en el sistema (utilización de centros de trabajo, atrasos de órdenes de producción, 
etc.). 
Es posible realizar alguna sensibilización de una programación variando las capacidades de uno o 
más CTs, lo que es particularmente útil cuando las capacidades de un CT son operarios que 
pueden contratarse a tiempo parcial. También estudiar el efecto que producen variaciones en 
tiempos de proceso y de setup en el desempeño del sistema puede ser útil. 
Desde un punto de vista académico, el sistema SPS_Optimizer constituye una herramienta 
flexible y eficaz para apoyar el proceso de enseñanza de programación de producción; es posible 
comprobar si se han aplicado correctamente procedimientos (algoritmos) para generar programas 
de producción, o bien, resolver rápidamente el problema de obtener un programa de producción 
como parte del análisis de un caso en administración de producción. 
 
 
 
Bibliografía 
 
 
1. Baker, K.R.: Introduction to Sequencing and Scheduling. Wiley, 1974. 
 
2. Davis, L. (1985): Job shop scheduling with genetic algorithms. Proceedings of the First 
International Conference on Genetic Algorithms and their Applications. Morgan 
Kaufmann, p.p. 136-140. 
 
3. Heizer,J. and Render,B.: Dirección de la producción y de operaciones – Decisiones 
tácticas. Pearson/PrenticeHall, 2007. 
 
4. Dorndorf, U. and Pesh,E. (1995): Evolution based learning in a jobshop environment. 
Computers and Operations Research,22, pp 25-40. 
 
5. Gonçalves, J.F., de Magalhaes Mendes, J.J., Resende, MG.C. (2005): A hybrid genetic 
algorithm for the job shop scheduling problem. European Journal of Operational 
Research, 167 (2005), pp 77-95. 
 
6. Haupt, R. (1989): A Survey of Priority Rules-Based Scheduling. OR Spektrum, 11, pp 3-
 
 
REVISTA ICHIO 
ISSN 718-9605 
Vol. 1 / Nº 2, pp. 33 – 46, Diciembre 2010 
46 
 
16. 
 
7. Jain, A.S. and Meeran,S. (1999): Deterministic job-shop scheduling: Past, present and 
future. European Journal of Operational Research, 113(2), pp 390-434. 
 
8. Jayamohan, M.S. and Rajendran,C. (2000): New dispatching rules for shop scheduling: a 
step forward. International Journal of Production Research, 38(3), pp 563-586. 
 
9. Johnson, L.A. (1974): Operations Research in Production Planning scheduling and 
Inventory Control. John Wiley and Sons, Inc. 
 
10. Morton, Th.E. And Pentico, D.W. (1993): Heuristic Scheduling Systems – with 
Applications to Production Systems and Project Management. Wiley Series in 
Engineering & Technology Management. John Wiley & Sons, Inc. 
 
11. Panwalkar, S.S. and Iskander, W. (1977): A Survey of Scheduling Rules. Operations 
Research, 25(1), pp 45-61. 
 
12. Pinedo, M: Planning and Scheduling in Manufacturing and Services. Springer, 2005. 
 
13. Pinedo, M: Scheduling – Theory, Algorithms and Systems. Springer, 3
th
 Edition, 2008. 
 
14. Salazar, E: Programación de Producción con SPS Optimizer, Actas (CD) Optima 2005, 
25 – 27.10.2005, Valdivia, Chile. 
View publication stats
https://www.researchgate.net/publication/285244333