Java求解贪心算法多机调度问题

ゞ浴缸里的玫瑰 2021-10-24 02:40 300阅读 0赞

1、问题描述

设有n个独立的作业{1, 2, …, n}, 由m台相同的机器进行加工处理. 作业i所需时间为t i. 约定:任何作业可以在任何一台机器上加工处理, 但未完工前不允许中断处理,任何作业不能拆分成更小的子作业。要求给出一种作业调度方案，使所给的n 个作业在尽可能短的时间内由m台机器加工处理完成。 
    
     多机调度问题是一个NP完全问题，到目前为止还没有完全有效的解法。对于这类问题，用贪心选择策略有时可以设计出一个比较好的近似算法。
    
     2、贪心算法求解思路
    
     采用最长处理时间作业优先的贪心策略:
     当n≤m时, 只要将机器i的[0, ti]时间区间分配给作业i即可。
     当n>m时, 将n个作业依其所需的处理时间从大到小排序,然后依次将作业分配给空闲的处理机。
    
      具体代码如下：

--------------------

package 贪心;
    
    //public class Greedy
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.LinkedList;
    import java.util.List;
    
    /**
     * @author 葛帅帅
     */
    public class Greedy {
        public static class JobNode implements Comparable{
            int id;//作业的标号
            int time;//作业时间
            public JobNode(int id,int time){
                this.id=id;
                this.time=time;
            }
            @Override
            public int compareTo(Object x) {//按时间从大到小排列
                int times=((JobNode)x).time;
                if(time>times) return -1;
                if(time==times) return 0;
                return 1;
    
            }
        }
        public static class MachineNode implements Comparable{
            int id;//机器的标号
            int avail;//机器空闲的时间（即机器做完某一项工作的时间）
            public MachineNode(int id,int avail){
                this.id=id;
                this.avail=avail;
            }
            @Override
            public int compareTo(Object o) {//升序排序，LinkedList的first为最小的
                int xs=((MachineNode)o).avail;
                if(avail<xs) return -1;
                if(avail==xs) return 0;
                return 1;
            }
        }
        public static int greedy(int[] a ,int m){
            int n=a.length;//a的下标从1开始，所以n（作业的数目）=a.length-1
            int sum=0;
            if(n<=m){
                for(int i=0;i<n;i++)
                    sum+=a[i+1];
                System.out.println("为每个作业分别分配一台机器");
                return sum;
            }
            List<JobNode> d=new ArrayList<JobNode>();//d保存所有的作业
            for(int i=0;i<n;i++){//将所有的作业存入List中，每一项包含标号和时间
                JobNode jb=new JobNode(i+1,a[i]);
                d.add(jb);
            }
            Collections.sort(d);//对作业的List进行排序
            LinkedList<MachineNode> h=new LinkedList<MachineNode>();//h保存所有的机器
            for(int i=1;i<=m;i++){//将所有的机器存入LinkedList中
                MachineNode x=new MachineNode(i,0);//初始时，每台机器的空闲时间（完成上一个作业的时间）都为0
                h.add(x);
            }
            int test=h.size();
            for(int i=0;i<n;i++){
                  Collections.sort(h);
                MachineNode x=h.peek();
                System.out.println("将机器"+x.id+"从"+x.avail+"到"+(x.avail+d.get(i).time)+"的时间段分配给作业"+d.get(i).id);
                x.avail+=d.get(i).time;
                sum=x.avail;
            }
            return sum;
        }
        public static void main(String[] args) {
            int[] a={14,2,3,4,5,6,8,8,9};
                  // 1,2,3,4,5,6,7 ,8,9
            int m=3;
            int sum=greedy(a,m);
            System.out.println("总时间为："+sum);
        }
    }
    /**
     运行结果：
     将机器1从0到14的时间段分配给作业1
     将机器2从0到9的时间段分配给作业9
     将机器3从0到8的时间段分配给作业7
     将机器3从8到16的时间段分配给作业8
     将机器2从9到15的时间段分配给作业6
     将机器1从14到19的时间段分配给作业5
     将机器2从15到19的时间段分配给作业4
     将机器3从16到19的时间段分配给作业3
     将机器3从19到21的时间段分配给作业2
     总时间为：21
     */