流水作业调度

时间:2021-07-04 11:30:09

2018-03-18 20:37:06

问题描述:

n个作业 N={1,2,…,n}要在2台机器M1和M2组成的流水线上完成加工。每个作业须先在M1上加工,然后在M2上加工。M1和M2加工作业 i 所需的时间分别为 ai 和bi,每台机器同一时间最多只能执行一个作业。

流水作业调度问题要求确定这n个作业的最优加工顺序,使得所有作业在两台机器上都加工完成所需最少时间。

问题求解:

流水作业调度问题的每个作业都会被分成若*分,例如本例中的2部分,然后这两部分会有先后的在两台不同的机器上进行执行,最后求解的是在最终所有任务完成的时间。

流水作业问题是个NPC问题,在m > 2的时候目前没有找到很好的解决方法。在n = 2的前提下,可以使用Johnson法则在O(nlogn)完成求解。

Johnson法则:

对作业i,j,若满足min{bi, aj} >= min{bj, ai},则称,作业i,作业j满足Johnson法则。

已经被证明所有满足John法则的调度都是最优调度,Johnson法则的证明过程是比较繁琐的,可以进行定性的证明:

直观上,一个最优调度应该使机器M1没有空闲时间,且机器M2的空闲时间最少。

bi和aj是产生重叠的部分,如果该部分越大,则说明机器M2的空闲时间越少,因此我们所有的调度都应该满足这个法则。

因此本题就规约为了如何构造出一个满足Johnson法则的调度。

可以采取以下的策略进行构造:

流水作业调度

public class MultiDispatch {
    class Pair{
        int index;
        int val;
        boolean flag;

        Pair(int index, int val, boolean flag) {
            this.index = index;
            this.val = val;
            this.flag = flag;
        }
    }

    int multiDispatch(int[] a, int[] b) {
        int[] res = new int[a.length];
        boolean[] visited = new boolean[a.length];
        Arrays.fill(visited, false);
        Pair[] queue = new Pair[a.length + b.length];
        int j = 0;
        for (int i = 0; i < a.length; i++) {
            queue[j++] = new Pair(i, a[i], true);
            queue[j++] = new Pair(i, b[i], false);
        }
        Arrays.sort(queue, new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                return o1.val - o2.val;
            }
        });
        int s = 0;
        int e = res.length - 1;
        for (int i = 0; i < queue.length; i++) {
            if (visited[queue[i].index]) continue;
            if (queue[i].flag) {
                res[s++] = queue[i].index;
                visited[queue[i].index] = true;
            }
            else {
                res[e--] = queue[i].index;
                visited[queue[i].index] = true;
            }
        }

        int m1 = 0;
        int m2 = 0;
        for (int i = 0; i < res.length; i++) {
            m1 += a[res[i]];
            m2 = Math.max(m1, m2) + b[res[i]];
        }
        return m2;
    }

    public static void main(String[] args) {
        MultiDispatch md = new MultiDispatch();
        System.out.println(md.multiDispatch(new int[]{5,12,4,8}, new int[]{6,2,14,7}));
    }
}