Sarbojit Basu
24BAI0187
Assignment 2
Problem statement:
A manufacturing company has two assembly lines, each with n stations. A station is denoted by Si,j
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 ai,j . Each station is dedicated to do some sort of work in the
manufacturing process. So, a chassis 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 Si,j , 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 ti,j . Each assembly line takes an entry time ei and exit time xi . Give an
algorithm for computing the minimum time from start to exit. Implement a C program, and all the
inputs like line number, number of stations, entry times, exit times, time taken per station, and
transfer times will be taken from user.
Concept:
This problem is solved using dynamic programming because the minimum time to reach a station
depends on the minimum times to reach the previous station on both lines. At each station, the
chassis has two choices: stay on the same line or transfer from the other line, each with a known
cost. By computing the minimum time step by step for each station and each line, and storing
intermediate results, we avoid redundant calculations. Finally, we add the exit times and choose the
smaller value, which gives the minimum total time from entry to exit.
Pseudocode:
Algorithm AssemblyLineScheduling
Input:
n ← number of stations
e1, e2 ← entry times for line 1 and line 2
x1, x2 ← exit times for line 1 and line 2
a[i][j] ← processing time at station j on line i
t[i][j] ← transfer time from other line to line i at station j
Output:
Minimum time to exit the assembly line
Begin
// Step 1: Initialization
T1[0] ← e1 + a[1][0]
Sarbojit Basu
24BAI0187
T2[0] ← e2 + a[2][0]
for j ← 1 to n − 1 do
T1[j] ← min(
T1[j − 1] + a[1][j],
T2[j − 1] + t[2][j] + a[1][j]
T2[j] ← min(
T2[j − 1] + a[2][j],
T1[j − 1] + t[1][j] + a[2][j]
end for
answer ← min(T1[n − 1] + x1, T2[n − 1] + x2)
print answer
End
Code:
#include <stdio.h>
int min(int a, int b) {
return (a < b) ? a : b;
int main() {
int n;
int e[2], x[2];
int a[2][100], t[2][100];
int T1[100], T2[100];
printf("Enter number of stations: ");
scanf("%d", &n);
Sarbojit Basu
24BAI0187
printf("Enter entry times for line 1 and line 2: ");
scanf("%d %d", &e[0], &e[1]);
printf("Enter exit times for line 1 and line 2: ");
scanf("%d %d", &x[0], &x[1]);
printf("\nEnter station times:\n");
for (int i = 0; i < 2; i++) {
printf("Line %d:\n", i + 1);
for (int j = 0; j < n; j++) {
scanf("%d", &a[i][j]);
printf("\nEnter transfer times:\n");
printf("From line 1 to line 2:\n");
for (int j = 1; j < n; j++) {
scanf("%d", &t[0][j]);
printf("From line 2 to line 1:\n");
for (int j = 1; j < n; j++) {
scanf("%d", &t[1][j]);
T1[0] = e[0] + a[0][0];
T2[0] = e[1] + a[1][0];
for (int j = 1; j < n; j++) {
T1[j] = min(
T1[j - 1] + a[0][j],
T2[j - 1] + t[1][j] + a[0][j]
Sarbojit Basu
24BAI0187
);
T2[j] = min(
T2[j - 1] + a[1][j],
T1[j - 1] + t[0][j] + a[1][j]
);
int result = min(T1[n - 1] + x[0], T2[n - 1] + x[1]);
printf("\nMinimum time to exit the assembly line = %d\n", result);
return 0;
Output:
Sarbojit Basu
24BAI0187
Time complexity analysis:
The time complexity of the assembly line scheduling program is O(n), where n is the number of
stations. This is because the dynamic programming computation processes each station exactly once,
and at every station only a constant number of operations are performed, such as comparisons and
additions. The input reading loops also take linear time with respect to the number of stations, which
does not change the overall complexity. Since no nested loops depend on n in the computation
phase, the total time complexity remains linear.