一、问题描述
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写的...没贴类纸膜，太滑，凑合看吧）
1、最优子结构
T(N,0)=min{ai + T(N-{i}, bi)}, i∈N。
ai：选一个作业i先加工，在M1的加工时间。
T(N-{i},bi}：剩下的作业要等bi时间后才能在M2上加工。注意这里函数的定义，因为一开始工作i是随机取的，M1加工完了ai之后，要开始加工bi了，这里M1是空闲的可以开始加工剩下的N-i个作业了，但此时M2开始加工bi，所以要等bi时间之后才能重新利用，对应到上面函数T(s,t)的定义的话，这里就应该表示成T(N-{i},bi), 所以最优解可表示为T(N,0)=min{ai + T(N-{i}, bi)}, i∈N，即我们要枚举所有的工作i，使这个式子取到最小值。
继续分析T(S,t)可得：
T(S,t)={ai + T(S-{i}, bi+max{t-ai,0})}, i∈S
其中：T(S-{i}, bi+max{t-ai,0})：剩下的作业等bi+max{t-ai,0}才能在M2加工，至于这里是怎么推导出来的呢？见下面推导：
2、最优子结构性质
这段证明不是很好理解，简单来说就是要证明问题的最优解包含子问题的最优解就行了，那么这里的证明思路是先假设一个最优调度，对于他的子调度T’，因为T(S,t)被定义为是完成S中作业所需的最短时间记为T(S,t)，所以有T’>=T(S, bπ1)，那么如果这个子调度这里不是最优解的话即T’>T(S, bπ1)，会得出aπ1+T’ > aπ1+T(S, bπ1)即原来假设的最优调度不符和最优调度的标准，矛盾，从而推出 T’是一定等于T(S, bπ1)，即这个子调度也是最优调度。
问题是：虽然满足最优子结构性质，也在一定程度满足子问题重叠性质。N的每个非空子集都计算一次，共2n-1次，指数级的。
为了解决这个问题引入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 } 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] { 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= j } 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< } return 0; } /* 1 7 5 2 3 4 6 7 4 2 8 9 9 7 6 3 */ 结果：43 相关阅读
发表评论