流水作业调度问题

问题描述：
n个作业{0,1,2,…,n}在2台机器上M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，后在M2上加工。在两台机器上加工的时间分别为ai和bi。
目标：确定这n个作业的加工顺序，使得从第一台作业开始加工，到最后一个作业完成加工所需要的时间最少。
题目类型：动态规划
算法描述：
流水作业调度问题的Johnson算法：
（1） 令
（2）将N1 中作业依t[i,1]的非减序排列；将N2中作业依t[i,2]的非增序排列；
问题分析：
当输入的作业数目为6时：
每个作业在M1上执行的时间为t[i,1]，在M2上执行的时间为t[i,2]，输入的数据为：

算法按照先执行的作业,保证M2机器上没有等待，本例中作业1、4、5满足条件，被选择先执行。当选择第一个作业时，算法选择让M2第一次等待时间最少的那个，本例中作业1的t[i,1]最小，这样就可以让M2第一次等待最少。所以在的集合中,t[i,1]越小越靠前执行。
当执行的作业时，要保证最后一个作业在M2上的执行时间最短，所以作业2，6，3是按照t[i,2]非增序排列，保证了作业3的t[i,2]是它们三个当中最小的一个。
算法在计算执行时间的过程如下图所示：

作业执行次序为：1，4，5，2，6，3

1)执行1时：M1上运行2个时间后交给M2，这时M2空闲了2个时间并开始工作。
所以此时要想将1做完需要7（2+5）个时间。
2)执行4时：M1上运行4个时间后，M2还在继续运行1，并没有结束。M1结束时间为6，而M2结束1的时间为7，即<6,7>。
所以此时要想把1，4做完，需要14（7+7）个时间。
3)执行5时：M1上运行6个时间后，M2还在继续运行4，并没有结束。M1的结束时间为12，而M2结束4的时间为14，即<12,14>
所以此时要想把1，4，5做完，需要23（14+9）个时间。
4)执行2时：M1上运行7个时间后，M2还在继续运行5，并没有结束。M1的结束时间为19，而M2结束5的时间为23，即<19,23>.
所以此时要想把1，4，5，2做完，需要26（23+3）个时间。
5)执行6时：M1上运行8个时间后，M2已经不在继续运行2。M1的结束时间为27，而M2结束2的时间为26，即此时M2已经空闲了一个时间，即<27,26>.
所以此时要想把1，4，5，2，6完成，需要29（27+2）个时间。
6)执行3时：M1上运行6个时间后，M2已经不在继续运行6。M1的结束时间为33，而M2结束6的时间为29，即此时M2已经空闲了3个时间，即<33,29>.
所以此时要把1，4，5，2，6，3完成，需要35（33+2）个时间。

所以，根据运行结果，作业执行时间为35.

代码如下：

/*
1)先执行t[i,1]<t[i,2],保证M2上没有等待。选择第一个作业时，让M2选择第一次等待时间最少的,
即t[i,1]越小，越靠前执行;
2)执行t[i,1]>=t[i,2]时，要保证最后一个作业在M2上执行时间最短，所以按照减序排列 
*/
#include<stdio.h>
#include<string.h>
#include<algorithm> 
#define N 100
using namespace std;

struct node {
    int time;//执行时间 
    int index;//作业序号
    bool group;//1代表第一个机器，0代表第二个机器 
};

bool cmp(node a,node b)
{//升序排序 
    return a.time<b.time; 
}
int main()
{
    int i,j,k,n;
    int a[N]={0},b[N]={0};
    int best[N];//最优调度序列 
    node c[N];
    scanf("%d",&n);
    for(i=0;i<n;i++) {
        scanf("%d%d",&a[i],&b[i]);
    }
    for(i=0;i<n;i++) {  //n个作业中，每个作业的最小加工时间 
        c[i].time=a[i]>b[i]?b[i]:a[i];
        c[i].index=i;
        c[i].group=a[i]<=b[i];

    }
    sort(c,c+n,cmp);//按照c[]中作业时间增序排序
    j=0,k=n-1;
    for(i=0;i<n;i++) {
        if(c[i].group) { //第一组，从i=0开始放入到best[]中 
            best[j++]=c[i].index;
        }
        else {
            best[k--]=c[i].index;
        }
    }
    j=a[best[0]];//最优调度序列下的消耗总时间 
    k=j+b[best[0]];
    for(i=1;i<n;i++) {
        j+=a[best[i]];
        k=j<k?(k+b[best[i]]):j+b[best[i]];//消耗总时间的最大值 
    }
    printf("%d\n",k);
    for(i=0;i<n;i++) {
        printf("%d ",best[i]+1); 
    }
    printf("\n");
    return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

运行结果：