51nod 1205 流水线调度 Johnson算法

缘起

学习了经典的流水线调度问题，自然要找道题目来ac来证明自己写的板子正确，遂找到了 51nod 1205 流水线调度

分析

题目是中文的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
N个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然
后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。你可以安排每个作业的执行顺序，使得从第一个作业在
机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。求这个最少的时间。

【输入】
第1行：1个数N，表示作业的数量。(2 <= N <= 50000) 
第2 - N + 1行：每行两个数，中间用空格分隔，表示在M1和M2上加工所需的时间ai, bi。（1 <= ai, bi <= 10000)。

【输出】
输出完成所有作业所需的最少时间。

【样例输入】
4
3 7
2 1
1 1
4 2

【样例输出】
14

【限制】
Time limit 1000 ms
Memory limit 131072 kB

从dp的角度推导流水作业调度问题的公式.

S是{1,…,n}的子集. 令
T(S,t) = “机器M1开始加工S中作业时，而此刻机器M2还要等时间t后才可利用”这种情况下完成S中所有作业的加工
（包括M1上的加工和M2上的加工）需要的最短时间

不难得知 T(S,t) 有如下dp公式
$$
T(S,t) = min_{i \in S}{a_i+T(S-{i}, b_i+max{t-a_i, 0})}
$$

因为你想啊，我们假设时空已经停滞在了S中的活儿刚开始准备拿到M1上去加工，而M2此刻还需要等待t时间才有空的场景.则这时候总要拿S中的一项活计给M1吧? 假设这项活计为i, 事后只需要枚举i（i属于S）取最小即可. 而i一旦敲定, 则需要ai时间加工，而此时M2还需要等待t的时间才有空, 则此刻就是M1和M2同时在工作——M1还需要ai时间才会移交i给M2然后立即处理下一项S中的活计, 而M2需要t时间才能空闲出来接i这项从M1移交来的活计. 则自然要看M1处理i快还是M2处理目前手头上的活计（耗时t）快, 如果 t>ai的话，则M1快，i就会积压在M2处，M2还需要等待bi+t-ai时间才能空闲. 如果M2快的话（即ai>=t）,则M2处理完手头上的活计M1才姗姗来迟的将i移交给M2，则M2还需要花费bi时间才能空闲. 综上述，就是T{S-{i}, bi+max{t-ai,0}}

所以上面的dp等式成立（上述等式其实就是M1处理i之后（则发生状态转移）剩下的最短时间中取最小）

特别的，我们有（令t=0，S为{1,…,n}, 记做N）
$$
T(N,0) = min_{1\le i\le n}{a_i+T(S-{i}, b_i)}
$$
其实T(N,0)就是我们要求的最短时间. 但是这个dp公式求解流水线调度问题太过复杂了——涉及状态太多. 怎么办呢? 这就涉及了 Johnson 不等式（或者有些文献称之为Johnson法则）.

我们来研究一下最优调度应该具备哪些性质. 假设i,j 是T(S,t)的一个最优调度$\pi$的前两项作业. 则根据dp公式

$$
\begin{split}
T(S,t) &= a_i+T(S-{i}, b_i+max{t-a_i,0}) \
&= a_i+a_j+T(S-{i,j}, t_{ij})
\end{split}\tag{1.3}
$$

其中
$$
\begin{split}
t_{ij} &= b_j+max{b_i+max{t-a_i,0}-a_j,0} \
&= b_j+b_i-a_j+max{max{t-a_i,0}, a_j-b_i} \
&= b_j+b_i-a_j+max{t-a_i,a_j-b_i,0} \
&= b_i+b_j-a_i-a_j+max{t, a_i+a_j-b_i, a_i}
\end{split}
$$

考虑交换i和j两项作业(注意，在$\pi$中, i和j是相邻的两项作业), 则得到作业集S的另一个调度方案$\pi’$, 它的最短耗时如下（即$\pi’$ 的前两项作业是j和i, 后面的作业取最优）
$$
\begin{split}
T’(S,t) = a_i+a_j+T(S-{i,j}, t_{ji})
\end{split}\tag{1.3}
$$
其中
$$
t_{ji}=b_i+b_j-a_i-a_j+max{t, a_i+a_j-b_j, a_j}
$$
既然$\pi$是最优，那么我们自然有对于任意t有
$$
max{t, a_i+a_j-b_i, a_i} \le max{t, a_i+a_j-b_j, a_j}
$$
也就是我们需要
$$
max{a_i+a_j-b_i, a_i} \le max{a_i+a_j-b_j, a_j}
$$
上式等价于
$$
a_i+a_j+max{-b_i, -a_j} \le a_i+a_j+max{-b_j, -a_i}
$$
等价于
$$
max{-b_i, -a_j} \le max{-b_j, -a_i}
$$
等价于
$$
min{b_i, a_j} \ge min{b_j, a_i}
$$
于是我们得到的这个不等式就称之为 Johnson 不等式. 即相邻两项满足Johnson不等式是流水调度方案最优的必要条件. 其实更强的，人们证明了

任意两项i , j（i<j） 满足 min{bi, aj} >= min{bj, ai} 则称此调度方案满足Johnson法则. 满足Johnson法则的调度都是最优的. 于是，通过Johnson法则, 我们将一个看似复杂度极高的dp问题转换为了一个构造性问题.

那么如何构造满足Johnson法则的调度方案呢? （得到了调度方案，则最短时间也就出来了——很容易通过上面的dp公式得到）

1
2
3
4
5
6
(1)令N1={1<=i<=n|ai<bi},N2={1<=i<=n|ai>=bi};

(2)将N1中作业按ai的非降排序；将N2中作业按bi的非增排序；

(3)N1中作业的尾部接上N2中作业就构成了满足Johnson法则的最优调度. 这在数学上是非常好证明的——只需要分两
项作业i,j（i<j）都属于N1，都属于N2，i属于N1,j属于N2三种情况进行论证即可.

于是给出此题的ac代码如下

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
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL

const int maxn = 50005;
int n;

struct Job
{
	int a,b,index,key; //index是此项作业在原数组中的索引,key为a或者b,这取决于到底属于N1还是N2,如果属于N1的话, 就是a,否则就是b
	bool type; // true表示属于N1
	bool operator<(Job job){return key<job.key;}
}jobs[maxn]; // 0索引不用于存储数据

Job best[maxn]; // 用于装载满足Johnson法则的序列

int johnson(int i, int t)
{
	if (i==1)
	{
		return max(t, best[n].a)+best[n].b;
	}
	return best[n+1-i].a+johnson(i-1,best[n+1-i].b+max(t-best[n+1-i].a, 0));
}

int main() 
{

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	scanf("%d", &n);
	for (int i = 1; i<=n;i++)
	{
		scanf("%d%d", &jobs[i].a, &jobs[i].b);
		jobs[i].index = i;
		jobs[i].type = jobs[i].a<jobs[i].b;
		jobs[i].key = jobs[i].type?jobs[i].a:jobs[i].b;
	}
	sort(jobs+1, jobs+n+1); // 则type为N1的就是按照a升序排序, type为N2的是按b也是升序排序
	int s = 1,e = n; // best的头尾指针
	for (int i = 1; i<=n;i++) jobs[i].type?best[s++] = jobs[i]:best[e--] = jobs[i]; // 如果是N1中的, 就装到best的头部, 如果是N2中的, 就装到best的尾部, 注意,这里很妙——因为N2中的依旧按照b进行升序排序,从而这里可以装到尾部避免了jobs的2次扫描——扫一次就够了
	// 得到了最优方案best之后, 开始求最优解
	printf("%d\n",johnson(n,0));
	return 0;
}

ac情况


yfs

2019/8/16 6:46:26

C++

15ms
3,660KB

Accepted