Discrete event with event queue

No preview image

1 collaborator

Default-person Russ Abbott (Author)

Tags

(This model has yet to be categorized with any tags)
Visible to everyone | Changeable by the author
Model was written in NetLogo 6.0.2 • Viewed 215 times • Downloaded 9 times • Run 0 times
Download the 'Discrete event with event queue' modelDownload this modelEmbed this model

Do you have questions or comments about this model? Ask them here! (You'll first need to log in.)


WHAT IS IT?

This is an extenstion of Nick Bennett's DEV queueing system model (http://blog.modelingcommons.org/browse/one_model/5086). It has a single, unlimited queue and 1-10 homogeneous servers. Arrivals follow a Poisson process, and service times are exponentially distributed.

HOW IT WORKS

This is a discrete-event simulation, which is a type of simulation that advances the clock in discrete, often irregularly sized steps, rather than by very small, regular time slices (which are generally used to produce quasi-continuous simulation). At each step, the clock is advanced to the next scheduled event in an event queue, and that event is processed. In this model, the different events are: customer arrival and entry into the queue (followed, if possible, by start of service); service completion, with the customer leaving the system (followed, if possible, by start of service for a new customer); statistics reset; and simulation end. Since these are the only events that can result in a change of the state of the simulation, there is no point in advancing the clock in smaller time steps than the intervals between the events.

HOW TO USE IT

Use the number-of-servers slider to set the number of servers; then press the Setup button to create the servers and reset the simulation clock.

The mean-arrival-rate and mean-service-time sliders control the arrival and service processes, respectively. These values can be changed before starting the simulation, or at anytime during the simulation run; any changes are reflected immediately in a running model.

The max-run-time and stats-reset-time control the length of the simulation and the time at which all the aggregate statistics are reset, respectively. The latter allows for minimizing the effects of system startup on the aggregate statistics.

The simulation can be run one step at a time with the Next button, or by repeatedly processing events with the Go button.

The aggregate statistics can be reset at any time - without emptying the queue or placing servers in the idle state - with the Reset Stats button.

THINGS TO NOTICE

After the simulation has started, the next scheduled arrival time is always shown in the Next Arrival Time monitor. When any of the servers are busy, the scheduled time of service completion is shown in the label below the server.

In queueing theory notation, the type of system being simulated in this model is referred to as M/M/n - i.e. Poisson arrivals, exponential service times, infinite queue capacity and source population, FIFO queue discipline. When there is a single server, or when all the servers have the same mean service time, the steady state characteristics (if the system is capable of reaching a steady state) can be determined analytically. In this model, these theoretical values are shown in the bottom row of monitors. If the theoretical server utilization - determined by multiplying the arrival rate by the service time, dividing by the number of servers, and taking the lesser the result of the calculation and 1 - is less than 1, then the queueing equations have a defined solution; otherwise, the expected queue length and expected time in the queue are unbounded. In this model, these unbounded values are denoted by "N/A" in the associated monitors.

This model displays servers in a row along the bottom of the NetLogo world; customers are shown in a queue which "snakes" from near the bottom of the NetLogo world to the top. However, these display features are purely for visualization purposes; the positions of the servers and customers, and the colors of the customers, have no functional purpose or impact. The colors of the servers, on the other hand, does have a meaning: an idle server is shown in green, while a busy server is red.

THINGS TO TRY

Run the simulation several times, to get a sense of the effects of the different parameters on the average queue length and average time in the queue. How do these observed statistics compare with the theoretical values? Do the input parameters seem to affect not only the average queue length, but also the variability of the queue length?

Try entering a single "arrive" into the command center while the model is running. What happens? Can you explain why?

EXTENDING THE MODEL

This model could easily be extended to support non-identical mean service times for different servers (possibly through an Add Server button that creates servers one at a time, each with a specified mean service time value); additional service time distributions besides exponential; a capacitated queue; and alternative queue disciplines (random priority and LIFO would be the easiest to add). However, when simulating a system with these complicating factors, the computations for expected queue length and expected time in the queue can become difficult, or even practically impossible. Note, however, that there is a general relationship - known as Little's formula - between expected queue length and expected time in the queue (or, more generally, between expected number of customers/transactions in the entire system, and the expected time a customer/transaction spends in the system), which holds for even very complicated queueing systems.

NETLOGO FEATURES

This model uses the tick-advance primitive to advance the NetLogo ticks value by non-integral amounts. This allows the NetLogo clock to be used as a discrete-event simulation clock. However, the standard ticks display (normally seen in the bar above the NetLogo world) is unable to display non-integral values, so this model uses a separate ticks monitor.

CREDITS AND REFERENCES

Copyright 2010, Nick Bennett, Grass Roots Consulting (http://www.g-r-c.com ). All rights reserved.

Copyright 2018, Russ Abbott, Californai State University, Los Angeles (Russ.Abbott@gmail.com)

See coyright details in the code tab.

Comments and Questions

Please start the discussion about this model! (You'll first need to log in.)

Click to Run Model

;;------------------------------------------------------------------------------
;; Copyright 2017 Nick Bennett
;;
;; Licensed under the Apache License, Version 2.0 (the "License");
;; you may not use this file except in compliance with the License.
;; You may obtain a copy of the License at
;;
;;     http://www.apache.org/licenses/LICENSE-2.0
;;
;; Unless required by applicable law or agreed to in writing, software
;; distributed under the License is distributed on an "AS IS" BASIS,
;; WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
;; See the License for the specific language governing permissions and
;; limitations under the License.
;;------------------------------------------------------------------------------

;;------------------------------------------------------------------------------
;; Version History
;; 2010-02-21 - v1.0:   M/M/n queueing simulation; up to 10 servers; standard
;;                      aggregate statistics & corresponding expected values.
;; 2017-07-26 - v1.5:   Updated for NetLogo 6. Licensed under Apache License
;;                      2.0.
;; 2017-07-29 - v1.6:   Added plot & more NetLogo 6-related updates, including
;;                      use of anonymous procedures and range reporter.
;; 2017-08-03 - v1.6.1: Fix info details.
;;------------------------------------------------------------------------------

;-------------------------------------------------------------------------------
; v2.0 Copyright 2018, Russ Abbott, California State University, Los Angeles
;;                     (Russ.Abbott@gmail.com)
;;
;; Licensed under the Apache License, Version 2.0 (the "License");
;; you may not use this file except in compliance with the License.
;; You may obtain a copy of the License at
;;
;;     http://www.apache.org/licenses/LICENSE-2.0
;;
;; Unless required by applicable law or agreed to in writing, software
;; distributed under the License is distributed on an "AS IS" BASIS,
;; WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
;; See the License for the specific language governing permissions and
;; limitations under the License.
;;
;; Contact Russ Abbott: Russ.Abbott@gmail.com
;-------------------------------------------------------------------------------

;-------------------------------------------------------------------------------
; Version History
; 2018-03-18 - v2.0  Uses and displays an actual event-queue.
;                    Updated to NetLogo 6.02.
;-------------------------------------------------------------------------------


; The model has two types of agents: customers, who enter and wait in a
; customer-queue until a server is available; and servers, who serve each
; customer in first-come, first-served order.

; Each customer records the time entering the system, and the time entering service,
; so that average time-in-queue/time-in-system statistics can be computed.
breed [customers customer]
customers-own [
  time-entered-queue
  time-entered-service
]

; Each server records the customer agent being served, and the scheduled
; completion of that service. Since servers are homogenous, individual
; utilization statistics aren't kept.
breed [servers server]
servers-own [
  customer-being-served
  next-completion-time
]


globals [
  ; Event-queue
  event-queue
  ; Waiting line
  customer-queue
  ; Arrival process
  arrival-count
  ; Statistics for average load/usage of customer-queue and servers
  stats-start-time
  total-customer-queue-time
  total-customer-service-time
  ; Statistics for average time-in-queue and time-in-service
  total-time-in-queue
  total-time-in-system
  total-queue-throughput
  total-system-throughput
  ; Physical layout parameters
  server-ycor
  customer-queue-server-offset
  customer-xinterval
  customer-yinterval
  customers-per-row
  ; Saved slider values to allow detection of changes during a simulation run
  save-mean-arrival-rate
  save-mean-service-time
  ; Theoretical measures, computed analytically using classic queueing theory
  expected-utilization
  expected-queue-length
  expected-queue-time
  ; max queue length
  max-queue
]

to startup
  setup
end 

; Initializes global variables and server agents.

to setup
  clear-all
  setup-globals
  setup-servers
  compute-theoretical-measures
  reset-ticks
  begin-stats-collection
  set-plot-pen-color magenta
  insert-event-into-event-queue (list begin-stats-collection-time (word "begin-stats-collection"))
  schedule-next-arrival
  print-event-queue
end 


; Resets statistics, initializes customer-queue, and sets agent shapes and other
; display properties.

to setup-globals
  set event-queue []
  set customer-queue []
  set arrival-count 0
  set-default-shape servers "server"
  set-default-shape customers "person"
  set server-ycor (min-pycor + 2)
  set customer-queue-server-offset 1.75
  set customer-xinterval 0.5
  set customer-yinterval 1
  set customers-per-row (1 + (world-width - 1) / customer-xinterval)
  set save-mean-arrival-rate mean-arrival-rate
  set save-mean-service-time mean-service-time
  set max-queue 0
end 


; Creates server agents and arranges them horizontally, evenly spaced along the
; bottom of the NetLogo world. This layout is purely cosmetic, and has no
; functional purpose or impact.

to setup-servers
  let horizontal-interval (world-width / number-of-servers)
  create-servers number-of-servers [
    set color green
    setxy (min-pxcor - 0.5 + horizontal-interval * (0.5 + who)) server-ycor
    set size 4
    set label ""
    set customer-being-served nobody
    set next-completion-time 0
  ]
end 


; The main loop.

to go
  update-theoretical-values
  ;; Event queue will eventually become empty because no events
  ;; are added with a scheduled time past max-run-time.
  if empty? event-queue [stop]
  let next-event first event-queue
  set event-queue but-first event-queue
  let event-time first next-event
  update-usage-stats event-time
  run second next-event
  print-event-queue
end 


; Creates a new customer agent, adds it to the customer-queue,
; and attempts to start service.

to arrive
  create-customers 1 [
    let color-index (arrival-count mod 70)
    let main-color (floor (color-index / 5))
    let shade-offset (color-index mod 5)
    set color (3 + shade-offset + main-color * 10)
    move-to-queue-position length customer-queue
    set customer-queue (lput self customer-queue)
    set time-entered-queue ticks
  ]
  set arrival-count (arrival-count + 1)
  schedule-next-arrival
  begin-service
end 


; If there are customers in the customer-queue, and at least one server is idle, starts
; service on the first customer in the customer-queue, using a randomly selected idle
; server, and generating a complete-service event with a time sampled from the exponential
; distribution. Updates the customer-queue display, moving each customer forward.

to begin-service
  let available-servers (servers with [not is-agent? customer-being-served])
  if (not empty? customer-queue and any? available-servers) [
    let next-customer (first customer-queue)
    let next-server one-of available-servers
    set customer-queue (but-first customer-queue)
    ;; Move each customer in the queue to the position of the customer in front of it.
    (foreach customer-queue (range length customer-queue)
          [ [cust pos] -> ask cust [  move-to-queue-position pos ]  ] )
    ask next-customer [
      set time-entered-service ticks
      set total-time-in-queue
        (total-time-in-queue + time-entered-service - time-entered-queue)
      set total-queue-throughput (total-queue-throughput + 1)
      move-to next-server
    ]
    ask next-server [
      set customer-being-served next-customer
      set next-completion-time precision (ticks + random-exponential mean-service-time) 2
      set label (word precision next-completion-time 2 " ")
      insert-event-into-event-queue (list next-completion-time (word "complete-service " who))
      set color red
    ]
  ]
end 


; Sets all aggregate statistics back to 0 - except for the simulation start
; time (used for computing average customer-queue length and average server utilization),
; which is set to the current time (which is generally not 0, for a begin-stats-collection
; event).

to begin-stats-collection
  set-plot-pen-color black
  set total-customer-queue-time 0
  set total-customer-service-time 0
  set total-time-in-queue 0
  set total-time-in-system 0
  set total-queue-throughput 0
  set total-system-throughput 0
  set stats-start-time ticks
end 

to-report begin-stats-collection-time
  report round (max-run-time * begin-stats-% / 100)
end 


; Updates time-in-system statistics, removes current customer agent, returns the
; server to the idle state, and attempts to start service on another customer.

to complete-service [server-id]
  ask (server server-id) [
    set total-time-in-system (total-time-in-system + ticks
        - [time-entered-queue] of customer-being-served)
    set total-system-throughput (total-system-throughput + 1)
    ask customer-being-served [ die ]
    set customer-being-served nobody
    set next-completion-time 0
    set color green
    set label ""
  ]
  begin-service
end 

to-report event-to-string [event]
  report (word first event ": " second event)
end 


;; Don't insert events at or past max-run-time into the event queue.

to insert-event-into-event-queue [an-event]
  if first an-event <= max-run-time [
    set event-queue (insert-item-into-queue an-event event-queue)
  ]
end 

to-report insert-item-into-queue [an-event the-queue]
  if empty? the-queue [report (list an-event )]
  let first-event first the-queue
  report
    ifelse-value (first an-event <= first first-event)
           [fput an-event the-queue]
           [fput first-event insert-item-into-queue an-event but-first the-queue]
end 


; Move to the specified customer-queue position, based on the global spacing parameters.
; The customer-queue display is purely cosmetic, and has no functional purpose or
; impact.

to move-to-queue-position [queue-position]
  let new-xcor
    (max-pxcor - customer-xinterval * (queue-position mod customers-per-row))
  let new-ycor (server-ycor + customer-queue-server-offset
    + customer-yinterval * floor (queue-position / customers-per-row))
  ifelse (new-ycor > max-pycor)
    [ hide-turtle ]
    [ setxy new-xcor new-ycor
      if (hidden?) [ show-turtle ] ]
end 


; Reports the busy server with the earliest scheduled completion.

to-report next-server-to-complete
  report (min-one-of
    (servers with [is-agent? customer-being-served]) [next-completion-time])
end 

to print-event-queue
  clear-output
  if not empty? event-queue [
    let n (min (list 10 length event-queue))
    let events (take n event-queue)
    foreach but-last events [ s -> output-print event-to-string s ]
    output-type event-to-string last events
  ]
end 


; Samples from the exponential distribution to schedule the time of the next
; customer arrival in the system.

to schedule-next-arrival
  let increment random-exponential (1 / mean-arrival-rate)
  insert-event-into-event-queue (list precision (ticks + increment) 2 "arrive")
end 

to-report second [a-list]
  report first but-first a-list
end 

;; the first n elements of a list

to-report take [n a-list]
  report ifelse-value (n <= 0 or empty? a-list)
             [ [] ]
             [ fput first a-list take (n - 1) but-first a-list ]
end 


; Updates the usage/utilization statistics and advances the clock to the
; specified event time.

to update-usage-stats [event-time]
  let delta-time (event-time - ticks)
  let busy-servers (servers with [is-agent? customer-being-served])
  let in-queue (length customer-queue)
  let in-process (count busy-servers)
  let in-system (in-queue + in-process)
  set total-customer-queue-time
        (total-customer-queue-time + delta-time * in-queue)
  set total-customer-service-time
        (total-customer-service-time + delta-time * in-process)
  tick-advance (event-time - ticks)
  update-plots
  set max-queue max list max-queue length customer-queue
end 


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Theoretical values calculations ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; Compute the expected utilization, customer-queue length, and time in customer-queue for an M/M/n
; customer-queueing system.

to compute-theoretical-measures
  let balance-factor (mean-arrival-rate * mean-service-time)
  let n (count servers)
  ifelse ((balance-factor / n) < 1) [
    let k 0
    let k-sum 1
    let power-product 1
    let factorial-product 1
    let busy-probability 0
    foreach (n-values (n - 1) [ ?1 -> ?1 + 1 ]) [ ?1 ->
      set power-product (power-product * balance-factor)
      set factorial-product (factorial-product * ?1)
      set k-sum (k-sum + power-product / factorial-product)
    ]
    set power-product (power-product * balance-factor)
    set factorial-product (factorial-product * n)
    set k (k-sum / (k-sum + power-product / factorial-product))
    set busy-probability ((1 - k) / (1 - balance-factor * k / n))
    set expected-utilization (balance-factor / n)
    set expected-queue-length
      (busy-probability * expected-utilization / (1 - expected-utilization))
    set expected-queue-time
      (busy-probability * mean-service-time / (n * (1 - expected-utilization)))
  ]
  [
    set expected-utilization 1
    set expected-queue-length "N/A"
    set expected-queue-time "N/A"
  ]
end 

; Checks to see if the values of the mean-arrival-rate and mean-service-time
; sliders have changed since the last time the theoretical system measures
; were calculated; if so, the theoretical measures are recalculated.

to update-theoretical-values
  if ((save-mean-arrival-rate != mean-arrival-rate)
      or (save-mean-service-time != mean-service-time)) [
    set save-mean-arrival-rate mean-arrival-rate
    set save-mean-service-time mean-service-time
    compute-theoretical-measures
  ]
end 

There are 2 versions of this model.

Uploaded by When Description Download
Russ Abbott about 1 year ago Minor formatting changes Download this version
Russ Abbott about 1 year ago Added an event queue Download this version

Attached files

No files

Parent: Discrete Event Simulation: Queues and Servers

This model does not have any descendants.

Graph of models related to 'Discrete event with event queue'