多机调度问题贪心算法 Java 代码实现

以下是多机调度问题的贪心算法 Java 代码：

import java.util.*;

public class MultMachineScheduling {
    public static int schedule(int[] jobs, int m) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(m);
        for (int i = 0; i < m; i++) {
            pq.offer(0);
        }
        for (int i = 0; i < jobs.length; i++) {
            int time = pq.poll();
            time += jobs[i];
            pq.offer(time);
        }
        int maxTime = 0;
        while (!pq.isEmpty()) {
            int time = pq.poll();
            maxTime = Math.max(maxTime, time);
        }
        return maxTime;
    }

    public static void main(String[] args) {
        int[] jobs = {10, 20, 30, 40, 50, 60, 70, 80, 90};
        int m = 3;
        int time = schedule(jobs, m);
        System.out.println('Minimum time required to schedule all jobs is: ' + time);
    }
}

在这个算法中，我们首先创建了一个优先队列来存储每个机器的完成时间。我们将所有机器的完成时间初始化为 0。然后，我们遍历所有作业，将它们按顺序分配给每个机器。我们选择完成时间最早的机器，并将当前作业的时间添加到该机器的完成时间中。最后，我们找到所有机器中完成时间最长的时间，它将是我们的最小总时间。

在上面的示例中，我们使用了一个具有 9 个作业和 3 个机器的示例来演示如何使用贪心算法来解决多机调度问题。运行此代码，将输出可以在给定的 3 台机器上完成所有作业所需的最小时间。