G/M/c/K Queue with Retrial Simulation Model

Theoretical Background

This queuing system already represents real-world systems.

Such a system is an advanced case of M/M/c/K with reneging.

In certain cases, the G/M/c/K with retrial can represent a reneging queue. Formally, the considered system is a G/M/c/K queue with reneging and retrial.

What remains the same as in the M/M/c/K with reneging:

Entities arrive at the queue according to a Poisson process and are served in FIFO order.
The queue capacity is finite, and if the queue is full, arriving entities are lost (blocked).
If an entity waiting in the queue exceeds the timeout, it leaves the queue and is lost.
Entities from the queue are assigned to one of the C servers.
If an idle server is found, the entity is passed to it, otherwise the entity is placed in a queue.
If several servers are idle, one of them is selected at random.
The service time of any server is exponentially distributed.

The difference from the M/M/c/K with reneging is that entities rejected from the queue due to a timeout are split into two flows.

The entities of the first one are destroyed. This simulates the loss of clients that don't want to try again to get service.

The second flow entities are delayed for a while before being sent back to the queue. This simulates the attempt of clients to get service again. After some delay, these entities are mixed with newly arrived entities and passed together to the queue.

So, the mixed flow entering the queue is a non-Poisson process, and, therefore, the designation of this system is G/M/c/K queue with reneging and retrial, where G stands for the general distribution.

The characteristics under study are the blocking probability, probability of waiting, mean waiting time, and mean queue length.

Since how an idle server is selected does not affect the characteristics of interest, this rule can be any, not necessarily random.

Model in OpenSIMPLY

The Generator, Selector, and Server blocks are still used to describe this system, as in the M/M/c/K queue with reneging model.

Instead of the Queue block, the YQueue block with additional secondary output is used in this model. Through this output, entities rejected because of timeout are not destroyed, but are passed on further.

Additionally, the Mixer, Splitter, Terminal and InfiniteServer blocks are used for this model.

The Mixer combines the entity flows from multiple inputs.

The Splitter divides the entity flow from the input into two outputs according to the specified portion.

The Terminal simply destroys entities; it is an end station.

The InfiniteServer block accepts every entity and delays it for a specified time.

In Delphi and Free Pascal, these blocks are represented by the TGenerator, TMixer, TYQueue, TSelector, TServer, TSplitter, TTerminal, and TInfServer classes, respectively.

Download executable model of the G/M/c/K queue with reneging and retrial as a real call center.

Block model of the G/M/c/K queue with reneging and retrial

Model Creation

Assume the timeout in this model is exponentially distributed. To specify this, use the ExpTime for the timeout function.

The Connection Rule item of the Initial Values parameter for the TSelector class should be specified as RandomConnection. However, because the method of selecting an idle server does not affect the results, the default FirstIdleConnection value can be used instead. Therefore, this parameter can be omitted.

Creating New Blocks

The TMixer and TTerminal have no items in the Initial Values parameter, and therefore the instances can be created using the CreateDefault constructor.

The Splitter and YQueue blocks have two outputs: 1-st (primary output) and 2-nd (secondary output).

The Initial Values parameter of the TSplitter Create constructor requires one mandatory item, Portion, which is the percentage of entities forwarded to the primary output. To specify this in the model the RetrialsPercentage variable is used.

The Connect method for the TSplitter and TYQueue has an implementation for assigning a block to a certain output.

For example to connect the primary output use this: Connect(1, SomeBlock);

To connect the secondary output use this: Connect(2, SomeBlock);

If a block should be connected to the Mixer block, the regular Connect method is used.

The Gen, Mix, YQue, Sel, Splt, Trm, and InfSrv variables will be used for the instances of the TGenerator, TMixer, TYQueue, TSelector, TSplitter, TTerminal and TInfServer classes, respectively.

Model Parameters

The following variables and constants will be used for the Initial Values of the blocks.

TotalEntities — the total number of entities to be simulated during the model run.
QueueCapacity — the number of waiting places in the queue.
QueueTimeout — the mean waiting time for an entity in the queue.
RetrialsPercentage — the percentage of timeout-rejected entities that attempt a retrial.
RetrialDelay — the mean time an entity waits before attempting a retrial.
NumberOfServers — the number of servers in the system.
InterarrivalTime — the mean time between entity arrivals.
ServiceTime — the mean service time.
ExpTime — a pointer to a function that returns exponentially distributed random values.

The code below defines the behavior of the G/M/c/K system with retrial as an OpenSIMPLY model.

Gen := TGenerator.Create([TotalEntities, ExpTime, InterarrivalTime]);    //  Creating Generator.

Mix := TMixer.CreateDefault;                                             //  Creating Mixer.

YQue := TYQueue.Create([QueueCapacity, ExpTime, QueueTimeout]);          //  Creating YQueue.

Sel := TSelector.Create([NumberOfServers]);                              //  Creating Selector with default rule.

Splt := TSplitter.Create(RetrialsPercentage);                            //  Creating Splitter.

Trm := TTerminal.CreateDefault;                                          //  Creating Terminal.

InfSrv := TInfServer.Create(ExpTime, RetrialDelay);                      //  Creating Infinite Server.

Gen.Connect(Mix);                                                        //  Connecting Generator to Mixer.

Mix.Connect(YQue);                                                       //  Connecting Mixer to YQueue.

YQue.Connect(1, Sel);                                                    //  Connecting YQueue to Selector.

YQue.Connect(2, Splt);                                                   //  Connecting YQueue to Splitter.

Sel.Connect(1, NumberOfServers, TServer, [ExpTime, ServiceTime]);        //  Creating Servers and assigning them to Selector.

Splt.Connect(1, InfSrv);                                                 //  Connecting Splitter to InfiniteServer.

Splt.Connect(2, Trm);                                                    //  Connecting Splitter to Terminal.

InfSrv.Connect(Mix);                                                     //  Connecting InfiniteServer to Mixer.

To compile a model, the code above should be placed in a standard model wrapper.

Complete Program Code with Input Data and Results

program GMCKretrial;
{$AppType GUI} 
{$S-}
uses
  SimBase,
  SimBlocks,
  SimStdGUI;
  
type
  TMyModel = class(TModel)             //  Model declaration.  
    procedure Body; override;
  end;

var                                    //  Model parameters.
  TotalEntities,                       
  QueueCapacity,
  NumberOfServers: Integer;
  
  InterarrivalTime,
  QueueTimeout,
  ServiceTime,
  RetrialsPercentage,
  RetrialDelay: Double;
 
procedure TMyModel.Body;               //  Model behavior.
var                                    
  Gen: TGenerator;                     //  Blocks declaration.
  Mix: TMixer;
  YQue: TYQueue;
  Sel: TSelector;
  Splt: TSplitter;
  Trm: TTerminal;
  InfSrv: TInfServer;
begin 
  Gen := TGenerator.Create([TotalEntities, ExpTime, InterarrivalTime]);
  Mix := TMixer.CreateDefault;
  YQue := TYQueue.Create([QueueCapacity, ExpTime, QueueTimeout]);
  Sel := TSelector.Create([NumberOfServers]);
  Splt := TSplitter.Create(RetrialsPercentage);
  Trm := TTerminal.CreateDefault;
  InfSrv := TInfServer.Create(ExpTime, RetrialDelay);

  Gen.Connect(Mix);
  Mix.Connect(YQue);
  YQue.Connect(1, Sel);
  YQue.Connect(2, Splt);
  Sel.Connect(1, NumberOfServers, TServer, [ExpTime, ServiceTime]);
  Splt.Connect(1, InfSrv);
  Splt.Connect(2, Trm);
  InfSrv.Connect(Mix);

  Run(Gen);                            //  Launching start block.
                                       
                                       //  Results.
                                       
  Gen.ShowStats;                       //  Blocking probability
  
  YQue.ShowStats;                      //  Probability of waiting,
                                       //  mean waiting time, mean queue length
end;

begin
  TotalEntities := 3000;               //  Initial values of model.
  InterarrivalTime := 1;
  QueueCapacity := 3;
  QueueTimeout := 1;
  ServiceTime := 1.3;
  NumberOfServers := 2;
  RetrialsPercentage := 20;
  RetrialDelay := 0.16;

  Simulate(TMyModel);                  //  Starting model.
end.