Assembly Line Scheduling using Dynamic Programming

«
»

This is a C++ Program that Solves Assembly Line Scheduling Problem using Dynamic Programming technique.

Problem Description

There are two assembly lines. Each assembly line has n stations.
Every station has some dedicated job that needs to done. For a station number i, you can get the job done on station number i of any assembly line.
You can go to station i only when you have been through station i-1.
From a station i, you can either go to the next station on the same line or you can transfer assebly line.

Information provided –
time to enter station 1 on both assembly lines
time to exit last station on both lines
job processing time for every station
The time to transfer from each station of assembly line 1 to next station of assembly line 2 is given
The time to transfer from each station of assembly line 2 to next station of assembly line 1

Objective of the problem is to finish all the jobs in minimum time.

Problem Solution

Create a matrix dp[2][n+1]. dp[i][j]=min. time to finish all the jobs currently being on assembly line i and station j.
dp[0][0]=entry time for assembly line 1 + processing time for station 1 on line 1
dp[1][0]=entry time for assembly line 2 + processing time for station 1 on line 2

Then fill the matrix for all n station. At the end, simply add the exiting time for respective assebly lines and return the minimum value.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
Expected Input and Output

Case-1:

No. of stations - 3
Entry time for station 1 on assebly lines 1 and 2 respectively - 3,1
Exit time from last station on assebly lines 1 and 2 respectively - 3,3
processing time for stations on assembly line 1 - 8, 4, 6
processing time for stations on assembly line 2 - 5, 7, 5
transfer times from a station on assebly line 1 to next station on assembly line 2 - 2, 2
transfer times from a station on assebly line 2 to next station on assembly line 1 - 1, 3
 
Minimum time to get all the jobs done is - 20 (1+5+1+4+6+3)
Program/Source Code

Here is source code of the C++ Program to Solve Assembly Line Scheduling Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4.  
  5. int assemblyLineScheduling(int n, vector<int> entry, vector<int> exit, vector<vector<int> > processing, vector<vector<int> > transfer)
  6. {
  7.     vector<vector<int> > dp(2, vector<int>(n+1));
  8.     int i;
  9.  
  10.     //initialization
  11.     //entry to first station
  12.     dp[0][0]=entry[0]+processing[0][0];
  13.     dp[1][0]=entry[1]+processing[1][0];
  14.  
  15.     for(i=1;i<n;i++)
  16.     {
  17.         //for being on station i of assembly line 1
  18.         dp[0][i]=min(dp[0][i-1],dp[1][i-1]+transfer[1][i-1])+processing[0][i]; 
  19.  
  20.         //for being on station i of assembly line 2
  21.         dp[1][i]=min(dp[1][i-1],dp[0][i-1]+transfer[0][i-1])+processing[1][i]; 
  22.     }
  23.  
  24.     //exiting from the last station
  25.     dp[0][n]=dp[0][n-1]+exit[0];
  26.     dp[1][n]=dp[1][n-1]+exit[1];
  27.  
  28.     return min(dp[0][n],dp[1][n]);
  29. }
  30.  
  31. int main()
  32. {
  33.     int i,n;
  34.     vector<int> entry(2), exit(2);
  35.  
  36.     cout<<"Enter the number of stations ";
  37.     cin>>n;
  38.  
  39.     vector<vector<int> > processing(2, vector<int> (n));
  40.     vector<vector<int> > transfer(2, vector<int> (n-1));
  41.  
  42.     cout<<"Enter the entry time for assebly line 1 and 2 respectively"<<endl;
  43.     cin>>entry[0]>>entry[1];
  44.  
  45.  
  46.     cout<<"Enter the exit time for assebly line 1 and 2 respectively"<<endl;
  47.     cin>>exit[0]>>exit[1];
  48.  
  49.     cout<<"Entry the processing time at all staions on assembly line 1"<<endl;
  50.     for(i=0;i<n;i++)
  51.         cin>>processing[0][i];
  52.  
  53.     cout<<"Entry the processing time at all staions on assembly line 2"<<endl;
  54.     for(i=0;i<n;i++)
  55.         cin>>processing[1][i];
  56.  
  57.     cout<<"Enter the transfer time from each station of assembly line 1 to next station of assembly line 2"<<endl;
  58.     for(i=0;i<n-1;i++)
  59.         cin>>transfer[0][i];
  60.  
  61.     cout<<"Enter the transfer time from each station of assembly line 2 to next station of assembly line 1"<<endl;
  62.     for(i=0;i<n-1;i++)
  63.         cin>>transfer[1][i];
  64.  
  65.     cout<<"The minimum time required to get all the jobs done is "<<endl;
  66.     cout<<assemblyLineScheduling(n, entry, exit, processing, transfer);
  67.  
  68.  
  69.     cout<<endl;
  70.     return 0;
  71. }
Program Explanation

In the main function, we ask the user to input the values for number of stations, entry and exit time of both assembly lines and processing and transfer time for all stations. We pass these values to the function assemblyLineScheduling as parameters. This function will calculate the expected result and return it. The returned value will be displayed.

Runtime Test Cases
 
Case-1:
$ g++ assembly_line.cpp
$ ./a.out
Enter the number of stations 3
Enter the entry time for assebly line 1 and 2 respectively
3 1
Enter the exit time for assebly line 1 and 2 respectively
3 3
Entry the processing time at all staions on assembly line 1
8 4 6
Entry the processing time at all staions on assembly line 2
5 7 5
Enter the transfer time from each station of assebly line 1 to next station of assembly line 2
2 2
Enter the transfer time from each station of assebly line 2 to next station of assembly line 1
1 3
The minimum time required to get all the jobs done is 
20

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

advertisement

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.