算法设计与分析——流水作业调度（动态规划）

一、问题描述

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

二、算法思路

直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。

最优调度应该是：

1. 使M1上的加工是无间断的。即M1上的加工时间是所有ai之和，但M2上不一定是bi之和。

2. 使作业在两台机器上的加工次序是完全相同的。

则得结论：仅需考虑在两台机上加工次序完全相同的调度。

设全部作业的集合为N={1，2，…，n}。S是N的作业子集。在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其他作业，要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。

这个T(S,t)该如何理解?举个例子就好搞了（用ipad pencil写的...没贴类纸膜，太滑，凑合看吧）

为了解决这个问题引入Johnson不等式

3、Johnson不等式

推导公式的最后两步，作用是提出bi和aj，然后直接max三元素

4、算法描述

假设有下列的7个作业：

推测一下这个Johson法则为什么能够得到最小的作业时间？

Johson法则分出的第一组都是M2加工时间大于M1的，且按M1时间递增；分出的第二组都是M1加工时间大于M2的，且按M2时间递减。

由于M1加工是无间断的，决定时间长短的只是M2。按照Johson法则会发现，中间部分都是一些M2耗时大的作业，两头都是一些耗时小的作业，个人觉得这样安排会很好填充M2中的时间空隙。

5、代码演示

#include 
#include 
using namespace std;
class JOB
{
public:
    int key,index;
    bool job;
};
bool cmp(JOB a,JOB b)
{
    return a.key<b.key;
}
int func(int n,int a[],int b[],int c[])
{
    int i,j,k;
    JOB *d =new JOB[n];
    for(i=0;i)
    {
        if(a[i]<b[i])
        {

            d[i].job =true;
            d[i].key =a[i];
        }
        else
        {
            d[i].job=false;
            d[i].key=b[i];
        }
        d[i].index=i;
    }
    sort(d,n+d,cmp);
    j=0,k=n-1;
    for(i=0;i)
    {
        if(d[i].job ==true)
            c[j++]=d[i].index;
        else
            c[k--]=d[i].index;
    }
    j=a[c[0]];
    k=j+b[c[0]];
    for(i=1;i)
    {
    j=j+a[c[i]];
    k= jb[c[i]] ;
    }
    delete d;
    return k;
}
int main()
{
    int i,n,m,a[100],b[100],c[100];
    cin>>n;
    while(n--)
    {
        cin>>m;
        for(i=0;i)
        {
            cin>>a[i];
            cin>>b[i];
        }
        cout<endl;
    }
    return 0;
}
/*
1
7
5 2
3 4
6 7
4 2
8 9
9 7
6 3
*/