SimuVeda

Operations · Simulator 076

Elevator Dispatch

People call a single lift from random floors. Choose how the lift decides where to go next: strictly in call order, always to the nearest stop, or sweeping up and down like a real lift. Click a floor to add a call yourself, then compare average and worst waiting times.

How the model works

The lift moves one floor every 1.5 s and spends 8 s at each stop for doors and boarding. It carries up to 8 people. Three dispatch rules decide its next stop:

First come, first served (FCFS): serve the oldest call completely (pick up, then drop off) before looking at the next one. It is fair, but the lift carries one person at a time, so each trip costs two stops. With trips of about three floors that is roughly 26 s per person, so FCFS can handle only about 60 / 26 ≈ 2.3 calls per minute.

Nearest stop first (SSTF): go to whichever pick-up or drop-off is closest, and take everyone waiting at each stop. Average waits are short, but a caller at the far end of the building can be skipped again and again while the lift serves a busy cluster: this is starvation.

Sweep (SCAN, the "elevator algorithm"): keep going in the current direction while there is any stop ahead, then turn round. Every floor is visited at least once per sweep, so the worst wait is bounded by about two trips along the building.

The same three rules appear in computer disk scheduling, where the "lift" is a disk head.

One lift, no direction-aware hall buttons (everyone at a stop boards if there is room), constant speed, and no acceleration. Waiting is measured from the call to boarding; worst wait depends strongly on run length and random seed.

Guided experiments

  1. Light traffic. One call per minute, random floors. Prediction: all three rules cope. FCFS waits are a little longer (about 14 s against about 9 s), because it never shares a trip.
  2. Busy building, FCFS. Three calls per minute. Prediction: demand exceeds FCFS's capacity of about 2.3 calls per minute, so the waiting crowd grows without limit. Switch to Sweep with the same traffic and it settles near a 25 s average wait.
  3. Fairness. Five calls per minute, nearest stop first, then sweep. Prediction: both keep up, but nearest-first has a higher average wait, and over a 30-minute run its worst wait is typically about twice sweep's (often 4–5 minutes against 2–3), because far floors get skipped while the lift serves a busy cluster. Try a few seeds.
  4. Morning rush. Everyone enters at the ground floor and goes up, five calls per minute, nearest stop first. Prediction: waits are similar under both rules, but nearest-first keeps dropping back to the lobby for new arrivals before finishing its drop-offs, so people already in the car ride about 45 s on average. Switch to Sweep: rides fall to about 35 s.

Challenge

Under FCFS each person costs two stops plus travel. In a 10-floor building where an average trip covers about 3.3 floors and the lift must first travel about 3.3 floors to reach the caller, estimate how many calls per minute FCFS can handle. What does sweep gain by sharing stops?

Reveal the explanation

Per person: 2 × 3.3 floors × 1.5 s ≈ 10 s of travel plus 2 × 8 s of stops = 26 s, so at most about 2.3 calls per minute. Sweep lets several people board and leave at the same stop and cuts empty travel, so its capacity is several times higher; at 3 calls per minute it is comfortably stable. Check with arrival rates of 2 and 3 per minute under FCFS.

References

  • Barney, G. and Al-Sharif, L., Elevator Traffic Handbook, 2nd ed. (2016), ch. 7 and 13.
  • Denning, P. J. (1967), "Effects of scheduling on file memory operations", AFIPS Spring Joint Computer Conference 30: 9–21.
  • Silberschatz, A., Galvin, P. B. and Gagne, G., Operating System Concepts, 10th ed. (2018), §11.2 (disk scheduling).