问题描述

某工厂有 $n$ 件物品需要进行加工，并且每件物品都需要先在 $A$ 工厂加工 $a_i$ 分钟，然后在 $B$ 工厂加工 $b_i$ 分钟， $A$ ， $B$ 工厂每次分别只能加工一件物品，问你最少需要多少时间能够加工完全部 $n$ 件物品

交换论证

假设有 $n$ 件待完成事件，当前完成了 $k$ 件，所花时间为 $T$ ，设当前先完成 $i$ 事件再完成 $j$ 事件的总时间代价为 $T + T_{i,j}$ ，先完成 $j$ 事件再完成 $i$ 事件的总时间代价为 $T + T_{j,i}$ ，那么若能够找到关于 $T_{i,j} < T_{j,i}$ 的满足条件，那么该条件即为贪心法则的完备条件

Johnson 法则

令 $N_1=\{i\ |\ a_i < b_i\}$ , $N_2=\{i\ |\ a_i \geq b_i\}$
将 $N_1$ 中作业依照 $a_i$ 增序排列， $N_2$ 中作业依 $b_i$ 减序排列
$N_1$ 中作业接 $N_2$ 中作业构成满足 Johnson 法则的最优调度

基于交换论证的 Johnson 法则证明

假设当前已完成了 $k$ 件物品的加工，其序列如下：

$a_1, a_2, a_3, ... a_k$
$b_1, b_2, b_3, ... b_k$

定义 $A_{i} = \sum_{i=1}^ia_i$ 为工厂 $A$ 加工完前 $i$ 件物品所花时间， $B_{i}=max(A_i,B_{i-1})+b_{i}$ 为工厂 $B$ 加工完成前 $i$ 件物品所花时间，那么此时有 $A_{k}=\sum_{i=1}^{k}a_{i}$ ， $B_{k}=max(A_{i},B_{i-1})+b_{k}$

根据交换论证的步骤，接下来需要讨论加工顺序为 $x,y$ 和 $y, x$ 所花时间的大小关系

设此时先加工第 $x$ 件物品所花时间为 $B_{x} = max(A_{k}+a_{x},B_{k})+b_{x}$ ，先加工第 $y$ 件物品所花时间为 $B_{y} = max(A_{k}+a_{y},B_{k})+b_{y}$ ，则有：

$B_{x,y}=max(A_{k}+a_{x}+a_{y},max(A_{k}+a_{x}, B_{k})+b_{x}) + b_{y}$
$B_{y,x}=max(A_{k}+a_{x}+a_{y},max(A_{k}+a_{y}, B_{k})+b_{y}) + b_{x}$

将上式中的 $b_x$ 和 $b_{y}$ 移入 $max$ 内部，得：

$B_{x,y}=max(A_{k}+a_{x}+a_{y}+ b_{y},A_{k}+a_{x}+b_{x}+ b_{y}, B_{k}+b_{x}+ b_{y})$
$B_{y,x}=max(A_{k}+a_{x}+a_{y}+ b_{x},A_{k}+a_{y}+b_{x}+ b_{y}, B_{k}+b_{x}+ b_{y})$

显然当 $B_{k}+b_{x}+ b_{y}$ 为最大值时对答案没有影响，故将其剔除

$B_{x,y}=max(A_{k}+a_{x}+a_{y}+ b_{y},A_{k}+a_{x}+b_{x}+ b_{y})=A_{k}+a_{x}+b_{y}+max(a_{y}, b_{x})$
$B_{y,x}=max(A_{k}+a_{x}+a_{y}+ b_{x},A_{k}+a_{y}+b_{x}+ b_{y})=A_{k}+a_{y}+b_{x}+max(a_{x}, b_{y})$

不妨设 $B_{x,y} < B_{y, x}$ ，则有：

$A_{k}+a_{x}+b_{y}+max(a_{y}, b_{x}) < A_{k}+a_{y}+b_{x}+max(a_{x}, b_{y})$

$a_{x}+b_{y}+max(a_{y}, b_{x})<a_{y}+b_{x}+max(a_{x}, b_{y})$

$max(-b_{x}, -a_{y})<max(-b_{y}, -a_{x})$

$min(b_{x}, a_{y})>min(b_{y}, a_{x})$

即当物品 $x$ 和物品 $y$ 满足 $min(b_{x}, a_{y})>min(b_{y}, a_{x})$ 条件时， $B_{x,y} < B_{y,x}$

但是该条件是不完备的，即该条件不满足传递性，若此时 $min(b_{x}, a_{y})=min(b_{y}, a_{x})$ ，则理论上 $B_{x,y}=B_{y,x}$ ，事实上也确实如此，但是由于 $B_{i}=max(A_i,B_{i-1})+b_{i}$ ，所以 $a_{i}$ 的前缀和 $A_{i}$ 对于后续答案的统计是有影响的，出现这种情况的根源在于推导式子时正确的传递条件应当在 $min(b_{x}, a_{y})=min(b_{y}, a_{x})$ 的条件下继续判断 $a_{i}$ 的大小，以满足排序条件的传递性

下面这组例子可以帮助理解：

3
2 100 3
1 1 1

这三件物品根据判断条件来看是等价的，但是其加工顺序不一样会导致结果不一样

再举一个例子，假设此时 $\forall i \in [1, n],b_{i}=c,\ a_{i}\geq c$ ，理论上来说总时间 $B_{n}=A_{n}+c$ 并且有 $B_{i}=A_{i}+c$ ，但若此时 $a_{i}$ 为无穷大，则会导致 $A$ 工厂流水线阻塞，为了避免这种情况或者说为了使得对于 $\forall i \in [1, n],B_{i}=A_{i}+c$ ，我们显然需要将 $a_{i}$ 小的先行加工

那么问题究竟出在了哪里呢？

在上述推导中显然我们只考虑了两件物品的先后关系，若每两件物品均满足 $B_{x,y} < B_{y,x}$ 的优先关系，称任意两件物品具有可比性，若 $\exists x,y,B_{x,y} = B_{y,x}$ ，则需要考虑其顺序的后效性，或者说是排序条件的传递性

AC Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long ll;
struct Node {
    ll a, b, id;
} p[maxn];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) p[i].id = i;
    for (int i = 1; i <= n; ++i) cin >> p[i].a;
    for (int i = 1; i <= n; ++i) cin >> p[i].b;
    sort(p + 1, p + n + 1, [&](Node x, Node y) {
        if (min(x.b, y.a) == min(y.b, x.a)) return x.a < y.a;
        return min(x.b, y.a) > min(y.b, x.a);
        });
    ll x = 0, y = 0;
    for (int i = 1; i <= n; ++i) {
        x += p[i].a;
        y = max(x, y) + p[i].b;
    }
    cout << y << '\n';
    for (int i = 1; i < n; ++i) cout << p[i].id << " ";
    cout << p[n].id << '\n';
    return 0;
}

NC50164 加工生产调度 题解 && Johnson法则证明

问题描述

交换论证

Johnson 法则

基于交换论证的 Johnson 法则证明

AC Code

NC50164 加工生产调度题解 && Johnson法则证明