动态规划流水作业问题

---

---

n个作业{0,1,2,…,n}在2台机器上M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，后在M2上加工。在两台机器上加工的时间分别为ai和bi。
　　目标：确定这n个作业的加工顺序，使得从第一台作业开始加工，到最后一个作业完成加工所需要的时间最少。

分析：

本题虽然用的是动态规划，但是与其他题目不同，这道题目牵扯到一个新的知识点：

　　这道题，刚好把在M1上工作的时间看做是先行工序时间，M2上的工作时间看成后行工序时间。
　　如果某个作业的M1时间>M2时间，它就是后行工序；反之，就是先行工序时间。
　　这个基本原理来解流水作业问题，很简单，很巧妙。程序中用到了结构体，也是为了程序的简化，避免出现太多数组。

#include<stdio.h>
#include<iostream>
#include<algorithm> 
#define n 6     //6个作业
using namespace std;

int M1[n]={2,7,6,4,6,8};
int M2[n]={5,3,2,7,9,2};
int c[n]={0};    //存放次序，注意：c[m]=k,意思是第m+1个执行的作业是k

typedef struct Node{
    int time;    //时间
    int index;   //来自第几个作业
    int position;  //是先行工序还是后行工序 
}Node;
 
bool cmp(Node x,Node y){
    return x.time<y.time;
}

int main(){
    Node node[n];   //设置n个Node型结构体，盛放n个作业
    int first=0,end=n-1; 
    int time1=0,time2=0; //分别记录在机器1 和 机器2 上的时间 
    
    for(int i=0;i<n;i++){  // 数组打底工作       
        node[i].index=i;    //记录一下当前这个node节点放的是哪个作业 
        if(M1[i]>M2[i]){
            node[i].time=M2[i];
            node[i].position=2;    //后行工序 
        }
        else{
            node[i].time=M1[i];
            node[i].position=1;    //先行工序 
        }
    }
    
    //虽然把n个作业都赋值到了Node型结构体中，
    //但是大小交错，没有顺序， 
    //所以需要排序 
    sort(node,node+n,cmp);
    //排完序后，把原本顺序都乱了，先行、后行工作虽然交错，但都已经从小到大排列了
    //需要用c数组记录执行顺序，先行工序从前往后放，后行工序从后往前放
    
    for(int i=0;i<n;i++){
        if(node[i].position==1){   //先序 
            c[first]=node[i].index;
            first++;
        } 
        if(node[i].position==2){    //后序 
            c[end]=node[i].index;
            end --;
        }
    }
    
    time1=M1[c[0]];
    time2=time1+M2[c[0]];   
    for(int i=1;i<n;i++){
        time1+=M1[c[i]];
        time2=time1>time2?time1+M2[c[i]]:time2+M2[c[i]];
    }
    printf("次序：\n");
    for(int i=0;i<n;i++){
        printf("%3d",c[i]+1);
    } 
    putchar('\n');
    printf("%d\n",time2);       
    return 0;
} 

运行截图