Elevator System: the car state machine, scheduling and the dispatch loop

With the controller, the cars and the strategy separated, each can be designed on its own. This lesson builds them in order: the lifecycle of one car, the scheduling policies the strategy could hold, the code that ties them together tick by tick, and the extensions that test whether the separation was right.

The car state machine

One car's lifecycle. Six states, and one rule — direction commitment — that prevents the behaviour every rider hates.

The states

Four floor-level states would be enough for a rough answer. Splitting the doors into three is what lets you handle the obstruction case, which is a question interviewers like.

Direction commitment: the rule that stops oscillation

Without a rule, a car going up from floor 3 to floor 10 that receives a hall request for floor 2 could turn around. The people inside, who pressed 10, now travel downward. Then a request at floor 12 arrives and it turns again.

The rule, which is the core of the classic elevator (SCAN) algorithm:

While moving in a direction, a car serves only the stops ahead of it in that direction. It reverses only when there is nothing left ahead.

So a car moving up from floor 3 with stops at 7 and 10 will serve 7, then 10, and only then consider floor 2. A new request for floor 5 while it is at floor 4 is taken — it is ahead and in the same direction — which is why the stop list is a sorted set rather than a queue.

This one rule gives three properties worth naming:

• No oscillation. Passengers always move toward their destination.
• Bounded wait. A car makes at most one full sweep before reaching any floor, so worst-case wait is roughly one sweep time — the ~85 seconds from the requirements in Elevator System: requirements and separating the dispatcher from the car.
• Efficiency. Stops on the way are free; the car was passing anyway.

The stop list, and why it is a sorted set

1public class StopList {2    private final NavigableSet<Integer> up   = new TreeSet<>();          // ascending3    private final NavigableSet<Integer> down = new TreeSet<>(reverseOrder());45    public void add(int floor, Direction travelDirection) {6        (travelDirection == UP ? up : down).add(floor);7    }89    public Optional<Integer> next(int currentFloor, Direction heading) {10        if (heading == UP) {11            Integer ahead = up.ceiling(currentFloor);12            return ahead != null ? Optional.of(ahead) : Optional.ofNullable(down.first());13        }14        Integer ahead = down.floor(currentFloor);15        return ahead != null ? Optional.of(ahead) : Optional.ofNullable(up.last());16    }17}

Two sets, one per direction. next() looks ahead in the current heading first and only falls back to the other direction when nothing is ahead — which is direction commitment expressed in four lines of code rather than in a paragraph of rules.

Scheduling as a Strategy

Here is where the problem has no single right answer, and where saying so scores.

Policy one: nearest car

Assign the hall request to the car with the smallest absolute distance to that floor.

1public class NearestCarStrategy implements DispatchStrategy {2    public ElevatorCar selectCar(List<ElevatorCar> cars, HallRequest r) {3        return cars.stream()4            .filter(c -> c.canServe(r))5            .min(comparingInt(c -> Math.abs(c.getCurrentFloor() - r.getFloor())))6            .orElseThrow(NoCarAvailableException::new);7    }8}

Good: four lines, correct on its face, easy to explain. Bad: it ignores direction and load. A car one floor away moving the other way with six stops queued "wins" over an idle car three floors away. Under a morning rush it clusters all cars near the lobby and floors 12–15 wait a long time.

Policy two: the elevator (SCAN) algorithm

Each car sweeps up serving everything above, then sweeps down serving everything below. A hall request joins the car already sweeping toward it in the matching direction.

Good: bounded worst-case wait — one sweep. No starvation by construction. Very efficient when requests are spread evenly. Bad: poor at low traffic. At 11 pm, one person on floor 2 waits for a car to finish a pointless sweep to floor 15. It also does not naturally use multiple cars well — you need a rule to keep cars spread out, or they converge and sweep together.

Policy three: a cost function

Score every car for the request and take the lowest score. This is close to what real commercial dispatchers do.

1public class CostFunctionStrategy implements DispatchStrategy {2    public ElevatorCar selectCar(List<ElevatorCar> cars, HallRequest r) {3        return cars.stream().filter(c -> c.canServe(r))4                   .min(comparingDouble(c -> cost(c, r)))5                   .orElseThrow(NoCarAvailableException::new);6    }78    private double cost(ElevatorCar car, HallRequest r) {9        int distance = Math.abs(car.getCurrentFloor() - r.getFloor());10        double c = distance * FLOOR_SECONDS;                       // travel time11        c += car.getStopList().countBetween(car.getCurrentFloor(), r.getFloor()) * STOP_SECONDS;12        if (car.getDirection() != IDLE && !car.isHeadingToward(r)) c += REVERSAL_PENALTY;13        if (car.isFull()) c += FULL_PENALTY;14        c -= ageSeconds(r) * STARVATION_WEIGHT;                    // older requests win15        return c;16    }17}

Good: every factor that matters is a named, tunable term — including the ageing term that satisfies requirement N1 directly. Adding a factor is one line. Bad: the weights are arbitrary and need tuning against real traffic. It is harder to reason about, and a bad weight produces behaviour nobody can explain.

How they behave under a morning rush

The figures below come from a small simulation described here for teaching, not from measured data on a real building: fifteen floors, four cars, a morning-rush pattern where roughly 70% of requests originate in the lobby, using the timings from Requirements.

What to notice: nearest car has a decent average and a terrible worst case — that tall second bar is somebody on floor 14 waiting nearly three minutes. SCAN has the opposite profile. The cost function with an ageing term is the only one that is good on both, and it is good on both because the ageing term explicitly buys worst case at the price of a little average.

The recommendation

Recommend the cost function with an ageing term — and then say the thing that actually scores:

"The specific policy matters less than the fact that it is one object. I'd ship the cost function because it lets me tune for whatever the building cares about, but the real answer to your question is that DispatchStrategy is an interface, so if the building manager wants SCAN at night and cost-based during rush hour, that is a swap at runtime, not a rewrite."

That sentence is what the pluggable interface is for. The policy is a guess; the ability to change the guess is the design.

The dispatch loop, in code

Two methods carry this design: assigning a hall request, and advancing a car by one tick.

Assigning a hall request

1public class ElevatorController {2    private final List<ElevatorCar> cars;3    private final DispatchStrategy strategy;4    private final Queue<HallRequest> unassigned = new ArrayDeque<>();56    public void submitHallRequest(int floor, Direction direction) {7        HallRequest request = new HallRequest(floor, direction, clock.now());8        if (isDuplicate(request)) return;          // button already lit — ignore9        try {10            ElevatorCar car = strategy.selectCar(cars, request);11            car.addStop(floor, direction);12            request.assignTo(car.getId());13        } catch (NoCarAvailableException e) {14            unassigned.add(request);               // every car full or out of service15        }16    }1718    public void submitCarRequest(String carId, int floor) {19        ElevatorCar car = carsById.get(carId);20        car.addStop(floor, car.directionToward(floor));   // never reassigned21    }22}

Three details worth narrating:

• Duplicate suppression. Ten people pressing "up" on floor 7 is one request. Without this check, one car gets ten identical stops. The physical analogue is that the button stays lit.
• The unassigned queue. When every car is full, the request does not vanish; it is retried next tick. Dropping it silently is a correctness bug someone will find.
• Car requests bypass the strategy entirely. The passenger is already in that car.

Advancing the system by one tick

An elevator system is naturally a simulation loop. One tick is one unit of time — say 100 milliseconds of real time, or one floor of movement in a simplified model.

1public void step() {2    retryUnassigned();3    for (ElevatorCar car : cars) car.step();4}

1public class ElevatorCar {2    public void step() {3        switch (state) {4            case IDLE -> {5                stopList.next(currentFloor, direction).ifPresent(target -> {6                    if (target == currentFloor) transitionTo(DOORS_OPENING);7                    else transitionTo(target > currentFloor ? MOVING_UP : MOVING_DOWN);8                });9            }10            case MOVING_UP, MOVING_DOWN -> {11                currentFloor += (state == MOVING_UP ? 1 : -1);12                if (stopList.contains(currentFloor, direction)) {13                    stopList.remove(currentFloor, direction);14                    transitionTo(DOORS_OPENING);15                }16            }17            case DOORS_OPENING -> { if (door.isFullyOpen()) transitionTo(DOORS_OPEN); }18            case DOORS_OPEN    -> { if (door.holdExpired()) transitionTo(DOORS_CLOSING); }19            case DOORS_CLOSING -> {20                if (door.isObstructed()) { transitionTo(DOORS_OPENING); return; }21                if (door.isFullyClosed()) {22                    Optional<Integer> next = stopList.next(currentFloor, direction);23                    transitionTo(next.isEmpty() ? IDLE24                        : next.get() > currentFloor ? MOVING_UP : MOVING_DOWN);25                }26            }27        }28    }29}

The switch here is on the car's own state inside its own class, which is different from the if-else ladder the vending machine section condemned: it is one method, in the one class that owns the state, and the compiler checks that every enum value is covered. For a system this small it is the honest choice, and you should say so:

"I'm using a switch on the enum here rather than the State pattern. Six states, one method, and exhaustive switch checking makes it safe. If door handling grew — different door types, different hold rules — I'd extract state classes as in the vending machine."

Knowing when not to use the pattern you used in the previous problem is the point of When not to use a pattern.

Where the stop actually gets inserted

canServe is what makes direction commitment real at dispatch time:

1public boolean canServe(HallRequest r) {2    if (state == OUT_OF_SERVICE || isFull()) return false;3    if (direction == IDLE) return true;4    boolean sameDirection = (direction == UP) == (r.getDirection() == UP);5    boolean ahead = (direction == UP) ? r.getFloor() >= currentFloor : r.getFloor() <= currentFloor;6    return sameDirection && ahead;7}

A car can always take a request when idle. When moving, it takes only requests that are ahead of it and going the same way. Everything else waits for another car or for this car's next sweep.

Extensions

1. Weight limits and skipped stops

A full car must pass a waiting passenger, which creates a visible failure: the hall button stays lit, the car goes by, and the person waits again.

Two changes. ElevatorCar.canServe returns false when full — already in the dispatch loop code above. And a skipped hall request must go back to the controller for reassignment, not silently stay on the car's list. The reassignment path is the interesting half:

1public void onCarFullAtFloor(ElevatorCar car, int floor, Direction dir) {2    HallRequest request = car.releaseStop(floor, dir);3    request.clearAssignment();4    submitHallRequest(request.getFloor(), request.getDirection());   // re-dispatch5}

Weight itself is a sensor reading with a threshold; model it as boolean isFull() backed by a WeightSensor interface rather than as a number the design depends on.

2. Express elevators and restricted floors

Both are the same shape: a per-car set of servable floors.

1public class ElevatorCar {2    private final Set<Integer> servableFloors;   // express car: {1, 10..15}3    public boolean canServe(HallRequest r) {4        return servableFloors.contains(r.getFloor()) && /* previous conditions */;5    }6}

The dispatch strategy needs no change at all, because it already filters on canServe. Point that out — it is evidence the earlier separation was right.

Restricted floors add an authorisation check on car requests: pressing 12 requires a keycard. That belongs behind an AccessPolicy interface, not inside the car.

3. Maintenance mode and fire service

Both are states above the normal state machine, and both are worth distinguishing:

• Maintenance: the car finishes its current stop, refuses new requests, and parks. Its pending hall requests are reassigned to other cars. Graceful.
• Fire service: immediate and non-negotiable. Every car cancels all stops, travels to the designated floor, opens its doors, and stays there until reset by a key. Not graceful — that is the point, and saying that the fire override deliberately ignores every optimisation is the right instinct to show.

Model these as an OperationalMode on the car (NORMAL, MAINTENANCE, FIRE_SERVICE, INDEPENDENT) that gates the state machine, rather than as more states inside it. Two orthogonal dimensions, two fields — the composition argument from Composition over inheritance.

4. Destination dispatch

In a destination-dispatch building, you enter your destination floor on a lobby panel and a display tells you which car to board. There are no floor buttons inside the car.

This changes the information available: the system knows every passenger's destination at request time rather than discovering it after they board. That allows grouping — send everyone going to floors 12–15 into car B — which cuts the number of stops per trip substantially, and stops are the expensive operation (Requirements).

In model terms: HallRequest and CarRequest merge into a single TripRequest(origin, destination), and DispatchStrategy gains a grouping objective. Knowing this system exists, and being able to say why it is better in one sentence — "it knows destinations before people board, so it can group trips and cut stops" — is a strong close to this problem.