# Assembly-Line Scheduling

Assembly line scheduling is a classic problem in production optimization, often encountered in manufacturing industries. The objective is to schedule tasks along multiple assembly lines to minimize the overall production time or cost. This problem is discussed in the book “Introduction to Algorithms” by Thomas H. Cormen et al.

Problem

Imagine a manufacturing plant with two assembly lines, each consisting of several stations. Parts move through these stations, undergoing various operations, before completing the assembly process. The goal is to schedule the tasks efficiently, minimizing the total time or cost required for production.

The problem involves:

• Identifying the sequence of stations to be visited on each assembly line.
• Determining the time associated with moving between stations & assembly lines and cost for performing operations at the station of a particular assembly line.

#### Approach

The problem can be solved efficiently using dynamic programming. Here’s the dynamic programming approach.

Pseudocode

1. Initialization
Initialize two arrays, f1 and f2, to store the fastest time/cost to reach each station on the first and second assembly lines, respectively.

Initialize f1[0] = entry[0] + cost[0][0] and f2[0] = entry[1] + cost[1][0] as the base cases.

2. Optimal substructure
For each station i from i = 1 to n-1:
Update f1[i] as min(f1[i - 1] + cost[0][i], f2[i - 1] + time[1][i] + cost[0][i]).
Update f2[i] as min(f2[i - 1] + cost[1][i], f1[i - 1] + time[0][i] + cost[1][i]).

3. Final solution
The minimum time to complete the assembly process is min(f1[n - 1] + exit[0], f2[n - 1] + exit[1]).

Example

Consider the following instance of the assembly line problem:

Some important points regarding the problem:

• entry[] and exit[]arrays represent the time of entry and time of exit to the assembly lines respectively, such that entry[0], entry[1] is entry time for assembly line 1 and 2 resp.
• There is a specific cost for performing operations at a particular station of a particular assembly line, represented by cost[i][j], where i is the assembly line number and j is the station number.
• There is no time cost associated with moving between stations on the same assembly line.
• There is a specific time cost associated with moving between stations on two different assembly lines, represented as time[i][j], where i is the current assembly line number and j is the current station number.

Consider the following parameters, as shown in the image above:

Input

entry[] = {10, 12}
exit[] = {18, 7}

cost[][] = {{4, 5, 3, 2}, {3, 10, 1, 4}}
time = {{0, 7, 4, 5}, {0, 9, 2, 8}}

Computations

Base cases
f1[0] = entry[0] + cost[0][0] = 10 + 4 = 14
f2[0] = entry[1] + cost[1][0] = 12 + 3 = 15

Iterations:

for i = 1
f1[1] = min(f1[0] + cost[0][1], f2[0] + time[1][1] + cost[0][1]) = min(14 + 5, 15 + 9 + 5) = min(19, 29) = 19
f2[1] = min(f2[0] + cost[1][1], f1[0] + time[0][1] + cost[1][1]) = min(15 + 10, 14 + 7 + 10) = min(25, 31) = 25

for i = 2:
f1[2] = min(f1[1] + cost[0][2], f2[1] + time[1][2] + cost[0][2]) = min(19 + 3, 25 + 2 + 3) = min(22, 30) = 22
f2[2] = min(f2[1] + cost[1][2], f1[1] + time[0][2] + cost[1][2]) = min(25 + 1, 19 + 4 + 1) = min(26, 24) = 24

for i = 3:
f1[3] = min(f1[2] + cost[0][3], f2[2] + time[1][3] + cost[0][3]) = min(22 + 2, 24 + 8 + 2) = min(24, 34) = 24
f2[3] = min(f2[2] + cost[1][3], f1[2] + time[0][3] + cost[1][3]) = min(24 + 4, 22 + 5 + 4) = min(28, 31) = 28

Minimum time for assembly = min(f1[3] + exit[0], f2[3] + exit[1]) = min(24 + 18, 28 + 7) = min(42, 35) = 35

Code Implementation

//
//  main.cpp
//  Assembly Line Scheduling
//
//  Created by Himanshu on 04/03/24.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

void printStations(const vector<int>& stations, const vector<string>& lines) {
cout << "Optimal Schedule:" << endl;
cout << "Station  Assembly Line" << endl;
for (int i = 0; i < stations.size(); ++i) {
cout << "   " << i + 1 << "        " << lines[stations[i] - 1] << endl;
}
}

void assemblyLineScheduling(const vector<vector<int>>& cost, const vector<vector<int>>& time,
const vector<int>& entry, const vector<int>& exit) {
int n = (int) cost[0].size();
vector<int> f1(n), f2(n), s1(n), s2(n);

// Base cases
f1[0] = entry[0] + cost[0][0];
f2[0] = entry[1] + cost[1][0];

// Dynamic programming – Optimal Substructure
for (int i = 1; i < n; ++i) {
// For the first assembly line
f1[i] = min(f1[i - 1] + cost[0][i], f2[i - 1] + time[1][i] + cost[0][i]);
s1[i] = (f1[i - 1] + cost[0][i] < f2[i - 1] + time[1][i] + cost[0][i]) ? 1 : 2;

// For the second assembly line
f2[i] = min(f2[i - 1] + cost[1][i], f1[i - 1] + time[0][i] + cost[1][i]);
s2[i] = (f2[i - 1] + cost[1][i] < f1[i - 1] + time[0][i] + + cost[1][i]) ? 2 : 1;
}

// Determine the minimum time/cost
int minCost = min(f1[n - 1] + exit[0], f2[n - 1] + exit[1]);
cout << "Minimum Time: " << minCost << endl << endl;

// Determine the assembly line selected at each station
vector<int> stations(n);
stations[n - 1] = (f1[n - 1] + exit[0] < f2[n - 1] + exit[1]) ? 1 : 2;
for (int i = n - 2; i >= 0; --i) {
stations[i] = (stations[i + 1] == 1) ? s1[i + 1] : s2[i + 1];
}

// Print the stations and assembly lines selected
vector<string> lines = {"Line 1", "Line 2"};
printStations(stations, lines);
}

int main() {
// Example usage
vector<vector<int>> cost = {{4, 5, 3, 2}, {3, 10, 1, 4}};
vector<vector<int>> time = {{0, 7, 4, 5}, {0, 9, 2, 8}}; //first value is 0 for base case
vector<int> entry = {10, 12};
vector<int> exit = {18, 7};

assemblyLineScheduling(cost, time, entry, exit);

return 0;
}


Output

Minimum Time: 35

Optimal Schedule:
Station  Assembly Line
1        Line 1
2        Line 1
3        Line 2
4        Line 2

Time complexity: O(n)

The assembly line scheduling problem is a classic example of dynamic programming application in optimization.