多机调度问题贪心算法 Java 代码示例

这里给出一个简单的多机调度问题贪心算法的 Java 代码。假设有 n 个任务需要分配到 m 台机器上，每个任务需要的时间不同，每台机器的处理能力也不同，目标是使得所有任务的完成时间尽可能短。

public class MultiMachineScheduling {

    // 贪心算法，返回完成时间最早的机器的编号
    public static int getEarliestFinishTimeMachine(int[] machines) {
        int minTime = machines[0];
        int index = 0;
        for (int i = 1; i < machines.length; i++) {
            if (machines[i] < minTime) {
                minTime = machines[i];
                index = i;
            }
        }
        return index;
    }

    // 多机调度贪心算法
    public static int schedule(int[] tasks, int m) {
        int n = tasks.length;
        int[] machines = new int[m]; // 记录每台机器的完成时间
        for (int i = 0; i < n; i++) {
            int index = getEarliestFinishTimeMachine(machines); // 找到完成时间最早的机器
            machines[index] += tasks[i]; // 将任务分配到该机器上
        }
        // 返回最后完成的任务的完成时间，即所有任务的完成时间的最大值
        int maxTime = machines[0];
        for (int i = 1; i < machines.length; i++) {
            if (machines[i] > maxTime) {
                maxTime = machines[i];
            }
        }
        return maxTime;
    }

    public static void main(String[] args) {
        int[] tasks = {3, 2, 5, 4, 6};
        int m = 3;
        int finishTime = schedule(tasks, m);
        System.out.println('Finish time: ' + finishTime); // 输出最后完成任务的时间
    }
}