Assembly Line Scheduling

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

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:

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:

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:

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:

1.  Reach station S1j from S1,j-1 (same assembly line).
   
2.  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ⁿ. 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

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:

#include <iostream>
using namespace std;
#define n 3

int min(int a, int b)
{ 
	return a < b ? a : b; 
} 

int assembly(int a[][n],	int t[][n], int *e, int *x) 
{ 
	int T1[n], T2[n], 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
int main() 
{ 
	int a[][n] = {{5, 4, 3}, {2, 3, 7}}; 
	int t[][n] = {{0, 2, 2}, {0, 1, 1}}; 
	int e[] = {3, 2}, x[] = {3, 4}; 

	cout<<"The minimum time taken is: "<<assembly(a, t, e, x); 

	return 0; 
} 

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)); 
	
	}
}

def assembly(a, t, e, x):
     
    n = len(a[0])
    T1 = [0 for i in range(n)]
    T2 = [0 for i in range(n)]
     
    # 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 in range(1, n):
        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
a = [ [ 5, 4, 3 ], [ 2, 3, 7 ] ] 
t = [ [ 0, 2, 2 ], [ 0, 1, 1 ] ]
e = [ 3, 2 ] 
x = [ 3, 4 ] 
print("The minimum time taken is:",assembly(a,t,e,x))

Output:

Complexity Analysis

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ⁿ) 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.