Assembly-Line Scheduling

• Problem
  • An item is being manufactured, on assembly lines denoted as i
    • There is a time to enter each assembly line $e_i$
    • There is a time to exit each assembly line $f_i$
  • Each assembly line has $n$ stations, denoted j
    • Each station is denoted $S_{i,j}$
    • The time at a station is denoted $a_{i,j}$
    • The time required at each station varies
  • An item can be transferred from one line to another after any station
    • The transfer time is $t_{i,j}$
  • How can we get the minimum time?
• Sub-Problems
  • The fastest way through $S_{i,j}$ is the minimum of
    • The fastest way through $S_{1,j-1}+a_{1,j}$
    • The fastest way through $S_{2,j-1}+t_{2,j-1}+a_{1,j}$
  • The fastest way through $S_{2,j}$ is the minimum of
    • the fastest way through $S_{2,j-1}+a_{2,j}$
    • the fastest way through $S_{1,j-1}+t_{1,j-1}+a_{2,j}$
• The fastest way through station j is the minimum of the two subproblems