优化电梯调度3：基于最短寻求时间

概述：

最短路径算法通常用于图论中找到两个节点之间的最短路径。在电梯算法的上下文中，可以将最短路径算法的概念应用于找到最有效的方式来处理一系列电梯呼叫请求，以便最小化等待时间和行程时间。电梯算法的优化可以通过多种方法实现，比如使用最短寻求时间优先（SSTF, Shortest Seek Time First）算法，这是最短路径算法思想的一种体现。

源码

以下是一个简化的电梯调度算法，它基于类似于 SSTF 的思路来优化电梯运行：

import java.util.TreeSet;
/**
 * @Author derek_smart
 * @Date 2024/6/6 13:41
 * @Description 最短寻求时间算法
 */
public class Elevator {
    private int currentFloor;
    //存储所有向上移动的目标楼层请求
    private TreeSet<Integer> upRequests;
    //存储所有向下移动的目标楼层请求。
    private TreeSet<Integer> downRequests;
    //表示电梯当前的移动方向是否向上。
    private boolean movingUp;

    public Elevator() {
        this.currentFloor = 0; // 假设电梯开始在底层
        this.upRequests = new TreeSet<>();
        this.downRequests = new TreeSet<>();
        this.movingUp = true; // 假设电梯初始向上移动
    }

    /**
     * 接收一个楼层号作为参数，根据该楼层号相对于当前楼层的位置，将该楼层号添加到相应的请求集合中（向上或向下）
     * @param floor
     */
    public void requestFloor(int floor) {
        if (floor > currentFloor) {
            upRequests.add(floor);
        } else {
            downRequests.add(floor);
        }
    }

    /**
     * 处理所有等待的楼层请求。电梯会根据当前的移动方向选择下一个要服务的楼层，移动到该楼层，
     * 然后从相应的请求集合中移除该请求。如果当前方向上没有更多的请求，电梯会改变移动方向。
     */
    public void moveAndServeRequests() {
        while (!upRequests.isEmpty() || !downRequests.isEmpty()) {
            if (movingUp) {
                Integer nextFloor = upRequests.ceiling(currentFloor);
                if (nextFloor != null) {
                    moveToFloor(nextFloor);
                    upRequests.remove(nextFloor);
                } else {
                    movingUp = false; // 没有更高层的请求，改变方向
                }
            } else {
                Integer nextFloor = downRequests.floor(currentFloor);
                if (nextFloor != null) {
                    moveToFloor(nextFloor);
                    downRequests.remove(nextFloor);
                } else {
                    movingUp = true; // 没有更低层的请求，改变方向
                }
            }
        }
    }

    /**
     * 移动电梯到指定的楼层。这个方法首先检查目标楼层是否有效，然后模拟电梯逐层移动的过程，直到到达目标楼层。
     * @param targetFloor
     */
    public void moveToFloor(int targetFloor) {
        // 检查目标楼层是否有效
        if (targetFloor < 1) {
            System.out.println("Invalid floor: The building does not have a floor below 1.");
            return;
        }
        // 模拟电梯移动过程
        while (currentFloor != targetFloor) {
            if (currentFloor < targetFloor) {
                // 电梯向上移动
                currentFloor++;
                System.out.println("Moving up to floor: " + currentFloor);
            } else {
                // 电梯向下移动
                currentFloor--;
                System.out.println("Moving down to floor: " + currentFloor);
            }
            // 模拟电梯移动需要时间
            try {
                Thread.sleep(1000); // 暂停1秒钟来模拟电梯移动到下一层所需的时间
            } catch (InterruptedException e) {
                System.out.println("The elevator movement was interrupted.");
            }
        }
        System.out.println("The elevator has arrived at floor: " + currentFloor);
    }
}

时序图：

时序图中，可以看到以下步骤：

1. 电梯在底层（楼层 0）开始。
2. 用户 1 请求电梯到 5 楼。
3. 用户 2 请求电梯到 3 楼。
4. 电梯开始处理请求，并依次移动到请求的楼层。
5. 电梯首先移动到 3 楼，因为它在路上。
6. 电梯到达 3 楼，然后继续移动到 5 楼。
7. 电梯到达 5 楼，此时所有向上的请求都已处理完毕。
8. 用户 2 再次请求电梯到 1 楼。
9. 电梯开始处理新的请求，移动到 1 楼。
10. 电梯到达 1 楼，所有请求都已处理完毕。

测试：

public class ElevatorTest {

    public static void main(String[] args) {
        // 测试场景 1: 从一楼到五楼
        System.out.println("Test Scenario 1: Moving from floor 1 to floor 5");
        Elevator elevator1 = new Elevator();
        elevator1.moveToFloor(5);

        // 测试场景 2: 从五楼到一楼
        System.out.println("\nTest Scenario 2: Moving from floor 5 to floor 1");
        Elevator elevator2 = new Elevator();
        elevator2.moveToFloor(5); // 先移动到五楼
        elevator2.moveToFloor(1); // 然后移动到一楼

        // 测试场景 3: 已经在目标楼层
        System.out.println("\nTest Scenario 3: Already at target floor");
        Elevator elevator3 = new Elevator();
        elevator3.moveToFloor(1); // 假设电梯已经在一楼

        // 测试场景 4: 无效的楼层请求
        System.out.println("\nTest Scenario 4: Invalid floor request");
        Elevator elevator4 = new Elevator();
        elevator4.moveToFloor(-2); // 请求一个无效的楼层
    }
}

代码分析：

测试场景 1: 电梯从一楼移动到五楼。 期望结果: 电梯逐层上升，最终到达第五层。

测试场景 2: 电梯从五楼移动到一楼。 期望结果: 电梯逐层下降，最终到达第一层。

测试场景 3: 电梯已经在目标楼层。 期望结果: 电梯不移动，直接报告已在目标楼层。

测试场景 4: 电梯接收到一个无效的楼层请求（例如，负数或零）。 期望结果: 电梯不移动，并报告无效的楼层请求。

总结：

最短寻求时间优先（SSTF）算法是一种在磁盘调度中常用的算法，其核心思想是选择与当前磁头位置最接近的下一个请求，以此来最小化磁头移动的总距离。当将SSTF算法应用于电梯调度时，它可以帮助减少电梯的旅行时间和能源消耗，提高效率 1. 核心原则： SSTF算法选择距离当前电梯位置最近的请求来服务，从而最小化电梯的移动距离。

2. 请求管理： 电梯系统维护一个请求列表，其中包括所有待处理的楼层请求。

3. 选择逻辑： 当电梯需要决定下一个要服务的请求时，它会遍历所有未完成的请求，并找出距离当前楼层最近的那个。

4. 方向考虑： 虽然SSTF算法本身不考虑移动方向，但可以对算法进行修改，以便电梯在移动到最近的请求时仍然保持当前的移动方向。当一方向上的请求被服务完后，电梯可以改变方向。 5. 优点： - 减少等待时间：通过优先服务最近的请求，可以减少乘客的平均等待时间。 - 提高效率：减少电梯移动距离可以提高能源使用效率。

6. 缺点： - 饥饿问题：在某些情况下，远离电梯当前位置的请求可能会长时间得不到服务，导致饥饿问题。 - 不适用于高峰期：在高峰流量期间，SSTF可能不如其他更复杂的调度算法（如基于学习的或预测的调度算法）有效。

7.实际应用： 在实际的电梯系统中，可能需要结合其他因素来优化SSTF算法，比如乘客流量预测、电梯的载重限制、紧急停止和维护模式等。

8. 多电梯系统： 在多电梯系统中，SSTF算法需要进一步扩展以考虑电梯之间的协调，以确保整个系统的效率。

总之，SSTF算法提供了一个电梯调度的基本框架，可以帮助减少电梯旅行的总距离和等待时间。然而，为了满足现代电梯系统的需求，SSTF算法通常需要与其他策略结合使用，并且根据电梯使用的实际情况进行调整和优化。