流水作业调度问题

有\(N\)个作业要在两台机器\(M_1\)和\(M_2\)组成的流水线上完成加工。每个作业\(i\)都必须先花时间\(a_i\)在\(M_1\)上加工，然后花时间\(b_i\)在\(M_2\)上加工。

确定\(N\)个作业的加工顺序，使得从作业1在机器\(M_1\)上加工开始到作业\(N\)在机器\(M_2\)上加工完为止所用的总时间最短。

【算法】

直观上，最优调度一定让\(M_1\)没有空闲，\(M_2\)的空闲时间尽量短。

Johnson算法:设\(N_1\)为\(a<b\)的作业集合，\(N_2\)为\(≥b\)的作业集合，将\(N\)的作业按\(a\)非减序排序，\(N_2\)中的作业按照\(b\)非增序排序，则\(N_1\)作业接\(N_2\)作业构成最优顺序。

算法的程序易于实现，时间复杂度为\(O(nlogn)\)，正确性需要证明。

P1248 加工生产调度

【问题描述】

某工厂收到了\(N\)个产品的订单，这\(N\)个产品分别在\(a\)、\(b\)两个车间加工，并且必须先在\(a\)加工后才可以送到\(b\)车间加工。

某个产品\(i\)在\(a\)、\(b\)两车间加工的时间分别为\(a_i\)、\(b_i\)。怎样安排这\(N\)个产品的加工顺序，才能总的加工时间最短？

这里所说的加工时间是指:从开始加工第一个产品到所有的产品都已在两车间加工完毕的时间。

【输入格式】

第一行仅一个数据\(N\)（0＜\(N\)＜1000），表示产品的数量。

接下来\(N\)个数据是表示这\(N\)个产品在\(a\)车间加工，各自所要的时间（都是整数）。最后的\(N\)个数据是表示这\(N\)个产品在\(b\)车间加工，各自所要的时间（都是整数）

【输出格式】

第一行一个数据，表示最短的加工时间。

第二行是一种用时最短的产品加工顺序。

【样例输入】

5

3 5 8 7 10

6 2 1 4 9

【样例输出】

34

1 5 4 2 3

【思路】

求一个加工顺序使得加工总用时最短，就是让机器的空闲时间最短。一旦\(a\)机器开始加工，则\(a\)机器将会不停地进行作业，关键是\(b\)机器在加工过程中有可能要等待\(a\)机器。很明显第一个部件在\(a\)机器上加工时，\(b\)机器必须等待，最后一个部件在\(b\)机器上加工时，\(a\)机器也在等待\(b\)机器的完工。

可以大胆猜想，要使机器总的空闲时间最短就要把在\(a\)机器上加工时间最短的部件最先加工，这样使得\(b\)机器能在最短的空闲时间内开始加工；把在\(b\)机器上加工时间最短的部件放在最后加工，这样使得\(a\)机器用最短时间等待\(b\)机器完工。

于是我们可以设计出这样的贪心策略:设\(M_i＝min｛a_i，b_i｝，\)将\(M\)按照从小到大的顺序排序，然后从第1个开始处理，若\(M_i＝a_i\)，则将它排在从头开始的作业后面，若\(M_i＝b_i\)，则将它排在从尾开始的作业前面。

例如:

\(N\)＝5，

\(（a_1，a_2，a_3，a_4，a_5）＝（3，5，8，7，10）\)，

\(（b_1，b_2，b_3，b_4，b_5）＝（6，2，1，4，9）\)，

则\(（M_1，M_2，M_3，M_4，M_5）＝（3，2，1，4，9）\)，

排序之后为\(（M_3，M_2，M_1，M_4，M_5）\)。

处理\(M_3\)： ∵ \(M_3＝b_3\)，∴\(M_3\)排在后面；加入\(M_3\)之后的加工顺序为\(（，，，，3）\)；

处理\(M_2\)： ∵ \(M_2＝b_2\)，∴\(M_2\)排在后面；加入\(M_2\)之后的加工顺序为\(（，，，2，3）\)；

处理\(M_1\)： ∵ \(M_1＝a_1\)，∴\(M_1\)排在前面；加入\(M_1\)之后的加工顺序为\(（1，，，2，3）\)；

处理\(M_4\)： ∵ \(M_4＝b_4\)，∴\(M_4\)排在后面；加入\(M_4\)之后的加工顺序为\(（1，，4，2，3）\)；

处理\(M_5\)： ∵ \(M_5＝b_5\)，∴\(M_5\)排在后面；加入\(M_5\)之后的加工顺序为\(（1，5，4，2，3）\)；

则最优加工顺序就是\(（1，5，4，2，3）\)，最短时间为34。

显然这个结果是最优解。

问题是这种贪心策略是否正确呢？还需证明。

【证明】

去年刚学OI时写的（萌新刚学OI），字写得渣。

Code

#include<bits/stdc++.h>

using namespace std;

const int N = 2005;

struct data {

	int id,a,b;

} J[N], ans[N];

int n;

inline bool cmp(const data &A, const data &B) {//Jhonson不等式排序

	return min(A.a, A.b) < min(B.a, B.b);

}

int main() {

	scanf("%d", &n);

	for(int i = 1; i <= n; ++i) {

		scanf("%d", &J[i].a);

		J[i].id = i;//原数组下标

	}

	for(int i = 1; i <= n; ++i) scanf("%d", &J[i].b);

	sort(J + 1, J + 1 + n, cmp);

	for(int i = 1, p = 1, q = n; i <= n; ++i) {//p--队头 q--队尾

		if(J[i].a <= J[i].b) ans[p++] = J[i];

		else ans[q--] = J[i];

	}

	int time1 = 0, time2 = 0;//time1--A机器上加工用时 time2--B机器上加工用时

	for(int i = 1; i <= n; ++i) {

		time1 += ans[i].a;//第i件产品在A机器上所用时间

		time2 = max(time1, time2);//在A机器上加工完才能到B机器 未加工完需要等待

		time2 += ans[i].b;//第i件产品在B机器上所用时间

	}

	printf("%d\n", time2);//最后一件在B机器加工完的时刻为结束时刻

	for(int i = 1; i <= n; ++i) printf("%d ", ans[i].id);//输出方案

	return 0;

}

巴特西

洛谷P1248 加工生产调度