每日算法 — 使用java实现调度算法：贪心策略与优先队列的任务 deadlines 最优排序

调度问题是操作系统、项目管理和游戏开发中的经典优化问题。给定一组任务，每个任务有执行时间和截止时间，如何安排执行顺序使得超时任务最少、或总延迟最小？本文用Java实现三种核心调度算法：最早截止时间优先（EDD）、最短处理时间优先（SPT）以及带权重的最小延迟调度，结合贪心策略与优先队列，并通过一个”游戏任务调度器”案例展示其在实际场景中的应用。

一、问题定义

设有n个任务，每个任务i有：
– 处理时间 p[i]：完成该任务需要的时间
– 截止时间 d[i]：任务必须在此时间前完成
– 权重 w[i]（可选）：任务的重要程度

目标1（可行性调度）：找出一个调度方案，使得所有任务都能在截止时间前完成。

目标2（最小化最大延迟）：最小化 max(0, C[i] – d[i])，其中C[i]为任务i的完成时间。

目标3（最小化总加权延迟）：最小化 Σ w[i] × max(0, C[i] – d[i])。

二、最早截止时间优先（EDD）算法

EDD算法按截止时间升序排列任务，若存在可行调度，则EDD调度必为可行调度。这是调度理论中最经典的贪心结论之一。

package com.algorithm.scheduling;

import java.util.*;

/**
 * 任务类：包含处理时间、截止时间和权重
 */
public class Task implements Comparable<Task> {
    String name;
    int processingTime;  // 处理时间
    int deadline;        // 截止时间
    int weight;          // 权重（用于加权调度）
    int startTime;       // 实际开始时间（调度后填充）
    int completionTime;  // 实际完成时间（调度后填充）

    public Task(String name, int processingTime, int deadline) {
        this(name, processingTime, deadline, 1);
    }

    public Task(String name, int processingTime, int deadline, int weight) {
        this.name = name;
        this.processingTime = processingTime;
        this.deadline = deadline;
        this.weight = weight;
    }

    public int getLateness() {
        return Math.max(0, completionTime - deadline);
    }

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

    @Override
    public String toString() {
        return String.format("%s[p=%d,d=%d,w=%d] -> [%d,%d], lateness=%d",
            name, processingTime, deadline, weight,
            startTime, completionTime, getLateness());
    }
}

/**
 * 最早截止时间优先调度器
 * 贪心策略：按截止时间升序排列
 */
public class EDDScheduler {

    /**
     * EDD调度：按截止时间升序排列
     * 定理：若存在可行调度（所有任务不超时），则EDD调度必可行
     */
    public List<Task> schedule(List<Task> tasks) {
        // 拷贝并排序
        List<Task> scheduled = new ArrayList<>(tasks);
        Collections.sort(scheduled);

        int currentTime = 0;
        for (Task task : scheduled) {
            task.startTime = currentTime;
            task.completionTime = currentTime + task.processingTime;
            currentTime = task.completionTime;
        }

        return scheduled;
    }

    /**
     * 检查调度是否可行（所有任务在截止时间前完成）
     */
    public boolean isFeasible(List<Task> scheduled) {
        for (Task task : scheduled) {
            if (task.completionTime > task.deadline) {
                return false;
            }
        }
        return true;
    }

    /**
     * 计算最大延迟
     */
    public int maxLateness(List<Task> scheduled) {
        int max = 0;
        for (Task task : scheduled) {
            max = Math.max(max, task.getLateness());
        }
        return max;
    }

    public static void main(String[] args) {
        EDDScheduler scheduler = new EDDScheduler();

        List<Task> tasks = Arrays.asList(
            new Task("任务A", 3, 5),
            new Task("任务B", 2, 8),
            new Task("任务C", 1, 4),
            new Task("任务D", 4, 10)
        );

        System.out.println("=== EDD调度演示 ===\n");
        System.out.println("原始任务:");
        tasks.forEach(System.out::println);

        List<Task> result = scheduler.schedule(tasks);
        System.out.println("\nEDD调度结果（按截止时间升序）:");
        result.forEach(System.out::println);

        System.out.println("\n是否可行: " + scheduler.isFeasible(result));
        System.out.println("最大延迟: " + scheduler.maxLateness(result));
    }
}

三、带优先队列的在线调度

实际系统中任务往往动态到达，需要使用优先队列（堆）维护就绪任务。

package com.algorithm.scheduling;

import java.util.*;

/**
 * 在线任务调度器：任务动态到达，使用优先队列选择下一个执行的任务
 * 策略：最早截止时间优先（EDF - Earliest Deadline First）
 */
public class OnlineScheduler {

    /**
     * 模拟在线调度过程
     * @param arrivingTasks 按到达时间排序的任务列表
     * @return 调度后的任务执行序列
     */
    public List<Task> simulateEDF(List<Task> arrivingTasks) {
        // 按到达时间排序
        List<Task> sorted = new ArrayList<>(arrivingTasks);
        sorted.sort(Comparator.comparingInt(t -> t.startTime)); // 此处startTime复用为到达时间

        // 优先队列：按截止时间排序的就绪任务
        PriorityQueue<Task> readyQueue = new PriorityQueue<>(
            Comparator.comparingInt(t -> t.deadline)
        );

        List<Task> executionOrder = new ArrayList<>();
        int currentTime = 0;
        int taskIndex = 0;

        while (taskIndex < sorted.size() || !readyQueue.isEmpty()) {
            // 将所有已到达的任务加入就绪队列
            while (taskIndex < sorted.size() &&
                   sorted.get(taskIndex).startTime <= currentTime) {
                readyQueue.offer(sorted.get(taskIndex));
                taskIndex++;
            }

            if (readyQueue.isEmpty()) {
                // 没有就绪任务，跳到下一个任务到达时刻
                if (taskIndex < sorted.size()) {
                    currentTime = sorted.get(taskIndex).startTime;
                }
                continue;
            }

            // 选择截止时间最早的任务执行
            Task next = readyQueue.poll();
            int actualStart = currentTime;
            int actualCompletion = currentTime + next.processingTime;
            next.startTime = actualStart;
            next.completionTime = actualCompletion;
            currentTime = actualCompletion;
            executionOrder.add(next);
        }

        return executionOrder;
    }

    public static void main(String[] args) {
        OnlineScheduler scheduler = new OnlineScheduler();

        // 任务到达时间分别为0,1,2,3
        List<Task> tasks = Arrays.asList(
            new Task("T1", 4, 10) {{ startTime = 0; }},  // 到达时间0，处理4，截止10
            new Task("T2", 2, 5)  {{ startTime = 1; }},  // 到达时间1，处理2，截止5
            new Task("T3", 3, 8)  {{ startTime = 2; }},  // 到达时间2，处理3，截止8
            new Task("T4", 1, 4)  {{ startTime = 3; }}   // 到达时间3，处理1，截止4
        );

        System.out.println("=== 在线EDF调度演示 ===\n");
        List<Task> result = scheduler.simulateEDF(tasks);
        System.out.println("执行顺序:");
        result.forEach(System.out::println);
    }
}

四、最小化加权延迟：基于优先队列的贪心算法

当任务有权重时，简单EDD不再最优。对于单位处理时间的任务，按权重降序排列可最小化总加权延迟。对于一般情况，需要使用更复杂的算法，如分支定界或动态规划。

package com.algorithm.scheduling;

import java.util.*;

/**
 * 带权任务调度：最小化总加权延迟
 * 对于单位处理时间任务，按权重降序贪心即可
 * 对于一般任务，使用基于优先队列的近似/精确算法
 */
public class WeightedScheduling {

    /**
     * 单位处理时间任务的最优调度
     * 贪心策略：按权重降序，在截止时间前尽量靠前安排
     */
    public List<Task> scheduleUnitTimeTasks(List<Task> tasks) {
        // 按权重降序排序
        List<Task> sorted = new ArrayList<>(tasks);
        sorted.sort((a, b) -> Integer.compare(b.weight, a.weight));

        // 使用并查集找到每个任务最晚可安排的时隙
        int maxDeadline = sorted.stream().mapToInt(t -> t.deadline).max().orElse(0);
        UnionFind slots = new UnionFind(maxDeadline + 1);

        List<Task> scheduled = new ArrayList<>();
        int[] slotAssignment = new int[maxDeadline + 1];
        Arrays.fill(slotAssignment, -1);

        for (Task task : sorted) {
            int slot = slots.find(Math.min(task.deadline, maxDeadline));
            if (slot > 0) {
                slotAssignment[slot] = scheduled.size();
                task.startTime = slot - 1;  // 时隙编号从1开始，时间从0开始
                task.completionTime = task.startTime + task.processingTime;
                scheduled.add(task);
                slots.union(slot, slot - 1); // 该时隙被占用，指向前一个可用时隙
            }
        }

        // 按开始时间排序输出
        scheduled.sort(Comparator.comparingInt(t -> t.startTime));
        return scheduled;
    }

    /**
     * 并查集：用于找最晚可用时隙
     */
    static class UnionFind {
        int[] parent;

        UnionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }

        int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        void union(int x, int y) {
            parent[find(x)] = find(y);
        }
    }

    public static void main(String[] args) {
        WeightedScheduling scheduler = new WeightedScheduling();

        // 单位处理时间任务
        List<Task> unitTasks = Arrays.asList(
            new Task("高优先级补丁", 1, 3, 50),
            new Task("日常更新", 1, 2, 10),
            new Task("安全修复", 1, 4, 40),
            new Task("UI优化", 1, 3, 20)
        );

        System.out.println("=== 加权单位任务调度 ===\n");
        List<Task> result = scheduler.scheduleUnitTimeTasks(unitTasks);
        System.out.println("调度结果（权重优先+并查集时隙分配）:");
        result.forEach(System.out::println);

        int totalWeightedLateness = result.stream()
            .mapToInt(t -> t.weight * t.getLateness())
            .sum();
        System.out.println("\n总加权延迟: " + totalWeightedLateness);
    }
}

五、游戏任务调度器实战

package com.algorithm.scheduling;

import java.util.*;

/**
 * 游戏任务调度器：管理NPC行为、技能冷却、资源加载等任务的执行顺序
 * 综合EDD、权重调度和优先队列
 */
public class GameTaskScheduler {

    private final PriorityQueue<GameTask> taskQueue;
    private int currentTick = 0;

    public GameTaskScheduler() {
        // 按优先级排序：截止时间早的优先，截止时间相同则权重高的优先
        this.taskQueue = new PriorityQueue<>(Comparator
            .comparingInt((GameTask t) -> t.deadline)
            .thenComparingInt(t -> -t.priority)
        );
    }

    /**
     * 游戏任务内部类
     */
    static class GameTask {
        String name;
        int duration;      // 执行持续时间（tick数）
        int deadline;      // 截止时间（tick）
        int priority;      // 优先级权重
        Runnable action;   // 实际执行逻辑
        int remaining;     // 剩余执行时间
        boolean completed;

        GameTask(String name, int duration, int deadline, int priority, Runnable action) {
            this.name = name;
            this.duration = duration;
            this.deadline = deadline;
            this.priority = priority;
            this.action = action;
            this.remaining = duration;
            this.completed = false;
        }
    }

    /**
     * 添加任务到调度队列
     */
    public void addTask(GameTask task) {
        taskQueue.offer(task);
    }

    /**
     * 执行一帧（一个tick）
     * 返回本帧执行的任务列表
     */
    public List<GameTask> tick() {
        List<GameTask> executed = new ArrayList<>();
        currentTick++;

        // 每帧可以执行总时间为1个tick的任务
        int availableTime = 1;

        // 使用临时队列，因为可能需要中断任务
        PriorityQueue<GameTask> nextQueue = new PriorityQueue<>(taskQueue.comparator());

        while (availableTime > 0 && !taskQueue.isEmpty()) {
            GameTask task = taskQueue.poll();

            if (task.deadline < currentTick && task.remaining > 0) {
                System.out.println("[超时] " + task.name + " 已错过截止时间!");
            }

            // 执行任务
            int executeTime = Math.min(availableTime, task.remaining);
            task.remaining -= executeTime;
            availableTime -= executeTime;

            if (task.remaining == 0) {
                task.completed = true;
                task.action.run();
                executed.add(task);
                System.out.println("[完成] Tick " + currentTick + ": " + task.name);
            } else {
                // 任务未完成，放回队列
                nextQueue.offer(task);
                System.out.println("[执行中] Tick " + currentTick + ": " + task.name +
                                   " 剩余 " + task.remaining + " tick");
            }
        }

        // 将未执行的任务移到下一轮
        nextQueue.addAll(taskQueue);
        taskQueue.clear();
        taskQueue.addAll(nextQueue);

        return executed;
    }

    public int getCurrentTick() {
        return currentTick;
    }

    public static void main(String[] args) {
        GameTaskScheduler scheduler = new GameTaskScheduler();

        System.out.println("=== 游戏任务调度器演示 ===\n");

        // 添加各类游戏任务
        scheduler.addTask(new GameTask("玩家输入响应", 1, 5, 100,
            () -> System.out.println("  -> 处理玩家键盘/鼠标输入")));
        scheduler.addTask(new GameTask("物理模拟", 2, 10, 80,
            () -> System.out.println("  -> 更新刚体碰撞与运动")));
        scheduler.addTask(new GameTask("AI行为树更新", 2, 8, 70,
            () -> System.out.println("  -> 更新所有NPC的AI决策")));
        scheduler.addTask(new GameTask("技能冷却检查", 1, 5, 90,
            () -> System.out.println("  -> 减少所有技能冷却计时器")));
        scheduler.addTask(new GameTask("资源异步加载", 3, 20, 50,
            () -> System.out.println("  -> 加载下一关地图资源")));
        scheduler.addTask(new GameTask("网络同步", 1, 3, 95,
            () -> System.out.println("  -> 发送/接收网络数据包")));

        // 模拟运行20个tick
        for (int i = 0; i < 20; i++) {
            List<GameTask> completed = scheduler.tick();
            if (completed.isEmpty() && scheduler.taskQueue.isEmpty()) {
                System.out.println("所有任务已完成！");
                break;
            }
        }
    }
}

六、复杂度分析

七、总结

调度算法的核心在于理解不同目标下的贪心选择性质：
– EDD/EDF：最小化最大延迟的最优贪心策略
– 权重优先+并查集时隙：单位时间任务的最小加权延迟解
– 优先队列：在线场景下动态选择最优就绪任务

在游戏开发中，调度思想广泛应用于：帧率稳定（每帧任务时间预算）、技能系统（冷却与优先级）、资源管理（异步加载顺序）以及NPC行为更新（LOD级别调度）。