问题描述

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

问题分析

直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。

在一般情况下，机器M2上会有机器空闲和作业积压两种情况

设全部作业的集合为N={1，2，…，n}。\(S\subseteq N\)是N的作业子集。

通常，机器M1开始加工S中作业时，机器M2还在加工其它作业，要等时间t后才可利用。

将这种情况下完成S中作业所需的最短时间记为T(S, t)。

流水作业调度问题的最优值为T(N, 0)。

算法思路

直观上，一个最优调度应使机器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)该如何理解?举个例子

最优子结构

\(T(N,0)=min\{a_i+T(N-\{i\},b_i)\},i\in N\)。

\(a_i\)：选一个作业i先加工，在M1的加工时间。

\(T(N-i,b_i)\)：剩下的作业要等\(b_i\)时间后才能在M2上加工。注意这里函数的定义，因为一开始工作i是随机取的，M1加工完了\(a_i\)之后，要开始加工bi了，这里M1是空闲的可以开始加工剩下的N-i个作业了，但此时M2开始加工bi，所以要等\(b_i\)时间之后才能重新利用，对应到上面函数T(s,t)的定义的话，这里就应该表示成\(T(N-\{i\},b_i)\), 所以最优解可表示为T(N,0)=min{ai + T(N-{i}, bi)}, i∈N，即我们要枚举所有的工作i，使这个式子取到最小值。

继续分析T(S,t)可得：\(T(S,t)=a_i+T(S-\{i\},b_i+max\{t-a_i,0\}),i\in S\)

其中：\(T(S-\{i\},b_i+max\{t-a_i,0\})\)：剩下的作业等\(b_i+max\{t-a_i,0\}\)才能在M2加工，至于这里是怎么推导出来的呢？见下面推导：

最优子结构性质

最优子结构性质：问题最优解，是否包含了子问题的最优解。

这段可以这么理解：设π是所给n个流水作业（N={1，2，…，n}）的一个最优调度，最优调度序列是π(1) ，π(2)， π(3)，…，π(n) ，π是否是调度π(2)， π(3)，…， π(n)的一个最优调度？若是，最优子结构性质成立。证明如下：

把π调度n个作业所需的加工时间分成两部分： \(a_{\pi (1)}\)和T’。 其中，T’是机器M1和M2加工作业{π(2)，…，π(n)}所需的时间。因此，π调度n个流水作业需要的总时间为\(a_{\pi (1)}\)和T’

令作业子集S=N - {π(1)} ，即：S={π(2)， π(3)，…，π(n)}。

假设π不是实现加工作业子集S所需时间最短（最优）的调度，设π’是M1和M2加工作业子集S所需时间最短的一个最优调度, 则按π’加工作业子集S的最短时间为\( T(S, b_{π(1)} )\)

因此π(1)， π’(2)，…， π’(n)是完成N ={1，2，…，n}作业 的一个调度，且该调度完成n个作业所需的时间 \(a_{\pi (1)}+T(S,b_{\pi (1)})\)

由于 π’是加工π(2)，…，π(n)的最优调度，则T(S,bπ(1))是最短 时间，则\(T(S, b_{π(1)})≤ T’\)，因此，\(a_{π(1)} +T(S,b_{π(1)}) ≤a_{π(1)}+T’\).由

此，按照π(1)， π’(2)，…， π’(n)调度顺序完成n个作业所需的时间，小于按照π(1)， π(2) ，…， π(n) 调度完成n个作业所需时间\(a_{\pi (1)}+T^'\)，这与π是N的最优调度矛盾，

因此，π’是完成π(2)，…，π(n)的最优调度假设不成立，因此，π是完成π(2)，…，π(n)作业的最优调度。即：作业调度问题最优子结构性质成立。

递归计算最优值

由流水作业调度问题的最优子结构性质可知:

一般情况下：

问题是：虽然满足最优子结构性质，也在一定程度满足子问题重叠性质。N的每个非空子集都计算一次，共2n-1次，指数级的。

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

Johnson不等式

推导公式的最后两步，作用是提出\(b_i\)和\(a_j\)，然后直接max三元素

算法描述

假设有下列的7个作业：

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

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

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

代码演示

#include <iostream>

#include <vector>
#include <algorithm>
using namespace std;
class JOB
{
public:
    int t1;
    int t2;
};
//第一道工序的升序排列
bool cmp(JOB a,JOB b)
{
    return a.t1<b.t1;
}
//第二道工序的降序排列
bool cmp2(JOB a,JOB b){
    return a.t2>b.t2;
}

int johnson(const vector<JOB>& parts){
    vector<JOB> N1;
    vector<JOB> N2;
    for(JOB x:parts){
        x.t1<=x.t2?N1.emplace_back(x):N2.emplace_back(x);
    }
    //Johnson调度
    //分别排序第一类和第二类
    sort(N1.begin(),N1.end(),cmp);
    sort(N2.begin(),N2.end(),cmp2);
    //合并到一起
    vector<JOB> total;
    total.insert(total.end(),N1.begin(),N1.end());
    total.insert(total.end(),N2.begin(),N2.end());

    //计算时间
    long t1 = total[0].t1;
    long t2 = t1+total[0].t2;
    for(vector<JOB>::iterator it = total.begin()+1;it!=total.end();++it){
        t1+=(*it).t1;//M1在执行c[i]作业,M1不间断
        t2 = max(t2,t1) + (*it).t2;//M1在执行c[i]作业的同时，M2在执行c[i-1]号作业，最短执行时间取决于M1与M2谁后执行完
    }
    return t2;
}

int main(int argc, char** argv)
{
    int N;
    cin>>N;
    vector<JOB> parts;
    for(int i=0;i<N;++i){
        JOB tmp;
        cin>>tmp.t1>>tmp.t2;
        parts.emplace_back(tmp);
    }
    cout<<johnson(parts)<<endl;
    return 0;
}
/*
7
5 2
3 4
6 7
4 2
8 9
9 7
6 3
*/

结果：43