Simulación – Modelado de eventos discretos

En la simulación de la cadena de Markov en tiempo contínuo, la idea principal era escoger un espacio alternativo en el tiempo de la simulación para que las transiciones ocurran exactamente en esos momentos en que los cambios en el sistema ocurren.

Consideremos el siguiente ejemplo.

Tenemos visitantes ingresando al banco acorde con el “Proceso estacionario de Poisson” con una intensidad λ. En el banco hay N cajas (ventanillas), cuando un visitante ingresa pasa directo a la caja de no existir una cola y de haber una caja libre.

No pondremos un límite a la longitud de la cola y la duración en que cada visitante es atendido será una variable aleatoria con un parámetro de distribución exponencial μ.

El sistema descrito es un ejemplo clásico de queueing systems y estos sistemas son denominados M/M/N/α donde:

M – Markov — Variable aleatoria exponencial.

N – Número de operadores (ventanillas/cajas).

α – Número ilimitado de puestos de espera en la cola.

En este caso tenemos que generar dos variables aleatorias.

  1. El momento en que un cliente llega
  2. El momento en que se desocupa una caja

Estos momentos son la base para el modelado ya que la simulación se moverá entre estos momentos de un evento a otro.

Un punto importante al construir los modelos de una simulación de un sistema complejo es la determinación de todos los componentes del vector de estados del sistema, de manera que la cadena resultante de cambios de estado sea un proceso de Markov, de manera que de los valores de sus componentes en un tiempo determinado sea posible calcular el estado al próximo instante en el tiempo.

También es importante identificar los factores que afectan al cálculo de estos puntos de tiempo cuando el estado del sistema cambia. En nuestro ejemplo tenemos los siguientes factores:

  • La longitud del periodo entre los momentos consecutivos en que los visitantes llegan al banco.
  • Duración del servicio (tiempo que pasa en ventanilla)

Los componentes de este vector de estados son:

  • Número de ventanillas ocupadas x ∈ {0, 1, 2, ... , N}
  • Número clientes en la cola y ∈ {0, 1, 2, ...}

Algoritmo

Las variables exponenciales aleatorias tienen una particularidad, si el intervalo entre la ocurrencia de los eventos tiene una distribución exponencial con un parámetro λ, entonces en un punto arbitrario en el tiempo, el tiempo restante hasta el próximo evento también tiene una distribucción con el parámetro λ. Por lo mismo,

En cualquier momento, el tiempo restante para que un nuevo cliente llegue al banco es una variable aleatoria exponencial con un parámetro λ.

En cualquier momento, el tiempo restante hasta que un cliente sea atendido es una variable aleatoria exponencial con un parámetro μ.

Donde:

  • x es el número de clientes atendidos.
  • y es el número de clientes en la cola.

Descripción

  1. La simulación empieza con tiempo t=0, x=0, y=0
  2. Se simula el tiempo restante para que un nuevo cliente sea atendido t = ExpRV(λ)
  3. x > 0, se simula el tiempo restante para cualquier cliente: δ = ExpRV(μ ∙ λ), dado que x clientes fueron atendidos la “intensidad” del servicio será μ ∙ x.
  4. t < δ ha llegado un cliente, entonces si x < N (hay ventanillas libres y es atendido) caso contrario pasa a la cola a la espera de que haya una ventanilla libre.

Proceso estadístico

El estado de este “queueing system” se caracteriza por que sus valores que son incluidos en el Proceso de Markov construidos para el modelo. En nuestro ejemplo este es el número de ventanillas ocupadas y el número de clientes en la cola. En casos más complejos el vector de estados incluiría también otros parámetros como el tiempo que toma atender a un cliente o el tiempo que transcurre entre la llegada de un cliente y otro, etc.

De todas maneras un análisis tan comprensivo usualmente no es requerido ya que en la mayoría de casos nos intereza más las características individuales del sistema, por ejemplo:

  • El número de ventanillas ocupadas
  • Clientes en la cola
  • Clientes en el banco (ventanilla y cola)

Estas características son procesos aleatorios con estados discretos tal cual en una cadena de Markov con tiempo continuo, y el proceso estadístico se lo realiza de la misma manera.

Para nuestro regimen estacionario QS M/M/N/α la siguiente condición está pressente

La distribución estacionaria del número de clientes en el sistema tiene la siguiente forma:

Donde

y P(0) son determinados mediante la siguiente expresión

Modelos basados en agentes

Estos modelos abordan el problema desde una perspectiva basada en eventos donde cada entidad afecta al modelo de tiempo y estado del sistema, esto implica agentes distintos y el proceso de modelado general se lo realiza procesando los eventos de estos agentes.

Reglas

  1. Cada agente es individual, tiene sus propias características y reglas de comportamiento.
  2. Cada agente es autónomo y puede tomar independientemente desciciones en cuanto a sus acciones.
  3. Un agente puede interactuar con otros agentes para obtener información, ajustar su comportamiento o notificar a otros agentes acerca de cambios en el estado del sistema.
  4. El egente debe estar en un ambiente en el cual pueda interactuar con otros agentes.

Estos modelos se los puede implementar de la siguiente manera:

Tiempo constante

Cuando los factores aleatorios no están presentes o no afectan los eventos. No es conveniente ya que al utilizar un modelo constante de tiempo dará lugar a errores y generará también una sobrecarga innecesaria en los recursos de cómputo.

Modelo Discreto

Un modelo con eventos discretos en el que el algoritmo de la simulación principal es el siguiente:

ProcessEvent(t) es un procedimiento para el agente, en el que procesa el evento de cambio en el modelo del tiempo. En este método el agente decide si necesita tomar alguna acción. El algorítmo para implementar los modelos discretos es el siguiente

El método GetNextEvent() de un agente retorna al sistema el punto en el tiempo en que u evento importante para dicho agente ocurrió y es necesario hacerse cargo, y se asume que hasta ese punto el estado del agente no ha cambiado.

En el modelado de agentes la selección de los agentes es ambigua ya que podría ser:

  • Los clientes
  • Las colas
  • Las ventanillas
  • El flujo de llegada de clientes
  • ….

La definición de agentes se basa en las preferencias del desarrollador del modelo y/o en la conveniencia para realizar dicho modelo.

Resultado

Implementación

/*
  * We have groups of windows, so different types
  * of windows work with different transactions
  *
  * For example a customer that wants to open an account
  * can only do it on window #1
  *
 */
 struct GroupThread
 {
     public int ID { get; set; }
     public List threadsList { get; set; }
 }

///
/// Handles the queue of the bank, to let customers go to their respective operator
/// Within the tuple, a new customer is enqued with a type of task and priority
///

public static void ProducerThreadProc()
{
    try
    {
        while (true)
        {
            if (queue.Count < queueSize)
            {
                queue.Enqueue(Tuple.Create(rand.Next(0, groups), rand.Next(), rand.Next()));
            }
            
            Thread.Sleep(4000);
            Thread.Yield();
        }
    }
    catch (ThreadInterruptedException) { return; }
}

///
/// Here is where the operator work happens
/// From people waiting, we pick the next
/// and check if the free window can do the work
/// So different types of consumers can only go
/// to some group of windows
///
/// 

public static void ConsumerThreadProc(object data)
{
    var currentData = (GroupThread)data;
    
    try
    {
        while (true)
        {
            if (queue.Count > 0)
            {
                if (mutex.WaitOne())
                {
                    if (queue.TryPeek(out Tuple<int, int, int> m) && m.Item1 == currentData.ID)
                    {
                        if (queue.TryDequeue(out Tuple<int, int, int> n))
                        {
                            mutex.ReleaseMutex();
                            
                            //Constant Time-Step of 5s
                            //Each process takes the same time for simplicity
                            Thread.Sleep(5000);
                        }
                    }
                }
            }
            Thread.Yield();
        }
    }
    catch (ThreadInterruptedException) { return; }
}

class Program
{
    private static int groups;
    private static int queueSize;
    private static List threads;
    private static Thread producerThread;
    private static Mutex mutex = new Mutex();
    private static Random rand = new Random();
    private static ConcurrentQueue> queue;
    
    [MTAThread]
    public static void Main()
    {
        int consumers;
        Console.CancelKeyPress += new ConsoleCancelEventHandler(Console_CancelKeyPress);
        
        do
        {
            Console.WriteLine("Enter the number of groups of windows -operators- (n > 0)");
            if (Int32.TryParse(Console.ReadLine(), out groups) && groups > 0)
            {
                do
                {
                    Console.WriteLine("Enter the max number of customers for each window -visitors- (n > 0)");

                    if (Int32.TryParse(Console.ReadLine(), out consumers) && consumers > 0)
                    {
                        do
                        {
                            Console.WriteLine("Enter the number of people (n > 4)");
                            if (Int32.TryParse(Console.ReadLine(), out queueSize) && queueSize > 4)
                            {
                                threads = new List<GroupThread>(groups);
                                queue = new ConcurrentQueue<Tuple<int, int, int>>();
             
                                for (int i = 0; i < queueSize; i++)
                                {
                                    queue.Enqueue(Tuple.Create(rand.Next(0, groups), rand.Next(), rand.Next()));
                                }

                                producerThread = new Thread(new ThreadStart(ProducerThreadProc));
                                producerThread.Start();

                                for (int i = 1; i <= groups; i++)
                                {
                                    GroupThread groupThread = new GroupThread
                                    {
                                        ID = i,
                                        threadsList = new List<Thread>(rand.Next(1, consumers))
                                    };
                                    for (int j = 0; j < groupThread.threadsList.Capacity; j++)
                                    {
                                        Thread ct = new Thread(new ParameterizedThreadStart(ConsumerThreadProc));
                                        ct.Start(groupThread);
                                        groupThread.threadsList.Add(ct);
                                    }
                                    threads.Add(groupThread);
                               }

                               //Infinite number of people arrives at the bank.
                               while (true)
                               {
                                   //Current number of people waiting at the bank
                                   Console.WriteLine("Waiting in line: {0}", queue.Count);
          
                                   //Operators attending people on their windows
                                   Console.WriteLine("State of the Windows");

                                   for (int i = 0; i < threads.Count; i++)
                                   {
                                       Console.WriteLine("Group: {0}", i + 1);

                                       for (int j = 1; j <= threads[i].threadsList.Count; j++)
                                       {
                                           Console.WriteLine("- {0} -> {1}", j, threads[i].threadsList[j - 1].ThreadState);
                                       }
                                       Console.WriteLine();
                                  }
         
                                  Thread.Sleep(1000);
                             }
                        }
                        else
                        {
                            queueSize = 0;
                        }
                    } while (queueSize > 4);
                }
                else
                {
                    consumers = 0;
                }
            } while (consumers > 0);
        }
        else
        {
            groups = 0;
        }
    } while (groups > 0);
}

Descargar Proyecto