ACM基础之动态规划DP：装配线调度Assembly-Line Scheduling

一、思路

1.图示介绍

我们要从chassis enters 出发，到达completed auto exists，寻找一条代价最小的路线。

这里有两条装配线，line 1和line 2。$S_{1,1}$的第一个1表示在第几条line上，第二个1表示第几个station。

我们一共要经过6个station，不同只在于要怎么分别选择在第几条Line上的station而已。决策取决于代价，一共有四种代价：

• 开头的代价：从chassis enters 出发的2和4。
• 结尾的代价：到达completed auto exists的3和2。
• 在两条line间移动的代价：如从line1上的$S_{1,1}$到line2上的$S_{2,2}$的5。
• line上的站代价：如$S_{1,1}$下的代价7，表示通过（或完成）其所需要的代价。

2.核心公式

符号：

• $f_i[j]$：第$i$条line上，从开头到已经通过了站点$S_{i,j}$的累积代价（已经把该站点的通过代价算进去了）。
• $f?$：累积的总代价。
• $e_i$：表示开头的代价。
• $x_i$：表示结尾的代价。
• $t_{2,j?1}$：表示从line1移动到line2上的$S_{2,j?1}$的代价。
• $a_{1,1}$：表示line上的站$S_{1,1}$代价。
  
  
• 代价$f_i[j]$：表示对应通过$S_{i,j}$的累积代价。
  注意：从1到6。
• 路径$l_i[j]$：表示如果到达$S_{i,j}$，要从几条line（就是其值$l_i[j]$）的上一个站点$S_{其值,j?1}$出发。
  如，到达$S_{1,2}$，要从第1条line上的$S_{1,1}$出发。
  注意：从2到6。

3.伪代码

(1)推导过程

FASTEST-WAY(a, t, e, x, n):// 通过两条流水线各第一个站点的代价f1[1] ← e1 + a1,1f2[1] ← 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,jl1[j] ← 1// 上一个站点由第二条流水线上的走更优else	f1[j] ← f2[j-1] + t2,j-1 + a1,jl1[j] ← 2// 第二条流水线上各站点的通过代价if f2[j-1] + a2,j ≤ f1[j-1] + t1,j-1 + a2,j// 上一个站点由第二条流水线上的走更优then	f2[j] ← f2[j-1] + a2,jl2[j] ← 2// 上一个站点由第一条流水线上的走更优else	f2[j] ← f1[j-1] + t1,j-1 + a2,jl2[j] ← 1// 由两条流水线最后一个站点到结束的通过代价// 第一条流水线if f1[n] + x1 ≤ f2[n] + x2:then	f* = f1[n] + x1l* = 1// 第二条流水线else	f* = f2[n] + x2l* = 2

(2)输出路径过程

• 方案A:

// 倒着输出路径
PRINT-STATIONS(l, n):// 获取从几条line的最后一个站点n出发i ← l*print "line" i ", station" n// 继续倒着从第n-1站到第二站for j ← n downto 2:// 从第几条Line的上一个站点do	i ← li[j]print "line" i ",station" j - 1

结果是这样：从右往左的，line表示流水线一号二号，station不是图上的站点而是表示这是加工过程的总共经过的第几个站点，用于告诉我们是倒着输出路径的意思

line 1, station 6
line 2, station 5
line 2, station 4
line 1, station 3
line 2, station 2
line 1, station 1

• 方案B：

// 正序输出
RECURSIVE-PRINT-STATIONS(l, i, j):if	j = 0 then returnRECURSIVE-PRINT-STATION(l, li[j], j - 1)print "line" i ",station" j// PS：调用时:RECURSIVE-PRINT-STATION(l, l*, n)