Dynamic Programming Assembly Line Scheduling

Assembly Line Scheduling

This is the second article on Dynamic Programming. You can refer to the first article (introduction) here. Let us get started by defining our problem.

Problem definition

The following bullet points define our problem:

1. We have two (parallel) car assembly lines (1) and (2).
2. Each assembly line has (n) stations.
3. The time to enter the first assembly line is (e1) and the time to exit is (x1).
4. Similarly the time to enter the second assembly line is (e2) and the time to exit is (x2).
5. Let (Sij) be station (j) on assembly lien (i) and (aij) be the time a car stays at station (j) on assembly line (i) for example (A21) is the time a car stays at station (1) on assembly line (2)
6. Let the time to transfer a car from station (Sij) to the next station on the other assembly line be (tij) for example (t2j) is the time needed to transfer a car from station (j) on assembly line (2) to station (j+1) on assembly line (1)
7. The time to transfer a car from station (Sij) to the next station on the same line is negligible for example the time to transfer a car from station (1) to station (2) on assembly line (1) is zero.

Here is a schematic diagram for the assembly lines

The question is what stations we should choose from both assembly lines so that the total time for a car to enter and exit the factory is minimal

Solution

Let us follow the steps we discussed in the first Dynamic Programming article.

Characterize the structure of an optimal solution

Ask the question “what are we intending to optimize?” The answer is minimizing the time a car needs to go through the factory assembly lines. The total time is going to be the entry time plus processing time at each station the car goes through plus any transfer time between stations on different assembly lines plus the exit time.

Recursively define the value of an optimal solution

The second step is to define the optimal value (minimum time through the factory) in a recursive way. Let us consider the following cases

1. The minimum time through station (1) on line (1) is simply the entrance time on line (1) plus the processing time at station (1) on line (1) which means (e1 + a11)
2. Similarly the minimum time through station (1) on line (2) is (e2 + a21)
3. The minimum time through station (j) on line (1) is the smaller value of two time values. The first time value is the processing time at station (j) on line (1) plus the minimum time through station (j-1) on line (1). The second time value to consider is the processing time at station (j) on line (1) plus the transfer time from station (j-1) on line (2) plus the minimum time through station (j-1) on line (2).
4. Similarly, the minimum time through station (j) on line (2) is the smaller value of two time values. The first time value is the processing time at station (j) on line (2) plus the minimum time through station (j-1) on line (2). The second time value to consider is the processing time at station (j) on line (2) plus the transfer time from station (j-1) on line (1) plus the minimum time through station (j-1) on line (1).

It looks complicated but in fact it is easy so let us explain it in plain English. If a car is currently being processed at some station then the next step is to move the car to the next station on the same assembly line or transfer it to the next station on the other assembly line. The one you choose is the one that adds less time to the total time through factory that is why we have two cases for each assembly line.

Now we are ready to write formulas otherwise computers will not understand our English. Let fi[j] be the fastest possible time (or minimum time) from start to station (Sij) then we can write

Similarly

Recall that Dynamic Programming uses a bottom up approach to build up the final solution. Putting this into perspective, we pay attention to the special case when j = 1 which is the very first sub problem to be solved. The recursive formula uses the solution of problem instance at (j-1) to solve problem instance at (j). In the case of j = 1 there is no previous instance so it is handled alone while other instances are computed from previous ones.

Lastly do pay attention to the fact that sub problems are overlapping for example both f1(j-1) and f2(j-1) are repeated twice. Only new sub problems are calculated but repeated sub problems are looked up in the table instead. Keep that in mind when using Dynamic Programming.

Compute the value of an optimal solution in a bottom up fashion

Alright we are almost ready to set the stage to do the computation but before doing that let us think a little bit about f1 and f2. It is very important to understand what they stand for and what is the meaning of parameter (j) before writing the actual code for the algorithm. Parameter (j) stands for station number which goes from (1) to (n). Fastest times f1 and f2 hold the time to go through the factory until station number specified by (j) for each assembly line so we need 2 (one dimensional) arrays for f1 and f2. It is obvious now that the fastest time through the factory is either the time through station (n) on line (1) plus the exit time on line (1) or the time through station (n) on line (2) plus the exit time on line (2). In other words the fastest time is

So filling the arrays f1 and f2 then taking the above MIN value is enough to calculate the minimum time. We are not done yet because we do not need to calculate just the minimum time however we need to identify the exact station numbers on both assembly lines with minimal time. This is a very important point in Dynamic Programming as calculating the optimized value is part of the solution but the full solution is to determine the steps to achieve that. We introduce the concept of back pointers to keep track of the steps needed to achieve the optimal solution. Back pointers are nothing but arrays (single or multi dimensional) to store pointers (or marks) so that we can go back and construct the solution. In our case we need two (one dimensional) back pointer arrays L1 and L2 to keep track (at each station) of the assembly line number (1 or 2) on which the car was being processed in the previous station. Remember that given a station number then the car just came from the previous station on either line not necessarily on the same line that is why we need to keep track of that. Let us now jump to the pseudo code.

So far we are done with all the computation we need. The last step is to construct the solution from the computed values which is discussed in the next section.

Construct an optimal solution from the computed information

All the information we need is now stored in the back pointers arrays L1 and L2. At each station we already stored the assembly line number on which the previous station was processing the car. Here is the code to print station numbers that yield minimum time through the factory.

The code above might seem confusing but if you take a deep breath it is actually easy. We are only tracing back through the back pointers arrays to print the station numbers that yield minimum time. Li[j] stores the assembly line number of the station preceding station (j) on line (i) for example L2[5] stores the assembly line number (could be 1 or 2) of the station preceding station (5) on line (2) (The station that was processing the car before got into station 5).

Let us talk a little bit about running time before we close. The code provided to populate the tables and the code to construct the solution runs in linear time. It is a single loop that runs (n) times. This is way better than the brute force solution which runs in exponential time.

We are done with part 2. In the next part I will explain the second Dynamic Programming problem “Matrix Chain Multiplication” discussed in “Introduction to Algorithms” by Thomas H. Cormen. Any comments or feedback is appreciated. Thanks for reading.