Assignment 3: Queueing Theory

In this assignment you will apply elementary queueing theory equations to compute statistics for the various scheduling systems described below. Please show your work and clearly indicate your final answers for full credit. You should submit your answers in a PDF document via the Blackboard assignment link. If your answers are handwritten, please write tidily!

Each problem is worth 5 points, for a total of 40 points.

Unless otherwise specified, assume exponential inter-arrival and service time distributions.

  1. Potbelly's is getting ready to open a new store at the MTCC, and is expecting approximately 8 students to arrive per minute during the lunch rush. If they want to guarantee that no more than 10 students, on average, are waiting in line to get serviced, how quickly must they be able to take and complete orders?

  2. During exam season faculty members need to be able to submit a photocopy job to the department secretary and get their copies back within 10 minutes. It has been determined that there are on average 5 jobs arriving in the secretary's inbox per hour. How fast must the photocopier be able to complete a given job to meet faculty requirements?

  3. Suppose that faculty demand a 50% decrease in turnaround time for their submitted photocopy jobs. How much faster of a copy machine must the department spring for? (Your solution should be expressed as a percentage of your answer to question 2.)

  4. At the South Loop Oil 'n Lube, a new customer arrives for an oil change every 20 minutes, and is annoyed to find, on average, 3 customers ahead of him (including the one being serviced).

    How much longer, typically, will it take for the current customer to finish his oil change?

    After that, how much longer will the new customer have to wait to complete his own oil change?

  5. The proprieter of the IIT 7-Eleven serves an average of 800 students a day, with inter-arrival times following an exponential distribution. Most students check out with very few items, but there are some that do all their grocery shopping there, which results in service times that are non-exponential. Based on recorded data, the checkout clerk takes an average of 1.2 minutes to ring up a student, with a standard deviation of 3.5 minutes.

    How many students, on average, are waiting to be checked out?

  6. Processes send an average of 50 requests to the disk every second, and the disk controller takes an average of 15 milliseconds to complete each request.

    What is the average length of time a process must wait for a request to complete, from the moment it is submitted?

    What is the average number of requests waiting in the disk controller queue?

  7. HTTP requests are dispatched to a single-threaded webserver process at the rate of 80/second, and the process can handle each request in 7.5ms, on average. What is the perceived response time for each incoming request? (Note that we ignore network latency.)

  8. If the process from question 7 is rewritten so as to be a purely cache-based server such that every request can be served in a constant time of 5ms, how much faster is the average response time?