DevJourney · code I wrote while learning

02_Assembly_Line_Scheduling

2 items

README.md

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 times e1,e2 and leave with x1,x2. If you switch lines between station i and i+1, a transfer time t_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)

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 f1 and f2 arrays 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.