More › discrete-event

More

Queueing: queues, servers and arrivals

Orders come to a packing line, patients to a clinic, calls to a help desk, packets to a router. They come at random, wait, are worked on, and leave. A queueing model says who they wait for and how long the work takes; archec runs it, and says how long they wait, how long the queues get and how much gets through. A requirement can then bound a waiting time the way it bounds a mass.

Extension — not covered by the 1.0 stability promise (queueing; the core)

A first model#

queueing packing "Order packing line" {
  horizon 8h
  warm-up 30min

  source orders every exponential(2min)
  queue waiting max 50
  server packer count 3 takes normal(4min, 1min)
  sink shipped

  orders -> waiting -> packer -> shipped
}

requirement REQ-WAIT "Orders wait under 10 min" {
  limit packing.waiting.wait.p95 < 10min
}

A queueing model has stations, and arrows that say the way from one to the next.

Station What it is
source orders every exponential(2min) Where things come from. One arrives, then the next after every.
queue waiting max 50 Where they wait for a server. With max, what arrives when it is full is lost.
server packer count 3 takes normal(4min, 1min) What works on them: 3 side by side, each on one thing for the time it takes.
sink shipped Where they leave the model.

The times are distributions: exponential(2min) is an arrival at random, 2 min apart on average. A time that does not vary is written as it is: every 30s.

$ archec queueing main.arche
queueing packing — Order packing line: 20 runs of 8h, the first 30min not measured (seed 1)

  source  every              arrived
  orders  exponential(2min)  228.9

  queue    wait      p50    p95      max       length  p95  max         lost
  waiting  1min 10s  11.6s  5min 4s  8min 38s  0.6056  3.1  6.85 of 50  0

  server  count  takes               utilisation  served
  packer  3      normal(4min, 1min)  67.7%        229.6

  sink     throughput  time     p50       p95       max
  shipped  30.61/h     5min 9s  4min 40s  9min 34s  12min 52s

  through the line: 30.61/h (29.33/h … 31.88/h with 95 % confidence), 5min 9s each on average, 9min 34s for 95 % of them
  9759 events

  ✗ REQ-WAIT  packing.waiting.wait.p95  5min 4s on average over 20 runs (3min 59s … 6min 9s with 95 % confidence), 12min 31s in the highest; held in 19 of 20 runs; the limit is < 10min

The model is run 20 times, each run with draws of its own. Every number in the tables is the mean over the runs. p50 is the median and p95 is what 95 % stay under.

archec queueing main.arche --svg build/ also writes build/packing.svg: the length of each queue over the first run.

How it is run#

archec runs a queueing model as a discrete-event simulation. It keeps a list of what happens next, ordered by time: an arrival, the end of a piece of work. It takes the first, changes the stations, and adds what follows from it. Nothing is computed between two events, so a million events take about a second.

  • horizon 8h is how long one run lasts, in the model's own time.
  • warm-up 30min is the start of each run that is not measured. The line is empty at time 0, which a real one seldom is.
  • runs 20 is how many times the model is run. 20 is the default.
  • seed 1 is the seed of the draws. The same seed gives the same runs.

Each station draws from its own generator, made from the seed, the run and the station. So changing a server's time leaves the arrivals as they were, and two designs are compared on the same orders.

Limits, and what proves them#

A requirement bounds what the runs measure with the limit that bounds a profile or a geometry. It names the model, a station and what is measured there.

Station Measured Written
queue how long things wait in it limit packing.waiting.wait < 2min
how many wait limit packing.waiting.length.max <= 20
how many found it full limit packing.waiting.lost < 1%, or a number of them
server the share of its time it works limit packing.packer.utilisation < 85%
the share it keeps a thing it cannot hand on limit packing.packer.blocked < 5%
served, and lost as a queue's limit packing.packer.served >= 200
resource the share of its time it is used limit clinic.doctor.utilisation < 90%
sink how many leave by it in a time limit packing.shipped.throughput >= 25/h
how long each was in the line limit packing.shipped.time.p95 < 15min
count limit packing.shipped.count >= 200
source count, how many arrived limit packing.orders.count >= 200
the model time, throughput and lost, over every sink limit packing.time.p95 < 15min

A wait, a time and a length are the mean, or .p50, .p95 or .max. A bound is written in the unit of what it bounds: a time (10min), a share (85%), a number of things in a time (25/h, 2/min) or a number.

A limit holds when it holds in every run. Above, one run in 20 had a bad day, so REQ-WAIT fails. Often that is too strict: say the share of runs the requirement needs with holds, as for a Monte Carlo study.

requirement REQ-WAIT "Orders wait under 10 min" {
  holds 90%
  limit packing.waiting.wait.p95 < 10min
}
? REQ-WAIT  packing.waiting.wait.p95  … held in 19 of 20 runs (95 %), 76.4 % … 99.1 % with 95 % confidence; needs 90 % — the runs do not say: run more (`runs 100`); the limit is < 10min

19 of 20 is 95 %, but 20 runs cannot tell 90 % from 80 %. The interval is where the true share is (the Wilson interval at 95 %). The requirement is proved when the low end reaches its holds, and fails when the high end is below it. In between, run more:

$ archec queueing main.arche --runs 200
✓ REQ-WAIT  packing.waiting.wait.p95  4min 41s on average over 200 runs (4min 25s … 4min 58s with 95 % confidence), 13min 26s in the highest; held in 194 of 200 runs (97 %), 93.6 % … 98.6 % with 95 % confidence; needs 90 %; the limit is < 10min

--runs and --seed are for a look. The record is made by the runs the model says, so write runs 200 in the line. archec queueing then records each limit, and archec status shows it under its requirement:

REQ-WAIT  Orders wait under 10 min
  ✓ queueing  packing.waiting.wait.p95  sim    just now  4min 41s on average over 200 runs (…); held in 194 of 200 runs (97 %), 93.6 % … 98.6 % with 95 % confidence; needs 90 %; the limit is < 10min

The record is out of date when the model changes, or the profile it runs over. A limit never run reads never measured: archec queueing. archec check reads a queueing model and says what is wrong in it, but it does not run it: a limit that is not held is said by archec queueing.

Ways out#

A source or a server may have several ways out. Each thing takes one:

source orders every exponential(2min) {
  prop express = choice(0, 0, 0, 1)
  prop weight = lognormal(2kg, 50%)
}
queue waiting priority express
…
packer -> courier [express == 1]
packer -> check 10%
packer -> shipped
  • prop in a source is a property of each thing that arrives, drawn for each. choice(0, 0, 0, 1) makes one order in four express.
  • [express == 1] is a condition on those properties. Comparisons are joined with and and or, and not goes before one: [weight > 20kg and not express == 1].
  • 10% is the share of the things that go that way.
  • A way out with neither takes the rest.

The conditions are tried first, in the order written. Then one way is drawn by the shares. The shares must not add up to more than 100 %, and when they add up to less a way out must take the rest.

queue waiting priority express serves the highest express first, and among equals the first come.

A queue leads to servers only. Each takes from it when it is free, the first written first. A server that several queues lead to takes from the first written that is not empty.

When there is no room#

Written What arrives when it is full
queue waiting max 50 is lost, and counted (lost)
queue waiting max 50 overflow drop-oldest takes the place of the one that waited longest, which is lost
queue buffer max 2 overflow block stays with the server that sends it, which is busy until there is room (blocked)

A thing sent straight to a busy server, with no queue between, is lost when a source sends it. This is a line with no waiting room, as a phone line is. When a server sends it, that server keeps it and stays busy, as on an assembly line with no buffer between two machines. A source never waits: what it sends where there is no room is lost.

Resources#

Several servers may need the same people or tools.

resource doctor "Doctors" count 3
server urgent-care count 2 takes lognormal(20min, 40%) uses doctor
server room count 3 takes lognormal(12min, 50%) uses doctor

A server that uses a resource starts only when one is free, and gives it back when its work is done. Three rooms and two urgent desks share three doctors, so no more than three patients are seen at once. When a resource comes free, the servers that use it are asked in the order they are written: here urgent care goes first.

Shifts and rush hours#

A queueing model can run over a profile. Each phase then changes a number of the model for the time it lasts, with the set that gives a part its number in a phase.

profile day "A day at the clinic" {
  phase morning 4h {
    set clinic.patients.every = exponential(4min)
  }
  phase afternoon 5h
  phase evening 3h {
    set clinic.doctor.count = 2
    set clinic.patients.every = exponential(15min)
  }
}

queueing clinic "Walk-in clinic" {
  over day
  …
}
  • A phase sets a source's every, a server's count or takes, and a resource's count. count = 0 closes a server for the phase.
  • A phase that sets nothing leaves the numbers as the model writes them.
  • Without a horizon, a run lasts what the profile lasts. With a longer one, the profile starts again from its first phase.
  • A server that loses a place finishes what it has started.

examples/des-packing is the packing line, with a second check for one order in ten. examples/des-clinic is a walk-in clinic over a day: triage, a waiting room by severity, two kinds of rooms that share the doctors, and fewer doctors in the evening.

Why a block of its own#

A queueing model is written at the top of a file, as a profile is, and not inside a system. A component's ports, messages and state machines say what one part does on each message; a queueing model says how many things wait for how many places, and no single part owns that. The stations are not kinds of your own either: a kind says what an element has and checks it, but the simulator must know what a queue does.

A workflow is not replaced. A workflow is the path of one case through its lanes, in order, and it is drawn as a sequence. A queueing model is many cases at once competing for the same places. Write the steps as a workflow, and the load on them as a queueing model.

archec sim runs the behaviour of a system: its state machines, handlers and threads. A queueing model has none of them, so it has a command of its own, archec queueing.

Limits#

  • A thing is in one place at a time. Nothing splits into two or joins another (an order and its box), and a server works on one thing per place.
  • The time of the work does not read the thing's properties: an express order takes as long as another at the same server. Send it to another server.
  • A property is a number. It is given at the source and does not change.
  • A queue is first come, first served, or by one priority. Nobody leaves a queue because the wait is long.
  • Those still in a queue when a run ends count with the time they have waited so far.
  • A source whose every changes with a phase forgets the arrival it had drawn and draws the next at the new rate.
  • A requirement that bounds a queueing model with holds is not drawn by a study: the model's own runs say the share. A study's monte-carlo does not vary what a queueing model draws.
  • A run stops at 20 million events, and says so.
  • A requirement's check p95(waiting.wait) < 10min is not read here: write the bound as a limit.
  • Arche has no queueing model: archec queueing runs it; nothing is written to the Arche project.