動(dòng)態(tài)規(guī)劃之流水作業(yè)問題

問題描述

n個(gè)作業(yè){1弯洗，2旅急，…，n}要在由2臺(tái)機(jī)器M1和M2組成的流水線上完成加工牡整。每個(gè)作業(yè)加工的順序都是先在M1上加工藐吮，然后在M2上加工。M1和M2加工作業(yè)i所需的時(shí)間分別為ai和bi。流水作業(yè)調(diào)度問題要求確定這n個(gè)作業(yè)的最優(yōu)加工順序谣辞，使得從第一個(gè)作業(yè)在機(jī)器M1上開始加工迫摔，到最后一個(gè)作業(yè)在機(jī)器M2上加工完成所需的時(shí)間最少。
使用動(dòng)態(tài)規(guī)劃的思想可以解決該問題泥从，具體的粉洗過程可參見：https://blog.csdn.net/baidu_32739019/article/details/51166345
這里僅給出結(jié)果句占。

解決方法

對(duì)于流水作業(yè)調(diào)度問題，可以使用Johnson法則實(shí)現(xiàn)最有調(diào)度躯嫉，流水作業(yè)調(diào)度問題的Johnson算法：
(1) 令N1={i|a_i<b_i}纱烘，N2={i|a_i<=b_i}
(2) 將N1中作業(yè)依a_i的非減序排列；將N2中作業(yè)依b_i的非增序排列祈餐；
(3) N1中作業(yè)接N2種作業(yè)構(gòu)成滿足Johnson法則的最優(yōu)調(diào)度

代碼實(shí)現(xiàn)

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("作業(yè)調(diào)度順序?yàn)?");
           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("作業(yè)調(diào)度總時(shí)間為:"+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);
       }
}