Eric Slud
Suggested Form of a Final Project on Queueing
=============================================
A supermarket with 20 cash registers must decide how many cashiers to
employ at various times of day (and night). Demand (ie number D(t) of
customers wanting to check out per unit time) is known to vary by a
factor of 5 during the day, somewhat cylclically with busy periods in
the morning and lunchtime and an extra-busy time from 5 to 8pm.
Assume that D(t) is given either analytically or as a data-determined
sequence, say for t at 10-minute intervals, either assumed
piecewise-linear or otherwise interpolated in-between.
For each customer who begins service, assume first that the time S to
complete service is (independently of all other customers) a random
variable with P(S >t) = G(t) known to be of the form exp(-b*t) for
appropriately chosen constant b. (You may choose some other G if you
like: but random variables S are particularly easy to simulate.) You
could make this more complicated by making the amount purchased by
each customer a random variable A, in which case the
service-completion rate b would be made to depend on A .
Also consider the possibility that customers come in "classes"
according to how many items they have in their baskets, either "many"
(number of items > 15) or "few", and that the proportion of the
customer population with "many" items at time t is also a function
Q(t) which is given in data or hypothesized.
Consider also the fraction F(t) who simply leave the store if they see
the lines are longer than K people (say, K=8 or 10) or if they have
actually been waiting longer than M minutes on line. Make some
reasonable assumptions about the profit lost to the supermarket by
such aborted purchases.
Based on specific choices for these input functions [maybe more than
one combination of such choices if you want to explore the robustness
of your conclusions], the objective of the project is to develop a
computational strategy to find the number of checkout clerks employed
by the store as a function of time, so as to optimize the profit to
the store. (You should also make reasonable assumptions about the
labor costs.)
The primary method of investigation in this project is stochastic
simulation and numerical optimization, so that you can look at many
trajectories of waiting-line and customer-purchases and can optimize
the choice of how many checkers to employ by looking at the typical or
average trajectories as well as the variability and the frequencies of
extreme waiting lines. The general methodology would fall under
`Operations Research', but you are urged to develop your own approach.
If you can find real data to make your parameter choices
realistic, so much the better. But after making some simulated
whole-day waiting-line trajectories, you should justify your choices
by the customer population and throughput you generate, by comparison
with a realistic supermarket.