动态规划之流水作业问题

问题描述

n个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。
使用动态规划的思想可以解决该问题，具体的粉洗过程可参见：https://blog.csdn.net/baidu_32739019/article/details/51166345
这里仅给出结果。

解决方法

对于流水作业调度问题，可以使用Johnson法则实现最有调度，流水作业调度问题的Johnson算法：
(1) 令N1={i|a_i<b_i}，N2={i|a_i<=b_i}
(2) 将N1中作业依a_i的非减序排列；将N2中作业依b_i的非增序排列；
(3) N1中作业接N2种作业构成满足Johnson法则的最优调度

代码实现

public class JobSchedule {
       private static class Node{
          int key;
          int index;
          boolean job;
          
       }
       public static void flowShop(int n,int[]a,int[]b,int[]c){
           Node[] d = new Node[n];
           int i;
           for(i=0;i<n;i++){
               Node node = new Node();
               node.key = a[i]>b[i]?b[i]:a[i];
               node.job = a[i]<=b[i];
               node.index = i;
               d[i]=node;
           }
           Node[] tmp = new Node[n];
           MergeSort(d,0,n-1,tmp);
           int j=0,k=n-1;
           for(i=0;i<n;i++){
               if(d[i].job){
                   c[j++]=d[i].index;
               }else{
                   c[k--]=d[i].index;
               }
           }
           System.out.println("作业调度顺序为:");
           for(i=0;i<n;i++){
               System.out.print(c[i]+" ");
           }
           System.out.println();
           j=a[c[0]];
           k=j+b[c[0]];
           for(i=1;i<n;i++){
               j+=a[c[i]];
               k=j<k?k+b[c[i]]:j+b[c[i]];
           }
           System.out.println("作业调度总时间为:"+k);
       }
       public static void MergeSort(Node[] node,int left,int right,Node[] tmp){
           if(left<right){
               int mid = (left+right)/2;
               MergeSort(node,left,mid,tmp);
               MergeSort(node,mid+1,right,tmp);
               Merge(node,left,mid,right,tmp);
           }
           
       }
       public static void Merge(Node[] node,int left,int mid,int right,Node[] tmp){
           int i=left;
           int j=mid+1;
           int t=0;
           while(i<=mid&&j<=right){
               if(node[i].key<node[j].key){
                  tmp[t++]=node[i++];
               }
               else{
                   tmp[t++]=node[j++];
               }
           }
           while(i<=mid){
               tmp[t++] = node[i++];
           }
           while(j<=right){
               tmp[t++] = node[j++];
           }
           t=0;
           while(left<=right){
               node[left++]=tmp[t++];
           }
       }
       public static void main(String[] args){
           int[] a={2,4,3,6,1};
           int[] b={5,2,3,1,7};
           int[] c = new int[5];
           flowShop(5,a,b,c);
       }
}