Dynamic Programming | Set 34 (Assembly Line Scheduling) | GeeksforGeeks

A car factory has two assembly lines, each with n stations. A station is denoted by S_i,j where i is either 1 or 2 and indicates the assembly line the station is on, and j indicates the number of the station. The time taken per station is denoted by a_i,j. Each station is dedicated to some sort of work like engine fitting, body fitting, painting and so on. So, a car chassis must pass through each of the n stations in order before exiting the factory. The parallel stations of the two assembly lines perform the same task. After it passes through station S_i,j, it will continue to station S_i,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 t_i,j. Each assembly line takes an entry time e_i and exit time x_i which may be different for the two lines. Give an algorithm for computing the minimum time it will take to build a car chassis.

T1(j) indicates the minimum time taken by the car chassis to leave station j on assembly line 1.

T2(j) indicates the minimum time taken by the car chassis to leave station j on assembly line 2.

The minimum time T1(j) is given by the minimum of the two obtained in cases #1 and #2.
T1(j) = min((T1(j-1) + a_{1, j}), (T2(j-1) + t_{2, j} + a_{1, j}))
Similarly the minimum time to reach station S2, j is given by:
T2(j) = min((T2(j-1) + a_{2, j}), (T1(j-1) + t_{1, j} + a_{2, j}))

int carAssembly(int a[][NUM_STATION], int t[][NUM_STATION], int *e, int *x)

{

    int T1[NUM_STATION], T2[NUM_STATION], i;

    T1[0] = e[0] + a[0][0]; // time taken to leave first station in line 1

    T2[0] = e[1] + a[1][0]; // time taken to leave first station in line 2

    // Fill tables T1[] and T2[] using the above given recursive relations

    for (i = 1; i < NUM_STATION; ++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]);

    }

    // Consider exit times and retutn minimum

    return min(T1[NUM_STATION-1] + x[0], T2[NUM_STATION-1] + x[1]);

}

Read full article from Dynamic Programming | Set 34 (Assembly Line Scheduling) | GeeksforGeeks