MA570 Spring 2021 Stochastic Methods in OR Krigman Final Exam
Please show all your work in the blue book provided and box off your answers.
Please be neat when writing down your answers. When it comes to your exam grade, neatness counts!!!
1. Problem (50 pts total) A student drives her car to school. She has a choice of parking it on the street in one space, parking it on the street and taking up two spaces, or parking in the lot.
• If she parks on the street in one space, her car gets dented with probability 1/10. If she parks on the street and takes two spaces, the probability of a dent is 1/50 and the probability of a $15 ticket is 3/10.
• Parking the car in a parking lot costs $5, but the car will not get dented.
• If her car gets dented, she can have it repaired, and it costs her $50.
• She can also drive her car dented, but she must pay a fine of $9 per day for driving a dented car.
Assume that at the beginning of a school year, her car is not dented. She wishes to determine the optimal policy for where to park and whether to repair the car when dented in order to minimize her (long-run) expected average cost per school day.
Let’s formulate this problem as a Markov decision process by identifying the states and decisions as follows. Let the states represent whether the student’s car is dented, i=1, or not, i=0. As well as possible decisions (actions) associated with each state. Currently assume deterministic policies, so whenever a certain state is reached, the same action will always follow.
Possible State: (0 = Not Dented; 1 = Dented)
Possible Action (Decision)
Immediate Cost
0 1 = Park on the Street in One Space 0 2 = Park on street in two spaces
0 3 = Park in a lot
1 4 = Have it Repaired
1 5 = Drive Dented
C01=? C02=? C03=? C14=? C15=?
a) (5 pts) Find the associated costs: C01 – C15 in the table above.
b) (10 pts) For all the (stationary deterministic) policies above, find the transition matrix and write an expression
for the (long-run) expected average cost per period in terms of the unknown steady-state probabilities: ().
c) (15 pts) Find these steady-state probabilities for each policy. Then evaluate the expression obtained in part (b) to find the optimal policy by exhaustive enumeration.
d) (10 pts) Are there any other policies that could be considered, besides those listed here? If “no”, give a brief justification. If “yes”, give a simple example.
2. Problem (15 pts total). A queueing system has two servers whose service times are independent random variables with an exponential distribution with a mean of 15 minutes. Customer X arrives when both servers are idle. Five minutes later, customer Y arrives and customer X still is being served. Another 10 minutes later, customer Z arrives and both customer X and Y are still being served. No other customer arrived during this 15-minute interval.
a. (10 pts) What is the probability that customer X will complete service before customer Y?
Hint: Use the property of exponential distributions that has to do with its “memory”.
b. (5 pts) What is the probability that customer Z will complete service before customer X?
3. Problem (20 pts total). Recall that we have been discussing properties of exponential distributions. Suppose a random variable T represents service times in a queueing model. Answer the following questions.
a. (10 pts) If service required is essentially identical for each customer, with the server always performing the same sequence of operations, and as a result the actual service times always tend to be near the expected times. Does the exponential distribution provide a good model for this type of service? (Need a one or two sentence explanation as to why you answered yes or no.)
b. (10 pts) The length of service is always going to run between 5 and 15 minutes, with service completion times being equally likely to fall anywhere inside that time interval. Does the exponential distribution provide a good model for this type of service? (Need a short explanation as to why you answered yes or no.)
4. Problem (25 pts)
a) (10 pts) Suppose a customer arriving at the system is told that he has to undergo three (3) different services in a
queuing model. Each one of these services can be described by an exponential distribution with the same mean value. Does the exponential distribution provide a good model for this type of service? Meaning the total time the customer spends in the system. (Need a short explanation as to why you answered yes or no.)?
b) (10 pts) Suppose that the next customer arriving at the system is told that he has to undergo one or more consecutive services where each service time again can be described by an exponential distribution with the same mean value. However, this customer is not told how many such services he will undergo (assume at least one). You need to answer the same question as part a.
c) (5 pts) Answer the same question as part (b) but now the Customer may or may not have to wait through an unknown number of consecutive services.
5. Problem (25 pts total). Customers arrive at a queueing system according to a Poisson process with a mean arrival rate of 2 customers per minute. The service time has an exponential distribution with a mean of 1 minute. An unlimited number of servers are available as needed so customers never wait for service to begin.
a. (5 pts) Construct the rate diagram for this queueing system.
b. (10 pts) Write down equations for Pn where n=0,1,2,…
c. (10 pts) Calculate the steady state probability that exactly one customer is in the system.
Hint: Use an expansion for the exponential function given in the cheat sheet.
6. Problem (30 pts total). Customers arrive at a single-server queueing system according to a Poisson process at a mean rate of 30 per hour. If the server works continuously the number of customers that can be served in an hour is has a Poisson distribution with a mean value of 50.
a. (8 pts) Determine the proportion of time when exactly one customer is waiting to be served.
b. (7 pts) Determine the proportion of time when at most one customer is waiting to be served
c. (7 pts) Determine the probability that exactly 1 customer is going to arrive in the next minute
d. (8 pts) Determine the probability that either 1 or 2 customers are going to arrive in the next 2 minutes.
7. Problem (15 pts). Suppose that you have an M/M/1 queuing system with the service rate is greater than arrival rate . What is the most likely state that your system may be found (i.e. the state where you expect the system to spend more time than any other state)? Justify your answer.
8.
9.
(30 pts) Suppose that you are operating a car repair center. Customers arrive at a rate per hour and get serviced at the rate per hour. (Assume Poisson Process on both ends and also assume that ). While customers are being serviced, they all wait inside your facility. You need to decide how many chairs to provide for waiting customers.
a. (10 pts) If = = and you decide to purchase 5 chairs, what percentage of time do you have some customers standing (at least one customer standing) because there are more customers than chairs?
Hint: Geometric series expansion given in the cheat sheet may be useful in this problem.
b. (20 pts) Answer the same question in terms of general value for = when And as a function of the number N of chairs that may be purchased.
(30 pts) Marsha operates an expresso stand. Customers arrive according to a Poisson process at a mean rate of 30 per hour. The time needed by Marsha to serve a customer has an exponential distribution with a mean of 75 seconds.
a. (8 pts) Use the M/ G/ 1 model to find Lq, and Wq.
b. (7 pts) Suppose Marsha is replaced by an expresso vending machine that requires exactly 75 seconds for each
customer to operate. State in words, how you expect the wait time Wq to change when using the machine.
c. (7 pts) Now compute Lq, and Wq for the case described in part b. (i.e. Expresso machine).
d. (8 pts) Another employee is going to help Marsha and he can process an additional 12 customers per hour.
(His processing times are also exponentially distributed). Will the two of them be enough to reduce the Lq to be less than the vending machine? (You must explain your answer.)
Problem # 1 2 3 4 5 6 7 8 9 Total Possible Points 50 15 20 25 25 30 15 30 30 240
Student Score
Submission Instructions
Failure to follow these steps may result in your submission not being graded.
1. Write Down Your Name and your BU ID
2. Make a pdf file of your write-up and upload the file to BB Learn
3. Your file name MUST be in the form Last Name_First Name.pdf (I would submit as Krigman_Steven.pdf)
4. Email me a copy in a single file, with the subject: MA 570; Final. → Cut & Paste this subject title. 5. You must upload AND email as attachment in a single file.
a. Do not send multiple files!
b. Attach the single file to your email; do not “drag and drop” it into your email message body.