Assembly Line Scheduling using Dynamic Programming

Assembly Line Scheduling Problem: Explained

Assembly line scheduling is a manufacturing problem. In automobile industries, assembly lines are used to transfer parts from one station to another.

• Manufacturing of large items like car, trucks etc. generally undergoes through multiple station, where each station is responsible for assembling particular part only. Entire product will be ready after it goes through predefined n stations in sequence.
• For example, manufacturing of car may be done in several stages like engine fitting, coloring, light fitting, fixing of controlling system, gates, seats and many other things.
• Particular task is carried out at the station dedicated for that task only. Based on requirement, there may be more than one assembly line.
• In case of two assembly lines, if load at station j of assembly line 1 is very high, then components are transferred to station j of assembly line 2, converse is also true. This helps to speed up the manufacturing process.
• The time to transfer partial product from one station to next station on same assembly line is negligible. During rush, factory manager may transfer partially completed auto from one assembly line to another, to complete the manufacturing as quick as possible. Some penalty of time t occurs when product is transferred from assembly 1 to 2 or 2 to 1.

Assembly Line Scheduling Problem

• Determine which station should be selected from assembly line 1 and which to choose from assembly line 2 in order to minimize the total time to build the entire product.
• Selecting stations by brute force attack is quite infeasible. If there are n stations, unfortunately there are 2ⁿ possible ways to choose stations. Brute force attack takes O(2ⁿ) time, it is not acceptable when n is large.
• General architecture of two assembly lines with n stations is shown in following figure.

• Terminologies are explained here :
  • S_ij = Station j on assembly line i.
  • a_ij = Time needed to assemble the partial component at station j on assembly line i.
  • t_ij  = Time required to transfer component from one assembly to other from station j to (j + 1).
  • e_i = Entry time on assembly line i.
  • x_i = Exit time from assembly line i.

Mathematical formulation

 Time required to build component on first station of both line is summation of entry time for particular assembly line and assembly time on first station of particular line.

f_i [j]    =   e_i + a_i1 ; Initial condition (if j == 1), i = 1, 2

Minimum time required to put the partially assembled product out of any station j on line 1 is minimum of :

1. (Minimum time taken up to station j – 1 on same assembly line 1) + (assembly time on station j of same assembly line)
2. (Minimum time taken up to station j – 1 on assembly line 2) + (assembly line transfer time) + (assembly time on station j of assembly line 2)

We can derive the conclusion for assembly line 2 in similar way. So mathematically we can formulate the problem as :

For j > 1 :

f_1[j] = min (f₁ [j – 1] + a₁, f₂ [j – 1] + t_{2 j – 1} + a_1j )

f_2[j] = min (f₁ [j – 1] + t_{1 j – 1} + a_2j, f₂ [j – 1] + a_2j )

Exit time from assembly line 1 and 2 are x₁ and x₂ respectively. Thus, minimum time to take away the product from assembly line is :

f*    =   min (f₁ [n] + x₁, f₂ [n] + x₂)

Algorithm for Assembly Line Scheduling

The algorithm for assembly line scheduling using dynamic programming is described below :

Algorithm ASSEMBLY_LINE_SCHEDULING(n, e, a, t, x)  
// n is number of stations on both assembly
// e is array of entry time on assembly
// a is array of assembly time on given station
// t is array of the time required to change assembly line
//x is array of exit time from assembly

f1[1] ← e1 + a1,1
f2[1] ← e2 + a2,1

for j ← 2 to n do
   if f1[j - 1] + a1, j  ≤ f2[j – 1] + t[j – 1] + t + a2, j then
      f1[j] ← f1[j – 1] + a1, j
      L1[j] ← 1
   else
      f1[j] ← f2[j – 1] + t2,j – 1+ a1, j
      L1[j] ← 2
   end

   if f2[j – 1] + a2, j ≤ f1[j – 1] + t1, j – 1 + a2, j then
      f2[j] ← f2[j – 1] + a2, j
      L2[j] ← 2
   else
      f2[j] ← f1[j – 1] + t1, j – 1 + a2, j
      L2[j] ← 1
   end

   if f1[n] + x1  ≤ f2[n] + x2 then
      F* ← f1[n] + x1
      L* ← 1
   else
      F* ← f2[n] + x2
      L* ← 2
   end
end

The above algorithm will just tell us the minimum time required to take away the product from station n. It does not tell anything about the sequence of stations on assembly. We can find the station sequence by tracing the solution using the following algorithm.

Algorithm  PRINT_STATIONS(l, n)

i ← 1*
print "line " i ", station " n
for j ← n downto 2 do
    i ← Li[ j ]
    print "line " i ",station " j – 1
end

Examples

Example: Find optimal assembly line schedule for given data.

Solution:

f_i [j] = e_i + a_i,₁; Initial condition (j = 1, i=1, 2)

f₁ [j] = min (f₁ [j – 1] + a_1j, f₂ [j – 1] + t_{2 j – 1}) + a_1j)

f₂ [j] = min (f₁ [j – 1] + t_{1 j – 1}) + a_2j, f₂ [j – 1] + a_2j )

f*  = min (f₁ [n] + x₁, f₂ [n]+x₂ )

f₁ [1] = e₁ + a₁₁

= 4 + 2

= 6

f₂ [1]  = e₂ + a₂₁

= 2 + 6 

= 8

f₁ [2] = min (f₁[j – 1] + a_1j, f₂ [j – 1] + t_{2j – 1}+ a_1j )

= min (f₁ [1] + a₁₂, f₂ [1] + t₂₁ + a₁₂) 

=  min (6 + 8, 8 + 3 + 8)

= min (14, 19) 

= 14

f₂ [2] = min (f₁ [j – 1]  + t_{j – 1} + a_2j, f₂ [j – 1] + a_2j)

= min (f₁[1]  + t₁₁ + a₂₂, f₂ [1] + a₂₂ )

=  min (6 + 3 + 11, 8 + 11)

= min(20, 19)

= 19

f₁ [3] = min (f₁[j – 1] + a_1j, f₂ [j – 1] + t_{2j – 1}) + a_1j )

= min (f₁[2] + a₁₃, f₂ [2] + t₂₂ + a₁₃ )

= min (14 + 9, 19 + 4 + 9)

= min (23, 32)

= 23

f₂ [3] = min (f₁[j – 1] + t_{j – 1} + a_2j, f₂ [j – 1] + a_2j )

= min (f₁[2] + t₁₂ + a₂₃, f₂ [2] + a₂₃)

= min (14 + 1 + 2, 19 + 2)

= min (17, 21)

= 17

f₁ [4] = min (f₁ [j – 1] + a_1j, f₂ [j – 1] + t_{2j – 1} + a_1j )

= min (f₁ [3] + a₁₄, f₂ [3] + t₂₃ + a₁₄)

= min (23 + 3 , 17 + 1 + 3)

= min (26, 21)

= 21

f₂ [4] = min (f₁ [j – 1] + t_{j – 1} + a_2j, f₂ [j – 1] + a_2j)

= min(f₁ [3] + t₁₃ + a₂₄, f₂ [3] + a₂₄)

= min (23 + 2 + 2, 17 + 2)

= min(27, 19)

= 19

Hence we can summarize f₁[j] and f₂[j] as follows :

	j = 1	j = 2	j= 3	j = 4	j = 5	j = 6
f1[j]	6	14	23	21	24	25
f2[j]	8	17	19	26	29	29

f*    =   min (f₁ [n] + x₁, f₂ [n] + x₂)

f*    =   min (25 + 3, 29 + 7)

= min (28, 36)

= 28

Compute fastest path :

Trace back the path :

• l* = 1, so we have to select last station S_1,6 on line 1. Now we will look at l₁[6], which is 1, so we will select previous station on line 1 that is station
  S_{1, 5}.
• Now we will look at l_{1, 5} which is 2 so we will change line to 2 and previous station that is S_{2, 4}.  
• Next observe l₂[4], its 2 so we have to remain on same line and select station S_{2, 3}. Now observe l₂[3], which is 1, so move on station S_1,2 on line 1. Now observe l₁[3], which is 1, so remain on same line.
• Final path is shown in following figure:

Example: Find optimal solution for given assembly line configuration

f_i[1] = e_i + a_i1 ,      for i = 1, 2

Here, i indicates assembly line, i.e. 1 or 2,

f₁ [1] = e₁ + a₁₁ 

=  2 + 7

= 9

f₂ [1] = e₂ + a₂₁ 

= 4 + 8

= 12

For j > 1, where j indicates station numbers.

f₁ [j] = min (f₁ [j – 1] + a_1j, f₂ [j – 1] + t₂, _{j – 1} + a_1j )

f₂ [1] = min (f₁ [j – 1] + t₁, _{j – 1}   + a_2j , f₂[j – 1] + a_2j )

For j = 2 :

f₁ [2] = min (f₁ [1] + a₁₂, f₂ [1] + t₂₁ + a₁₂)

= min (9 + 9, 12 + 2 + 9)

= 18

f₂ [2] = min (f₁  [1]  + t₁₁ + a₂₂ , f₂ [1] +  a₂₂)

= min (9 + 2 + 5, 12 + 5)

= 16

For j = 3 :

f₁ [3]   =  min (f₁ [2] + a₁₃ , f₂ [2] + t₂₂ + a₁₃)

= min (18 + 3, 16 + 1 + 3)

= 20

f₂ [3]   =  min (f₁ [2] + t₁₂ + a₂₃  , f₂ [2] + a₂₃)

= min (18 + 3 + 6,  16 + 6)

= 22

For j = 4 :

f₁ (4) = min (f₁ [3] + a₁₄, f₂ [3] + t₂₃ + a₁₄)

= min (20 + 4, 22 + 2 + 4)

= 24

f₂ (4) = min (f₁ [3] + t₁₃ + a₂₄, f₂ [3] + a₂₄)

= min (20 + 1 + 4, 22 + 4)

= 25

For j = 5 :

f₁ (5) = min (f₁ [4] + a₁₅, f₂ [4] + t₂₄ + a₁₅)

= min (24 + 8, 25 + 2 + 8)

= 32

f₂ (5) = min (f₁ [4] + t₁₄ + a₂₅, f₂ [4] + a₂₅)

= min (24 + 3 + 5, 25 + 5)

= 30

For j = 6 :

f₁ (6) = min (f₁ [5] + a₁₆, f₂ [5] + t₂₅ + a₁₆)

= min (32 + 4, 30 + 1 + 4)

= 35

f₂ (6) = min (f₁ [5] + t₁₅ + a₂₆, f₂ [5] + a₂₆)

= min (32 + 4 + 7, 30 + 7)

= 37

f* =  min (f₁ (n) + x₁, f₂ (n) + x₂)

where n = number of stations  =  6

x₁ and x₂ are exit time from line 1 and line 2 respectively.

x₁ = 3,

x₂ = 2

f* = min (f₁ [6] + x₁, f₂ [6] + x₂)

= min (35 + 3, 37 + 2)

= 38

Some Popular Problems Solved using Dynamic Programming

• Binomial Coefficient
• Making a Change
• Knapsack Problem
• Multistate Graph Problem
• Optimal Binary Search Tree
• Matrix Chain Multiplication
• Longest Common Subsequence
• Bellman-Ford (Single Source Shortest Path) Algorithm
• Floyd-Warshall (All Pair Shortest Path) Problem
• Assembly Line Scheduling
• Travelling Salseman Problem
• Flow Shop Scheduling

---

Additional Reading: Read More