加工生产调度

求一个加工顺序，使得加工时间最短，就要让机器的空闲时间最短，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\n",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机器上加工时间短的排在后面。

[Johnson法则]

原文：https://www.cnblogs.com/-Wind-/p/11737732.html