Problemas MLLS(Multilevel-lot sizing)

Los problemas MLLS (Multilevel-lot sizing) hacen parte de los problemas clásicos de MRP(Planeación de requerimientos de los materiales) que básicamente están definidos para establecer el articulo adecuado, en la cantidad adecuada y en el momento adecuado(Joseph Orilcky 1975).

A su vez esta puede ser definida  como un grupo de técnicas que utiliza los datos de inventario, las estructuras de productos, y los planes maestros de producción para determinar los materiales requeridos. La determinación del tamaño de lotes multinivel es un problema al cual se enfrentan las empresas a menudo organizando sus planes de producción. Su objetivo principal es determinar el tamaño óptimo del lote y de inventario para minimizar  el costo (de producción, inventarios, costo de nuevo el pedido, y otros). Este problema también puede ser clasificado en diferentes categorías de acuerdo a las estructuras de los productos (sistema de un solo nivel, montaje en serie, los sistemas generales ...) y según las estructuras de la capacidad (sin capacidad determinada, capacitados único recurso, y capacitado a varios recursos).

Aunque los modelos con capacidad determinada son mejores, en la práctica los modelos sin límite de tamaño son  utilizados más frecuentemente debido a que la implementación de los anteriores requiere muchos datos que las empresas no son capaces o simplemente no quieren recoger.

El propósito del artículo es presentar la solución al problema de determinación del tamaño del lote multinivel por medio de un algoritmo de enjambre de partículas.

Solución de problemas MLLS

Para la solución de estos problemas generalmente se usaban métodos heurísticos (basados en la experiencia), pero con el avance de la computación (EMC) se comenzó a usar herramientas tales como la simulación y el uso de algoritmos tales como el de enjambre de partículas (Particle Swarm Optimization(PSO)), el cual fue desarrollado por Kennedy y Eberhart en 1995, como un método de cálculo que optimiza un problema de forma iterativa tratando de mejorar una solución de candidatos en relación con a una determinada medida de la calidad. El algoritmo de enjambre de partículas optimiza un problema teniendo una población de soluciones candidatas, aquí llamado partículas, y moviendo estas partículas en torno al espacio búsqueda a través de unas fórmulas matemáticas simples sobre la velocidad y la posición de la partícula.

El movimiento de cada partícula es influenciada por su mejor posición local conocida y se orienta también hacia las mejores posiciones conocidas en el espacio de búsqueda, y son actualizadas como una mejor posición cuando se encuentran con otras partículas. Esto mueve el enjambre hacia las mejores soluciones. La intención original de PSO fue simular gráficamente la coreografía elegante, pero impredecible de una bandada de aves, pero ahora se está aplicando en diferentes campos de la investigación de operaciones.

Para la solución de estos modelos se debe establecer el modelo matemático a utilizar, el esquema adecuado para el PSO y por ultimo a través de la simulación llevar el problema MLLS a su nueva posible solución.

Modelo Matemático

Estos problemas poseen tres estructuras de producto (1) estructura de montaje, (2) estructura arborescente (Ramificación)  y la (3) estructura general. Este modelo matemático representa un conjunto de nodos donde cada nodo corresponde a un artículo y el limite (i,j) entre el nodo i y el nodo j quiere decir que el articulo i es directamente requerido para montar el articulo j. Donde      R^-1(i) y R(i) para representar al inmediato predecesor y al sucesor del nodo i, mientras que R´ ^-1(i) denota a todos los predecesores del nodo i. Un ejemplo según la imagen R^-1(1)={2,3} , R´ ^-1(1)={2,3,4,5} para el nodo 1 y para el nodo 4, R-1(4)={2,3} , R´ -1(4)={1,2,3}.

Tipos de Estructuras

Se asume que la estructura de producción solo incluye un solo producto final, los costos variables y los costos de producción no son  tomados en cuenta, el lead time= 0 (tiempo de reorden del pedido), el inventario inicial (I_i,0= 0  ∀ i). los problemas de MLLS son programas enteros mixtos, y para su modelación se usara la siguiente denotación:

·         i índice del articulo

·         C_i,j Cantidad de articulo i para producir un artículo j

·         H_i Costo de tener en inventario para articulo i

·         K_i Costo de puesta en marcha del articulo i

·         L_i Lead Time para montar, comprar o manufacturar el articulo i

·         L_i.t Nivel de inventario i al final del periodo t

·         A_i,t Variable binaria para capturar el costo de puesta en marcha del articulo i entregada en el tiempo t

·         D_i,t Requerimientos para el articulo i en el tiempo j

·         P_i,t  Cantidades de producción/reposición para i en el tiempo t

·         M un número muy grande

·         N  El número total de artículos

·         T La longitud del horizonte de producción

La matriz de decisión:

Función Objetivo

Restricciones

La función objetivo es la suma de los costos de puesta en marcha y de mantenimiento de inventarios para todos los artículos dentro del horizonte de producción. La primera restricción establece el balance entre la ecuación de producción y la de reposición del inventario y la demanda. La segunda restricción proporciona la fórmula para calcular la demanda interna. La tercera restricción garantiza que el tamaño de la reposición de cierto periodo depende de la decisión de puesta en marcha de periodos anteriores. La cuarta restricción garantiza que el costo de puesta en marcha tendrá valor cuando un lote sea comprado o producido y por último que los atrasos no son permitidos y que la producción es mayor o igual que cero.

Esquema para el algoritmo PSO

Como previamente se había nombrado el algoritmo PSO es capaz de encontrar la solución óptima de un conjunto de partículas (candidatas a solución) a través de fórmulas simples de velocidad y aceleración para encontrar la posible ubicación de la partícula es así que la elección de su esquema se define en la elección de la ecuación que definirá el modelo de la simulación:

 Velocidad(V)

·         Velocidad+Velocidad

·         Velocidad-Velocidad

·         Posicion+Velocidad

·         Pocision-Posicion

·         Coeficiente*Velocidad

Para más información sobre la elección del esquema a utilizar buscar  las siguientes referencias:

Pseudocodigo del algoritmo PSO

Marcos experimentales y  simulación

Luego de tener el modelo matemático listo y el esquema del algoritmo PSO se va a la obtención de resultados por medio de la simulación aqui un ejemplo:

REDES NEURONALES BASADAS EN LA OPTIMIZACION

La inmensa potencia de cálculo de los sistemas neuronales para resolver problemas de percepción, con gran cantidad de datos, alcanzan una gran capacidad de procesamiento. Las estrategias de el cálculo neuronal  se han adaptado estos últimos años para resolver problemas de optimización. Las redes neuronales son una gran red paralela de simples procesadores  interconectados (neuronas) donde cada neurona tiene un conjunto de entradas (para otras neuronas) y calcula una salida que es propagada a los nodos que se encargan de esta (salida). Así podemos decir que las redes neuronales están compuestas por la neurona individual, la red colectiva,  los pesos (ganancia) asociados con las interconexiones entre las neuronas y la activación de la función de cada neurona. En los mapas de las redes se muestra la entrada de un vector de un espacio a otro.

Considerando una neurona (como se muestra en la figura) 

La neurona tiene n entradas(X_I , i= 1, 2,…..,n),  de sus neuronas vecinas y su valor tiende a ser igual a 1.cada entrada tiene un peso W_I asociado a ella, la suma ponderada de las entradas determinada el estado o actividad de una neurona, y es dado por : 

Una funcion simple es proporcionada para realizar un mapa de n espacios de entrada con un espacio de salida dirigido hacia sus vecionos. La salida de una neurona es una funcion de sus estados y puede denotarse como f(a). Usualmente no se producira una salida a menos que el nivel de activacion del nodo exceda un valor de umbral.

La salida de cada neurona es usualmente descrita por la siguiente función:

Y se puede mostrar graficamente de la siguiente forma:

La funcion puede manejar grandes, medianas o pequeñas señales de entrada. La pendiente de la funcion f(a) representa la ganancia disponible. Ya que la salida de la neurona depende de las entradas y del valor umbral, cada neurona puede ser considerada como un procesador separado operando en paralelo con otras neuronas. El proceso consiste en determinar el valor de los pesos W_i  ya que estos nos conducen a una optima asociacion de las entradas y la salidas de la red neuronal.

Varios modelos de las redes neuronales se han propuesto para reflejar las caracteristicas fundamentales de una neurona, estas arquitecturas difieren unas de las otras en cuanto al numero de neuronas en la red, la naturaleza de las funciones de umbral, la conectividad de cada neurona y el aprendizaje del procedimiento.

Un tipico modelo es el multilayer feedforwars que mostramos a continuación:

En esta figura los arcos representan la unidireccional comunicacon feedforward (alimento hacia delante), como enlace entre cada neurona. Un peso o ganancia asociado con cada conexión, controla el paso de una salida a una conexión, el peso puede ser positivo o negativo dependiendo de lo exitada o inhibitoria que este una neurona. Las ventajas de tener varias interconexiones es que pueden actuar como depositos para la informacion que se contiene en la red.

La red tambien esta capacitada para minimizar el error cuadratico entre la actual salida y el destino de salida de todos los patrones de entrada, el error es minimizado por los ajustes del peso asociado con varias interconexiones, los pesos deben ser variados para minimizar el error en la salida de cada nodo.

Para apreciar mejor miremos esta ilustración

Esta red esta capacitada para trazar la relacion entre el desplazamiento angular, la velocidad angular y los angulos de transmicion. Las entradas a las 5 neuronas en la capa de entradas incluyen 3 longitudes de enlaces de el mecanismo (r1,r2 y r3) y el desplazamineto y velocidad angular del enlace de entrada (Ө1 y Ө2). Las salidas de las 6 neuronas en la capa de salidas incluyen la posicion y velocidad angular de los enlces de salida (Ө3,w3,Ө4 y w4), el angulo de transmicion (y) y la ventaja mecanica (n) de el mecanismo.

Las redes pueden insertar varias posibles combinaciones de valores de r2,r3,r4,Ө2 y w2 abasteciendo los correspondientes valores de Ө3,Ө4,w3,w4,y e n. La diferencia entre los valores previstos por las redes y la actual salida es usada para ajustar la interconeccion del peso, tal que el error cuadratico en la salida de los nodos es minimizado. Una vez capacitada, la red proporciona un rapido y eficiente esquema de los mapas de las entradas con las deseadas salidas en el mecanismo de 4 barras. Se puede notar que las explicitas ecuaciones relacionadas de r2,r3,r4,Ө2 y w2 y la cantidad de salidas Ө3,Ө4,w3,w4,y e n no han sido programadas en la red, mas bien, la red aprendio a relacionarlas en el proceso de capacitarse para ajustar los pesos asociados con las interconecciones.

Bibliografia: A. K. Dhingra and S. S. Rao, A neuronal network based approach to mechanical design optimization, Engineering Optimization, Vol 20

JMT (Java Modeling Tools)

JMT (Java Modeling Tools) es una herramienta para la evaluación del desempeño, la capacidad de planificación y modelado de sistemas informáticos y de comunicación basados en redes de colas. Esta cuenta con un conjunto de numerosos instrumentos basados en la técnica de algoritmos para el análisis exacto, asintótico y de simulación de modelos de redes de colas, ya sea con o sin solución Product-Form. Los modelos pueden ser descritos ya sea a través de diálogos del asistente o con una interfaz gráfica fácil de usar. La suite JMT se compone de seis herramientas que apoyan los diferentes análisis que se usan frecuentemente en los estudios de capacidad de planificación, estas son JMT incluye herramientas para la caracterización de la carga de trabajo (JWAT), solución de redes de colas con algoritmos de análisis(JMVA), simulación de modelos de colas de propósito general (JSIM), la identificación de cuellos de botella (JABA), y el apoyo a la docencia para los modelos de cadena de Markov subyacente sistemas de colas (JMCH ) descritas más a profundidad a continuación:

Arquitectura del Simulador

·         JSIMwiz: un simulador de eventos discretos para el análisis de modelos de redes de colas. El motor de simulación apoya varias distribuciones de probabilidad para la caracterización de los tiempos de servicio y los tiempos entre llegadas. También apoya el estado independiente de las estrategias de enrutamiento, por ejemplo, de Markov o round robin, así como el estado que dependen de las estrategias, por ejemplo, el enrutamiento en el servidor con la utilización mínima, o con el tiempo de respuesta, o con un mínimo de longitud de la cola. El motor de simulación soporta varias características extendidas no permitidas en los modelos Product-Form, es decir, la capacidad finita de regiones (el bloqueo), servidores que suministran simultáneamente y las clases de prioridad. El análisis de la simulación de los resultados on-line emplea técnicas de detección de transitorios basados en el análisis espectral.

·         JSIMgraph: una sencilla interfaz gráfica para el simulador de motor utilizado por JSIMwiz. Lo integra de las mismas funcionalidades de JSIMwiz con un espacio de trabajo gráficamente intuitivo. Este permite una fácil descripción de la estructura de la red, así como una definición simplificada de las características de ejecución como de las regiones de bloqueo. Las topologías de red se pueden exportar en los formatos de imagen vectorial o raster.

·         JMVA: Creado para el análisis exacto de modelos de redes de cola Product-Form de una clase o multiclase, ya sea de procesamiento abierto, o de las cargas de trabajo cerradas o mixtas.  Se usa el clásico algoritmo de solución del MVA. La estructura de red se especifica por los asistentes de texto, con la conversión de funciones de probabilidades a las relaciones de visita promedio (y viceversa).

·         JMCH: se aplica una técnica de simulación para resolver un modelo de una sola estación, si la cola es finita (M/M/1/k) o con cola infinita (M/M/1), y muestra la base de la cadena de Markov. También es posible cambiar dinámicamente la velocidad de llegada y el tiempo de servicio del sistema.

·         JABA: una herramienta para la identificación de cuellos de botella en redes cerradas de la forma Product-Form. La herramienta es compatible con modelos con un máximo de tres clases de trabajo. Es posible identificar posibles cuellos de botella que corresponde a las diferentes mezclas de clases de clientes. Los modelos con miles de colas pueden ser analizados de manera eficiente. la saturación de los sectores, es decir, la mezcla de clases de clientes que saturan más de un recurso al mismo tiempo, se identifican.

·         JWAT (caracterización de la carga de trabajo): apoya la fase de caracterización de la carga de trabajo, con énfasis en los datos de registro Web. Algunos de los formatos estándars del archivo de entrada se proporcionan (por ejemplo, Apache HTTP archivos de registro), y los formatos personalizados también se pueden especificar. Los datos importados inicialmente pueden ser analizados utilizando técnicas estadísticas descriptivas (por ejemplo, los medios, las correlaciones, histogramas, diagramas de caja, diagramas de dispersión), ya sea para datos univariados o multivariados. Algoritmos para la ampliación de datos, extracción de la muestra, el filtrado de valores atípicos, identificación de las similitudes en los datos de entrada que se proporcionan. Estas técnicas permiten determinar el grupo de centroides, y la estimación de la media de las demandas de carga de trabajo y el servicio que se utilizará para el modelo de parametrización.

Ejemplo de un diagrama de secuencia de un flujo de mensajes. Las etiquetas (Delay:d) indica el tiempo transcurrido antes de que la simulación de entrega de los mensajes

JMT es una gran herramienta que nos permite tomar buenas decisiones de una manera más rápida y fácil pero no se debe olvidar que son respuestas a travez de simulaciones, estos modelos pueden fallar o producir resultados imprecisos, que generalmente se dan por la falla al elegir el modelo estadístico adecuado , una mala modelación y descripción para nuestro problema.

JMT es un programa de licencia gratis echo para los mas expertos y para los que menos experiencia tengan sobre el tema, aquí esta el enlace donde lo pueden descargar JMT Software 

Interfaz del JMT

APLICACIÓN DE LA TEORÍA DE COLAS EN LOS CALL CENTER

Los Call Centers son centros de atención de llamadas en donde se recibi y transmite un amplio volumen de llamadas a través del teléfono; para poderlo representar matemáticamente y para lograr analizar una variedad de problemas de optimización de revelancia, como por ejemplo para determinar en qué horarios se necesita incorporar más cantidad de personal, de lineas, de posiciones de trabajo y para analizar la impaciencia del cliente mientras espera ser atendido por el agente, es necesario modelar el Call Center como un sistema de colas. 

En este sistema las entidades que arriban a él son las llamadas de los clientes, los servidores son los agentes y las colas son los espacios virtuales en donde las llamadas esperan la atención de los agentes.

Los tiempos entre llegadas y los tiempos de servicio siguen disribuciones exponenciales con medias conocidas; las tasas de llegada al sistema, cantidad de llamadas por  intervalo de tiempo, seguirán una distribución de Poisson no estacionario ya que las tasas de llegada varian con el tiempo. Sin embargo se utilizaran los procesos de Poisson estacionarios ya que se puede lograr que las tasas sean mas o menos constante a lo largo del tiempo.


Como notamos en el párrafo anterior los call center presentan una serie de elementos los cuales pueden ser modelados por varias teorías. Una ejemplificación de esto son las tasas de arribo en las cuales se puede utilizar la teoría de pronósticos de series de tiempo. La propensión a la llamada es el punto de partida del modelo de pronósticos, siendo esta la tasa de llamadas efectuadas por un cliente al sistema en un periodo determinado, es de vital importancia abordarla al momento de modelar las tasas de arribo.

Encontramos varios tipos de Call Center; el especializado es aquel en en que cada uno de los grupos de agente que lo conforman sólo atiende un unico tipo de llamada, el de una sola linea existe un solo grupo de agente que atiende todos los tipos de llamadas existente, y el multiskill es en el que existen varios grupos de agentes que aunque cada grupo es mejor en un determinado tipo de llamado, esta en la capacidad de atender cualquiera de los otros tipos. Si el dueño de un Call Center desea buscar eficiencia operativa debería utilizar el tercer tipo ya que produce mejores resultados, proporciona mejores niveles de servicio y aprovecha mas eficientemente los recursos.

En los Call center ocurre un fénomeno que no sucede en otros sistemas de colas, este se denomina rellamada,  el cual se produce cuando no se atiende una llamada por la gran ocupación que presenta los agentes, de esta manera la llamada se retira del sistema pero vuelve a ingresar y esta vez como una nueva llamada. para calcular la tasa de rellamada necesitamos la probabilidad de que todos los agentes se encuentren ocupados (Pb), la probabilidad de que una llamada abonde el sistema por encontrarlo ocupado (Pa) y la probabilidad de que una llamada que abonda el sistema sin ser atendida vuelva a ingresar como rellamada (Pr).


tasa de rellamada (r) = Pb * Pa * Pr 

Diagrama de Flujo de una llamada entrante