1.1Taxis arrive at a taxi stand according to a Poisson process with rate . Customers arrive wanting a taxi according to a Poisson process with rate . Taxi’s leave with a customer whenever a customer is waiting. Assume that an arriving customer will leave immediately if there is someone else already waiting. Similarly, if an arriving taxi finds another taxi waiting, it leaves without waiting for a customer. What is the distribution of time between leaving taxis leaving with a customer inside?
Solution
A loaded taxi leaves only when both a customer and a taxi are present. Assume a taxi left with a customer at time 0. Let X1 be the time until a taxi arrives and X2 be the time until a customer arrives. Since any arriving entity (taxi or customer) leaves if there is already an entity of that type present, then the time between departures of loaded taxi's, T, is max(X1, X2). Therefore, using the memoryless property of the exponential distribution we get
1.2For the problem above (1.1), assume that a taxi balks only if there are already 3 taxis waiting and a customer balks only if there are already 5 customers waiting. Formulate a model that can be used to analyze the long run behavior of the system. A model consists of
- State Definition
- State transition rate diagram
- Steady-State balance equations
Solution
Define the system state to be the number of waiting customers (as a positive number) or the number of waiting taxis (as a negative number). We know the arrival rate of taxis and the arrival rate of customers. The following is the state transition rate diagram.
Balance equations are as follows.
1.3Winston, p.1124, #3
Solution
Define the system state as the number of restaurants, 0, 1, 2, ... For state i, the rate of transition to state i+1 is max(16-0.5i,0). Call this value i. Thus, the market can support at most 32 restaurants. The failure rate of restaurants for state i is 1/(10+i). Call this value i. The simple form of writing the balance equations yields the following.
Now, knowing that the probabilities must sum to 1, we can use a simultaneous equation solver to get the P’s.
a) To get the steady state expected number of restaurants open we solve
b) The fraction of time more than 20 open =
1.4
Memorandum
To: Industrial Engineering
From: R.E. King, Stamping Division Manager, Bass Auto Works
Subject: Stamping Line Analysis
Please submit a short memo describing your specific recommendations for the problem described below. Humor me and also describe the problem so that I am sure you understand what I am asking for. Also, tell me about your methodology. Be sure to state any assumptions you have made and why. You can attach specific details, calculations, etc. as an appendix.
The stamping division at Bass Auto Works performs all necessary metal stamping operations for fenders. Currently, there are 15 stamping lines. Data on the breakdown and repair times of the lines has been analyzed by a group of Senior Design Students at State College. They determined that it was reasonable to assume that both are exponentially distributed. The mean time to failure for a single stamping line was found to be about 3 hours. The division currently employs 6 repairmen who work in teams of 2. When a stamping line breaks down, a single team is sent to repair it. The average repair time for a stamping line is about 1.5 hours.
The line feeds fenders to the main assembly process. Fenders are needed in assembly at a rate of about 85/hour. A fully operational stamping line produces fenders at a rate of about 10/hour. We are having problems supplying fenders to assembly at the required rate in the long run and my job is on the line, i.e., the cost is extremely high and to be avoided at all cost.
I want to know how many repair crews I should hire or lay off. Also, I've heard that corporate is thinking about offering some major rebates to our dealers that could increase the rate of fenders required to 100/hour. In this case, what should I do?
Next, I know that State College offers a course in setup time reduction that I believe can reduce the amount of time required to repair a stamping line to 1 hour. I'd like to know how much it is worth to us to send our repair crews to the course.
Finally, the manufacturer of the stamping equipment told me that they are developing a new product that can crank out fenders at a rate of 25/hour. I'm not sure of the cost yet but I want to be prepared to make a decision as to whether I should buy one or more of these new lines. I am limited by floor space so for every new line I buy, I'd have to replace one of the existing lines. In fact, I'd like to get rid of as many as I can. I believe that the new lines will break down less often (perhaps every 8 hours on average). I do not want a specific recommendation, but can you give me some insight into how I can do this analysis when I get all the data?
Solution
Must hire 2 additional crews to meet objective of 85 fenders per hour. (See table below).
Number of Crews / Expected Production3 / 60.8
4 / 77.6
5 / 89.8
6 / 96.1
7 / 99.6
Theoretically, if there was a repair crew for each line, the maximum production is 100 fenders/hour. This is because 1/3 or the time (approximately every 3 hours a line would be down for the repair time of 1.5 hours, thus line is down 1.5 out of every 4.5 hours, 5/4.5 = 1/3). Thus, expected production is 15(10)(2/3)=100/hour
In this case, with the training, the existing 3 crews meet objective of 85 fenders per hour. (See table below). Objective of 100/hour is met with 4 crews.
Number of Crews / Expected Production2 / 59.9
3 / 86.7
4 / 102.7
A quick and dirty analysis as follows is a start. Assume there are plenty of repair crews. As shown above an existing machine is producing about 2/3 of the time which yields about 6.67 fenders/hour. A new machine would be up 8 hours out of every 9.5, thus it can produce about 8/9.5 times 25 fenders/hour = 21.05. Thus, one new machine can produce as much as about 3.15 old ones and just over 4 machines could meet the requirement of 85 fenders/hour (say 4 new one and 1 old one). To be a bit more precise, you can model the system using new machine types with the 3 crews to determine the number required to meet the production. In this way, you can trade off repair crews against new machines.
You can also create a “mixed” model of both technologies. You will need to make some assumptions about which the repair if both types are down. (It would seem obvious to repair new machines over old ones.)
1.5Winston, p.1133 #2
Solution
For this problem we want to compute the operating cost rate for both the slow and fast copier. The cost rate is made up of the fixed cost of renting the copier plus the delay cost which depends upon the number of customers in line. To compute L, the expected number in the system, we model the system as an M/M/1 queue. For this system . The arrival rate is 4 customers/hour. The service rate depends on the copier. For the slow copier it is 6/hour and for the fast copier it is 10/hour. Using these numbers we get that L(slow)=2 and L(fast)=0.6667. Therefore
Use faster copier.
1.6Winston, p.1134 #9
Solution
We want to have 100 tires/hour produced. The system can be modeled as an M/M/1 queue. In an M/M/1 queue no customers are lost due to balking so the input (arrival) rate must equal the output (throughput) rate. Thus, since we want 100 tires/hour out, then 100 tires/hour must come in. Now, tires will be batched. Call the batch size Q. Then the arrival rate is a function of the batch size, i.e., . Similarly, the service rate is a function of the batch size, i.e., . Now, for an M/M/1 system with given and , the waiting time is and since, in general, , then . Therefore since the arrival rate and service rate are both functions of Q we get
In order to minimize W(Q) we take the derivative and set equal to 0 which leads to Q=33.4 (you can also just plug in values using a sheedsheet or MATLAB until you see that the W(Q) starts increasing). Now since Q must be integer we take the smaller of Q(33) and Q(34).
1.7Winston p. 1136 #2
Solution
We have an M/M/1//4 system. For this system let =40/15.
a)From pages 1134-1135 in the book we can compute
b) Customers arrive at rate 40/hour but are lost if we are in state 4. Therefore, actual throughput rate is
c) Waiting time is where e is the effective arrival rate 15.6. Plugging in we get W=0.22.
1.8Winston p. 1144 #2, assume customers form a single queue and the person at the head of the line goes go the next available server.
Solution
If we employ s tellers, then we have a M/M/s queuing system with the arrival rate = 50 customers/day and an individual teller service rate of 60 customers/day. From the book we know that for this system . The cost of operating the system is a function of the number of tellers and the waiting cost of customers, i.e., where L(s) is the expected number of customers in the system given s tellers. Since the service rate per teller is faster than the arrival rate we can get by with as few as 1 teller. So, we try s=1,2,3, etc. and find that 2 tellers is optimal.
1.9A garage has a single line for cars needing to be inspected. The time to inspect a car is exponentially distributed with mean 15 minutes. There is enough room for 3 cars to be parked while waiting on service (room for 4 cars total in system). The arrival rate depends on the number of cars in the system because people are more likely to stop with fewer cars in queue:
Cars in System / Arrival Rate0 / 4/hour
1 / 3/hour
2 / 2/hour
3 / 1/hour
4 / 0/hour
a)Formulate this problem as a Discrete State - Continuous Time Stochastic Process. Define the states of the system, the events in the systems and draw the state transition rate diagram.
b)Give the flow balance equations.
c)Solve for the long-term probabilities of being in each state.
d)If I go by the garage at 3PM (after the system has reached steady state) and am willing to stop if there 0 or 1 cars in line. What is the probability that I will stop.
e)The garage is open 8 hours a day and the profit from each inspection is $10. Assuming the system stays in steady state, what is the average daily profit of the inspection service.
Solution
Define the state of the system as the number of cars in the garage {0,1,2,3,4}. We have state dependent arrival rates, i.e., the arrival rate depends upon the number of cars in the garage. This is equivalent to a finite source of arrivals with an individual car arrival rate of 1/hour. There is a single server who inspects cars at rate 4/hour. The events in the system are car arrivals and departures. The state transition diagram is below.
b) The node balance equations are:
c) Solving for , we get:
d)P[I stop] = P[0 or 1 in line] = P[0,1,or 2 in system] = (32+32+24)/103 = 88/103 0.8544
e) Average daily profit = $10 x throughput rate x 8 hours/day = $10 x 4(1-P[empty system]) x 8
= 10*4*71/103 = $27.57/hr x 8 hours/day = $220.56 / day
1.10A limousine company has 4 cars. Calls to use a car arrive according to a Poisson rate with rate 6/day. The time to use a car is exponentially distributed with mean 0.33 days. The cars breakdown with a rate of 0.2/day. A single repairperson is available to work on broken cars and time to service a car is exponentially distributed with mean 1 day. Assume that a car only breaks down when the car is in use. Additionally, when the car breaks, the customer pays for the time used to that point and exits the system. The car is immediately place in the repair shop. Determine a Continuous Time Markov Chain, which considers the number of cars broken and the number of cars in service. Draw the state transition rate diagram and give four flow balance equations.
Solution
In this system there are four different types of events: arrival of a call, completion of service, breakdown of a limo and repair of a limo. Some assumptions must be made for this problem concerning calls for limos. In particular, the question is do they queue up or not. Lets assume they do not. Let
Define the state of the system as the pair ij where i = the number of operating
limos and j = the number of limos in use. The state transition diagram is as
follows:
1.11Data has been collected on the time between arrivals of customers to an M/M/1/k queueing system. The raw data is in a file called arrivals.dat. Go to J: \eos\info\ie\ie401_info and copy this file to your directory. Data has also been collected on the service time. Sample data is in the file service.dat in the directory as arrivals.dat. The first number in each file is the number of observations. The first number in the file is the number of observations.
- Computer the sample mean, variance and coefficient of variation of the
interarrival data.
- We would like to build a Markov model of the queueing system. Assuming
we want to model the interarrival process as an r-stage, special Erlang,
determing r, as well as the stage rate.
- Compute the sample mean, variance, and coefficient of variation for the
service time data.
- We have observed the system and it appears that there are two different types
of service and each type is needed about 50% of the time. Determine a hyper-
exponential distribution that can be used to model this service process.
Solution
- Using a spreadsheet for the arrival time data we get
- From class notes, we know that . Since r is not an integer and should be, we can use either 5 or 6. To understand the impact of choosing 5 vs. 6 we have to understand the difference. If we choose 6 then we have elected less variance than exists in reality, therefore we have a lower bound on performance. If we choose 5 then we have elected more variance than exists in reality and we have an upper bound on performance.
- Using a spreadsheet for the service time data we get
- For a hyperexponential,
To solve for 1and 2 we must solve the following system of equations.
To solve these we can solve the first for 1 and then substitute it into the
second. This leads to a second order equation in 2. Using the quadratic rule
yields 1=.0541 and 2=.1535 .
1.12Winston p. 1153, #3
Solution
L = 1,000 = average number of street lamps burned out
W = average length of time a lamp is burned out before it is fixed
= average number of lamps to burn out daily
We know that each lamp burns out at a rate 1/100 per day and since on average 10,000-L = 10,000 - 1,000 = 9,000 lamps are operating then the overall average burn out rate is = 9,000/100 = 90 lamps/day. Using Little’s Law, we should have W = L/ = 1,000/90 = 11.11 days. Therefore, Mafia, Inc. is not living up to their bargain
1.13Winston p. 1154, #8
Solution
Problem 8 page 1154 Winston. Let K = the number of dumpers to rent. The cost of renting the bulldozer and dumpers is $(40K + 100). Think of the bulldozer as the server and the dumpers as customers. Assuming exponentially distributed times, we have an M/M/1//K/K system, i.e., a machine repair problem with 1 server and K machines. The average service time is 12 minutes, i.e., the service rate is =5/hr. Once served a dumper returns to the queue on average 5 minutes later or at a rate of =12/hour. If we know the throughput rate in terms of dumpers/hour we can compute the rate that dirt is moved to the dam. The steady state throughput rate is (1-P0) so the rate that dirt is moved to the dam is (1-P0)1,000 where 1,000 is the load size of a dumper.
Since we need 10,000,000 cuft of dirt it will take 10,000,000/(1-P0)1,000 = 2,000/(1-P0)
hours to do the job at a cost of $(40K + 100)/hour. Thus, the total cost would be $2,000(40K +
100)/(1-P0). Now, we must compute the value of P0 for K dumpers.
From page 1150 we know that, for R = 1 server, where . So if K = 1 then
Simlarly, if R = 2 then
K / P0 / Cost1 / 0.294 / $396,600
2 / 0.058 / $382,160
Notice that for K = 3 even if P0 = 0.0 (which minimizes the cost for a given K) the cost would be
$440,000 so K=2 is optimal.
1.14Winston p. 1157, #1
Solution
Problem 1 page 1157 Winston. Option 1 is an M/M/3 queue with =4.8 applicants/hour and single server rate of =4/hr. Using Little’s Law the waiting time is W = L/. From page 1139 we know that L=Lq+/ and Lq = P(j3)/(3-). Now P(j3) can be looked up in Table 6 page 1140 and is = 0.14. Plugging Everything in yields W = 0.27 hours.
Option 2 is a series arrangement of an M/M/infinity queue (since every applicant is their own server) followed by an M/M/3 queue. A quick check shows that W for the first queue is the expected time for the applicant to fill out the form which is 65 minutes = 1.08 hours. Therefore, there is no need to even compute the time at the second queue since the time at the first queue fars exceeds that of Option 1. Option 1 is better.
1.15Winston p. 1157, #2
Solution
Problem 2 page 1158 Winston.
This is an M/M/2 system with =22.4 cars/hr, =16 cars/hr, and =22.4/32=0.70.
Then P(j2)=.57 and
cars
b) cars
hours
1.16Winston p. 1157, #3
Solution
Problem 3 page 1158 Winston.
System 1 is 2 M/M/1 queues in series. As shown in class, the arrival rate is the same for both queues, i.e., =40 customers/hour. For the first queue the service rate 1=120 and for the second 2=60. Therefore, the total waiting time W is the sum of the waiting times at each stage, (W1 + W2). Now, from Little’s Law Wi =
1/(i-). Using this we get W = 1/(1-) + 1/(2-) = 1/80 + 1/20 = 1/16 =
0.0625 hour.
System 2 is an M/M/2 system so
Therefore System 2 is better.
1.17Winston p. 1161, #1
Solution
Problem 1 page 1161 Winston. For this problem we have an M/M/s//s system since each call must be handle by a fire engine. We assume that if an engine is not available then a call is lost. We want the probability of loosing a call to be <1%. In this case =/=24/3=8. Using the table on page 1160 (Erlang’s Loss Table) looking up from =8 until we reach 0.01, we see that we need at least 15 fire engines