动态规划---装配线调度
子问题的最的解
f1[j] = e1+a1,1 如果j=1
min(f1[j-1]+a1,j,f2[j-1]+t2,j-1+a1,j) 如果j>=2
f2[j] = e2+a2,1
如果j=1
min(f2[j-1]+a2,j,f1[j-1]+t1,j-1+a2,j) 如果j>=2
原问题的解
f* = min(f1[n] +a1,f2[n] +x2)
伪代码
Fastest-Way(a, t, e, x, n)
f1[1] = e1 + a1,1
f2[2] = e2 + a2,1
for j=2 to n
do if f1[j-1] + a1,j < = f2[j-1] + t2,j-1 + a1,j
then f1[j] = f1[j-1] +a1,j
L1[j] = 1 //上面显示,通过S1[j]装配点最优解是在前一个装配点S1[j-1]最优解基础上得到的,
所以,Li[j]记录的是在最优解情况下,在第i生产线的j点的前一个装配点j-1所在的 生产线号
else f1[j] = f2[j-1] +t2,j-1 + a1,j
L1[j] = 2
if f2[j-1] + a2,j < = f1[j-1] + t1,j-1 + a2,j
then f2[j] = f2[j-1] +a1,j
L2[j] = 2
else f2[j] = f1[j-1] +t1,j-1 + a2,j
L2[j] = 1
if f1[n] +x1 <= f2[n] +x2
then f* = f1[n] +x1
L* = 1
else f* = f2[n] + x2
L* = 2
end
Print-stations (L, L*, n)
i = L*
print "line" + i + ",station " + n
for j = n downto 2
do i = Li[j]
print "line" + i + ", station " + j-1
end
详细参考:http://www.cnblogs.com/Anker/archive/2013/03/09/2951785.html