Upload
others
View
15
Download
0
Embed Size (px)
Citation preview
Página 0 de 33
PLANEACIÓN DE PRODUCCIÓN EN MÁQUINAS IDÉNTICAS EN PARALELO CON TIEMPOS
DE ALISTAMIENTO DEPENDIENTES DE LA SECUENCIA, PARTICIÓN DE TRABAJOS Y
RESTRICCIONES DE NO SIMULTANEIDAD.
CASO DE ESTUDIO: SISTEMA DE EMPAQUE EN LÍNEA DE PAPA
Daniel Alejandro Ortiz Parra
Asesores:
Ph.D. José Fidel Torres Delgado
Fabián Sampayo (PepsiCo)
Facultad de Ingeniería
Departamento de Ingeniería Industrial
Universidad de los Andes
Bogotá D.C., Mayo de 2013
Página 1 de 33
PLANEACIÓN DE PRODUCCIÓN EN MÁQUINAS IDÉNTICAS EN PARALELO CON TIEMPOS
DE ALISTAMIENTO DEPENDIENTES DE LA SECUENCIA, PARTICIÓN DE TRABAJOS Y
RESTRICCIONES DE NO SIMULTANEIDAD.
CASO DE ESTUDIO: SISTEMA DE EMPAQUE EN LÍNEA DE PAPA
TABLA DE CONTENIDOS
1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Marco teórico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1 Formulación del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1.1 Descripción de la compañía . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1.1 Definición de la situación problemática . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1.2 Alcance del proyecto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.3 Justificación del proyecto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Situación actual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2.1 Actores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2.2 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Herramientas conceptuales de investigación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.4 Estado del arte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5 Entorno del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.1 Objetivo general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Objetivos específicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4. Metodología . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Página 2 de 33
5. Desarrollo del modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.1 Caracterización del sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.2 Supuestos del modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5.3 Formulación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5.4 Implementación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
6. Metodología heurística . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
7. Resultados finales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
8. Conclusiones y recomendaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
9. Apéndice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
9. Bibliografía . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Página 3 de 33
PLANEACIÓN DE PRODUCCIÓN EN MÁQUINAS IDÉNTICAS EN PARALELO CON TIEMPOS
DE ALISTAMIENTO DEPENDIENTES DE LA SECUENCIA, PARTICIÓN DE TRABAJOS Y
RESTRICCIONES DE NO SIMULTANEIDAD.
CASO DE ESTUDIO: SISTEMA DE EMPAQUE EN LÍNEA DE PAPA
1. INTRODUCCIÓN
En el presente documento se considera el problema de planeación de la producción en un
ambiente de máquinas paralelas considerando tiempos de alistamiento que dependen de la
secuencia, partición de trabajos y restricciones de no simultaneidad de algunos trabajos. El
objetivo del trabajo realizado es encontrar un programa de producción que logre minimizar el
máximo tiempo de terminación del último programado en cada una de las máquinas.
Inicialmente se plantea un modelo de programación lineal con el fin de obtener una solución
óptima para una serie de trabajos. No obstante, se llega a que dada la estructura del modelo
matemático y al número de restricciones y variables, es complicado llegar a una solución óptima (o
a una solución aceptable) en un tiempo de corrida razonable para el problema de interés. Por este
motivo se plantea un algoritmo heurístico basado en programación lineal, en el que se agrupan
trabajos con características similares y se planea la producción de cada grupo por aparte.
Para terminar, el algoritmo heurístico es utilizado para resolver problemas reales en un sistema de
empaque en una línea de producción de papa. Las programaciones obtenidas se comparan con las
realizadas históricamente con el fin de ilustrar como el nuevo algoritmo introduce mejoras en los
indicadores de interés, específicamente en términos de eficiencia y tasa de cumplimiento.
Este documento se encuentra estructurado de la siguiente manera: inicialmente se describe la
compañía donde se aplicará el modelo desarrollado y se plantea la solución problemática; se
presenta también el alcance ya la justificación del proyecto. A continuación se definen conceptos
clave que serán utilizados a lo largo del proyecto y que deben ser comprendidos claramente para
la correcta comprensión de la metodología desarrollada. Antes del planteamiento de una solución,
se hace un estudio bibliográfico de trabajos relacionados con el problema de interés para
posteriormente desarrollar el modelo de programación lineal de la situación de interés. Para
terminar se propone una metodología heurística enfocada específicamente al proceso de
empaque de la empresa de interés, donde se logra aumentar 21% la eficiencia del proceso.
Página 4 de 33
2. MARCO TEÓRICO
2.1 Formulación del problema
2.1.1 Descripción de la compañía [16]
PepsiCo en una compañía internacional dedicada a la producción, mercadeo y distribución
de alimentos empacados. Esta compañía nace de la fusión dada entre Pepsi-Cola Company
y Frito-Lay Inc. en el año de 1965. A partir de 1995, Frito-Lay hace presencia en
Colombia y cuenta actualmente con un 60% de participación de mercado con productos
tales como Doritos, Cheetos, Choquis, Margarita, Choclitos, Natuchips, entre otros.
2.1.1 Definición de la situación problemática
Actualmente PepsiCo realiza la planeación del empaque en la línea de papa de manera
manual basándose en la experiencia de los operarios encargados, razón por la cual estos
desconocen la calidad de las programaciones que realizan y adicionalmente no logran
cumplir los objetivos establecidos en términos de eficiencia y porcentaje de cumplimiento.
Se entiende eficiencia del sistema de empaque como la razón entre la cantidad de
kilogramos empacados y la capacidad máxima de empaque en una hora:
A continuación se presenta el desempeño en el proceso de empaque en términos de
eficiencia para el mes de febrero del año 2013.
Figura 1. Eficiencia real y esperada para enero de 2013
0.0%
10.0%
20.0%
30.0%
40.0%
50.0%
60.0%
70.0%
80.0%
90.0%
1 2 3 4 5 6 7 8 9 10 11
Efic
ien
cia
(%)
Instancia (febrero 13 a febrero 23)
Eficiencia
Real
Esperada
)0(1001181
%Kg/hora
horaempacados/Kgη
Página 5 de 33
2.1.2 Alcance del proyecto
Con el fin de lograr mejorar la planeación de la producción para el proceso de empaque, se
realiza una caracterización del problema según su estructura con el fin de plantear un
modelo de programación lineal con el que se pueda obtener una solución óptima en
distintos escenarios. Debido a que las dimensiones del problema son extensas, se procede
a utilizar un algoritmo heurístico basado en el modelo lineal con el fin de obtener buenas
soluciones en un tiempo razonable. Se propone entonces soluciones para demandas
históricas y se comparan los resultados obtenidos con las planeaciones realizadas para
estas fechas. Finalmente se realiza la comparación de la planeación actual con la nueva
propuesta con el fin de detectar los beneficios de utilizar una metodología estructurada
para solucionar el problema de la planeación de manera sistemática.
2.1.3 Justificación del proyecto
Dada la necesidad de la empresa de mejorar su estrategia de planeación del proceso de
empaque, es adecuado recurrir a una metodología que de manera estructurada permita
obtener soluciones sistemáticas para el problema en cuestión. Mediante un modelo de
matemático de programación lineal y el uso de un algoritmo heurístico será posible
encontrar buenas soluciones para secuenciar el empaque diario de distintas referencias
que son solicitadas por la gerencia de producción.
2.2 Situación actual
2.2.1 Actores
Clientes: personas o grupos que adquieren los productos ofrecidos por PepsiCo.
Gerencia de producción: grupo encargado de supervisar el correcto funcionamiento de las
distintas líneas de producción de la empresa, entre las que se encuentra la línea de
producción cuyo proceso de empaque es punto de estudio de este documento.
Gerencia de línea: encargado de liderar el grupo de personas involucradas en el proceso
de producción y empaque de papa.
Oficina de planeación de producción: personal encargado de estimar la demanda de los
distintos productos ofrecidos a nivel nacional por la empresa y quienes posteriormente
(según pronósticos de demanda) envían a la gerencia de línea la cantidad de unidades de
venta por referencia que deben producirse diariamente.
Operarios: cada uno de las personas especializadas en tareas específicas y que son
requeridos para ejecutar el proceso de producción y empaque de papa.
Página 6 de 33
A continuación se presenta las relaciones presentes entre los actores relevantes.
Realizan pedidos periódicos de productos
Estima la demanda de productos a producir
Ordena demanda de producto a líneas de producto
Decide como producir durante cada día
Figura 2. Relaciones entre los actores relevantes del problema
2.2.2 Variables
Variables determinísticas
Demanda de productos: referente a la cantidad de unidades de venta (por referencia) que
deben ser empacadas a lo largo de un día de producción.
Velocidad de empaque: dependiente del tamaño de empaque requerido.
Variables calculables
Tiempos de proceso: calculado como la razón entre la cantidad de unidades de venta y la
velocidad de empaque (según tamaño).
Tiempos de alistamiento: tiempo requerido para pasar a empacar una referencia distinta
a la que se terminó de empacar. Estos tiempos dependerán de los tamaños y de los
sabores de las referencias involucradas.
Clientes
Planeación
Gerencia de producción
Gerencia de línea
Operarios
Página 7 de 33
2.3 Herramientas conceptuales de investigación
Dada la estructura del problema y teniendo en cuenta que para la gerencia de producción la
demanda es establecida por la oficina de planeación, es adecuado modelar la situación mediante
programación lineal. Con este fin, es adecuado revisar algunos conceptos básicos de programación
lineal y de caracterización de problemas de planeación de producción.
Conceptos clave (Pinedo, 2002 & Nahmias, 2007)
Programa lineal: formulación lineal de una función objetivo y de un conjunto de restricciones.
Variables de decisión: conjunto de valores que deben determinarse para solucionar un problema.
Función objetivo: cantidad que se desea maximizar o minimizar.
Restricción: desigualdad que involucra una combinación lineal de las variables de decisión.
Solución factible: conjunto de valores de las variables de decisión con los que se cumplen todas
las restricciones del problema formulado.
Solución óptima: solución factible que maximiza o minimiza la función objetivo.
Trabajo: operación que es realizada en un máquina y tiene una duración establecida.
Máquina: recurso que procesa un trabajo durante un intervalo de tiempo.
Secuencia: orden en el que se procesa una serie de trabajos en una máquina específica.
Tiempo de proceso: tiempo requerido para realizar una tarea específica a un objeto o producto.
Fecha de entrega: fecha en la que se debe terminar el trabajo para no recibir penalización.
Un problema de programación de la producción se describe por medio de los campos α|β|γ. El
campo α describe el ambiente de las máquinas y contiene una única entrada. Por otra parte, el
campo β brinda detalles de las características del procesamiento de los trabajos y de las
restricciones; este campo puede no tener entradas o tener varias. El campo γ describe el objetivo
que va a ser minimizado y generalmente contiene una sola entrada.
Las posibles entradas para el campo α son:
Una máquina (1): el caso más básico de los posibles ambientes de maquinaria.
Máquinas idénticas en paralelo (Pm): hay m máquinas idénticas en paralelo. El trabajo j requiere
solo una operación y debe procesarse en una de las m máquinas
Página 8 de 33
Máquinas en paralelo con distintas velocidades (Qm): hay m máquinas en paralelo con diferentes
velocidades. La velocidad de la máquina i se denota vi .
Máquinas no relacionadas en paralelo (Rm): hay m máquinas diferentes en paralelo. La máquina i
puede procesar el trabajo j a una velocidad vij.
Línea de producción o Flow shop (Fm): hay m máquinas en serie. Cada trabajo debe procesarse en
cada una de las m máquinas. Todos los trabajos deben seguir la misma ruta y luego de completar
el procesamiento en una máquina el trabajo se une a la cola de la máquina siguiente.
Línea de producción flexible o Flexible flow shop (FFc): es una generalización de la línea de
producción. Hay c etapas en serie con un número de máquinas idénticas en paralelo en cada
etapa. Cada trabajo debe procesarse en cada una de las etapas.
Taller o Job shop (Jm): en un taller con m máquinas, cada trabajo tiene una ruta predeterminada.
Taller flexible o Flexible job shop (FJc): hay c centros de trabajo con un número de máquinas
idénticas en paralelo en cada centro. Cada trabajo tiene su propia ruta a seguir a través del taller.
Open shop (Om): hay m máquinas, cada trabajo debe procesarse nuevamente en cada máquina.
No obstante, algunos de los tiempos de procesamiento serán nulos. No hay restricciones respecto
al ruteo de cada trabajo en el sistema de manufactura.
Las restricciones del procesamiento se especifican en el campo β y las posibles entradas son:
Fechas de disponibilidad (rj): el trabajo j no puede iniciar su proceso hasta después de la fecha de
disponibilidad. Si rj no aparece en el campo β, el trabajo j podrá procesarse en cualquier momento.
Tiempos de alistamiento dependientes de la secuencia (Sjk): Sjk representa el tiempo de
alistamiento dependiente de la secuencia entre los trabajos j y k. Si el tiempo de alistamiento
entre los trabajos j y k depende de la máquina, entonces si incluye el subíndice i (Sijk).
Preempción (prmp): una vez iniciado el proceso de un trabajo, no es necesario mantenerlo en la
máquina hasta que sea terminado. El programador tiene permitido interrumpir el proceso en
cualquier instante de tiempo y poner otro trabajo en esa máquina. Cuando el trabajo que fue
interrumpido se pone de nuevo en la máquina, solo se procesa el tiempo que estaba pendiente.
Restricciones de precedencia (prec): uno o más trabajos deben completarse antes de que otro
trabajo pueda ser procesado. Existen distintas formas de restricciones de precedencia: si cada
trabajo tiene a lo más un predecesor y un antecesor, las restricciones son llamadas cadenas. Si
cada trabajo tiene a lo más un sucesor, las restricciones son llamadas intree. Si cada trabajo tiene a
lo más un predecesor, las restricciones son llamadas outtree.
Página 9 de 33
Fallas (brkdwn): las máquinas no están disponibles continuamente. Los periodos que la máquina
no está disponible, se asumen fijos. Si hay un número de máquinas idénticas en paralelo, el
número de máquinas disponibles en cualquier instante de tiempo es una función m(t).
Restricciones de eligibilidad de máquinas (Mj): aplica para el ambiente de manufactura de m
máquinas en paralelo. El conjunto Mj senota el conjunto de máquinas que está en capacidad de
procesar el trabajo j.
Permutación (prmu): aplica para líneas de producción en los que las colas frente a cada máquina
operan de acuerdo a la disciplina FIFO (el primero que entra es el primero que sale). La
permutación implica que el orden en el que los trabajos pasan por la primera máquina, se
mantienen a través de todo el sistema.
Bloqueo (block): aplica para líneas de producción cuando estas tienen espacio limitado entre
máquinas. Cuando el espacio está lleno, la máquina anterior a dicho espacio no podrá soltar un
trabajo que ya está completo.
No-espera (nwt): aplica para líneas de producción en las que no se permite que los trabajos
esperen entre dos máquinas sucesivas. Esto implica que el tiempo de inicio de un trabajo en la
primera máquina debe retrasarse para asegurar que el trabajo pueda ir por la línea de producción
sin tener que esperar por alguna máquina.
Recirculación (recrc): se presenta en líneas de producción o líneas de producción flexible cuando
un trabajo visita una máquina o un centro de trabajo en más de una ocasión.
Partición de trabajos (split): propiedad de un trabajo que le permite distribuir su tiempo de
proceso en distintas máquinas. Estas partes pueden o no procesarse simultáneamente.
Restricción de no simultaneidad: pareja de trabajos que no pueden procesarse simultáneamente.
El objetivo a ser minimizado es siempre una función de los tiempos de terminación de los trabajos,
que dependen de la programación realizada. El tiempo de terminación del trabajo j en la máquina i
se denota Cij. El objetivo puede ser también función de las fechas de entrega dj. Se define el
retraso del trabajo j como Lj = Cj - dj. La tardanza del trabajo j como Tj = Max(0, Lj).
Algunas funciones objetivo que pueden ser entrada en el campo γ son:
Tiempo de terminación del último trabajo que sale del sistema o Makespan (Cmax)
Tiempo de terminación total ponderado (ƩwjCj): indicador de inventario o costos de inventario.
Máximo retraso (Lmax): Max(L1, L2, ..., Ln).
Tardanza ponderada total (ƩwjTj): suma ponderada de las tardanzas teniendo en cuenta las
prioridades wj de cada trabajo.
Página 10 de 33
2.4 Estado del arte [9]
Se han realizado numerosos estudios en temas relacionados al presente proyecto,
específicamente se nota un gran interés en el tema de planeación de producción en máquinas en
paralelo a partir de los años 50. Los trabajos más significativos en este tema fueron desarrollados
por McNaughton [1] en 1959 y Hu [2] en 1961. Más tarde en 1978, Frederickson [3] y sus
compañeros implementaron la primer heurística (basada el vecino más cercano) aplicada al
problema de máquinas paralelas. También se encuentran trabajos significativos de otros autores
tales como Hahn (1989) [4] y Kim (1997) [5]. Años después en 1993, Guinet [6] propone una
heurística de dos pasos basándose en el problema de ruteo de vehículos (VRP por sus siglas en
inglés). Posteriormente en el año 2000, Xing y Zhang [7] trabajan en el problema de máquinas
idénticas en paralelo pero con dos aspectos adicionales: tiempos de alistamiento independientes
de la secuencia y partición de trabajos. Más adelante en el año 2003, Yalaoui y Chu [8] proponen
una heurística de dos pasos para solucionar el problema de planeación de la producción en
máquinas idénticas en paralelo con tiempos de alistamiento dependientes de la secuencia y con la
propiedad de partición de trabajos. Finalmente en el año 2005 Nait [9] y su grupo de trabajo
presentan una mejora del método propuesto por Yalaoui y Chu para el mismo problema de
planeación de producción basándose también en el trabajo realizado por Riotteau [10] en el 2000.
El presente trabajo estudia el problema de planeación de producción en máquinas idénticas en
paralelo con tiempos de alistamiento dependientes de la secuencia, partición de trabajos y
restricciones adicionales de no simultaneidad de algunos trabajos. La programación lineal
planteada se basa en los trabajos de Riotteau y Nait.
2.5 Entorno del problema
A continuación se describen las principales variables que pueden facilitar o inhibir el desarrollo del
proyecto, dando una descripción específica del efecto de cada variable.
Facilitadores
- Interés de la compañía: dado el interés que muestran las personas encargadas del área de
estudio, estos realizarán un mayor esfuerzo para aportar en el desarrollo del proyecto ya sea
mediante la obtención y entrega de información, la dedicación de tiempo para establecer las
prioridades de la empresa, entre otros. Este interés por el proyecto genera un ambiente de
cooperación que termina aliviando la carga del proyecto y que finalmente se puede ver reflejado
en el desarrollo a tiempo de tareas y la obtención de buenos resultados en el proyecto.
- Conocimiento y herramientas: dados los aspectos básicos del problema se ha encontrado una
metodología para encontrar una solución adecuada al problema de asignación de recursos. El
conocimiento de teorías que sean aplicables a la solución del problema y la destreza en el manejo
de software especializado para optimización es un factor de éxito del proyecto.
Página 11 de 33
Inhibidores
- Disponibilidad de la información: algunos de los datos de entrada requeridos por el modelo
propuesto pueden no existir o estar disponibles, por lo que puede requerirse dedicar tiempo a la
adquisición y caracterización de datos. La no disponibilidad de cierta información puede causar
demoras en el proyecto que finalmente afecten el cumplimiento de fechas de avances y entrega.
- Políticas de información: cierta información requerida para el desarrollo del proyecto puede ser
confidencial por lo que debe justificarse a la empresa la importancia de esta información para
obtener buenos resultados que aporten a la compañía.
- Desconocimiento operacional: debe dedicarse tiempo adicional para entender los aspectos
básicos de las operaciones que realiza la compañía con el fin de modelar adecuadamente el
problema y de este modo obtener buenas alternativas para la planeación del proceso de empaque
de la compañía. El desconocimiento de aspectos básicos de la empresa pueden generar soluciones
que no sean útiles por lo que debe dedicarse tiempo suficiente a esta labor.
- Tiempo limitado: Dado que el tiempo disponible para el desarrollo del proyecto es relativamente
corto, se requiere una adecuada planeación para culminar exitosamente los objetivos del
proyecto. Debe tenerse en cuenta entonces posibles inconvenientes con el fin de cumplir a
cabalidad con los requerimientos del proyecto.
3. OBJETIVOS
3.1 Objetivo general
Plantear una estrategia de planeación del proceso de empaque que mejore el desempeño
de la empresa en esta labor llegando a cumplir el valor meta de los indicadores de interés.
3.2 Objetivos específicos
- Modelar la situación problemática adecuadamente teniendo en cuenta supuestos y
variables de entrada relevantes.
- Analizar la sensibilidad y robustez del modelo propuesto para garantizar el
funcionamiento de este en los casos de interés de la empresa.
Página 12 de 33
4. METODOLOGÍA
Solución de problemas de ingeniería mediante programación lineal [11]
Definición del problema: inicialmente debe comprenderse el problema identificando
específicamente la situación problemática, los alcances y la justificación. Este proceso es requerido
en la solución de todo problema en Ingeniería y ya se presentó anteriormente para el caso de
estudio de PepsiCo.
Establecimiento de objetivos: luego de plantear claramente el problema deben establecerse los
objetivos que se pretenden lograr mediante el estudio que se va a realizar. Este procedimiento se
presenta de manera más detallada posteriormente en este documento.
Formulación del modelo: se plantea un modelo conceptual de la situación teniendo en cuenta los
alcances del problema y estableciendo que datos son necesarios para poder hacer inferencias
sobre el modelo.
Adquisición de datos: deben conseguirse los datos ya existentes y tomar los datos que no estén
disponibles con el fin de modelar la situación de manera adecuada y realista (teniendo en cuenta
cada uno de los supuestos del modelo).
Desarrollo del modelo: el modelo debe desarrollarse en algún lenguaje de programación en un
software especializado en la metodología de interés. Para el caso de estudio se hará uso intensivo
de Xpress (Software especializado en optimización).
Verificación: luego de la construcción del modelo, debe verificarse que este representa
adecuadamente el modelo conceptual, es decir que el modelo siga la lógica planteada. En el caso
en que no se de la verificación, debe revisarse la formulación del modelo para poder continuar.
Validación: después de verificado el modelo, debe validarse que este representa de manera
adecuada (bajo ciertos supuestos) la situación problemática de interés.
Experimentación: utilizando datos históricos se realizan distintas corridas para encontrar
soluciones al problema planteado.
Análisis de resultados: calcular variables de interés e interpretar los resultados.
Presentación de resultados: ilustrar a la compañía como la nueva estrategia de planeación de
producción afecta positivamente sus variables de interés.
Implementación: la compañía tomará la decisión de implementar o no alguna la nueva estrategia
de planeación de producción mediante la metodología desarrollada.
Página 13 de 33
Figura 3. Diagrama de flujo del desarrollo del proyecto
Definición del problema
Formulación de objetivos
Formulación conceptual del modelo
Adquisición de datos Acordar supuestos
Retroalimentación
Caracterización de datos Desarrollo del modelo
¿Modelo verificado?
¿Modelo validado?
Experimentación
Análisis de resultados
Presentación de resultados
Implementación
NO
NO
Redacción de documento final
Página 14 de 33
5. DESARROLLO DEL MODELO
5.1 Caracterización del sistema
Para el proceso de empaque de papa se dispone de 6 máquinas en paralelo, para las cuales se
debe planear (diariamente) el orden en que se empacarán las referencias demandadas. Como se
ilustra en la figura 4, la empresa ofrece distintas referencias (según gramaje del empaque) en 6
distintos sabores: natural, pollo, limón, BBQ, pollo asado y costillitas. Adicionalmente para
unidades de empaque de decenas y docenas, se tienen dos tipos de empaque: DTS (Down to
Street) y OT (Organized Trade). Las unidades DTS se empacan en bolsas transparentes, mientras
que las unidades OT se empacan en cajas de cartón.
Figura 4. Referencias
Cada una de las seis máquinas posee dos tubos en los cuales se pueden empacar referencias de
distintos tamaño pero del mismo sabor. Adicionalmente existen tiempos de alistamiento para
pasar a producir una referencia diferente a la que se terminó; para realizar un cambio de sabor en
una máquina se requiere de un lavado que tiene una duración de 90 minutos y para un cambio de
gramaje se requiere de un cambio de molde que toma un tiempo de 15 minutos. Existen algunas
excepciones para los tiempos de alistamiento requeridos: pasar de empacar natural a otro sabor
solo requiere de 15 minutos y de igual manera sucede entre los sabores pollo y pollo asado. Dado
a que cada tubo tiene la capacidad de empacar 60 unidades por minuto, estos tiempos de
alistamiento no son despreciables y es importante tenerlos en cuenta en el modelo.
Debe tenerse en cuenta que debido a características de las máquinas y a procesos que se llevan a
cabo después del empaque, existen restricciones adicionales con respecto al empaque en paralelo
de algunas referencias. Específicamente, no es posible empacar paralelamente dos referencias de
48, 115 ó 250g y de manera similar, no se deben empacar dos referencias DTS del mismo sabor
durante un mismo intervalo de tiempo.
Unidad empaque GramajeUnidades por
cajaNATURAL POLLO LIMÓN BBQ ASADO COSTILLITAS
CAJA Familiar 115 12 X X X X
Decena OT (auto) 28 4 X
Docena OT 25 6 X X X X X
25 6 X X X X
28 4 X X X X
30 4 X X X X
33 4 X X X X
28 8 X
48 5 X X
32 4 X
48 24 X X
25 60 X X X
BOLSA
CAJA
Docena DTS
Sextas
Sabritas
Página 15 de 33
Por otra parte, la gerencia de producción recibe al inicio de cada día la cantidad de unidades que
debe empacar durante un día, por lo que todos los trabajos se encuentran disponibles al inicio de
la planeación del proceso de empaque. Adicionalmente, cada uno de los trabajos puede dividirse
en varias secciones que pueden ser o no procesadas paralelamente en dos o más máquinas.
De acuerdo a las características expuestas anteriormente y mediante el uso de la notación
generalizada propuesta por Pinedo [12] el problema de interés puede verse como:
Es decir, 6 máquinas en paralelo, con partición de trabajos, tiempos de alistamiento dependientes
de la secuencia (sequence-dependent setup times), restricciones de trabajos específicos que no
pueden procesarse simultáneamente (specific job constraints) y con el objetivo de minimizar el
tiempo máximo de terminación (Makespan).
5.2 Supuestos del modelo
Dadas las características del sistema real y a los objetivos establecidos por la empresa es adecuado
suponer que tanto los tiempos de proceso como los tiempos de alistamiento son determinísticos.
Adicionalmente el modelo se basará en que siempre hay materia prima disponible, y que no se
presentan fallas en las máquinas, ni se realizan mantenimientos preventivos o similares.
5.3 Formulación
Conjuntos
Parámetros
Constantes
max6 ,, SJC|CST|SplitP sd
tiempoalprocesarcepuedennoquetrabajosV
abajos) , n} (Tr, , , {N
quinas) , m} (Má, , , {M
:
321
321
jalitrabajodelpasarparatoalistamiendetiempoS
itrabajodelprocesodetiempoP
ij
i
:
:
10:
:
quemenoryquemayornúmero
grandementearbitrariapositivonúmeroK
Página 16 de 33
Variables
Función objetivo
Restricciones (se explican detalladamente a continuación)
itrabajoelhastammáquinalaensprogramadotrabajosdecantidadZu
il después demente inmediatajjo a el traba se procesmmáquina si en la : x
mquina a en la má se procesio del trabaj si parte: y
muina en la máqitrabajoelfinalizasequeeln: tiempo eC
muina en la máqitrabajo inicia el el que se tiempo en t
ma a máquinocesa en l que se pri el trabajoe tiempo dfracción dQ
im
ijm
im
im
im
im
:
1}1,0{
1}1,0{
:
:
..min max asC
)5(,,
)4(,,)1(
)3(,
)2(,
)1(
max
1
miQyyP
Q
mjiijxKtSxC
miQtC
miCC
iPQ
imimim
i
im
ijmjmijijmim
imimim
im
M
m
iim
)9(1
)8(1
)7(
)6(
1
0
1
)1(
1
1
0
mx
mx
miyx
mjyx
N
j
jm
N
i
mNi
im
N
j
ijm
jm
N
i
ijm
)13(,,)(1
)12(,,)(
)11(,,1
)10(0
nmjiVijQttxK
nmjiVijQttxK
mjiijNxNuu
mix
ininjm
jk
kjm
jmjmin
jk
kjm
ijmjmim
iim
Página 17 de 33
Una vez definidos los conjuntos, parámetros, constantes y variables involucradas en el modelo se
presenta a continuación la construcción de las restricciones del problema mediante ejemplos
ilustrativos con el fin de establecer claramente el propósito de cada una de estas. El modelo
propuesto a continuación se basa en el trabajo propuesto por Riotteau et al., 2001 [10], Nait et al.,
(2005) [9] y Huang et al., 2010 [13]
Veamos inicialmente un problema de planeación en 2 máquinas y 3 trabajos con tiempos de
proceso de 10, 7 y 5 minutos respectivamente. Adicionalmente no se tienen en cuenta tiempos de
alistamiento entre trabajos y los trabajos 1 y 2 no pueden procesarse simultáneamente.
Una solución factible se presenta en la figura 5.
Figura 5. Solución factible
La solución factible está representada por los siguientes valores de las variables:
La ecuación (1) tiene en cuenta que la suma de las partes en las que se divide cada trabajo, debe
ser igual al tiempo de proceso de ese trabajo:
Adicionalmente la ecuación (2) garantiza que el máximo tiempo de terminación es mayor o igual a
los tiempos de terminación de cada una de las máquinas:
Por otra parte el tiempo en el que se finalice el trabajo i en la máquina m debe ser equivalente al
tiempo de inicio más la fracción de tiempo procesada [ecuación (3)]:
11
11
10
y
32
25
100
Q
5
7
10
P
33231
22221
11211
PQQ
PQQ
PQQ
iPQgeneralen i
m
im
2
1
:
miQtC imimim ,
miCCim ,max
Página 18 de 33
La ecuación (4) garantiza que si el trabajo j se procesa después del i, entonces el tiempo de inicio
del trabajo j sea mayor o igual al tiempo de finalización del i más un tiempo de alistamiento:
En general:
Se debe también tener en cuenta las restricciones (ecuación 5) referentes a la variable binaria :
- Debe tomar el valor de 1 si parte del trabajo i se procesa en la máquina m:
- Debe tomar el valor de 0 si parte del trabajo i no se procesa en la máquina m:
En cuanto a la entrada al proceso de empaque se debe cumplir que si se pasa a procesar parte del
trabajo j en la máquina m, entonces debe tomar el valor de 1 (Ecuación 6):
Para la solución factible que se presentó en la figura 5 se tiene:
En general:
)1(
)1(
322223232232
231312323121
xKtSxC
xKtSxC
mjiijxKtSxC ijmjmijijmim ,,)1(
imy
miyP
Qim
i
im ,
miCteQy imim ,)(10
jmy
1)2,3(
1)2,2(
1)2,1(
1)1,3(
1)1,2(
0)1,1(
32332232132032
22322222122022
12312212112012
31331231131031
21321221121021
11311211111011
yxxxxmj
yxxxxmj
yxxxxmj
yxxxxmj
yxxxxmj
yxxxxmj
mjyx jm
N
i
ijm 0
Página 19 de 33
De manera similar para las restricciones de salida del proceso de empaque (7), debe cumplirse que
si se pasa de procesar parte del trabajo i en la máquina m, entonces debe tomar el valor de 1.
En general:
También debe incluirse restricciones que garanticen que algún trabajo se programe al final y al
inicio en cada una de las máquinas (ecuaciones 8 y 9):
Para la solución factible:
En general:
Adicionalmente el modelo debe garantizar que no se programen consecutivamente dos partes de
un mismo trabajo (ecuación 10):
imy
1)2,3(
1)2,2(
1)2,1(
1)1,3(
1)1,2(
0)1,1(
32342332322312
22242232222212
12142132122112
31341331321311
21241231221211
11141131121111
yxxxxmi
yxxxxmi
yxxxxmi
yxxxxmi
yxxxxmi
yxxxxmi
miyx im
N
j
ijm
1
1
1
1
342242142
341241141
xxx
xxx
1
1
032022012
031021011
xxx
xxx
mxN
i
mNi
11
)1(
mxN
j
jm
11
0
mixiim 0
Página 20 de 33
También es necesario agregar restricciones adicionales para evitar la formación de sub-tours (11):
En el caso de estudio un sub-tour sería una secuencia en la que en una misma máquina se pasa a
empacar dos partes de un mismo trabajo (no consecutivamente) tal como ilustra la figura 6:
Figura 6. Sub-tour
El caso presentado en la figura 6 se tendría las siguientes restricciones:
Para probar como funcionan estas tres ecuaciones, basta con sumarlas y notar que para el sub-
tour en cuestión no existirían para que se cumpla la desigualdad .
Finalizando, se requieren las restricciones para los trabajos que no pueden procesarse
simultáneamente (Ecuaciones 12 y 13). Teniendo en cuenta que para el caso ejemplo los trabajos
1 y 2 tienen esta restricción, se utiliza la solución factible ilustrada en la figura 7 con el fin de
aclarar el funcionamiento de las restricciones propuestas.
Figura 7. Nueva solución factible
Si se pasa a procesar el trabajo 1 en la máquina 2, debe haberse terminado de procesar el trabajo
2 en la máquina 1:
Si se pasa a procesar el trabajo 1 en la máquina 1, entonces debe haberse terminado de procesar
el trabajo 2 en la máquina 2:
mjiijNxNuu ijmjmim ,,1
23
23
23
1323212
2121222
3222232
xuu
xuu
xuu
suim ' 69
222211222211311211011
111122111122311211011
)()1(
)()()(
QttQttxxxK
QttKQttxxxK
212112212112312212012
121221121221312212012
)()1(
)()()(
QttQttxxxK
QttKQttxxxK
Página 21 de 33
5.4 Implementación
A continuación se ilustran varios casos hipotéticos utilizados para el proceso de validación del
modelo de programación lineal que fue explicado en la sección anterior; el modelo se programó
en el software Xpress IVE.
Caso 1:
- 3 trabajos, 2 máquinas
- Tiempos de proceso: 10, 7 y 5 minutos
- Tiempos de alistamiento: 0 minutos
- Los trabajos 1 y 2 no pueden procesarse simultáneamente
Para el caso 1, se llega a la siguiente solución óptima:
Figura 8. Solución óptima encontrada para el caso 1
Caso 2:
- 5 trabajos, 2 máquinas
- Tiempos de proceso: 8, 7, 15, y 3 minutos
- Tiempos de alistamiento: 1 minuto entre los trabajos 1,2 y 3; 2 minutos entre los trabajos
4 y 5; 0 minutos para otros casos.
- Los trabajos 2 y 4 no pueden procesarse simultáneamente
Para el caso 2, se llega a la siguiente solución óptima:
Figura 9. Solución óptima encontrada para el caso 2
Página 22 de 33
Caso 3:
- 6 trabajos, 4 máquinas
- Tiempos de proceso: 7, 5, 3, 9, 2 y 8 minutos
- Tiempos de alistamiento: 1 minuto entre los trabajos pares y 2 minutos entre los trabajos
impares; 0 minutos para otros casos.
- Los trabajos 3 y 5 no pueden procesarse simultáneamente
Para el caso 3, se llega a la siguiente solución óptima:
Figura 10. Solución óptima encontrada para el caso 3
Como se observa en las soluciones encontradas para los 3 casos ilustrados anteriormente, el
modelo funciona tal como se esperaba por lo que el siguiente paso es probar con instancias más
grandes (cercanas al caso real) con el fin de evaluar la posibilidad de solucionar el problema
directamente con el modelo propuesto. En la figura 11 se muestra el resumen de las corridas
realizadas, puede observarse que dependiendo del número de restricciones y variables el modelo
no llega a la solución óptima con certeza pues las soluciones encontradas llegan a tener un GAP
entre el 19 y el 39% después de más de 10 horas de corrida.
Figura 11. Resumen de corridas
amente simultáneprocesarse pueden no que trabajos de parejas de Cantidad*
Página 23 de 33
A partir del resultado obtenido, se puede inferir que para casos más grandes (caso real) no será
posible llegar a la solución óptima en un tiempo razonable. No obstante se realizó una corrida con
el fin de poner a prueba esta afirmación, y se corrió el programa para un caso con 15 trabajos que
deben programarse en 6 máquinas. El programa logra obtener varias soluciones, pero la mejor
solución encontrada tiene un GAP del 92% por lo que no se conoce la calidad de la solución
encontrada. Por este motivo debe acudirse a una metodología alterna con la cual puedan
encontrarse buenas soluciones al problema real.
Históricamente se han utilizado dos enfoques para la solución de problemas similares
(programación en máquinas en paralelo con partición de trabajos y tiempos de alistamiento
dependientes de la secuencia) que son: métodos híbridos basados en programación lineal (Nait et
al., 2006) y metaheurísticas (algoritmo genético (Tavakkoli, 2009 & Vallada, 2011), búsqueda tabú
(Bilge, 2004; Eksioglu 2008 & Celik, 2011), enfriamiento simulado, colonización de hormigas, entre
otros).
Con el fin de seleccionar la metodología más adecuada para solucionar el problema, se estudiaron
distintos aspectos adicionales de las características del sistema real, de la estructura de las
soluciones óptimas y de las estrategias utilizadas para la programación en la empresa. Se
encontraron aspectos clave que al tenerse en cuenta reducen la complejidad de solución:
- Los tiempos de alistamiento largos (90 minutos) se evitan al máximo y se trata de tener
máximo uno de estos tiempos muertos en un día de producción
- La cantidad de particiones de trabajos es pequeña debido a que estas introducen más
tiempos de alistamiento (de 15 minutos)
- La cantidad de trabajos no simultáneos tiende a ser pequeña
- Las soluciones óptimas tienen a ser balanceadas (i.e. los tiempos de terminación de cada
máquina son similares o iguales)
Teniendo en cuenta las anteriores características se propone una metodología heurística
“avariciosa” basada en programación lineal buscando obtener soluciones balanceadas y evitando
al máximo los tiempos de alistamiento grandes.
Página 24 de 33
6. METODOLOGÍA HEURÍSTICA
Debido a la estructura del problema y a la cantidad de variables y restricciones presentes en el
modelo de programación lineal propuesto aplicado al sistema real, no es posible encontrar buenas
soluciones en un tiempo razonable. Por este motivo se propone a continuación una metodología
basada en la experiencia de los operarios, las características de soluciones óptimas y aspectos
adicionales con el fin de encontrar buenas soluciones para el problema en cuestión.
Teniendo en cuenta que para el caso de estudio se debe programar una cantidad de trabajos
variable (entre 10 y 24 trabajos) en seis máquinas, la metodología propuesta se basa en agrupar
los trabajos según sabores y posteriormente calcular el número de máquinas requeridas para
empacar cada sabor teniendo en cuenta el porcentaje de participación de cada uno de estos en el
total de referencias a empacar. Haciendo uso del número de máquinas requeridas por sabor se
procede a utilizar el modelo de programación lineal para encontrar el programa óptimo de
empaque para cada sabor. A continuación se presenta el pseudo-algoritmo de la metodología:
Fin
máquinasR(m en saboresde resto el programar
máquinasmR(m en naturaly escogido saborel programa se
entero un a cerca más estém(m que el para saborel escoger
m(m calcular natural a diferente saborcada para Paso
6 paso al ir contrario lo de
5 paso al ir entonces m
4 paso al ir entonces m
:es )(m natural saborpara requeridas máquinas el siPaso
P
P6m
saborcada para requerido máquinas de aproximado número el calcularPaso
jsabordelsreferenciadenúmeronpnP
tos)alistamien o(incluyend total proceso de tiempo el calcular saborcada paraPaso
x de entera parte la E(x) Sea
x de decimal parte la D(x) Sea
x de cercano más entero al redondear función la R(x) Sea
j
j1
j1
j1
1
1
1
j
total
total
j
j
n
i
ijtotal
j
j
j
j
)
)
)
):4
35.1
85.0
:3
:2
:)1(15
:1
1
Página 25 de 33
Fin
máquinasR(m en saboresde resto el programar
máquina 1 en natural saborel programar :6 Paso
Fin
máquinasR(m en saboresde resto el programar
máquinas E(menE(m programa se
máquinasmR(D(m en naturaldeD(my escogido saborel programa se
entero un a cerca más estém(D(m que el para saborel escoger
m(D(m calcular natural a diferente saborcada para Paso
j
j
11
j11
j1
j1
)
)
))
)))
))
)):5
La metodología propuesta se implementó mediante el uso de macros de Excel, donde el usuario
final (operador de línea) debe ingresar las unidades de venta que se deben empacar en un día.
Inmediatamente después de ingresados los datos, se calcula en número aproximado de máquinas
requeridas por sabor y también la recomendación de cómo realizar la programación (que puede
incluir combinación de sabores). Finalmente se debe ejecutar el algoritmo principal de la macro
que automáticamente genera varios archivos de datos que deben ejecutarse en Xpress con el fin
de encontrar a programación óptima para cada sabor en el número de máquinas establecido.
Con fines ilustrativos se presenta en la figura 12 la interfaz del usuario para uno de los casos
solucionados. De igual manera se ilustra en la figura 13 el resultado obtenido para este día.
Figura 12. Interfaz
Página 26 de 33
Figura 13. Diagrama de Gantt de la solución obtenida
Se puede observar en este caso que la solución encontrada es bastante balanceada (los tiempos
de terminación en cada máquina no están muy alejados) y adicionalmente se logra un tiempo
máximo de terminación de 1170 minutos (19.5 horas), es decir que se puede cumplir con el
empaque de todas las referencias solicitadas. Con el fin de evaluar la calidad de las soluciones, se
utilizó la eficiencia del proceso de empaque, obteniendo para el caso de la figura 13 una eficiencia
del 91.4% (ver ecuación 0), valor superior a la meta establecida del 85% de eficiencia. Como se
verá en la siguiente sección, para cada uno de los días de febrero se logra obtener un tiempo
máximo de terminación inferior a 24 horas y en promedio se logra una eficiencia del proceso de
empaque superior a la meta establecida por la gerencia.
Página 27 de 33
7. RESULTADOS FINALES
Se solucionaron 11 casos reales de requerimientos diarios de empaque. A continuación se
presentan los resultados obtenidos para los distintos casos y se compara la eficiencia de las
soluciones propuestas con las programaciones realizadas en esas mismas fechas.
Instancia Fecha Tubos Trabajos Sabores Parejas de no simultáneos
Makespan (horas)
Eficiencia
Real Heurística
1 feb-13 12 17 3 10 20.16 73.7% 86.0%
2 feb-14 12 15 3 5 15.67 65.5% 80.3%
3 feb-15 12 19 3 14 20.83 62.1% 90.4%
4 feb-16 12 16 4 7 21.17 61.0% 84.6%
5 feb-17 12 12 4 2 12.67 48.0% 89.1%
6 feb-18 12 16 4 10 18.00 68.9% 89.4%
7 feb-19 12 16 3 7 18.83 67.6% 88.5%
8 feb-20 12 15 4 5 20.33 66.1% 94.7%
9 feb-21 12 16 4 12 19.50 70.8% 91.4%
10 feb-22 12 10 4 2 17.90 65.8% 76.8%
11 feb-23 12 17 4 10 20.83 69.5% 82.2%
65.4% 86.7%
Figura 14. Síntesis de resultados
En la tabla presentada en la figura 14 se sintetizan los resultados obtenidos para 11 días donde se
puede observar que en la mayoría de los días, 24 horas es tiempo suficiente para lograr empacar
los pedidos solicitados por la oficina de planeación. Adicionalmente se observa una mejora de la
eficiencia del proceso al utilizar la metodología propuesta; en promedio se logra una mejora del
21.3% llegando a un 86.7% de eficiencia (superior al 85% establecido como meta).
Adicionalmente con el fin de ilustrar un poco más la mejora que introduce la metodología en
términos de eficiencia, se ilustra en la figura 15 el comportamiento de este indicador de interés
para su valor real y el valor obtenido mediante la heurística. Se puede observar que se logra una
mejora significativa en términos de eficiencia del proceso de empaque.
Página 28 de 33
Figura 15. Eficiencia
8. CONCLUSIONES Y RECOMENDACIONES
Se logró construir un modelo de programación lineal que representa adecuadamente un
sistema real en un ambiente de máquinas paralelas, con tiempos de alistamiento,
partición de trabajos y restricciones adicionales de trabajos que no pueden procesarse
simultáneamente. No obstante, se encontró que para casos reales y específicamente para
el caso de estudio, no es posible encontrar buenas soluciones con este modelo en un
tiempo razonable para el problema de interés.
Mediante el planteamiento de una metodología heurística basada en programación lineal
se logró construir un algoritmo que encuentra una buena programación de los trabajos
teniendo en cuenta aspectos tales como las características de las soluciones óptimas y
experiencia de los operadores de línea.
Utilizando la metodología heurística propuesta se logra mejorar la eficiencia del proceso
de empaque en un 21.3%. Con este aumento en este indicador de interés la compañía
logra superar la meta establecida por la gerencia de la planta.
Como trabajo futuro puede plantearse otros algoritmos heurísticos o meta-heurísticos con
los que se logren soluciones aún mejores que las obtenidas.
0.0%
10.0%
20.0%
30.0%
40.0%
50.0%
60.0%
70.0%
80.0%
90.0%
100.0%
1 2 3 4 5 6 7 8 9 10 11
Efic
ien
cia
(%)
Instancia (febrero 13 a febrero 23)
Eficiencia
Real
Heurística
Página 29 de 33
Apéndice A1: cálculo de los parámetros de la metodología heurística
En el paso 3 de la metodología heurística se utiliza como criterio el número de máquinas
requeridas para empacar sabor natural para decidir si este sabor se combina o no con otro. En
caso de que este número tome un valor entre 0.85 y 1.35 las referencias de sabor natural se
programan en una sola máquinas y en caso contrario se combina este sabor con otro.
La fijación de estos valores se realizó probando distintos valores con el fin de encontrar los
parámetros con los cuales se obtiene (en promedio) el menor tiempo máximo de terminación en
todas la máquinas. A continuación en la figura 16 se ilustra el procedimiento realizado.
Figura 16. Fijación de parámetros de la metodología heurística
Página 30 de 33
Figura 16 (continuación). Fijación de parámetros de la metodología heurística
Se observa en la figura 16 que al fijarse el límite superior en 0.85 la metodología logra un mejor
desempeño en términos de tiempo máximo de terminación en todas las máquinas. Por otra parte
la el límite inferior se observa que es equivalente seleccionar un valor entre 0.85 y 0.95 para
obtener el mejor desempeño. Se encuentra que al reducir el límite inferior, el tiempo máximo de
terminación aumenta de manera considerable.
Página 31 de 33
BIBLIOGRAFÍA
[1] McNaughton, R. Scheduling with deadlines and loss functions. Management Science 6, pp. 1-12. 1959
[2] Hu, T. Parallel sequencing and assembly line problems. Operations Research 9, pp. 841-948. 1961.
[3] Frederickson, G., Hecht, M., Kim, C. Approximation algorithm for some routing problems. SIAM journal
on Computing 7, pp. 178-193. 1978.
[4] Hahn, C., Bragg, D. & Shin, D. Impact of the setup variable on capacity and inventory decisions. Academic
Management Review 13, pp. 91-103. 1989.
[5] Kim, S. & Bobrowski, P. Scheduling jobs with uncertain setup times and sequence dependency.
International Journal of Management Science 25, pp. 437-447. 1997.
[6] Guinet, A. Scheduling sequencing-dependent jobs on identical parallel machines to minimize completion
criteria. International Journal of Production Research 31, pp. 1579-1594. 1993.
[7] Xing, W. & Zhang, J. Parallel machine scheduling with splitting jobs. Discrete Applied Mathematics 103,
pp. 259-269. 2000.
[8] Yalaoui, F. & Chu, C. An efficient heuristic approach for parallel machine scheduling with job splitting and
sequence-dependent setup times. IEE Transactions 35, pp. 183-190. 2003.
[9] Nait, T. & Yalaoui, F. A linear programming approach for identical parallel machine scheduling with job
splitting and sequence-dependent setup times. International Journal of Production Economics, Volume 99,
Issue 1, pp.63-73, February 2006.
[10] Riotteau, G., Scaloni, O., Néron, E. Ordonnancement sur des machines parallèles identiques avec
splitting et temps de preparation dependants de la sequence. Proceeding of MOSIM’ 01, pp.69-74, 1990.
[11] Banks, J. Discrete events system simulation. Prentice-Hall, 2010.
[12] Pinedo, M. Scheduling: theory, algorithms and systems. Prentice-Hall, 2002.
[13] Huang, S., Cai, L. & Zhang, X. Parallel dedicated machine scheduling problem with sequence-dependent
setups and single server. Computers & Industrial Engineering, Volume 58, Issue 1, pp. 165-174, 2010.
[14] Nahmias, S. Análisis de la producción y las operaciones. McGraw-Hill, 2007.
[15] Conway, R., Maxwell, W. & Miller, L. Theory of scheduling. Dover Publications, 2003.
[16] PepsiCo, Inc. Disponible online en http://secfilings.nasdaq.com
[17] Tavakkoli, R. & Taheri, F. Design of a genetic algorithm for bi-objective unrelated parallel machines
scheduling with sequence-dependent setup times and precedence constraints. Computers & Operations
Research, Volume 36, Issue 12, pp. 3224-3230, December 2009.
Página 32 de 33
[18] Vallada, E. & Ruiz, R. A genetic algorithm for the unrelated parallel machine scheduling problem with
sequence dependent setup times. European Journal of Operations Research, Volume 211, Issue 3, pp. 612-
622, June 2011.
[19] Bilge, U., Kirac, F., Kurtulan, M. & Pekgun, P. Tabu search algorithm for parallel machine total tardines
problem. Comput. Oper. Res. 31, pp.397-414, 2004.
[20] Celik, C. & Saricicek, I. Two meta-heuristics for parallel machine scheduling with job splitting to
minimize total tardiness. Applied Mathematical Modeling 35, pp. 4117-4126, 2011.
[21] Eksioglu, B., Duni, S. & Jain, P. A tabu search algorithm for the flowshop scheduling problem with
changing neighborhoods. Computers & Industrial Engineering 54, pp. 1-11, 2008.
[22] Leite, P. & Gómez, M. Exact algorithms for a scheduling problem with unrelated parallel machines and
sequence and machine-dependent setup times. Computers & Operations Research, Volume 35, Issue 4, pp.
1250-1264, April 2008.
[23] Kim, Y., Shim, S., Kim, S., Choi, Y., Yoon, H. Parallel machine scheduling considering a job splitting
poperty. Int. J. Prod. Res. 42, pp.4531-4546, 2004.
[24] Morton, T. & Pentico, W. Heuristic scheduling systems. With applications to production systems and
project management. John Wiley & Sons, Inc. ,1993