Assembly Line Scheduling

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.

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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

```
#include<iostream>
```
```
#include<vector>
```
```
using namespace std;
```
```
 
```

int assemblyLineScheduling(int n, vector<int> entry, vector<int> exit, vector<vector<int> > processing, vector<vector<int> > transfer)

```
{
```

    vector<vector<int> > dp(2, vector<int>(n+1));

```
    int i;
```
```
 
```
```
    //initialization
```
```
    //entry to first station
```
```
    dp[0][0]=entry[0]+processing[0][0];
```
```
    dp[1][0]=entry[1]+processing[1][0];
```
```
 
```
```
    for(i=1;i<n;i++)
```
```
    {
```

        //for being on station i of assembly line 1

        dp[0][i]=min(dp[0][i-1],dp[1][i-1]+transfer[1][i-1])+processing[0][i];

```
 
```

        //for being on station i of assembly line 2

        dp[1][i]=min(dp[1][i-1],dp[0][i-1]+transfer[0][i-1])+processing[1][i];

```
    }
```
```
 
```
```
    //exiting from the last station
```
```
    dp[0][n]=dp[0][n-1]+exit[0];
```
```
    dp[1][n]=dp[1][n-1]+exit[1];
```
```
 
```
```
    return min(dp[0][n],dp[1][n]);
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int i,n;
```
```
    vector<int> entry(2), exit(2);
```
```
 
```

    cout<<"Enter the number of stations ";

```
    cin>>n;
```
```
 
```

    vector<vector<int> > processing(2, vector<int> (n));

    vector<vector<int> > transfer(2, vector<int> (n-1));

```
 
```

    cout<<"Enter the entry time for assebly line 1 and 2 respectively"<<endl;

```
    cin>>entry[0]>>entry[1];
```
```
 
```
```
 
```

    cout<<"Enter the exit time for assebly line 1 and 2 respectively"<<endl;

```
    cin>>exit[0]>>exit[1];
```
```
 
```

    cout<<"Entry the processing time at all staions on assembly line 1"<<endl;

```
    for(i=0;i<n;i++)
```
```
        cin>>processing[0][i];
```
```
 
```

    cout<<"Entry the processing time at all staions on assembly line 2"<<endl;

```
    for(i=0;i<n;i++)
```
```
        cin>>processing[1][i];
```
```
 
```

    cout<<"Enter the transfer time from each station of assembly line 1 to next station of assembly line 2"<<endl;

```
    for(i=0;i<n-1;i++)
```
```
        cin>>transfer[0][i];
```
```
 
```

    cout<<"Enter the transfer time from each station of assembly line 2 to next station of assembly line 1"<<endl;

```
    for(i=0;i<n-1;i++)
```
```
        cin>>transfer[1][i];
```
```
 
```

    cout<<"The minimum time required to get all the jobs done is "<<endl;

    cout<<assemblyLineScheduling(n, entry, exit, processing, transfer);

```
 
```
```
 
```
```
    cout<<endl;
```
```
    return 0;
```
```
}
```

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.

If you find any mistake above, kindly email to [email protected]

« Prev - Weighted Activity Selection using Dynamic Programming

» Next - Dynamic Programming Solutions – Balanced Partition Problem

Related Posts:

Apply for Computer Science Internship
Check Computer Science Books
Check Data Structure Books
Practice Design & Analysis of Algorithms MCQ
Practice Programming MCQs

Recommended Articles: