Assembly Line Scheduling

A factory has two parallel assembly lines, each with the same n stations in sequence. A product normally flows straight down one line, but between stations it may switch lines for a transfer cost. Each station has its own processing time, and there are entry and exit costs at the ends. Assembly line scheduling finds the route — which line at each station — that finishes fastest. It's a tiny, beautiful DP that runs in a single forward sweep.

The only decision at each station

Arriving at station j on line i, you came from one of just two places: station j-1 on the same line (no transfer), or station j-1 on the other line (pay the transfer cost). Let f[i][j] = the earliest possible time to finish station j on line i. Each value reads only the two values from the previous station, so the whole factory resolves left to right.

1. 1Entry: f[0][0] = entry[0] + a[0][0] and f[1][0] = entry[1] + a[1][0] (cost to reach and run the first station on each line).
2. 2For station j on line 0: f[0][j] = a[0][j] + min( f[0][j-1], f[1][j-1] + transfer[1][j-1] ).
3. 3Symmetrically for line 1: f[1][j] = a[1][j] + min( f[1][j-1], f[0][j-1] + transfer[0][j-1] ).
4. 4Final answer: min( f[0][n-1] + exit[0], f[1][n-1] + exit[1] ).

function fastestWay(a, t, entry, exit, n) {
  const f = [new Array(n), new Array(n)];
  f[0][0] = entry[0] + a[0][0];
  f[1][0] = entry[1] + a[1][0];
  for (let j = 1; j < n; j++) {
    f[0][j] = a[0][j] + Math.min(f[0][j - 1], f[1][j - 1] + t[1][j - 1]);
    f[1][j] = a[1][j] + Math.min(f[1][j - 1], f[0][j - 1] + t[0][j - 1]);
  }
  return Math.min(f[0][n - 1] + exit[0], f[1][n - 1] + exit[1]);
}