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
     
      () {            @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}));    }}