Discrete Event Simulator

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. 

     

We receive a few cents from each purchase.  Thanks

 


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Mensa® Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa® 365 Puzzlers  Calendar 2017

Mensa® 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

 

Problem Description

Create a program capable of  answering questions about job processing systems with input queuing.   

For example:  

A gas station has a single pump with customers arriving every 5 minutes on average, It takes an average of 4 minutes to fill up and pay. The owner makes $1 per customer, but a customer will give up and leave after 3 minutes, costing the station $8 in future profits. Each pump costs $1/hour in depreciation, electricity, overhead, etc. Should the owner install a second pump?

or

In a manufacturing firm, machines break down at the rate of 0.8 per hour, and the lost production cost of each machine waiting for service or repair is is estimated to be $25 per hour. There are two repair teams available to the firm. Team A asks for $25 per hour and guarantees that it can repair 1.5 machines per hour. Team B charges $20 per hour and can fix 1 machine per hour. Which team should the firm employ?

 

Background & Techniques

A couple of caveats -  

1. Simulation systems are typically covered in graduate level Math or Computer Science courses, this page will not be the equivalent.  But if we skim over arrival and service time distribution math,  there is nothing too complex about the modeling.  In fact it's simpler and more flexible than pure analytical solutions.     

2. There are many "simulation languages"  -  for good reason.  The real world is complicated and serious simulations will require processing logic that doesn't fit  predefined models.  So each case on will typically have it's own program.  But there are lots of common features that we can model here.

 

 A system that serves discrete customers,  humans,  automobiles, messages, jobs, or dairy cows at milking time,  is a queuing system.  Such systems typically have one or more waiting areas and one or more servers.  The customers may be of different classes or priorities and be handled differently as a result (emergencies at the doctors office or the express line at the grocery store, for example).

 Most of our transactions involve queuing systems:  the gas station, bank, grocery store, post office,  doctor's office,  public restrooms, and phoning a business ("Your call is very important to us, please  hold for the next available representative" ha!) , to name a few.  

Discrete event simulators are fun because they model these types of systems, especially this animated version where you can watch the little customers arrive, wait, get service and leave.  We'll define customer classes and their arrival and cost characteristics.  We'll also define one or more servers and what kinds of customer classes they can handle and how they process those classes.

Several sample problem are included with both source and executable versions of the program.  Most problems are from my old college text   "Introduction to Operations Research",  Frederick Hiller and Gerald Lieberman,  Holden-Day Inc.

The  details of defining job class and server characteristics are included with the program,  but for now  lets look at the basic program processing loop.

Non-programmers are welcome to read on, but if that sounds boring, click here to jump to the bottom of the page to download an executable version of the program.

Programmer notes

The key trick is that everything is driven off of future events queue.   We have four event types: Arrival, Start processing, End processing departure, and Give-up departure.    (Give-ups result when a maximum wait time parameter has been exceeded.)   Each event  generated is placed in the future events queue in future time sequence.   A new class TSim,   derived  from Delphi's TQueue type, serves as the future events queue.  Initially a single job of each class is created and placed in this queue.   The loop always  removes the top queue entry, updates the clock to that time,  and acts based on it's type.

bulletArrivals check for an idle server that can process it's class and starts the job immediately if one is found.   Otherwise the job is placed in a First-in, First-out (FIFO) Wait queue to be removed later when an appropriate server becomes idle.   When the server starts a job, it calculates when it will finish, marks itself as busy,  and places the Departure event on the future events queue.  
bulletStartProcess events do not get added to the wait queue but they are passed to the optional Callback procedure (as are each of the other event types) in order to allow the caller to add event specific processing.   In this program, Callback is used to implement the animation.  
bulletWhen a Departure event is popped off of the future events queue, the server checks for another job on a wait queue to process and starts that job if one is found.  
bulletMaxWaitTime events result in removing the job from the wait queue and updating statistics to indicate that a job was lost.

This is a large, fairly complex,  program (2500+ lines of code) and has lots of rough edges remaining.  I could spend a couple of more weeks more working on smoothing them out.    But the great thing about writing for fun, is that I don't have to!    

Learn and have fun!  

Running/Exploring the Program 

bulletDownload Source (including sample cases)
bulletDownload executable (including sample cases)

Suggestions for Further Explorations

A few  possible enhancements: 

Priorities - the option of assigning priority to customers has not been implemented here.  Priorities alter the normal First-in, First-out wait queue to a "priority queue" where members are arranged by waiting time within priority.  For example: transactions may be assigned classes as short, medium, or long based on their service requirements, but within each of these classes it might be desirable to have priorities move entries to the waiting queue at some location other that at the end.  
"Balking" - customers may be lost based on waiting queue size.
Uniform service time distributions uniform  within a range (I have a sample problem that can't be simulated with the current program. It tests replacement strategies for part failures with part life distributed uniformly between 2000 and 4000 hours.  Not)  
"Custom" arrival time distribution could come in several flavors.  One interesting one is to collect actual arrival data and use that to drive simulations to see the effect of different processing strategies. 

 

Original: October 28, 2002

Modified: May 15, 2018

 

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright © 2000-2018, Gary Darby    All rights reserved.