[Arjen Markus] (25 june 2007) Monte Carlo simulations are useful in many cases where the system being studied reacts to random input, but also if you want to determine the integral of a function over a complicated area. Such simulations usually require a lot of steps and sometimes numerous runs to get meaningful results. The script below is an attempt to model a simple queueing system. See the comments for more information. It tries to answer a vexing question: how long does one have to wait (on average)? ---- # simple_queue.tcl # A simulation of a queue: # - On average 1 person per 5 minutes enters the system # - Handling his/her request takes either 3 minutes or 10 minutes # (with a 1/10 chance for the longer request). # - The average handling time is therefore (9*3+10)/10 = 3.7 minutes # - The system can handle this - on average # - Question is, however, what is the mean waiting time? If you # are in the queue behind two people whose requests will take 10 # minutes, you will be waiting longer than if these two both have # the short requests # # randomBinomial -- # Return a random value (0 or 1) according to the binomial distribution # # Arguments: # p Chance of returning 1 # # Result # Random value of 0 or 1 # proc randomBinomial {p} { return [expr {rand()>\$p? 0 : 1}] } # runQueue -- # Run the queuing system # # Arguments: # nosteps Number of steps to run the system # # Result: # None # # Side effects: # Fills the global variables waiting_times and queue # proc runQueue {nosteps} { global waiting_times global queue # # Start with an empty queue # set queue {} # # Loop over time # for { set time 0 } { \$time < \$nosteps } { incr time } { # # New client entering the system? # if { [randomBinomial 0.2] == 1 } { if { [randomBinomial 0.1] == 1 } { set request 10 } else { set request 3 } set person [list \$time \$request] lappend queue \$person } # # Handle the current request, if any # if { [llength \$queue] > 0 } { set person [lindex \$queue 0] foreach {arrival_time request} \$person {break} if { \$request <= 0 } { # We are done with this client set queue [lrange \$queue 1 end] lappend waiting_times [expr {\$time-\$arrival_time}] } else { # Reduce the time left for the request set request [expr {\$request-1}] lset queue 0 1 \$request } } } } # main -- # Run the queueing system, timestep is one minute: # For a period of 8 hours (480 minutes), do the following # every minute: # - If someone comes in, add them to the queue with the arrival # time and the type of request # - If there is someone in the queue, take one minute off the # remaining time for their request, if it is positive. Otherwise # remove the entry from the queue and record the waiting time # # To get a fairer estimate, we run the queueing system 50 times set av_av_time 0 set av_max_time 0 set av_queue 0 set av_count 0 for { set i 0 } { \$i < 50 } { incr i } { set waiting_times {} runQueue 480 set count 0 set average_time 0 set max_time 0 foreach time \$waiting_times { set average_time [expr {\$average_time + \$time}] incr count if { \$time > \$max_time } { set max_time \$time } } set average_time [expr {\$average_time/double(\$count)}] set av_count [expr {\$av_count + \$count}] set av_av_time [expr {\$av_av_time + \$average_time}] set av_max_time [expr {\$av_max_time + \$max_time}] set av_queue [expr {\$av_queue + [llength \$queue]}] puts "Simulation \$i: [format %.1f \$average_time] - \$max_time" } puts "Sample averages:" puts "----------------" puts "Number of persons: [format %.1f [expr {\$av_count/50.0}]]" puts "Average waiting time: [format %.1f [expr {\$av_av_time/50.0}]]" puts "Maximum waiting time: [format %.1f [expr {\$av_max_time/50.0}]]" puts "People still waiting: [format %.1f [expr {\$av_queue/50.0}]]" ---- [[ [Category Mathematics] ]]