如果给定2台相同的机器，有N个作业，第i个作业需要T[i]时间完成，是否存在一种精确的算法将这N个作业分配给这2台机器，使最大完工时间最小或完成所有N个作业所需的总时间最小?我只需要解决N=50的问题。还要注意，所有进程的总执行时间以10000为限。
是否贪婪地将最大的作业分配给获得空闲作业的机器?
// s1 -> machine 1
//s2->machine 2 , a[i]-> job[i] ,time-> time consumed,jobs sorted in descending order
// allocated one by one to the machine which is free.
long long ans=INT_MAX;
sort(a,a+n);
reverse(a,a+n);
int i=2;
int s1=a[0];
int s2=a[1];
long long time=min(s1,s2);
s1-=time;
s2-=time;
while(i<n)
{
if(s1==0 && s2==0)
{
s1=a[i];
if(i+1<n) s2=a[i+1];
int c=min(s1,s2);
time+=c;
s1-=c;
s2-=c;
i+=2;
continue;
}
else
{
if(s1<s2) swap(s1,s2);
s2=a[i];
int c=min(s1,s2);
time+=c;
s1-=c;
s2-=c;
i++;
}
}
assert(s1*s2==0);
ans = min(ans,time+max(s1,s2));
您所描述的问题是NP-难以通过或多或少直接从子集和中简化，这使得精确的多项式时间算法不可能，除非 p =NP。贪心赋值一般情况下不会产生最优解。然而，由于作业数以50为限，N中任何具有运行时间指数的精确算法实际上都是具有恒定运行时间的算法。
这个问题可以通过如下的动态规划来解决。设P为所有处理时间的总和，这是最优makespan的上界。定义一个数组S[N][P]作为状态空间。S[i][j]的含义是由1,...,i索引的作业所能达到的最小完工时间，其中机器1的负载正好是j。外部循环遍历作业，内部循环遍历机器1的目标负载。在每次迭代中，我们必须决定作业i应该运行在机器1还是机器2上。当然，状态值的确定必须以这样一种方式进行:只考虑存在的解。
在第一种情况下，我们将S[i][j]设置为[i-1][j-T[i]] + T[i](机器1的结果负载)的最小值和{1,...,i-1}中pi'对i'的总和减去[i-1][j-T[i]](机器2的结果负载，也就是说，机器1的补充负载，我们的选择没有改变)。
在第二种情况下，我们将S[i][j]设置为[i-1][j](机器1的结果负载，我们的选择不改变)的最小值，以及{1,...,i-1}中T[i']对i'的总和减去[i-1][j-T[i]]加上T[i](机器2的结果负载，也就是说机器1的补充负载)。
最后，通过确定每个j的S[N][j]的最小值，可以找到最优makespan。注意，该方法只计算最优值，而不是最优解本身。通过回溯或使用合适的辅助数据结构，可以找到最优解。运行时间和空间需求为O(N*P)，即N中的伪多项式。
注意这个问题和方法与背包问题非常相似。然而，对于调度问题，要选择的不是是否包含一个项目，而是是否在机器1或机器2上执行一个作业。
还要注意，这个问题实际上已经得到了很好的研究;所谓的三字段表示法的问题描述是P2||Cmax。但是，如果我没有记错的话，按照处理时间的不增加顺序贪婪地调度作业会产生如下文章所证明的近似比率为2。
R.L.Graham，"边界-某些多处理异常"，Bell System technology Journal 45 (1966) 1563-1581