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 2n possible ways to choose stations. Brute force attack takes O(2n) 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 :
• Sij = Station j on assembly line i.
• aij = Time needed to assemble the partial component at station j on assembly line i.
• tij  = Time required to transfer component from one assembly to other from station j to (j + 1).
• ei = Entry time on assembly line i.
• xi = 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.

fi [j]    =   ei + ai1 ; 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 :

f1[j] = min (f1 [j – 1] + a1, f2 [j – 1] + t2 j – 1 + a1j )

f2[j] = min (f1 [j – 1] + t1 j – 1 + a2j, f2 [j – 1] + a2j )

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

f*    =   min (f1 [n] + x1, f2 [n] + x2)

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:

fi [j] = ei + ai,1; Initial condition (j = 1, i=1, 2)

f1 [j] = min (f1 [j – 1] + a1j, f2 [j – 1] + t2 j – 1) + a1j)

f2 [j] = min (f1 [j – 1] + t1 j – 1) + a2j, f2 [j – 1] + a2j )

f*  = min (f1 [n] + x1, f2 [n]+x2 )

f1 [1] = e1 + a11

= 4 + 2

= 6

f2 [1]  = e2 + a21

= 2 + 6

= 8

f1 [2] = min (f1[j – 1] + a1j, f2 [j – 1] + t2j – 1+ a1j )

= min (f1 [1] + a12, f2 [1] + t21 + a12

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

= min (14, 19)

= 14

f2 [2] = min (f1 [j – 1]  + tj – 1 + a2j, f2 [j – 1] + a2j)

= min (f1[1]  + t11 + a22, f2 [1] + a22 )

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

= min(20, 19)

= 19

f1 [3] = min (f1[j – 1] + a1j, f2 [j – 1] + t2j – 1) + a1j )

= min (f1[2] + a13, f2 [2] + t22 + a13 )

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

= min (23, 32)

= 23

f2 [3] = min (f1[j – 1] + tj – 1 + a2j, f2 [j – 1] + a2j )

= min (f1[2] + t12 + a23, f2 [2] + a23)

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

= min (17, 21)

= 17

f1 [4] = min (f1 [j – 1] + a1j, f2 [j – 1] + t2j – 1 + a1j )

= min (f1 [3] + a14, f2 [3] + t23 + a14)

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

= min (26, 21)

= 21

f2 [4] = min (f1 [j – 1] + tj – 1 + a2j, f2 [j – 1] + a2j)

= min(f1 [3] + t13 + a24, f2 [3] + a24)

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

= min(27, 19)

= 19

Hence we can summarize f1[j] and f2[j] as follows :

f*    =   min (f1 [n] + x1, f2 [n] + x2)

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 S1,6 on line 1. Now we will look at l1[6], which is 1, so we will select previous station on line 1 that is station
S1, 5.
• Now we will look at l1, 5 which is 2 so we will change line to 2 and previous station that is S2, 4.
• Next observe l2[4], its 2 so we have to remain on same line and select station S2, 3. Now observe l2[3], which is 1, so move on station S1,2 on line 1. Now observe l1[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

fi[1] = ei + ai1 ,      for i = 1, 2

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

f1 [1] = e1 + a11

=  2 + 7

= 9

f2 [1] = e2 + a21

= 4 + 8

= 12

For j > 1, where j indicates station numbers.

f1 [j] = min (f1 [j – 1] + a1j, f2 [j – 1] + t2, j – 1 + a1j )

f2 [1] = min (f1 [j – 1] + t1, j – 1   + a2j , f2[j – 1] + a2j )

For j = 2 :

f1 [2] = min (f1 [1] + a12, f2 [1] + t21 + a12)

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

= 18

f2 [2] = min (f[1]  + t11 + a22 , f2 [1] +  a22)

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

= 16

For j = 3 :

f1 [3]   =  min (f1 [2] + a13 , f2 [2] + t22 + a13)

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

= 20

f2 [3]   =  min (f1 [2] + t12 + a23  , f2 [2] + a23)

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

= 22

For j = 4 :

f1 (4) = min (f1 [3] + a14, f2 [3] + t23 + a14)

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

= 24

f2 (4) = min (f1 [3] + t13 + a24, f2 [3] + a24)

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

= 25

For j = 5 :

f1 (5) = min (f1 [4] + a15, f2 [4] + t24 + a15)

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

= 32

f2 (5) = min (f1 [4] + t14 + a25, f2 [4] + a25)

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

= 30

For j = 6 :

f1 (6) = min (f1 [5] + a16, f2 [5] + t25 + a16)

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

= 35

f2 (6) = min (f1 [5] + t15 + a26, f2 [5] + a26)

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

= 37

f* =  min (f1 (n) + x1, f2 (n) + x2)

where n = number of stations  =  6

x1 and x2 are exit time from line 1 and line 2 respectively.

x1 = 3,

x2 = 2

f* = min (f1 [6] + x1, f2 [6] + x2)

= min (35 + 3, 37 + 2)

= 38