SCAN Algorithm for Multiple Elevators in Java — Scheduling Explained with Example

SCAN Algorithm for Multiple Elevators in Java — Complete Explanation

In real-world buildings, elevators do not randomly change direction for every request. Instead, they follow a disciplined scheduling strategy. One such strategy is the SCAN Algorithm, also known as the Elevator Algorithm.

In this blog, we implement the true SCAN algorithm for a multi-elevator system, exactly as defined in operating systems and scheduling theory.

What Is the SCAN (Elevator) Algorithm?

The SCAN algorithm works by moving the elevator in one direction until it reaches the end of the building, then reversing direction.

• The elevator commits to a direction (UP or DOWN).
• It serves all requests encountered along the way.
• It continues moving even if there are no pending requests.
• The direction changes only at the extreme floors.

This behavior is exactly why the algorithm is called SCAN — the elevator scans the entire building in both directions.

Important Rule of SCAN

A critical rule of the SCAN algorithm is:

The elevator must not reverse direction in the middle, even if there are no requests ahead.

Reversing early would turn the algorithm into LOOK — which is a different scheduling strategy.

Why SCAN Is Used in Multi-Elevator Systems

• Predictable elevator movement
• No starvation of lower or higher floors
• Fair servicing of all requests
• Scales well for tall buildings

Example Scenario

Assume the following setup:

• Building floors: 0 to 10
• Elevator A at floor 2, direction UP
• Elevator B at floor 9, direction UP
• Incoming requests: 1, 3, 5, 6, 9, 4, 8

Key Observation

If Elevator B is at floor 9 and moving UP, and a request arrives for floor 8, the elevator does not immediately go down.

Instead:

• It continues moving UP to the top floor
• Reverses direction at the building end
• Then serves floor 8 while moving DOWN

This behavior strictly follows the SCAN algorithm.

Java Program — SCAN Algorithm for Multiple Elevators

import java.util.*;

class Elevator {
    int currentFloor;
    String direction;
    int minFloor;
    int maxFloor;
    Set<Integer> requests = new HashSet<>();

    Elevator(int floor, String direction, int minFloor, int maxFloor) {
        this.currentFloor = floor;
        this.direction = direction;
        this.minFloor = minFloor;
        this.maxFloor = maxFloor;
    }

    void addRequest(int floor) {
        requests.add(floor);
    }

    void moveOneStep() {
        if (direction.equals("UP")) {
            currentFloor++;
            if (currentFloor == maxFloor) {
                direction = "DOWN";
            }
        } else {
            currentFloor--;
            if (currentFloor == minFloor) {
                direction = "UP";
            }
        }
    }

    void processRequests() {
        System.out.println(
            "Starting at floor " + currentFloor + " moving " + direction
        );

        while (!requests.isEmpty()) {

            if (requests.contains(currentFloor)) {
                System.out.println("Serving floor " + currentFloor);
                requests.remove(currentFloor);
            }

            moveOneStep();
        }
    }
}

public class MultiElevatorSCAN {

    public static void main(String[] args) {

        Elevator e1 = new Elevator(2, "UP", 0, 10);
        Elevator e2 = new Elevator(9, "UP", 0, 10);

        List<Elevator> elevators = Arrays.asList(e1, e2);

        List<Integer> incomingRequests =
                Arrays.asList(1, 3, 5, 6, 9, 4, 8);

        for (int request : incomingRequests) {
            Elevator assigned = assignElevator(elevators, request);
            assigned.addRequest(request);

            System.out.println(
                "Request at floor " + request +
                " assigned to elevator at floor " +
                assigned.currentFloor
            );
        }

        System.out.println("\n--- SCAN Execution ---\n");

        for (Elevator e : elevators) {
            e.processRequests();
            System.out.println();
        }
    }

    static Elevator assignElevator(List<Elevator> elevators, int requestFloor) {
        Elevator best = null;
        int minDistance = Integer.MAX_VALUE;

        for (Elevator e : elevators) {
            int distance = Math.abs(e.currentFloor - requestFloor);
            if (distance < minDistance) {
                minDistance = distance;
                best = e;
            }
        }
        return best;
    }
}

Why This Implementation Is Correct

• No early direction reversal
• Direction changes only at building ends
• Requests are naturally served during sweeps
• Matches textbook SCAN behavior

Practice Challenges

1. Calculate total elevator movement (distance traveled).
2. Convert this SCAN implementation into LOOK and compare efficiency.
3. Add time-based simulation to show floor-by-floor movement.

The SCAN algorithm demonstrates how disciplined scheduling leads to predictable and fair elevator behavior. This is a classic example of computer science concepts applied to real life.