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[]andexit[]arrays represent the time of entry and time of exit to the assembly lines respectively, such thatentry[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], whereiis the assembly line number andjis 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], whereiis the current assembly line number andjis 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.