[Johnson法则]

p1248

加工生产调度

求一个加工顺序，使得加工时间最短，就要让机器的空闲时间最短，A一旦开始加工就要不停地加工，但加工过程中存在A机器会等待B机器加工，B机器也要等待A机器加工。很明显A机器的第一个工件，B机器必须要等待，B机器的最后一个工件，A机器必须要等待。所以要让(a_i)小的在A先加工，让(b_i)大的在B先加工。令(m_i)表示(min(a_i,b_i))然后从小到大排序(m_i)，令(ans[i])表示最终工件的加工顺序，接着从(1~n)循环，如果(m_i=a_i),让(head++,ans[head] = a_i)的位置，否则(tail--,ans[tail] = b_i)的位置。代码如下

#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2005;
int n,a[maxn],b[maxn];
int head,tail,ans[maxn];
int time_a,time_b;
struct qwq{
	int mini,pos;
	bool operator < (const qwq &x)const
	{
		return mini < x.mini;
	}
}e[maxn];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		scanf("%d",&b[i]);
	for(int i=1;i<=n;i++)
	{
		e[i].mini = min(a[i],b[i]);
		e[i].pos = i;
	}
	sort(e+1,e+n+1);
	tail = n + 1;
	for(int i=1;i<=n;i++)
	{
		if(e[i].mini == a[e[i].pos])
		{
			head ++;
			ans[head] = e[i].pos;
		}
		else
		{
			tail --;
			ans[tail] = e[i].pos;
		}
	}
	for(int i=1;i<=n;i++)
	{
		time_a += a[ans[i]];
		if(time_b < time_a)
			time_b = time_a;
		time_b += b[ans[i]];
	}
	printf("%d
",time_b);
	for(int i=1;i<=n;i++)
		printf("%d ",ans[i]);
	return 0;
}

算法证明

设(S={J_1,J_2,J_3,.........J_n}),为待加工工件的顺序，A正在加工，(t)时刻后B开始加工A加工完的，则在这样的条件下，加工完(S)中工件所需要的最短时间为(T(S,t) = min(a_i+T(S-{J_i},b_i+max(t-a_i,0))，其中(J_i∈S)。
得到(min(b_j,a_i))(leq)(min(a_j,b_i))即(Johnson)不等式，所以在A机器上加工时间短的排在前面，在B机器上加工时间短的排在后面。