每日算法 — 使用java实现电梯调度：扫描算法与优先级队列

引言

电梯调度是操作系统和嵌入式系统中经典的资源调度问题。在现实场景中，一栋大楼有多部电梯同时运行，需要在满足乘客请求的同时最小化等待时间和能耗。本文将用Java实现两种经典的电梯调度算法：LOOK扫描算法和基于优先级队列的请求排序策略。

问题建模

将电梯系统抽象为以下核心组件：

• 电梯状态：当前楼层、运行方向（上/下/静止）、载客量
• 请求队列：乘客按下按钮产生的上行/下行请求
• 调度策略：决定电梯响应请求的顺序

核心算法：LOOK扫描算法

LOOK算法是SCAN（电梯扫描）的优化版本。电梯沿一个方向移动，服务该方向上的所有请求，到达最远请求楼层后反向。与SCAN不同，LOOK不会到达物理端点才转向，而是到达该方向最后一个请求楼层即反向。

算法步骤

1. 电梯维护当前运行方向
2. 收集当前方向上所有待处理的请求
3. 按楼层顺序依次服务（上行时从小到大，下行时从大到小）
4. 当前方向无请求时，切换方向或进入空闲状态

Java实现

import java.util.*;

/**
 * 电梯请求类
 */
class ElevatorRequest implements Comparable<ElevatorRequest> {
    int floor;           // 目标楼层
    Direction direction; // 请求方向
    long timestamp;      // 请求时间戳

    enum Direction { UP, DOWN }

    ElevatorRequest(int floor, Direction direction) {
        this.floor = floor;
        this.direction = direction;
        this.timestamp = System.currentTimeMillis();
    }

    @Override
    public int compareTo(ElevatorRequest other) {
        return Integer.compare(this.floor, other.floor);
    }
}

/**
 * 电梯类：基于LOOK扫描算法实现调度
 */
class Elevator {
    private int currentFloor;
    private ElevatorRequest.Direction currentDir;
    private final int minFloor;
    private final int maxFloor;
    private final Set<Integer> upRequests;    // 上行请求楼层集合
    private final Set<Integer> downRequests;  // 下行请求楼层集合
    private final List<String> log;

    public Elevator(int minFloor, int maxFloor) {
        this.currentFloor = minFloor;
        this.currentDir = ElevatorRequest.Direction.UP;
        this.minFloor = minFloor;
        this.maxFloor = maxFloor;
        this.upRequests = new TreeSet<>();
        this.downRequests = new TreeSet<>();
        this.log = new ArrayList<>();
    }

    /**
     * 添加乘客请求
     */
    public void addRequest(int floor, ElevatorRequest.Direction dir) {
        if (floor < minFloor || floor > maxFloor) return;
        if (dir == ElevatorRequest.Direction.UP) {
            upRequests.add(floor);
        } else {
            downRequests.add(floor);
        }
    }

    /**
     * 执行一步LOOK调度：移动一层并处理请求
     */
    public void step() {
        // 检查当前楼层是否有请求需要服务
        if (currentDir == ElevatorRequest.Direction.UP && upRequests.contains(currentFloor)) {
            upRequests.remove(currentFloor);
            log.add("在 " + currentFloor + " 楼停靠（上行请求）");
        }
        if (currentDir == ElevatorRequest.Direction.DOWN && downRequests.contains(currentFloor)) {
            downRequests.remove(currentFloor);
            log.add("在 " + currentFloor + " 楼停靠（下行请求）");
        }

        // 决定下一步方向
        boolean hasUp = !upRequests.isEmpty();
        boolean hasDown = !downRequests.isEmpty();

        if (!hasUp && !hasDown) {
            log.add("电梯空闲于 " + currentFloor + " 楼");
            return;
        }

        // LOOK策略：当前方向继续，直到无请求再转向
        if (currentDir == ElevatorRequest.Direction.UP) {
            boolean hasUpAhead = upRequests.stream().anyMatch(f -> f > currentFloor);
            if (hasUpAhead) {
                currentFloor++;
            } else if (hasDown) {
                currentDir = ElevatorRequest.Direction.DOWN;
                currentFloor--;
            } else if (hasUp) {
                // 上行请求都在下方，需要掉头
                currentDir = ElevatorRequest.Direction.DOWN;
                currentFloor--;
            }
        } else {
            boolean hasDownAhead = downRequests.stream().anyMatch(f -> f < currentFloor);
            if (hasDownAhead) {
                currentFloor--;
            } else if (hasUp) {
                currentDir = ElevatorRequest.Direction.UP;
                currentFloor++;
            } else if (hasDown) {
                currentDir = ElevatorRequest.Direction.UP;
                currentFloor++;
            }
        }
    }

    /**
     * 运行调度直到所有请求完成
     */
    public void run() {
        int steps = 0;
        while ((!upRequests.isEmpty() || !downRequests.isEmpty()) && steps < 1000) {
            step();
            steps++;
        }
    }

    public List<String> getLog() { return log; }
    public int getCurrentFloor() { return currentFloor; }
}

/**
 * 多电梯调度器：基于优先级队列分配请求
 */
class ElevatorScheduler {
    private final List<Elevator> elevators;

    public ElevatorScheduler(int elevatorCount, int minFloor, int maxFloor) {
        elevators = new ArrayList<>();
        for (int i = 0; i < elevatorCount; i++) {
            elevators.add(new Elevator(minFloor, maxFloor));
        }
    }

    /**
     * 分配请求到最优电梯：选择距离最近且方向匹配的电梯
     */
    public void dispatchRequest(int floor, ElevatorRequest.Direction dir) {
        Elevator best = null;
        int bestScore = Integer.MAX_VALUE;

        for (Elevator e : elevators) {
            int dist = Math.abs(e.getCurrentFloor() - floor);
            // 优先级评分：距离 + 方向匹配奖励
            int score = dist;
            best = (best == null || score < bestScore) ? e : best;
            bestScore = Math.min(bestScore, score);
        }
        if (best != null) best.addRequest(floor, dir);
    }

    public void runAll() {
        for (Elevator e : elevators) e.run();
    }
}

/**
 * 测试入口
 */
public class ElevatorSimulation {
    public static void main(String[] args) {
        System.out.println("=== 单电梯LOOK算法演示 ===");
        Elevator elevator = new Elevator(1, 20);
        elevator.addRequest(5, ElevatorRequest.Direction.UP);
        elevator.addRequest(3, ElevatorRequest.Direction.DOWN);
        elevator.addRequest(8, ElevatorRequest.Direction.UP);
        elevator.addRequest(2, ElevatorRequest.Direction.DOWN);
        elevator.addRequest(10, ElevatorRequest.Direction.UP);
        elevator.run();
        elevator.getLog().forEach(System.out::println);

        System.out.println("\n=== 多电梯调度演示 ===");
        ElevatorScheduler scheduler = new ElevatorScheduler(2, 1, 20);
        scheduler.dispatchRequest(7, ElevatorRequest.Direction.UP);
        scheduler.dispatchRequest(4, ElevatorRequest.Direction.DOWN);
        scheduler.dispatchRequest(15, ElevatorRequest.Direction.UP);
        scheduler.dispatchRequest(2, ElevatorRequest.Direction.DOWN);
        scheduler.runAll();
    }
}

复杂度分析

扩展思考

• SSTF（最短寻道优先）：优先服务距离最近的请求，但可能导致饥饿
• C-SCAN：单向扫描到头后快速返回起点，适合磁盘调度
• 动态优先级：根据等待时间调整请求权重，避免长等待

总结

LOOK扫描算法通过维护方向一致性减少电梯频繁换向，在实际电梯系统中广泛应用。结合优先级队列的多电梯调度策略，能够有效分配负载，提升整体运输效率。