实验4贪心法（作业调度问题）(代码片段)

1.问题的已知
设有n个独立的作业1, 2, …, n，由m台相同的机器M1, M2, …, Mm进行加工处理，作业i所需的处理时间为ti（1≤i≤n），每个作业均可在任何一台机器上加工处理，但不可间断、拆分。

2.所求的目标
要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

3.算法步骤
当n>m时，首先将n个作业从大到小排序，然后依此顺序将作业分配给空闲的处理机。也就是说从剩下的作业中，选择需要处理时间最长的，然后依次选择处理时间次长的，直到所有的作业全部处理完毕，或者机器不能再处理其他作业为止。

4.程序

public class Greedy 
    private static int greedy (int[] arr, int m) 
        int n = arr.length;
        int sum = 0;
        if (n <= m) 
            for (int i = 0; i < n; i++) 
                if (sum < arr[i]) 
                    sum = arr[i];
                
            
            System.out.println("为每一台机器分工一个作业");
            return sum;
        
        List<Job> jobs = new ArrayList<>();
        for (int i = 0; i < n; i++) 
            Job job = new Job(i + 1, arr[i]);
            jobs.add(job);
        
        Collections.sort(jobs);
        LinkedList<Machine> machines = new LinkedList<>();
        for (int i = 1; i <= m; i++) 
            Machine machine = new Machine(i, 0);
            machines.add(machine);
        
        for (int i = 0; i < n; i++) 
            Collections.sort(machines);
            Machine mac =machines.peek();
            System.out.println("将机器" + mac.getId() + "从" + mac.getAvaile() + "到" + (mac.getAvaile() + jobs.get(i).getTime()) + "分配给作业" + jobs.get(i).getId());
            int a = mac.getAvaile() + jobs.get(i).getTime();
            mac.setAvaile(a);
            sum = a;
        
        return sum;
    

class Job implements Comparable 
    private int id;
    private int time;
    public Job (int id, int time) 
        this.id = id;
        this.time = time;
    
    public int getId () 
        return id;
    
    public void setId (int id) 
        this.id = id;
    
    public int getTime () 
        return time;
    
    public void setTime (int time) 
        this.time = time;
    
    @Override
    public int compareTo (Object o) 
        int otherTime = ((Job) o).getTime();
        if (this.time < otherTime) return 1;
        if (this.time == otherTime) return 0;
        return -1;
    


class Machine implements Comparable 
    private int id;
    private int availe;


    public Machine (int id, int availe) 
        this.id = id;
        this.availe = availe;
    

    public int getId () 
        return id;
    

    public void setId (int id) 
        this.id = id;
    

    public int getAvaile () 
        return availe;
    

    public void setAvaile (int availe) 
        this.availe = availe;
    

    @Override
    public int compareTo (Object o) 
        int otherTime = ((Machine) o).getAvaile();
        if (this.availe < otherTime) return -1;
        if (this.availe == otherTime) return 0;
        return 1;
    

5.测试数据

测试数据一：

测试数据二：

6.测试结果

7.结果分析

经分析结果符合预想！
时间复杂度为O(nlogn)