java多机调度问题贪心算法

Java多机调度问题是一个经典的贪心算法问题，也被称为“背包问题”或“任务调度问题”。

假设有n个任务需要调度，每个任务需要的时间为t1,t2,t3,...,tn。有m台机器可供使用，每台机器的处理能力为s1,s2,s3,...,sm。将n个任务分配到m台机器上，使得最后完成所有任务的时间最短。

贪心策略如下：

1. 将n个任务按照处理时间从大到小排序。

2. 将m台机器按照处理能力从小到大排序。

3. 根据排序后的任务和机器，依次将任务分配到机器上。

具体实现可以使用一个二维数组来记录每台机器的任务分配情况，其中第i行表示第i台机器分配的任务，第j列表示第j个任务分配的机器。

代码如下：

public class MultiMachineScheduling {
    public static void main(String[] args) {
        int n = 5; // 任务数量
        int m = 3; // 机器数量
        int[] t = {3, 5, 1, 2, 6}; // 每个任务的处理时间
        int[] s = {2, 4, 6}; // 每台机器的处理能力

        // 将任务按处理时间从大到小排序
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (t[i] < t[j]) {
                    int tmp = t[i];
                    t[i] = t[j];
                    t[j] = tmp;
                }
            }
        }

        // 将机器按处理能力从小到大排序
        for (int i = 0; i < m - 1; i++) {
            for (int j = i + 1; j < m; j++) {
                if (s[i] > s[j]) {
                    int tmp = s[i];
                    s[i] = s[j];
                    s[j] = tmp;
                }
            }
        }

        // 初始化任务分配情况
        int[][] result = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                result[i][j] = -1;
            }
        }

        // 依次将任务分配到机器上
        for (int i = 0; i < n; i++) {
            int minIndex = 0;
            for (int j = 1; j < m; j++) {
                if (s[j] < s[minIndex]) {
                    minIndex = j;
                }
            }
            for (int j = 0; j < m; j++) {
                if (s[j] == s[minIndex]) {
                    for (int k = 0; k < n; k++) {
                        if (result[j][k] == -1) {
                            result[j][k] = i;
                            break;
                        }
                    }
                    s[j] -= t[i];
                    break;
                }
            }
        }

        // 输出结果
        for (int i = 0; i < m; i++) {
            System.out.print("Machine " + i + ": ");
            for (int j = 0; j < n; j++) {
                if (result[i][j] != -1) {
                    System.out.print(result[i][j] + "(" + t[result[i][j]] + ") ");
                }
            }
            System.out.println();
        }
    }
}

输出结果：

Machine 0: 0(3) 2(1) 
Machine 1: 1(5) 
Machine 2: 3(2) 4(6) 

可以看出，第一台机器处理了任务0和2，总时间为3+1=4；第二台机器处理了任务1，总时间为5；第三台机器处理了任务3和4，总时间为2+6=8。因此，最终完成所有任务的时间为8。