Dynamic Programming is an important concept in DSA and many of its problems are quite interesting to solve. Today we are going to take a look at one such problem called as the "**Assembly Line Scheduling Problem**".

## Problem Description

**Sij**where i denotes the assembly line the station is on and j denotes the number of the station. The time taken per station is denoted by

**aij**. Each station is dedicated to do some sort of work in the manufacturing process. So, a car must pass through each of the n stations in order before exiting the company. The parallel stations of the two assembly lines perform the same task. After it passes through station Sij , it will continue to station Si,j+1 unless it decides to transfer to the other line. Continuing on the same line incurs no extra cost, but transferring from line i at station j − 1 to station j on the other line takes time

**tij**. Each assembly line takes an entry time

**ei**and exit time

**xi**. Our task here is to develop an algorithm for computing the minimum time from start to exit.

## Approach

In this problem we need to start from one of the assembly lines and then at each point we have two options whether to switch to other assembly line or stay on the same line. Thus, basically if we are at a particular station say Sij then we can determine the time taken by simply adding aij to the previous station cost. This approach seems similar to the recursive technique used in Fibonacci numbers problem. Indeed we shall be using recursion here and with the concept of **Dynamic Programming**, we will optimize our recursive solution so that it requires lesser time complexity.

## Recursive Solution

### Optimal Substructure:

To develop an optimal recursive substructure, we need to break the given problem into smaller sub-problems. In the given problem, if we know the minimum time taken by the car to leave station
Si,j−1, then the minimum time taken to leave station Si,j can be calculated easily by combining ai,j and
ti,j. This serves as our optimal substructure for the problem.

#### Final Solution:

**f ^{final} = min{ f1[n] + x1, f2[n] + x2 }**

Where f1[n] and f2[n] denote fastest times from start to last station on line 1 and 2 respectively, and x1, x2 represent the exit times on lines 1 and 2 respectively.

### Base Case:

** **The entry times e1, e2 comes into picture only when the car enters the car factory. Thus, time to leave station 1 on both lines serves as our base case:

f1[1] = e1 + a11

f2[1] = e2 + a21

### Solution:

The car at station S1j can come either from station S1,j−1 or station S2,j−1 (Since, the tasks done by both S1j and S2j are same). But if the chassis comes from S2,j−1, it additionally incurs the transfer cost for changing the assembly line. Thus, the recursion relation to reach the station j in assembly line i can be obtained as follows:

f1[j] = e1 + a11 **{if j = 1}**

min(f1[j−1]+a1j, f2[j−1]+t2, j−1+a1j) **{if j ≥ 2}**

f2[j] = e2 + a21 **{if j = 1}**

min(f2[j−1]+a2j, f1[j−1]+t1, j−1+a2j) **{if j ≥ 2}**

## Dynamic Solution

The above recursive solution can be used to solve the problem but the only issue here is that there is an overlap of the subproblems that we have divided our main problem into. To solve this issue, we use Dynamic Programming and use an extra table to solve the overlapping problem.

### Why use Dynamic Programming?

The above recursive relations show overlapping of sub-problems. Let us understand how the overlap occurs:

Suppose we want to reach a station S1j. In our factory set up, we have two ways to do so:

- Reach station S1j from S1,j-1 (same assembly line).
- Reach station S1j from S2,j-1 (switch from second assembly line).

Since, there are two ways to reach station S1,j , the minimum time to **leave **station S1,j can be calculated by
finding the minimum time to leave the previous two stations, S1,j−1 and S2,j−1 and then combining it with the time spent on station S1,j i.e. a1,j. At each station we have two options and if we go in a recursive manner, we would have to check for both of these solutions thus the total solutions would reach an exponential value of **2 ^{n}**. The following diagram clearly shows that the recursive solution has a large number of overlapping subproblems.

We can calculate the leaving time of previous stations using recursive relations. Thus, we need two tables to store the partial results that are calculated for each station in an assembly line. The table will be filled in a bottom-up fashion.

### Pseudocode

assembly()

Declare := T1[n], T2[n]

T1[0] := e1 + a11

T2[0] := e2 + a21

for i in 1 to n, do

T1[i] := minimum(T1[i-1] + a[0][i],
T2[i-1] + t[1][i] + a[0][i])

T2[i] := minimum(T2[i-1] + a[1][i],
T1[i-1] + t[0][i] + a[1][i])

return minimum(T1[n - 1] + x1,
T2[n- 1] + x2)

In the aboce pseudocode, we first initialize two arrays for storing the time taken to reach each station in a given assembly line. The first value of each array is initialized with our base case, i.e. the entry time(**e1/e2**) and the time spent at first station(**a11/a21**). Then we loop through all the remaining stations from `1 to n`

and for each station we compute the time taken to leave from that station with the help of the timings for previous station. For example `T1[i]`

stores the minimum time taken if-

- We reach it from same line by adding the previous time in the same line(
`T1[i-1]`

) and the time spent in the current station(`a[0][i]`

), OR - We reach it by switching our assembly line by adding the time in the same line(
`T2[i-1]`

), plus the additional time spent in switching lanes(`t[1][i]`

) and the time spent in the current station(`a[1][i]`

)

Similarly we compute the time taken to reach and leave a particular station for all stations in both assembly lines and at last we select the minimum time out of the time for leaving last station(**Ti[n-1]**) plus the exit time(**xi**). Let us understand with an example:

a = [[5,4,3], [2,3,7]], t = [[0,2,2], [0,1,1]]

e1 = 3, e2 = 2

x1 = 3, x2 = 4

T1[0] = e1 + a[0][0] = 3+5 = 8

T2[0] = e2 + a[0][1] = 2+2 = 4

**T1 = [8, 0, 0] T2 = [4, 0, 0]**

i = 1

T1[1] = min(T1[1-1] + a[0][1], T2[1-1] + t[1][1] + a[0][1])

= min(8+4, 4+1+4) = min(12,9)

**T1[1] = 9**

T2[1] = min(T2[1-1] + a[1][1], T1[1-1] + t[0][1] + a[1][1])

= min(4+3, 8+2+3) = min(7,13)**T2[1] = 7**

**T1 = [8, 9, 0] T2 = [4, 7, 0]**

i = 2

T1[2] = min(T1[2-1] + a[0][2], T2[2-1] + t[1][2] + a[0][2])

= min(9+3, 7+1+3) = min(12,11)**T1[2] = 11**

T2[2] = min(T2[2-1] + a[1][2], T1[2-1] + t[0][2] + a[1][2])** **= min(7+7, 9+2+4) = min(14,15)**T2[2] = 14**

**T1 = [8, 9, 11] T2 = [4, 7, 14]**

**ans = min(T1[n-1]+x1, T2[n-1]+x2)** = min(11+3, 14+4) = min(14, 18)

**ans = 14**

Thus, the minimum time taken for a car from start to end of the assembly unit is 14.

- C/C++
- Java
- Python

```
import java.io.*;
class CarAssembly
{
static int n = 3;
static int min(int a, int b)
{
return a < b ? a : b;
}
static int assembly(int a[][], int t[][], int e[], int x[])
{
int T1[]= new int [n];
int T2[] =new int[n] ;
int i;
// adding base case times
T1[0] = e[0] + a[0][0];
T2[0] = e[1] + a[1][0];
// Filling the dp tables T1[] and T2[] using recursive relations
for (i = 1; i < n; i++)
{
T1[i] = min(T1[i - 1] + a[0][i], T2[i - 1] + t[1][i] + a[0][i]);
T2[i] = min(T2[i - 1] + a[1][i], T1[i - 1] + t[0][i] + a[1][i]);
}
// finding final times and returning the minimum value
return min(T1[n-1] + x[0],
T2[n-1] + x[1]);
}
// Driver code
public static void main (String[] args)
{
int a[][] = {{5, 4, 3}, {2, 3, 7}};
int t[][] = {{0, 2, 2}, {0, 1, 1}};
int e[] = {3, 2}, x[] = {3, 4};
System.out.println("The minimum time taken is: "+assembly(a, t, e, x));
}
}
```

Output:

The minimum time taken is: 14

## Complexity Analysis

Approach | Time Complexity | Space Complexity |
---|---|---|

Dynamic Programming | O(n) | O(n) |

In the above program if we solely use the recursive solution, it becomes quite hectic as for each substation, you need to recursively find its previous stations time and for each station there are two ways to reach it. All this makes it an exponentially grwoing slution with **O(2 ^{n}) **time complexity.

On the other hand if we simply store the previous stations time value in an array, we don't need to find it again. Thus, we can see that by dynamic programming approach we can reduce the time complexity significantly to** O(n) **at the cost of additional space complexity of **O(n)**.

In this way, we have seen the dynamic programming approach to solve the famous "**Assembly line Scheduling**" problem.