Assembly Line Scheduling (Dynamic Programming)
Problem
- There are two assembly lines, each with n stations. Station i on line j takes time
a_j[i]. Products enter with timese1,e2and leave withx1,x2. If you switch lines between station i and i+1, a transfer timet_j[i]applies. Find the minimum total processing time and the sequence of chosen lines.
Key idea (intuition)
- The optimal way to reach station i on a line depends only on the optimal ways to reach station i-1 — a classic DP with local choices (stay or transfer).
DP recurrence
- Let
f1[i]= best time to finish station i and be on line 1;f2[i]likewise for line 2.- Base:
f1[1] = e1 + a1[1]f2[1] = e2 + a2[1]
- Transition for i = 2..n:
f1[i] = min(f1[i-1] + a1[i], f2[i-1] + t2[i-1] + a1[i])f2[i] = min(f2[i-1] + a2[i], f1[i-1] + t1[i-1] + a2[i])
- Final answer:
ans = min(f1[n] + x1, f2[n] + x2)
- Base:
Reconstruction
- Store which previous line produced the minimum for each
f1[i]/f2[i]and backtrack from the last station to retrieve the chosen line at each station.
Complexity
- Time: O(n)
- Space: O(n) for reconstruction arrays (can be reduced to O(1) if only the minimum time is needed).
Example (trace)
n = 4
e1 e2 = 2 4
x1 x2 = 3 2
a1 = 7 9 3 4
a2 = 8 5 6 4
t1 = 2 3 1
t2 = 2 1 2- Trace the
f1andf2arrays by hand using the recurrence to get the minimal time and chosen lines.
Notes
- Useful to understand simple DP formulation and path reconstruction.
Code: main.cpp — computes minimal time and prints the station-by-station line choices.