cs-131 — The Two-Desk Counter

Problem

A campus help desk serves students one at a time. Eight students will arrive today; their arrival minute and service duration (in minutes) are known in advance:

student:  S1   S2   S3   S4   S5   S6   S7   S8
arrives:   0    1    2    6    7   10   12   13
service:   4    3    5    2    4    3    2    5

Rules: students are served in arrival order; a server starts a student at max(arrival, when the server next frees); nobody jumps the queue.

Compare two designs:

• One desk: a single server, as today.
• Two desks: a waiting student takes any free desk; if both are free, desk 1; if both are busy, they wait for the one that frees first.

Your deliverables:

1. For each design, each student's waiting time (start − arrival).
2. The total waiting time and the makespan (last finish) per design.
3. One sentence on the trade-off: the second desk costs money — under what conditions is it worth it?

If the problem is ambiguous anywhere, state the assumption you are making and carry on — a stated assumption is part of a good answer.

Examples

• Input: the arrival/service table, the two designs
• Output: one desk: total wait 48 min, last finish 28 — two desks: total wait 3 min, last finish 18

Solve for the worked instance first. Then ask what would change if one number, name, or condition were replaced by something stranger.

What to notice

• This is a trace, not a stochastic simulation: every number is determined, so two correct answers must agree exactly.
• The state you must carry is tiny — "when does each desk free up" — and the whole simulation is one update rule applied in order.
• Total waiting and makespan can move in different proportions; a design decision should say which one it is buying.

Discussion starter

After the solution is revealed, the class spends five minutes on this prompt: "Arrivals double next semester (same gaps, twice the service load spread over more students). Does the two-desk advantage grow, shrink, or stay put — and how would you check without simulating all day?"

Constraints and assumptions

• Difficulty: Intermediate (multi-step simulation with a design decision).
• Topics: simulation, service systems, trade-offs.
• Service is non-preemptive: a desk finishes the student it started.
• Classroom-scale inputs unless the problem says otherwise.
• Time-box: about five minutes for a first attempt; partial answers with clear reasoning are worth more than silent struggling.
• Optional stretch (not required): describe an alternative approach and say when it beats the obvious one.

Hints and extension

• First nudge: for one desk there is a single running "free at" time — find it for S1, S2, S3 and watch the pattern.
• If stuck after three minutes, write the input/output line you expect and trace the smallest example by hand.
• After the reveal, attempt the extension below before the next lecture.
• Extension challenge: with two desks and both free at S3's arrival, the rule says desk 1. Invent an instance where that tie rule changes the makespan, and one where it does not.