[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}]]" ---- [http://img515.imageshack.us/img515/8632/tclwikirandomqueuesym2.png] ---- !!!!!! %| [Category Mathematics] | [Category Simulator] |% !!!!!!