Simulation Case Statement A campus cafeteria has been receiving constant complai
ID: 3911162 • Letter: S
Question
Simulation Case Statement
A campus cafeteria has been receiving constant complaints that it is too crowded and slow. You have been asked to simulate the cafeteria operation to see whether the complaints are justified and if so, what can be done to fix the problems.
The problem is the dinner rush hour (90 minutes, actually) from 5:00 to 6:30. The cafeteria serves approximately 350 students. The cafeteria offers snacks, drinks, a salad bar (all self-serve), and two hot dinner options. The first hot option is a pre-cooked line, offering hamburgers, hotdogs, burritos and the like, with a variety of side dishes and desserts. This is a true cafeteria line where you tell a server what you want, the server assembles your choices on a tray and hands you the tray. There are two servers for the precooked line. You then stand in line to pay and move into the seating area to eat. The second option is a customized (also called “interactive”) meal, where you tell a chef exactly how you want your meal prepared, choosing from whatever entrees and sides are available that night. The chef (there are two chefs for the custom dinner line) prepares the food to your specifications and then hands you your plate and you go pay.
You have gathered the following data:
· 75% of the dinner students get a hot meal, 25% get snacks
· Of the students that get a hot meal, the ratio of precooked to customized is two to one (2:1)
· Students arrive in an exponential process with a mean of 0.26 minutes
· Cashier service is an exponential process with a mean of 0.40 minutes
· Precooked service is an exponential process with a mean of 1.03 minutes
· Custom service is a uniform process with a minimum of 4 minutes and a maximum of 8 minutes
· There are two cashier stations but only one cashier is scheduled for the dinner rush
Build a simulation to copy this situation. Check for validity errors and fix them if need be. Determine the wait time for each precooked and custom dinner customer, and find the maximum and average wait time for both the precooked and the custom lines, as well as the percentage of students in each line that wait to be served. In addition, for the precooked customers, determine the number of students that wait less than 1 minute, between 1 and 5 minutes, and more than 10 minutes. For the Custom dinner customers, determine the number of students that wait less than 5 minutes, between 5 and 10 minutes, and more than 20 minutes. For the cashier line, calculate both customer wait time (maximum, average and percent that wait) and cashier idle time (maximum and total (sum)). Use the output data from the simulation to determine whether a problem exists during the dinner rush. Then implement the “What-If” scenarios listed below to see what improvements are justified. Base your decisions on the average outputs of the data tables.
What-If Scenarios
· Offering “early-bird” and “night-owl” specials (lower prices) will encourage students to eat before the dinner rush starts or after it ends, increasing the average inter-arrival time from 0.26 minutes to 0.29 minutes
· Adding better signs and overhead menus, as well as rearranging the two servers as an assembly line, will decrease the precooked average service time from 1.03 minutes to 0.85 minutes
Adding overhead menus, decreasing the number of entrees offered each night, and having the customers complete check sheets for their orders will decrease the custom dinner service range from 4 to 8 minutes down to 3 to 6 minutes.
Explanation / Answer
An input is accepted if there is a tiling of the s × s square {0, ..., s ? 1} × {0, ..., s ? 1} with the given tiles such that the first row of the tiling is the one given in the problem instance. Note that this problem is decidable by the brute force algorithm of trying out every possible tiling of the remaining s 2 ? s cells with tiles from T, and checking whether the tiling is consistent .
Let us first see that this problem is in NP: A prospective tiling is given by guessing a sequence of s 2 tiles. The sequence is encoded by a string of length O((s log k) 2 ) = O(N2 ), so the time required to produce the guess is bounded above by a polynomial in the size of the input. To verify that the guess is a correct tiling, we have to examine each edge of 8 the s2 tiles, so roughly 2s 2 pairs of edges must be inspected, which is still polynomial in the original input size. Note that if we had not given the first row and just encoded s in binary, then the size of the guessed tiling could have been exponential in the size of the input. This is the reason for insisting that the whole first row be given–to ensure that the size of a tiling be polynomial in the size of the input. Now let us suppose this tiling problem is actually in P. We want to show that every problem in NP must then be in P. Let L be in NP. Then L is recognized by a nondeterministic Turing machine M such that for some c, r > 0, every computation of M on an input of length n terminates (in acceptance or rejection) after no more than cnr steps. Let us tweak M a little bit to make a new machine N: N behaves exactly like M, except whereveve M has a transition into the accept state: (q, a) ? qaccept, N instead runs forever. That is, we add a new state called qf orever and replace each transition of the above form by the transitions (q, a) ? (qf orever, a, R) (qf orever, b) ? (qf orever, a, R), for all tape symbols b. Note the critical property of N: For every input string w, every computation of M on w ends after at most c|w| r steps, and M accepts w if and only if some computation of M on w ends in the accept state. Thus M accepts w if and only if some computation of N on w lasts for at least c|w| r + 1 steps. So, given M and w, we construct N as just described. We use the transition function of N to construct a set of tile types T as described in the preceding section (note that nothing in that construction requires the Turing machine to be deterministic). Let w = a1 · · · an. We add a different corner tile with ?? at left, + at bottom, (q0, a1, 0) at top, and B at right, and n ? 1 additional tiles with + at bottom, B at left and right, and a2, . . . , an at top. Set s = c|w| r + 1 and specify the first row of the tiling: The first n tiles in the row are the corner tile just specified, followed by the n ? 1 tiles with labels a2, . . . , an at the top; the remaining s ? n tiles in the first row are the ones with B at top, right, and bottom. Note that it takes time polynomial in the length of w to extract this description of the set of tile types and the first row. Once again, tiling of the subsequent rows is possible if and only if there is a computation of N whose successive configurations match the top colors in each row. In particular, tiling the first s = c|w| r + 1 rows is possible if and only if M accepts w. Thus if we had an algorithm for deciding the bounded tiling problem in polynomial time, then for every language L in NP, we would have a polynomial-time algorithm to decide whether w is in L, and thus P would be equal to NP. We say that the bounded 9 tiling problem is NP-complete. This means that, first, it is in NP, and second, that every probably in NP can be reduced to it in polynomial time. Proving that a problem is NP complete is often taken as evidence that there is no efficient algorithm for solving it, since the existence of such an algorithm would imply the result (considered unlikely) that every problem in NP has an efficient decision algorithm.