I wanted to take a minute to help some users become more familiar with Dynamic Programming, so I decided to write a script on the Assembly Line Scheduling Problem.

To introduce the problem I want to tell you a story about a friend of mine. Keisha recently started a clothing company that uses two assembly lines to produce articles of clothing. She has separated the the process of manufacturing an item of clothing into n steps, so each assembly line is separated into n different stations, with each station performing a specific task (So for example station three’s job may be to add a right sleeve to shirts). The task of a specific station is independent of which line the station occurs on (so if station three’s job is to add a right sleeve to shirts, this will be true in both assembly line 1 and assembly line 2). Lets denote the j^th station (with j = 1, 2, …, n) on line i (where i is 1 or 2) by S_{i, j}. Although they’re doing the same jobs the time it takes the employee at station S_{1, j} may be different from the time it takes the employee at station S_{2, j}. We will denote the time required at station S_{i, j} by a_{i, j}. For each line, there is also an amount of time required for the article of clothing to enter assembly line i, e_i; and an amount of time required for the article of clothing to exit assembly line i, x_i.

One of the reasons that assembly lines are very productive is that stations on the same assembly line are generally in close proximity to one another, resulting in a very low cost of transferring an item from one station to the next on the same assembly line. When we have multiple lines in place, as Keisha has, there is a (possibly beneficial) cost of transferring an item from one line to another. Lets denote this cost by t_{i, j} which represents the cost of transferring a partially completed item of clothing from line i after having gone through station S_{i, j} (again, i is 1 or 2 and j = 1, 2, …, n).

The problem that Keisha would like solved is to determine which station to choose between lines 1 and 2 in order to minimize the total time it takes to produce an article of clothing.

Consider the following example:

Our goal is to get the clothing through the 3 states to produce a final product. What if we initially had the product take the route through station S_{2, 1} instead of station S_{1, 1}? Lets assume that we make the decisions to send the article of clothing to stations S_{2, 2} and S_{2, 3} afterwards. This would result in a solution whose total cost is 3 + 8 + 4 + 6 + 3 = 24. Is this solution optimal (aka is this solution the minimum total time through the factory)? Lets consider what would happen if we had chosen station S_{1, 1} instead of S_{2, 1}. The entry cost for line 1 is 1, the time required at station S_{1, 1} is 5 and the transfer time to go to assembly line 2 is 1. So the cost of this new solution is 1 + 5 + 1 + 4 + 6 + 3 = 20, which gives a cheaper solution.

This is called the principle of optimality (optimal substructure property) which states that in order for an overall solution to be optimal, the solution must also give the optimal solutions to every subproblem of the original problem. This problem of solving all subproblems may seem like a daunting task at first, but lets consider the example above again.

Initially, we have a new product and there are two options – either line one or line two. We will need these values in the future, so lets keep track of both choices in the form of a table.

After this initial step, the question becomes given the current path to station j-1, which assembly line can best serve station j? This cam be computed for each j > 1 by
cost₁(j) = min{cost₁(j-1) + a_{1, j}, cost₂(j-1) + t_{2, j-1} + a_{1, j}}
cost₂(j) = min{cost₂(j-1) + a_{2, j}, cost₁(j-1) + t_{1, j-1} + a_{2, j}}

As you can see, the calculation of cost_i(j) relies on the computation of cost_i(j-1). By calculating these values from station 1 to to station n, we are able to simply look up the values in the table instead of having to recalculate these values.

These give optimal solutions to each of the subproblems. We repeat this same step for all stages j = 2, …, n then we arrive at the final step were we finish the job. Lets define total_cost to indicate the cost of the optimal solution.
total_cost = min{cost₁(n) + x₁, cost₂(n) + x₂}

We’d like to see which value minimizes total_cost. Then we can trace back to find the values that minimized cost₁ or cost₂ at each step depending on which assembly line was chosen. The following algorithm does just this, and stores the assembly line chosen at each state in the variable line.

For the above example, the table would be calculated as follows:

We can reconstruct the optimal path through assembly lines by seeing that we finish by going through station S_{2, 3}.
We arrive at station S_{2, 3} by going through the assembly line station S_{2, 2}.
We arrive at station S_{2, 2} by going through the assembly line station S_{1, 1}.

This is precisely the path that is highlighted in the image above.

The algorithm to construct these paths and compute the total_cost for such problems is given below.

Algorithm FastestWay(a, t, e, x, m)
cost₁ [<-] e₁ + a_{1, 1}
cost₂ [<-] e₂ + a_{2, 1}
for (j [<-] 2 to n) if (cost₁(j-1) + a_{1, j} [<=] cost₂(j-1) + t_{2, j-1} + a_{1, j}
cost₁(j) [<-] cost₁(j-1) + a_{1, j}
line₁(j) [<-] 1 else cost₁(j) [<-] cost₂(j-1) + t_{2, j-1} + a_{1, j}
line₁(j) [<-] 2if (cost₂(j-1) + a_{2, j} [<=] cost₁(j-1) + t_{1, j-1} + a_{2, j}
cost₂(j) [<-] cost₂(j-1) + a_{2, j}
line₂(j) [<-] 1 else cost₂(j) [<-] cost₁(j-1) + t_{1, j-1} + a_{2, j}
line₂(j) [<-] 2if (cost₁(n) + x₁ [<=] cost₂(n) + x₂)
total_cost = cost₁(n) + x₁
final_line = 1
else
total_cost = cost₂(n) + x₂
final_line = 2

For more information please refer to My Assembly Line Scheduling Examples Page.

Note: I used Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein to help with this post.