Engee documentation
Notebook

Mass service theory: basic examples

Let's begin to master the EventSimulation library toolkit for the analytical study of discrete event logic and mass service system (MSS) models.

Problem description

Mass service theory includes tools for analysing the performance of complex systems that deal with repeatedly occurring stochastic events and allow the evaluation of system characteristics such as the presence of queues, average waiting time before service starts or average equipment downtime.

The common components of any mass service system are the presence of an inbound flow of requests, a given system structure (number and capacity of storage units, queues and other service devices), time to service requests and service discipline (the algorithm for distributing requests to handlers, selecting requests from the queue and forming queues).

EventSimulation library

The EventSimulation library allows you to program systems based on discrete event logic. In such systems, the time between events can be expressed in relative values, and simulation is based on events rather than on an explicitly defined continuous time vector, as in simulation of graphical models created from blocks.

First, let's install this library in our system (this step is performed once, comment out the following line when running it again).

In [ ]: 
Pkg.add( "EventSimulation" )

Let's consider the simplest situation - when five clients "came" to our system with an interval of 1 unit of time between them, and servicing each of them took 1.5 units of time.

In [ ]: 
using EventSimulation

function arrival(s)
    t = s.now
    println("$(s.now): Новый клиент")
    register!(s, x -> println("    $(x.now): Уход клиента, который пришел в $t"), 1.5)
end

s = Scheduler()

for t in 1.0:5.0
    register!(s, arrival, t)
end

go!(s)

1.0: Новый клиент
2.0: Новый клиент
    2.5: Уход клиента, который пришел в 1.0
3.0: Новый клиент
    3.5: Уход клиента, который пришел в 2.0
4.0: Новый клиент
    4.5: Уход клиента, который пришел в 3.0
5.0: Новый клиент
    5.5: Уход клиента, который пришел в 4.0
    6.5: Уход клиента, который пришел в 5.0

Inside the arrival function, for each customer, the arrival time is logged and a leave event is created and stored in the dispatcher (Scheduler) along with an anonymous function that will be called by the dispatcher when the time comes.

The value x.now is taken from the dispatcher state vector.

If we want to analyse a situation with an unlimited number of incoming objects or events, it will not be enough to process clients in a loop. We will need a source of events, which we will create using repeat_register.

In [ ]: 
using EventSimulation

function arrival(s)
    t = s.now
    println("$(s.now): Новый клиент")
    register!(s, x -> println("    $(x.now): Уход клиента, который пришел в $t"), 1.5)
end

s = Scheduler()
repeat_register!(s, arrival, x -> 1.0)

go!(s, 7)

1.0: Новый клиент
2.0: Новый клиент
    2.5: Уход клиента, который пришел в 1.0
3.0: Новый клиент
    3.5: Уход клиента, который пришел в 2.0
4.0: Новый клиент
    4.5: Уход клиента, который пришел в 3.0
5.0: Новый клиент
    5.5: Уход клиента, который пришел в 4.0
6.0: Новый клиент
    6.5: Уход клиента, который пришел в 5.0
7.0: Новый клиент

Clients still arrive once every 1 time unit, but now their queue is infinite. The simulation duration is defined in the go!(s, 7) command as 7 time units.

Let's add a counter of clients to our model. To do this we need to define the structure CounterState, which will be initialised for the dispatcher Scheduler when it is created.

It should be noted that redefining already created structures usually requires reloading the Julia kernel (e.g. by means of GUI Engee).

In [ ]: 
using EventSimulation
using Random

mutable struct CounterState <: AbstractState
    count::Int
end

function arrival(s)
    function departure(x)
        x.state.count -= 1
        println("    $(round(x.now,digits=2)): Уход клиента, который пришел в $(round(t,digits=2)) (клиентов в очереди $(x.state.count + 1))" )
    end
    
    t = s.now
    println( "$(round(s.now,digits=2)): Новый клиент (клиентов в очереди $(s.state.count+1))")
    register!( s, departure, 1.0 )
    s.state.count += 1
end

s = Scheduler( CounterState(0) )

Random.seed!(1)
repeat_register!(s, arrival, x -> rand())
go!(s, 5)

0.07: Новый клиент (клиентов в очереди 1)
0.42: Новый клиент (клиентов в очереди 2)
    1.07: Уход клиента, который пришел в 0.07 (клиентов в очереди 2)
1.12: Новый клиент (клиентов в очереди 2)
    1.42: Уход клиента, который пришел в 0.42 (клиентов в очереди 2)
1.75: Новый клиент (клиентов в очереди 2)
    2.12: Уход клиента, который пришел в 1.12 (клиентов в очереди 2)
2.66: Новый клиент (клиентов в очереди 2)
    2.75: Уход клиента, который пришел в 1.75 (клиентов в очереди 2)
2.86: Новый клиент (клиентов в очереди 2)
3.63: Новый клиент (клиентов в очереди 3)
    3.66: Уход клиента, который пришел в 2.66 (клиентов в очереди 3)
    3.86: Уход клиента, который пришел в 2.86 (клиентов в очереди 2)
4.41: Новый клиент (клиентов в очереди 2)
    4.63: Уход клиента, который пришел в 3.63 (клиентов в очереди 2)

M/M/1 system

Finally we realise a classical system with the following parameters:

  • the incoming flow of requests has a Poisson distribution
  • the distribution of service time is exponential
  • the number of servicing servers/request handlers is equal to 1
  • the service queue is infinite,
  • service discipline is called FCFS (FIFO) from first in, first served or first in, first out.

To be on the safe side, let's put libraries that may not be in the system by default.

In [ ]: 
Pkg.add( ["Distributions", "Statistics", "Random"] )

After installing them in the system, we can simulate M/M/1 LMS using the following algorithm.

The structure MMQueue accumulates statistics on the current work of the dispatcher (in the course of the current simulation) and allows us to obtain, as an output of the function run!, the average value of the difference between the arrival and departure times of each particular object (mean( d-a )) that passed through the system during the simulation 1 000 000 time units.

In [ ]: 
using EventSimulation
using Distributions
using Statistics
using Random

mutable struct MMQueue <: AbstractState
    sp::Exponential{Float64} # скорость обслуживания (service rate)
    qlen::Int   # длина очереди (queue length)
    busy::Bool  # занят ли обработчик (сервер)?
    arrival_times::Vector{Float64} # время когда клиент пришел
    departure_times::Vector{Float64} # время когда клиент ушел
end

# Событие "клиент пришел"
function arrival(s)
    push!(s.state.arrival_times, s.now)
    if s.state.busy # server is working?
        s.state.qlen += 1
    else
        s.state.busy = true
        register!(s, leave, rand(s.state.sp))
    end
end

# Событие "клиент покинул систему"
function leave(s)
    push!(s.state.departure_times, s.now)
    if s.state.qlen > 0 # есть ли ожидающие клиенты?
        s.state.qlen -= 1
        register!(s, leave, rand(s.state.sp))
    else
        s.state.busy = false
    end
end

# Запуск системы M/M/1 с заданным параметрами
#   ar: среднее время между появлениями клиентов
#   sr: среднее время, затраченное на обслуживание
function run(ar, sr)
    q = MMQueue( Exponential(1 / sr), 0, false, Float64[], Float64[] )
    s = Scheduler( q, Float64 )
    repeat_register!( s, arrival, x -> rand(Exponential(1/ar)) )
    go!( s, 1_000_000 )
    mean( d-a for (a,d) in zip(s.state.arrival_times, s.state.departure_times) )
end

# Запустим симуляцию системы с изменяемым средним
# временем между поступлением заявок на обработку
# (от 1/0.1 до 1/0.9 временных единиц)
plot()
arrival_rates = 0.1:0.1:0.9
rates = []

for seed in 1:20
    Random.seed!(seed)    
    r = [ abs(run(ar, 1.0)*(1-ar)-1) for ar in arrival_rates ]
    plot!( arrival_rates, r )
    append!( rates, r )
end

hline!( [0.03], c="red", ls=:dash, legend=false )
plot!( title="Среднее время обслуживания" )
Out[0]:

We see that with an event rate of 1.11, 3 out of 20 runs resulted in exceeding the specified average service time.

In [ ]: 
count( last.(hcat(rates...)) .> 0.03 )
Out[0]:
3

More examples can be found in the repository of the library developers: https://github.com/bkamins/EventSimulation.jl/tree/master/examples.

The English-language documentation for the EventSimulation library can be found at https://bkamins.github.io/EventSimulation.jl/stable/.

Conclusion

We have explored basic techniques for modelling mass maintenance systems. Engee allows inserting into simulation loops the invocation of external information systems or the running of models placed on the canvas, so mass service theory tools can become an important part of the chain of systems reliability analysis.