Assembly line scheduling

What stations should be chosen from line 1 and which fro m line 2 in order to minimize the total time through the factory for one car?

There are

2^n

possible ways to choose stations

Station $S_{line, index}$

Assembly line $a_{line, index}$ - usually assembly line is 2

Transfer time $t_{line, index}$

Entry time $e_{line}$

Exit time $x_{line}$

Step $n$ - max index

Dynamic Programming

Optimal substructure

An optimal solution to the problem find the fastest way through $S_{1, j}$ contains, within it, an optimal solution to subproblems: find the fastest way through $S_{1, j-1}$ or

S_{2, j–1}

Let $f^*$ is the fastest time to get through the entire factory

Let $f_i[j]$ is the fastest time to get from the starting point through station $S_{i,j}$

f^*= min(f_1[n] + x_1, f_2[n]+x_2) \newline f_1[1] = e_1 + a_{1,1}, \newline f_2[1] = e_2 + a_{2,1}

f_1[j] = min(f_1[j-1] + a_{1,j}, f_2[j-1] + t_{2, j-1}) \newline f_2[j] = min(f_2[j-1] + a_{2,j}, f_1[j-1] + t_{1, j-1})

O(n)

Assembly line scheduling

Dynamic Programming

Recommendations