ACM试题1180 Batch Scheduling.pptVIP

Batch Scheduling周鹏 问题描述 有N个工作排成一串1，2……N 这些工作必须被分成若干个包 每个包包含连续的一些工作，如{2，3，4} 处理一个包所用的时间=S (Setup Time)+处理每个工作所用的时间 工作完成的时间O [i]是它所属的包完成的时间 每个工作知道 T[i]:完成这项工作要用的时间 F[i]:单位时间的费用 每个工作的费用：O[i](输出时间)*F[i] Sample: Setup Time: 1 5 jobs: T[]={1,3,4,2,1}, F[]={3,2,3,3,4} partitioned into 3 batch {1,2},{3},{4,5} Output Time for batch 1 : 1+1+3=5 batch 2 : 5+1+4=10 batch 3 : 10+1+2+1=14 Output time for each job is {5,5,10,14,14} and cost for each job is {5*3,5*2,10*3,14*3, 14*4}={15,10,30,42,56} Total Cost=15+10+30+42+56=153 目的：对这些工作如何划分使得总费用最小 输入： N : number of jobs (1=N=10000) S : Setup Time (0=S=50) T[i] F[i] : T[i]=100,F[i]=100 解决方法？ （简单）求出前i个工作的划分成j个包的最优划分c[i][j] 递推公式 c[i][j]=min{ c[i-1][j-1]+(s+t[i])*f[i], c[i-2][j-1]+(s+t[i]+t[i-1])*(f[i]+f[i-1]), …, c[j-1][j-1]+(..)*(..) } 效率太低：求c[i][j]: O (n) , 总体 O (n*n*n) 结果…………超时? 失败的分析： 原因：状态选得不好（工作1-i分成j包）二维 另外一种状态表述： 处理工作I,I+1,..,N的最佳方案:d[i] 一维！ d[i][k] 表示第一个包从i到k-1, k=n+1 (k=n+1时，只有一个包） d[i][k]=d[k]+(s+t[i]+..+t[k-1])*(f[i]+..+f[n]) 递推公式： d[i]=min{d[i][k]|i+1=k=n+1} 效率：0（n*n) 结果…………………………超时 失败的分析：（如何改进） 再改进只能从递推公式入手： 如何很快的求出d[i][k]的最小值？ 若d[i][j]d[i][k] (ijk) ?d[j] + (s+ t[i]+..+ t[j-1]) * ( f[i]+..+ f[n]) d[k] + (s+t[i]+..+t[k-1]) * (f[i]+..+ f[n]) ?(d[j]-d[k])/(t[j]+..+t[k-1])f[i]+..f[n] let sf[i]=f[i]+..+f[n], st[i]=t[i]+..+t[n] i.e. (d[j]-d[k])/(st[j]-st[k]) sf[i] let g[j][k]= (d[j]-d[k])/(st[j]-st[k]) i.e g[j][k]sf[i] 改进： 两条性质： (ijkl) g[j][k]sf[i]?d[i][j]d[i][k] g[j][k]sf[i]?d[i][j]d[i][k]//easy g[j][k]g[k][l]?d[i][k]一定不是最小的 简证：if g[j][k]sf[i] then d[i][j]d[i][k] if g[k][l]sf[i] then d[i][k]d[i][l] whatever d[i][k] is not the smaller one 性质2的意义： 可以对所有的(ik)排除d[i][k]是最小值的可能 改进方法： 原来要考察的序列为 {i+1,i+2,…,n} 要从中选出d[i][k]的最小值 利用性质2，删除一些元素，使得 {…j, k, l,…} 满足 g[j][k]g[k][l] 利用性质1,若g[j][k]sf[i],d[i][j]d[j][k],就是d[i][k]不可能是最小值，从序列尾部删除它，使得{…j,k,l}满足..g[j][k]g[k][l]sf[i] 就是说：d[i][l]d[i][k]d[i][j]… 所以d[i][l]就是要求的最小值！ 因此，对于任何一个i都可以按上述步骤，得到一个序列 但是这种对每一个i都重新处理，太没效率了！ 能不能从i+1的序列，推出来i的序