Exercises

From Sigma

(Difference between revisions)
Jump to: navigation, search
(Spreadsheet interface)
Line 500: Line 500:
Create a spreadsheet interface for the experiment in the previous exercise.
Create a spreadsheet interface for the experiment in the previous exercise.
 +
 +
 +
[[Main Page|Back to Main Page]]

Revision as of 22:18, 7 August 2008

Here you will find an index of exercises categorized by topic.

Contents

Discrete Event Systems Modeling

Model Evaluation

Read a recent article where discrete event simulation models are used to solve real-world problems. Some of the publications you might look at are Management Science, Interfaces, Industrial Engineering, Operations Research, Material Handling, Medical Care, Computer Performance Evaluation, Expert Systems, and Simulation. Conference proceedings in various fields of engineering also have articles about simulation; in particular, the Winter Simulation Conference Proceedings is a good source.

Collect or create the following:

  1. Photocopies of the title page and abstract of the article (explicitly give the source).
  2. A brief statement of the objective of the simulation project (in your own words).
  3. What programming language was used? Did they justify their choice?
  4. A paragraph describing what real-world data was needed for the model and how it was collected.
  5. A paragraph describing what experiments were run with the model. What factors were varied? What system performance measurements were taken? What analysis was done with these measurements?
  6. Give a one-page critique of the article and project. What would you have done differently?

Short Answers

  1. Give the most important advantage as well as the greatest disadvantage to having a simulation model with very few events as opposed to an equivalent model with many events.
  2. What two features generally distinguish a discrete event simulation program from other types of programs?
  3. What are the two broad classifications of entities in a discrete event system?
  4. Give one advantage and one disadvantage to modeling the flow of transient entities in a system.
  5. Does a model with few entities each having many attributes have more or less detail than a model with many entities each having fewer attributes? Which will generally take more memory to run? Why?

Identifying Discrete Event Systems

For a real system of your choice, describe the system in less than a page and give a one-sentence objective for studying this system with a simulation model. Identify the dynamic attributes of entities in the system and the events where these attributes change values. Give a rough event graph for the system. (Pick something interesting to you (but simple).

Simultaneous Events

In the carwash model, if Q=5 and there is a time tie between an ENTER event and a LEAVE event, which event should be executed next? Why?

Events List

In the event graph of Figure 2.6, what is the maximum number of events that might be scheduled on the events list at one time?

Edge Interpretation

For Figure 2.5, which of the following statements are true?

  1. Whenever event A occurs: if t time units later, condition (i) is true, then event B will be scheduled to occur immediately.
  2. Whenever event A occurs: if condition (i) is true, then event B will be scheduled to occur t time units later.
  3. Whenever event A occurs and condition (i) is false, event B will be scheduled to occur t time units after condition (i) becomes true.

Future Events List

Assume for the example in Table 2.4 that the times between the next three part arrivals are 2, 1.5, and 3.2 (each ARRIVAL event schedules the next ARRIVAL event in this model). Furthermore, assume that the processing time for each machine is 0.5 minutes and that there are currently 6 parts waiting in the queue for processing. Finally, assume that once machine 2 is repaired it will be 10 minutes before it breaks again. What does the future events list look like at time 8.00? What is the status of each machine? How many parts are waiting in the parts queue?

Simultaneous Event Errors

Assume that for the model corresponding to the future events list in Table 2.4 that the FINISH event made a machine idle and scheduled a START event if there were parts waiting in the queue. Also assume that an ARRIVAL event will schedule a START event if it finds an idle machine. What would happen if a part arrived at time 4.40, just as machine 0 finishes processing? What would happen if the FINISH event occurred before the ARRIVAL events?

Running a Sigma Simulation

The models referred to in these exercises are SIGMA models.

A Semi-Random Walk

Build a simulation of a semi-random walk. The location of the walker on the line is given by the variable, X. Every step is in an opposite direction and has an expected step length equal to 4 feet. However, the steps to the right are uniformly distributed between 3 and 5 while steps to the left are exactly 4 feet long. Would you expect the location of the walker to change much over time?

Stopping a Run Based on Event Counts

Run CARWASH.MOD until 10 customers LEAVE the system.

Time Scaling

Without changing the run stopping criterion in the Run Options dialog box, double the effective run duration of CARWASH.MOD. (Hint: Rescale the unit for measuring time from minutes to half-minutes.)

Event List Dynamics

Twenty jobs were run through a computer system with one CPU. They all had one of three priorities (lowest number has higher priority and is executed first). A historical data file of these jobs is as follows:

Job     Time job        Job        CPU time
Number  was submitted   priority   used by the job
1	    .00             1       .02
2	    .00             2       .01
3           .01             3       .02
4           .02             2       .04
5           .04             3       .02
6           .05             2       .01
7           .07             1       .01
8	    .12	            1	    .01
9	    .14	            2	    .02
10	    .15	            1	    .01
11	    .15	            2	    .01
12	    .17	            1	    .02
13	    .18	            3	    .04
14	    .21	            1	    .03
15	    .22	            2	    .05
16	    .23	            1	    .02
17	    .23	            1	    .01
18	    .26	            1	    .03
19	    .33	            2	    .02
20	    .34	            1	    .03
  1. By hand, schedule the job submission and job completion events as they would occur if all jobs had the same priority; assume that nothing else changes except the priorities. Schedule only the next job submission and next job completion event, not all future job submissions (that is, at most two events will be scheduled at any given time). At time 0.25 what is the state of the system, i.e., the number of jobs in the queue, the status of the CPU (busy/idle), and the events that are scheduled to occur in the future (and when they are scheduled)?
  2. Do part (a) with the execution priorities enforced.
  3. Assume that a second identical CPU has been installed and that the two processors operate in parallel on the same single queue of jobs. A single CPU will finish a complete job before taking the next job in the queue. With job priorities enforced, plot the queue size and number of idle CPU's every .01 time units.

A Theater with Limited Seating Capacity

Suppose that customers arrive at a movie theater at a uniform rate of one every 10 to 25 seconds and each is served in constant time of 20 seconds. There is limited seating in the theater, so the ticket window closes after it has sold 100 tickets. Model this queue.

A Restaurant

A popular restaurant, which does not accept reservations, serves parties in the order that they arrive. For dinner, parties arrive with a rate uniformly distributed between 5 and 15 minutes. Parties range in size from 2 to 6 people, each with the same probability of arrival. Service time for each party, regardless of size, is 2 hours. Assume the restaurant has a capacity for 12 parties. Model this system.

Event Graph Modeling

The models referred to in these exercises are SIGMA models.

Batch Arrivals to a Queue

Assume that cars arrive at a drive-up fast food restaurant with equal probability of having 1, 2, 3, or 4 customers in the car. Assume that service takes between 25 and 35 seconds per customer and cars arrive every 1 to 3 minutes (both service and interarrival distributions are uniform). Modify the carwash event graph in Figure 2.6 to model this system.

Parameter Passing

In the following event graph, plot the values of X at times 0 to 6.5?

Future Events List

In a simulated queue with one line and five parallel servers (like Bank1.MOD):

  1. What is the minimum number of events on the events list while the simulation is running?
  2. What type of event(s) does this minimum list contain?
  3. What is the maximum number of events on the list during a run?
  4. What type of event(s) does this maximum length list contain?

Limited Waiting Space

Assume that the waiting line in BANK1.MOD has space for only 5 customers; there are three tellers. The maximum number of customers in the system is eight: three in service and five in line. Customers who arrive to find a full system are turned away. Change BANK1.MOD to reflect this constraint and re-run the first 30 customer service completions. Print your graph, output, and model. Record the number of arrivals that were turned away because the queue was full when they arrived. Again calculate the average waiting time for the first 10, 20, and 30 customers. Compute averages by hand or use a special statistics gathering vertex).

A Two Server Queue

Consider a queueing system with a single line and two identical parallel servers. The resident entity model, BANK1.MOD, and the transient entity model, BANK2.MOD, on your SIGMA disk are simulations of such a system.

Modify BANK2.MOD to have a finite capacity in this system of a total of at most 10 customers (a maximum of two customers in service and eight waiting in line). Arrivals that occur when the system is full are turned away. Customer arrivals occur according to a Poisson process with a constant rate of 1.5 customers per minute. (This is the same as exponentially distributed interarrival times with a mean of 1/1.5 = 0.667, given by .667*ERL{1}.) Each server has an exponentially distributed service time with mean of 1 minute. The arrival and service processes are all mutually independent. The objective for studying this system is to estimate the distributions for the customer waiting times and distributions for the server utilizations.

  1. Give the entities in this system (tell which are resident and which are transient). Give the attributes of each entity. Also list the sets of entities with their owners and members.
  2. List the events for this system. Give the state transformations for each event. Also give the conditions and delay times for scheduling each of the events. Show the relationships between events with an event graph.
  3. What event(s) should be scheduled initially to begin running this simulation for 100 simulated hours?
  4. What event(s) should be initially scheduled to run this simulation for 100 simulated customer service completions?
  5. What would happen if a customer tries to ENTER a full queue at the exact same time that another customer LEAVEs the server? Which of these two simultaneous events should be executed first?

Sensitivity Analysis

Customers arrive at an ice cream parlor at a rate uniformly distributed between 2 and 6 minutes and are served at a rate uniformly distributed between 3 and 8 minutes. Model this queue. After 4 hours, what is the average length of the queue? If another scooper is hired, what is the average length of the queue? How many scoopers must be hired to keep the average length of the queue below 2 customers?

Fast Food

Customers waiting for fast food are very impatient. If they see 4 or more people waiting in line already, they will not enter. At peak hours, customers arrive at a rate uniformly distributed between 0.5 and 3 minutes. With current processes, each customer can be served in 2 minutes. Can the processes be speeded up enough to make sure the store never loses customers? (no). Can we speed up service so that we have a very low probability of losing customers? (yes). What is the necessary processing time for a specified probability for losing a customer that you think is reasonable? Build a model that can be used to answer this question.

Parameter Passing

Give the number and types of events that will be on the list of scheduled events at time 21.5 in the following event graph.

A Bank

  1. Suppose that cars arrive at a bank's drive-through facility at a rate uniformly distributed between 2 and 10 minutes and each transaction requires 3 minutes. Model this queue.
  2. Now suppose that the bank added two more identical tellers and customers arrive at each one at a uniform rate between 5 and 15 minutes. Model this situation by modifying your answer for (a).

The Post Office

  1. Suppose customers arrive at a post office at a rate uniformly distributed between 2 and 3 minutes. A postal official can serve each customer at a rate uniformly distributed between 1 and 10 minutes. Model the service at the post office.
  2. Modify this model for a post office with 3 postal officials. Upon entry, all customers line up in one queue. The first person in the queue is served by the next available official.
  3. Modify this model again for a post office where one lazy clerk takes a 5 minute break (will not serve) after he serves 3 customers.

An Assembly Station

A factory mass produces widgets. Each widget has 3 component parts: A, B, and C. Each of these 3 types of parts is produced in its own area of the factory and then transported via assembly line to the assembly area. Parts A, B, and C arrive at the assembly area every 4, 5, and 10 minutes, respectively. A worker takes a time uniformly distributed between 5 and 10 minutes to assembly the widget. Model this production process.

Communications Network Repair

A local area network has 100 identical links between work stations. Links fail at random intervals. The time until a working link fails has an exponential distribution with a mean of 5 days. Once a link fails, it must wait for a repairman to fix it. The time to repair a link has a uniform distribution between 1 and 2 hours. A single repairman is on duty at all times. Build a simulation of this maintenance system. Use your model to develop a trade-off curve between performance of the system (how should this be measured?) and the number of repairmen on duty. (Hint: Use the model, CARWASH.MOD, as a starting place where links (instead of cars) queue up for the single repairman (instead of a carwash machine). Also note that the rate that links fail depends on the number of working links at a given time. (This failure process is called a state-dependent Poisson process.)

A Water Reservoir System

Three water reservoirs (at A, B, and C) serve a city through the pipeline system shown below.

Three identical (type 1) pumps at stations a, b, and c pump water from each reservoir to pumping station d. A large (type 2) pump at d pumps water to another type 2 pump at booster station e, which pumps water to the city. The time until failure of a type i pump (i = 1 or 2) is uniformly distributed between 12i and 4(i+1) months. Pump failures are independent, and pumps are not repaired until the water flow to the city actually stops. Model this system to predict when the city will run out of water due to pump failures.

Preventive Maintenance Policy Optimization

A conveyor system has 40 identical rollers, each with a failure distribution uniformly distributed between 20 and 45 days. When a roller fails, it must be repaired at a cost of $500. When preventive maintenance is performed on the conveyor, the cost is $300+$50*N, where N is the number of rollers replaced. A partial group replacement policy of performing preventive maintenance every M months and replacing all rollers over A months old is being considered. Model this system to try to suggest reasonable values for M and A.

Elimination of the Future Events List.

Create an event graph that is logically equivalent to the carwash model but does not schedule any events on the future events list. (Hint: Use a generic minimum function, min(a,b), to determine the next event time.)

  1. What is the main advantage of your modified model? (Consider speed)
  2. What is the main disadvantage of your model?

Queues with Blocking

There are three identical and independent servers for each of two tandem queues. There is room for only 3 customers in queue 2; when queue 2 is full, no one can exit from any of the first set of three servers until a service completion for the second set of servers occurs.

  1. Identify the resident and transient entities along with their attributes. Present your entity-attribute hierarchy in outline form. Give the set of possible values for each attribute.
  2. Identify sets of entities and tell which entities (if any) "own" each set and what entities may be members of each set.
  3. Describe the discrete events in the cycles of activities for each resident entity. Also describe the events in the path of each temporary entity as they flow through the system. For each event tell what state changes occur and the conditions for these changes along with what further events will be scheduled or cancelled in a computer routine for the event.

Simultaneous Events

In a queueing simulation, BRKDN.MOD (Figure 5.10), if an idle server is scheduled to start a break (STARTBREAK event) at the same time a customer arrival occurs (ARRIVAL event), which event should be executed first? No other events are on the events list and all other events have the same execution priority.

Nested Loops

  1. Create a nested loop with three index variables: I going from 1 to 4, J going from 1 to I, and K going from 0 to I*J.
  2. Create an event graph which finds the sum of all the elements of a 3 by 5 array.
  3. Give the event graph for a nested loop where the inner loop moves twice as fast as the outer loop.
  4. Draw an event graph for a program that produces the entries in a table that translates from 1 to 20 degrees Celsius to Fahrenheit.

Building Models

The models referred to in these exercises are SIGMA models. Exercises identified as mini projects are more extensive and may take considerably longer than the typical exercise.

Event Execution Priorities

Modify CARWASH.MOD so that arrivals occur exactly every 2 minutes and make the execution priorities on every edge the same. Run the model for 50 minutes then look at the output. What happens when an ENTER event and a LEAVE event take place simultaneously? What event should be executed first if there is an ENTER event and a START event scheduled at the same time and QUEUE=1?

Pre-emptive Vertex Execution

Using pre-emptive vertex execution, modify the model, CARWASH.MOD, so that the logic of the simulation does not change but the number of events scheduled on the future events list is minimized. (Hint: Make some of the edge delay times equal to *; you will in effect incorporate the START vertex into both the ENTER and the LEAVE events).

Why might the output from a model that uses pre-emptive vertex execution be different from the output of the same model where pre-emptive execution is not used, i.e., all * delays are changed to 0? Why might the outputs be different even if the two models are logically equivalent in a probabilistic sense (output sample paths have the same probability of occurring)?

Pre-emptive Vertex Execution with Parameter Passing

Using pre-emptive vertex execution (edge delay times set equal to *), modify the multiple server queue, BANK2.MOD, so that the logic of the simulation is not changed but a minimum number of events are scheduled on the future events list.

System Reliability

Consider two systems, each with 50 identical components. System A is a serial system that fails when the first component fails. System B is a parallel system that fails when the last component fails. The times until failure, T, for the components are independent and have beta distributions with parameters 0.5 and 0.2. System B is obviously more reliable; however, it is desired to estimate the expected difference between the times until system failure for the two systems.

  1. Model both systems and then estimate the difference between the failure times of the two system.
  2. Would the variance of the sample difference generated in part (a) be biased? If so, in what direction?

A Drive-in Bank Window (Mini Simulation Project)

A drive-in window is added to the side of the bank being modeled by BANK2.MOD. This window is serviced by the same tellers as before. The tellers rotate in serving customers at the drive-in window. Each teller will serve one drive-in customer and then return to service the line in the bank. If there are no customers at the drive-in window when a particular teller's turn comes up, s/he will miss a turn at the window.

Drive-in customers arrive according to the same pattern as the customers who arrive on foot (as described in the text) except that during the noon hour (12:00 to 1:00 P.M.) drive-in customers arrive at the rate of 2 per minute. Drive-in customers will balk if there are three or more cars waiting for service at the drive-in window. Of the balking drive-in customers, 80% will try to park their cars in the bank parking lot and walk inside for service. Once a former drive-in customer parks and walks inside, s/he will not balk unless the line has more than 20 customers in it.

The bank rents parking spaces in an adjacent parking lot for its customers. Currently the bank rents spaces for 10 cars. Customers desiring parking will wait only 30 seconds in a full lot before balking. Assume that it takes between 2 and 3 minutes (uniformly) for a customer to travel from the lot to the bank and vice versa (including time to park).

To better serve their customers, the bank is considering hiring additional tellers. Each teller costs the bank $1500.00 a month in salary and fringe benefits. As an alternative, the bank is considering renting additional parking spaces at $150.00 a month each.

Experiment with your simulation to advise the bank if they should hire tellers or rent parking spaces (or both). State your decision criteria and any additional assumptions that you need to make (e.g., tellers absent from work). Evaluate each of your assumption. (Are the assumptions conservative? Are they realistic? Can you confirm them with real-world data?)

Variability and System Performance

The model FLOWSHOP.MOD is a simulation of a flow shop where there are several parallel machines at each of N sequential stations. A part needs to be processed by only one machine at each station. Run the system for three stations in a series where there are 5 machines at the first station, 3 machines at the second station, and 4 machines at the third station. The mean processing times (in hours) at each station have uniform distributions with means of 0.2 for each machine at the first station, 0.1 for the second station, and 1.5 at the third station. The processing time range is 0.05 for all machines. Run several 8 hour shifts and increase the processing time range to see the effect of variability on the performance of the system.

A Queue with Service Breaks

Modify the model, BANK2.MOD, to more accurately simulate a ticket line at a major airport. At the ticket counter there are three agents. The time it takes an agent to serve a single passenger has an ERLANG (3) distribution with a mean of 15 minutes (5*ERL{3}). Every hour each agents takes a 5 minute break. They rotate breaks so one agent goes on break every 20 minutes. When an agent's break time is due, s/he will immediately stop whatever s/he is doing and go on break. If the agent is busy at the time, the passenger must wait until the agent returns from the break. An agent will finish the remaining service of a customer when s/he comes off break. Customers may not change agents once they start service even if the agent goes on break; the agent has their ticket. All passengers arrive at this departure desk in a taxi. The time between taxi arrivals has an exponential distribution with a mean of 1 minute. Passengers sometimes arrive in groups to share the taxi fare. Each taxi carries between 1 and 4 passengers. The likelihood of a group size of 1 is 0.6, the likelihood of a group size of 2 or 3 is 0.15, and the likelihood of 4 passengers arriving in a taxi is 0.1. Customers arrive in groups but each is processed alone. Run your model and watch the queue build up. Do you think the queue length will ever stabilize or do you expect it to continue to grow in an unbounded manner?

Project Management

In the project management model in Section 5.6, assume that the activity times have beta distributions with both parameters equal to 0.5 (see Chapter 7) and scaled to be between the limits given in the following table.

Activity  Must Follow	Number of  Time Range
          Activities    Workers

A         None          1          1-3
B         A             1          1-5
C         None          1          2-4
D         B and C       2          3-7
E         B and D       1          2-4
F         C             2          4-6
  1. Run the simulation of this project 100 times and estimate the probability that the project will take longer than 14 days.
  2. Assume that there are only 3 workers and a task needs the number of workers specified in the table above (tasks cannot be done partially, they must be completed once started). Modify the model to account for this resource constraint (PUT activities in a queue when their precedence constraints are met but not enough workers are available to start; GET tasks from this queue when activities finish.)

Functions

Exercises identified as mini projects are more extensive and may take considerably longer than the typical exercise.

A Priority Serving System

  1. The system administrators of a mainframe computer have devised of method of partitioning processing time. Every job submitted to the mainframe is assigned a priority: urgent and not urgent. When two jobs have the same priority, the first one submitted is processed first. However, when two jobs are of different priority, the job with the higher priority is always processed first. Urgent jobs arrive at a rate uniformly distributed between 3 and 5 hours and have required processing times uniformly distributed between 1 and 10 hours. Not urgent jobs arrive at a rate uniformly distributed between 30 minutes and 1 hour and have processing times uniformly distributed between 15 minutes and 2 hours. Model the mainframe queue assuming every job, once it is started, is finished without preemption.
  2. Now model the mainframe queue where jobs can be pre-empted by priority. In other words, if a job is submitted to the mainframe while a job of lower priority is processing, the lower priority job is discontinued until the job of higher priority finishes. When a pre-empted job returns to the mainframe, it does not need to be entirely reprocessed. It is processed only for the required time remaining when it was pre-empted. Use the PUT and GET functions in modeling this system.

Empirical Distributions

How can the function, DISK{FILE;I}, be used to generate a random variable from an empirical distribution function with data in the disk file, FILE? (Hint: Consider a random index, I.)

Condensing Events

Use pre-emptive event execution (edge delays equal to * to "condense" several event vertices into a single event) to make the simulation, NETWORKR.MOD, run as fast as possible without changing the output. Be careful about using * too often and causing a stack overflow as explained in the text.

Worker Assignment Problem

In the model, TWOQUEUE.MOD, there are 2 servers assigned to a constant time set-up operation followed by 6 workers assigned to a random time processing operation. Is this a good assignment of the 8 workers? Experiment with the model to determine an optimal allocation of the 8 workers, assuming that all of the workers are equally skilled and paid the same amount. Justify your answer (how do you define "optimal" and why?) as well as the way you designed your experiment.

Execution Priorities

Look at the model, TWOQUEUE.MOD. This is a model of two multiple-server queues in a series, where a constant time setup operation is followed by a random duration processing operation. The first set of servers has a constant service time of 5 minutes. The second set of servers has a random service time with an Erlang(1) (i.e., exponential) distribution with a mean of 4 minutes.

  1. Click on the double edge between the STRT1 and LEAV1 vertices. Change the execution priority on the edge from the LEAV1 vertex to the STRT1 vertex from 3 to a 5. Notice that QUEUE[1] goes negative before time 60. Why?
  2. Change the execution priority on the self-scheduling edge from STRT1 to STRT1 from 1 to 6. Notice that the number of idle servers for queue 0 goes negative right away. Why?

Welding Line (Mini Simulation Project)

The following system is used to weld hoods to automobiles. There are several parallel welding robots. The cars pass by the robots on conveyor lines. Transfers between lines are done using cranes that run north and south on fixed tracks. A schematic of the system for four welding robots is given below.

Type	Percent	Average Weld Times
A	31%	50 (sec.)
B	16	63
C	16	25
D	16	41
E	12	155
F	 9	155

The input rate is 93 jobs per hour. There are six types of automobiles produced at this plant. The average welding times and percentages for each type of car are given below the figure. The time it takes for the crane to pick up a car or release a car is 8 seconds. For simplicity we consider only an approximation to the effects of crane acceleration. The first section of track traveled takes 9 seconds and every additional section traveled without stopping takes 6.5 seconds. A section of track is between each of the loading or unloading points on a crane track. For example, the crane takes 15.5 seconds to travel two sections of the track without stopping.

Cars must leave the welding operation in the same order that they enter it since components added later on in the assembly process must be for the right car. Set-up times for some of these later operations are very large, thus, requiring that set-ups start before cars arrive. The last crane in the schematic above is to sort the cars as they come out of the hood welding operation.

Write a simulation program for this system. For now, consider each of the times to be deterministic. Your model should allow up to three cranes per track and up to six parallel robots. You may use any computer language that you wish for this assignment. Flesh out your model and translate it to C to fill in the details (see Chapter 11). Use "entities" and the PUT and GET functions.

In the automobile production sub-system simulation model, add 33 seconds to each of the average welding times given. Now make the welding times uniformly distributed with a range of 20% of the mean. All confidence intervals are to be at the 90% level.

  1. Run the simulation of the automobile production system five times for 200 cars each. Use independently selected pseudo-random number generator seeds for each replications. Compute a confidence interval for the mean throughput rate of the system (rate that cars exit).
  2. Run the simulation for one run of 1000 automobiles. Compute confidence intervals for the mean throughput rate using the batched means method with 5 batches.)
  3. Comment on the above experiment, including identification of possible sources of error.
  4. Given that there are spaces for 15 automobiles in the system, decide how these 15 buffer spaces should be allocated. Justify your design and give confidence intervals for the throughput rate.

A Barge Unloading System (Mini Simulation Project)

River barges arrive at a warehouse carrying "piggyback" truck trailers mounted on flatcars. These flatcars are to be unloaded and mounted on railroad flatcars that will be taken away by trains. There are 4 trailers on each barge. The time between barge arrivals has a uniform distribution between 3 and 5 hours. A barge must wait for a single berth before it can dock. A single crane is used to move the trailers from the barge to the warehouse and from the warehouse to the flatcars. After being unloaded from the barges and mounted on flatcars, the trailers are taken to a large rail yard where they are assigned to trains according to their destination.

Once a barge has docked, 4 spaces in a warehouse must be free in order for unloading to start. There are 20 trailer spaces in the warehouse. The time to unload a barge is uniformly distributed between 1 and 3 hours. A train arrives at the warehouse to collect the waiting trailers. The time between train arrivals has a uniform distribution between 3 and 7 hours. The train has between 6 and 12 empty flatcars when it arrives. It takes 30 minutes to load each trailer onto a flatcar.

  1. Develop a resident entity simulation model that will keep track of the lengths of all important queues and utilizations of the warehouse space, berths, and crane. Clearly state any assumptions you are making in your model. Run this model for a time of 20 (hours) and trace the number of trucks unloaded. Run the model for 100 hours in High Speed mode and use the output file see how many trucks were unloaded from the barges. What is the major bottleneck: the berth, number of available flatcars, warehouse space, the crane?
  2. Consider the purchase of an automatic crane that cuts the barge unloading time by 50%. Model this (reduce the delay time between the start unload event and the end unload event). Run the new model for 100 time units and observe (from the output trace) the number of trucks unloaded. Do not create any new state variables.
  3. Add the necessary (two) event vertices that permit the crane to shut down every 10 hours for 1 hour of preventive inspection/maintenance. The crane will finish what it is doing before undergoing inspection.
  4. Eliminate the inspection/maintenance procedure and have the automatic crane break down every 8 to 12 hours (uniformly distributed). Have the repair time be uniformly distributed between 0.5 and 1.5 hours. If the crane is busy when it breaks, the current unloading operation must be restarted from scratch (use a cancelling edge). Run the simulation for 100 hours and compare with the systems in parts (a), (b), and (c). (This problem was suggested by G. Samorodnitsky.)

Buffer Capacities

In the model, NETWORKR.MOD, assume that each machine group has a finite capacity queue. For machine group, G, no more than B[G] jobs can be waiting. If the next queue for a job is filled, that job does not free its machine; it is blocked. Enrich your model to include this constraint. Be careful not to send two parts to a queue that only has space for one; when the second part arrives, it will find the queue full! (Hint: Reserve space in the next queue before freeing the current machine.) Assume that B[G] is 4 for all machine groups, and run at least 20 jobs through your model. Debug your model.

A Layout (Mini Simulation Project)

Using NETWORKR.MOD as a starting place, include the transit times between the various machines. Assume the job transit data is deterministic (conveyors?) and is provided in an array called TRANS(I,J), which is the time it takes to travel from machine group I to machine group J. The transit times are proportional to the distance between machine groups (state assumptions you are making). What data structures in C could be used effectively in this model? (Hint: The ENTITY structure). Tell how the structures will be used. How is your model improved with these structures (if at all)?

  1. Translate your model to C.. Use this simulation (or your model) to help determine an efficient high-level layout for a jobshop (i.e., the shapes, sizes, and locations for the different machine groups. Each machine takes 16 square yards of space (including space for the job being processed and aisle space). Each job waiting in the queue takes 4 square yards of space. Transit between machine groups is by overhead crane, so travel is rectilinear not line-of-sight. Transit time between machine groups is 5 seconds per yard traveled between the head of each input queue. Write a report that explains and sells your design.
  2. Assume that you will make $10 for each type 1 job completed, $20 for each type 2 job completed, and $30 for each type 3 job completed. You may sequence the jobs in each queue in any manner you see fit. With the machines specified in the text, lay out the factory to maximize the rate that income is generated and minimize the size of the factory.
  3. To help solve this problem, design and run experiments to decide how to allocate waiting space for work-in-process (be creative). Explain the rationale for your experimental strategies: How did you initialize the system? Determine run lengths? Use variance reduction techniques? Compute confidence intervals?

Processing Priorities

Assume in NETWORK.MOD that completed type 1 jobs are worth twice as much money as type 2 jobs, which in turn are worth three times the money as type 3 jobs. It has been suggested that the jobshop operate by priority. The obvious scheme is to process waiting type 1 jobs before waiting type 2 jobs, with waiting type 3 jobs to be processed last. Make the necessary adjustments to your model for priority job processing. (Use the PUT and GET functions in SIGMA.)

  1. Make 5 runs of 8 hours each with the priority service rule and 5 runs of 8 hours with the current FIFO rule (a total of 10 one-day runs). Use independent streams for each run and estimate a confidence interval for the difference in total income for the day.
  2. Repeat this experiment using common seeds for each pair of runs (with and without the priority rule). Use independent seeds for different pairs of runs. Again estimate a confidence interval for the difference in total income for the 8 hour day.
  3. Comment on the differences between parts (a) and (b). What might be wrong with this experiment? Do you recommend the priority processing rule? Do you know a better one?

Motor Vehicles Department (Mini Simulation Project)

A State Motor Vehicles office has three clerks on duty. The office opens at 10:00 A.M. and closes its doors at 5:00 P.M. Customers already inside the office after closing are served. Between the hours of 10 and 12 (noon), walk-in customers arrive according to a Poisson process at a rate of (t-10) customers per minute, where t denotes time in hours. Between the hours of 12 and 13 (i.e., over the noon hour), customers arrive at a constant rate of 2 . Finally, between times 13 (1:00 P.M.) and 17 (5:00 P.M.), the arrival rate is (17 - t)/2.

Clerks process customers according to a uniform distribution between 0.5 and 2 minutes per customer. Occasionally a customer will call on the telephone and one of the clerks will take the call (possibly interrupting service for a customer). The time between phone calls is distributed as an exponential random variable with a mean of 5 minutes. It typically takes half the time to serve a call as to serve a walk-in customer. Every 20 minutes, one of the clerks is due for a ten minute break on a rotating basis (one break per hour for each clerk).

  1. With at most 10 runs of the model give an estimate of the capacity of the system as a function of the demand constant . Use whatever system performance measures you think are reasonable and justify them. Make and carefully state any additional assumptions about the system that you need; be sure to offer some justification for each assumption. A run is for a single day of operation. Carefully plan your experiment and give the rationale for your experimental design.
  2. As an aid in contract negotiations, consider the effect of adding an additional clerk or cutting the amount of break time taken by each clerk.

There is a plan to add a drive-up window to the office. This window is to be serviced by the same clerks that serve walk-in customers. Drive-in customers arrive according to the same pattern as the walk-in customers. Drive-in customers will balk if there are 3 or more cars waiting for service at the drive-in window. Of these balking drive-in customers, 80% will try to park their cars in the parking lot and walk inside for service. Once a former drive-in customer parks and walks inside, s/he will not balk unless the line has more than 10 customers in it. The parking lot has space for 10 cars. Customers desiring parking in a full lot will wait only 30 seconds before balking. Assume that it takes between 2 and 3 minutes (uniformly) for a customer to travel from the lot to the office and vice versa (including time to park).

Enrich you simulation to include the possible drive-in window. Use the your model to advise the State as to what they should do (hire more clerks?, build the drive-up window?, increase the size of the parking lot?, etc.).

A Turnpike Gas Station

A toll road gas station has 2 pumps in tandem but only 1 access lane. Cars arrive only from the left at intervals that are spaced T minutes apart. Pumping gas and paying takes P minutes. If both pumps in a lane are free when a customer arrives, the customer will use the "down stream" pump. A car at pump 1 cannot pass a car at the pump in front of it even if it has finished.

  1. What are the resident entities in this system? What are their attributes? What are the transient entities and their attributes? Describe, in words, the resident entity cycles and transient entity path(s). List any additional assumptions you are making about this system? Give an event graph model for the resident entities in this system. At a minimum, your graph could be used to measure the utilization of each pump.
  2. Create a SIGMA model of the turnpike gas station. Modify the problem so that if there are four or more cars in line when a customer arrives, the customer will go on to another station. Run you model until 20 cars have been served and analyze the queue size and utilization of each pump (charts, numbers, intuition, etc.). Start the system empty. Assume that car interarrival times are uniformly distributed between 1 and 5 minutes and service times are between 1 and 7 minutes.

A Turnpike Gas Station (continued) (Mini Simulation Project)

Enrich the preceding turnpike gas station model to include two access lanes, one on either side of the pumps. Potential customers arrive from the right at intervals that are randomly spaced. Assume that customer interarrival times are uniformly distributed between 2 and 6 minutes when coming from the left and uniformly spaced between 2 and 4 minutes when coming from the right. Service times are between 3 and 5 minutes at each pump.

  1. Customers cannot pass cars in front of them even if they have finished. Each pump can pump to only one car at a time in either lane and cars cannot drive around to change lanes. If there are more than four cars waiting in a lane, customers arriving from that direction will not stop. Draw an event graph of this system that can be used to study the resident entities (pumps and queues). Carefully justify your event graph model; do not just tell what you did and how, include why!
  2. Create a SIGMA model of your graph and print the English translation (*.ENG) and the event graph for your model. Run your model and discuss the output (what kinds of questions can you answer with your model?).
  3. Using the PUT and GET functions, collect waiting time data for customers in each lane. Present and discuss histograms and time plots of the waiting time data.
  4. Using event parameters, tell us how you would enrich your model to include several service islands.
  5. Consider two service options: "full" service where service times are between 3.5 and 4.5 minutes at each pump and "self" service where service times are uniformly between 1 and 7 minutes at each pump. If both pumps are free when a customer arrives, that customer will use the "down stream" pump only half the time unless there is a "full" service attendant on duty. Create a SIGMA model of this system that can be used to study these two alternatives. Run your model under each alternative for 1 simulated hour. Write up your experiment and recommendations in less than five pages. How much can you afford to pay the extra attendant needed for the full service option (in terms of profit from lost sales)?

Parts Assembly

In an assembly operation, machines A, B, and C make parts that are joined together by machine D. It takes 3 parts from machine A, 2 parts from B, and 1 part from C for each assembly operation at machine D. All processing times have exponential (Erlang{1}) distributions. The mean processing times are input to the simulation as parameters of the first vertex. Build a simulation model of this simple assembly operation. Run your model for 10 complete assembly operations where the mean processing times for machines A, B, C, and D are 0.1, 0.2, 0.3, and 0.4. Which machine appears to be the bottleneck machine in this operation? What if the machine D's processing time were reduced to 0.05 minutes? Translate your model to C or Pascal and run it until 1000 assemblies are finished. Does your bottleneck machine change once the system has warmed up?

The Texas Ferry Service (Mini Simulation Project)

Along the Texas Coast, an east-west four-lane highway was built to promote the tourist trade to the Padre Islands. Unfortunately, this highway must cross a wide channel used by large oil tankers. Providing free automobile ferry service is considered to be an alternative to building a bridge. There is room for up to 6 loading/unloading berths on each side of the channel. Whenever a tanker comes through the channel, the ferries have to wait until it passes. Evaluate the ferry option. Do a sensitivity analysis to various levels of demand. (How much can we spend on a bridge? How bad can it be?) Hint: Consider modeling aggregate arrival processes; e.g, ferry-loads/hour for the different size ferries.

Relevant data is as follows: Each berth costs $2,500,000 to build. There are three sizes of ferries that can use the berths:

Type 0 holds 25 cars and costs $1,500,000,
Type 1 holds 50 cars and costs $3,250,000,
Type 2 holds 100 cars and costs $5,500,000. 

On Friday afternoons during a two-hour peak period, it is estimated that cars will arrive roughly according to a Poisson process with a rate of 20 per minute from the east (Corpus Christi toward the Padre Islands). The time between arrivals is thus 20*ERL{1}. On Sunday afternoon over a four-hour period, roughly the same number of cars will return to Corpus Christi. At other times (during the tourist season) traffic in both directions is expected to arrive at a rate of about 6 cars per minute.

The ferries take between 12 and 18 minutes to cross the channel (depending on the tides). Tankers come by according to a Poisson process at a rate of 1 every half-hour, and it takes 8 minutes for a tanker to pass the ferry lanes. Cars can be loaded onto a ferry at a rate of 3 per minute and unloaded at a rate of 5 per minute.

Note: They decided to use ferries instead of build the bridge. Five berths on each side were built and 6 medium-sized ferries operate during the peak periods. Do you think this was a good decision? What factors, in addition to cost, might have guided their decision?

Modeling Input Processes

Chaos

A simple example of a “chaotic system” is the recursive equation: X = R*X*(1-X).

If you start off with a particular value of X, if R is set high enough, it becomes impossible to predict the value of X very far into the future. Starting the system with X = 0.2, try values of R = 0.5, 1, 2, and 4. Does the system behave differently for different values of R? Does "chaos" describe the behavior? (Do you think chaotic systems might make good pseudo-random number generators!)

Generating Discrete Random Variates

1. Consider the probability distribution function: P(X=i)=i/6 where i =1,2,3
i. Create an event graph using RND to generate 25 random variates from this distribution.
ii. Create an event graph using DISK{} and a data file to generate 25 random variates of this distribution.
2. What is the probability distribution function of X?
           U =RND and X=(U>0.2) + (U>0.5)

Generating Continuous Random Variates

1. Let A and B be two random variables uniformly distributed between 0 and 1. Let X be the larger of A and B. Create an event graph which generates 20 values of X (try to be clever).
2. Consider the following probability distribution function: f(x) = x/8 0<=x<=4. Create an event graph using RND to generate 25 random variates of this distribution.
3. What is the delay time corresponding to an exponential rate with parameter 5?
4. What does the probability distribution function of X look like if X is given by the following?
           U=RND  and X=(2*RND)*(U <0.5) + (4+RND)*(U>=0.5)
5. If U is a random variable with a uniform distribution between zero and one, what is the distribution of V=1/2-U/2?
6. What will the following state changes do in SIGMA to the value of X? That is, give the value(s) of X and tell how the(se) values might occur. [Assume that all variables are REAL valued (i.e., floating point)].
           R=RND
           X=(RND<0.2) + (RND<0.5)*2 + (RND<0.7)*4
7. What does the following SIGMA state change do?
           X=(RND>0.5)*1 + (RND<=0.5)*2

Generation of Minimum Statistics

There are 100 identical components operating independently in a system. Each component has a lifetime, X, that has an exponential distribution with a mean of 6 days. Generate the time until the first component fails from a single uniform random number, RND? (Hint: The minimum of N uniform random variables is given in Section 9.10.1, and X=-M*LN{RND} is an exponential random variable with mean, M.)

Testing Variate Generators

SIGMA has build-in generators for uniform (RND), gamma (GAM), and normal (NOR) random variates. Using the methods in texts referenced in this book (Bratley, Fox, and Schrage and Law and Kelton), perform at least three tests of these functions (at least two of the tests should be quantitative). Program and test generators for lambda variates.

A Variance Reduction Technique

Two runs are made of a simulated queue. The random number stream that was used to generate interarrival times in the first run is used to generate the service times for the second run. The random number stream that was used to generate service times in the first run is used to generate the interarrival times for the second run. Will the average customer waiting times from these two runs tend to have zero, positive, or negative correlation? Explain why.

Dependent Processes

Run CARWASH.MOD where the interarrival times and service times are exponentially distributed with the same means as before but now follow EAR models with lag-one correlation of p = 0.7. Compare this system with CARWASH.MOD having deterministic service and CARWASH.MOD having independently distributed exponential service.

A Simple Recursion for Queue Times

Generate 90% confidence intervals for the average waiting time, E[W], in an M/M/1 queue with traffic intensity of 0.9. Use the recursion, W=MAX{W+S-A;0} starting with W=0, where S is the service time of the ith customer (exponential with mean =1) and A is the ith customer interarrival time (exponential with mean 1/0.9).

Dependent Input Data

You are building a model for a chain of automatic carwashes. These carwashes have deterministic service rates. A sample of car arrivals indicates that the times between car arrivals has an exponential distribution. Unfortunately, the people collecting the demand data simply tabulated a histogram of the interarrival times rather than recording the actual sequence of arrival times.

  1. What problem(s) do you anticipate this might cause in getting a valid model for the customer arrival process? Specifically, what information are you missing that you wish you had? Why?
  2. What if you are also told that the lag-1 serial correlation between successive interarrival times is 0.7? Given that an arrival event just occurred and the simulated time is CLK, how can you generate the time of the next car arrival (call this time T) using all of the information you have?
  3. Why might your approach not be acceptable to the people who own this chain of carwashes?

Generating Points in a Plane

Generate a sample of N independent points uniformly scattered over the area in the two-dimensional region in the plane bounded by the horizontal axis and an arbitrary function.

Generating Source Code for SIGMA Models and Running Simulations from a Spread Sheet

Translations

Translate any of the models in Chapter 5 into C and run them.

Batched experiments

Create an experiment file for a batched experiment with any model you translated and compiled in the previous exercise.

Spreadsheet interface

Create a spreadsheet interface for the experiment in the previous exercise.


Back to Main Page

Personal tools