15.1 Assembly-line scheduling

| < Day Day Up > |

## 15.1 Assembly-line scheduling

Our first example of dynamic programming solves a manufacturing problem. The Colonel Motors Corporation produces automobiles in a factory that has two assembly lines, shown in Figure 15.1. An automobile chassis enters each assembly line, has parts added to it at a number of stations, and a finished auto exits at the end of the line. Each assembly line has n stations, numbered j = 1, 2, ..., n. We denote the jth station on line i (where i is 1 or 2) by Si,j. The jth station on line 1 (S1,j) performs the same function as the jth station on line 2 (S2,j). The stations were built at different times and with different technologies, however, so that the time required at each station varies, even between stations at the same position on the two different lines. We denote the assembly time required at station Si,j by ai,j. As Figure 15.1 shows, a chassis enters station 1 of one of the assembly lines, and it progresses from each station to the next. There is also an entry time ei for the chassis to enter assembly line i and an exit time xi for the completed auto to exit assembly line i.

Figure 15.1: A manufacturing problem to find the fastest way through a factory. There are two assembly lines, each with n stations; the jth station on line i is denoted Si,j and the assembly time at that station is ai,j. An automobile chassis enters the factory, and goes onto line i (where i = 1 or 2), taking ei time. After going through the jth station on a line, the chassis goes on to the (j + 1)st station on either line. There is no transfer cost if it stays on the same line, but it takes time ti,j to transfer to the other line after station Si,j. After exiting the nth station on a line, it takes xi time for the completed auto to exit the factory. The problem is to determine which stations to choose from line 1 and which to choose from line 2 in order to minimize the total time through the factory for one auto.

Normally, once a chassis enters an assembly line, it passes through that line only. The time to go from one station to the next within the same assembly line is negligible. Occasionally a special rush order comes in, and the customer wants the automobile to be manufactured as quickly as possible. For rush orders, the chassis still passes through the n stations in order, but the factory manager may switch the partially-completed auto from one assembly line to the other after any station. The time to transfer a chassis away from assembly line i after having gone through station Si,j is ti,j, where i = 1, 2 and j = 1, 2, ..., n - 1 (since after the nth station, assembly is complete). The problem is to determine which stations to choose from line 1 and which to choose from line 2 in order to minimize the total time through the factory for one auto. In the example of Figure 15.2(a), the fastest total time comes from choosing stations 1, 3, and 6 from line 1 and stations 2, 4, and 5 from line 2.

Figure 15.2: (a) An instance of the assembly-line problem with costs ei, ai,j, ti,j, and xi indicated. The heavily shaded path indicates the fastest way through the factory. (b) The values of fi[j], f*, li[j], and l* for the instance in part (a).

The obvious, "brute force" way of minimizing the time through the factory is infeasible when there are many stations. If we are given a list of which stations to use in line 1 and which to use in line 2, it is easy to compute in Θ(n) time how long it takes a chassis to pass through the factory. Unfortunately, there are 2n possible ways to choose stations, which we see by viewing the set of stations used in line 1 as a subset of {1, 2, ..., n} and noting that there are 2n such subsets. Thus, determining the fastest way through the factory by enumerating all possible ways and computing how long each takes would require Ω(2n) time, which is infeasible when n is large.

#### Step 1: The structure of the fastest way through the factory

The first step of the dynamic-programming paradigm is to characterize the structure of an optimal solution. For the assembly-line scheduling problem, we can perform this step as follows. Let us consider the fastest possible way for a chassis to get from the starting point through station S1,j. If j = 1, there is only one way that the chassis could have gone, and so it is easy to determine how long it takes to get through station S1,j. For j = 2, 3, ..., n, however, there are two choices: the chassis could have come from station S1,j-1 and then directly to station S1,j, the time for going from station j - 1 to station j on the same line being negligible. Alternatively, the chassis could have come from station S2,j-1 and then been transferred to station S1,j, the transfer time being t2,j-1. We shall consider these two possibilities separately, though we will see that they have much in common.

First, let us suppose that the fastest way through station S1,j is through station S1,j-1. The key observation is that the chassis must have taken a fastest way from the starting point through station S1,j-1. Why? If there were a faster way to get through station S1,j-1, we could substitute this faster way to yield a faster way through station S1,j: a contradiction.

Similarly, let us now suppose that the fastest way through station S1,j is through station S2,j-1. Now we observe that the chassis must have taken a fastest way from the starting point through station S2,j-1. The reasoning is the same: if there were a faster way to get through station S2,j-1, we could substitute this faster way to yield a faster way through station S1,j, which would be a contradiction.

Put more generally, we can say that for assembly-line scheduling, an optimal solution to a problem (finding the fastest way through station Si,j) contains within it an optimal solution to subproblems (finding the fastest way through either S1,j-1 or S2,j-1). We refer to this property as optimal substructure, and it is one of the hallmarks of the applicability of dynamic programming, as we shall see in Section 15.3.

We use optimal substructure to show that we can construct an optimal solution to a problem from optimal solutions to subproblems. For assembly-line scheduling, we reason as follows. If we look at a fastest way through station S1,j, it must go through station j - 1 on either line 1 or line 2. Thus, the fastest way through station S1,j is either

- the fastest way through station S1,j-1 and then directly through station S1,j, or

- the fastest way through station S2,j-1, a transfer from line 2 to line 1, and then through station S1,j.

Using symmetric reasoning, the fastest way through station S2,j is either

- the fastest way through station S2,j-1 and then directly through station S2,j, or

- the fastest way through station S1,j-1, a transfer from line 1 to line 2, and then through station S2,j.

To solve the problem of finding the fastest way through station j of either line, we solve the subproblems of finding the fastest ways through station j - 1 on both lines.

Thus, we can build an optimal solution to an instance of the assembly-line scheduling problem by building on optimal solutions to subproblems.

#### Step 2: A recursive solution

The second step of the dynamic-programming paradigm is to define the value of an optimal solution recursively in terms of the optimal solutions to subproblems. For the assembly-line scheduling problem, we pick as our subproblems the problems of finding the fastest way through station j on both lines, for j = 1, 2, ..., n. Let fi[j] denote the fastest possible time to get a chassis from the starting point through station Si,j.

Our ultimate goal is to determine the fastest time to get a chassis all the way through the factory, which we denote by f*. The chassis has to get all the way through station n on either line 1 or line 2 and then to the factory exit. Since the faster of these ways is the fastest way through the entire factory, we have

(15.1) |

It is also easy to reason about f1[1] and f2[1]. To get through station 1 on either line, a chassis just goes directly to that station. Thus,

(15.2) |

(15.3) |

Now let us consider how to compute fi[j] for j = 2, 3, ..., n (and i = 1, 2). Focusing on f1[j], we recall that the fastest way through station S1,j is either the fastest way through station S1,j-1 and then directly through station S1,j, or the fastest way through station S2,j-1, a transfer from line 2 to line 1, and then through station S1,j. In the first case, we have f1[j] = f1[j - 1] + a1,j, and in the latter case, f1[j] = f2[j - 1] + t2,j-1 + a1,j. Thus,

(15.4) |

for j = 2, 3, ..., n. Symmetrically, we have

(15.5) |

for j = 2, 3, ..., n. Combining equations (15.2)-(15.5), we obtain the recursive equations

(15.6) |

(15.7) |

Figure 15.2(b) shows the fi[j] values for the example of part (a), as computed by equations (15.6) and (15.7), along with the value of f*.

The fi[j] values give the values of optimal solutions to subproblems. To help us keep track of how to construct an optimal solution, let us define li [j] to be the line number, 1 or 2, whose station j - 1 is used in a fastest way through station Si,j . Here, i = 1, 2 and j = 2, 3, ..., n. (We avoid defining li[1] because no station precedes station 1 on either line.) We also define l* to be the line whose station n is used in a fastest way through the entire factory. The li[j] values help us trace a fastest way. Using the values of l* and li[j] shown in Figure 15.2(b), we would trace a fastest way through the factory shown in part (a) as follows. Starting with l* = 1, we use station S1,6. Now we look at l1[6], which is 2, and so we use station S2,5. Continuing, we look at l2[5] = 2 (use station S2,4), l2[4] = 1 (station S1,3), l1[3] = 2 (station S2,2), and l2[2] = 1 (station S1,1).

#### Step 3: Computing the fastest times

At this point, it would be a simple matter to write a recursive algorithm based on equation (15.1) and the recurrences (15.6) and (15.7) to compute the fastest way through the factory. There is a problem with such a recursive algorithm: its running time is exponential in n. To see why, let ri(j) be the number of references made to fi[j] in a recursive algorithm. From equation (15.1), we have

(15.8) |

From the recurrences (15.6) and (15.7), we have

(15.9) |

for j = 1, 2, ..., n - 1. As Exercise 15.1-2 asks you to show, ri(j) = 2n-j. Thus, f1[1] alone is referenced 2n-1 times! As Exercise 15.1-3 asks you to show, the total number of references to all fi[j] values is Θ(2n).

We can do much better if we compute the fi[j] values in a different order from the recursive way. Observe that for j ≥ 2, each value of fi[j] depends only on the values of f1[j - 1] and f2[j - 1]. By computing the fi[j] values in order of increasing station numbers j-left to right in Figure 15.2(b)-we can compute the fastest way through the factory, and the time it takes, in Θ(n) time. The FASTEST-WAY procedure takes as input the values ai,j, ti,j, ei, and xi , as well as n, the number of stations in each assembly line.

    FASTEST-WAY(a, t, e, x, n)
     1  f1[1] ← e1 + a1,1
     2  f2[1] ←e2 + a2,1
     3  for j ← 2 to n
     4       do if f1[j - 1] + a1,j ≤ f2[j - 1] + t2,j-1 + a1,j
     5             then f1[j] ← f1[j - 1] + a1, j
     6                  l1[j] ← 1
     7             else f1[j] ← f2[j - 1] + t2,j-1 + a1,j
     8                  l1[j] ← 2
     9          if f2[j - 1] + a2,j ≤ f1[j - 1] + t1,j-1 + a2,j
    10             then f2[j] ← f2[j - 1] + a2,j
    11                  l2[j] ← 2
    12             else f2[j] ∞ f1[j - 1] + t1,j-1 + a2,j
    13                  l2[j] ← 1
    14  if f1[n] + x1 ≤ f2[n] + x2
    15      then f* = f1[n] + x1
    16          l* = 1
    17      else f* = f2[n] + x2
    18             l* = 2

FASTEST-WAY works as follows. Lines 1-2 compute f1[1] and f2[1] using equations (15.2) and (15.3). Then the for loop of lines 3-13 computes fi[j] and li[j] for i = 1, 2 and j = 2, 3, ..., n. Lines 4-8 compute f1[j] and l1[j] using equation (15.4), and lines 9-13 compute f2[j] and l2[j] using equation (15.5). Finally, lines 14-18 compute f* and l* using equation (15.1). Because lines 1-2 and 14-18 take constant time and each of the n - 1 iterations of the for loop of lines 3-13 takes constant time, the entire procedure takes Θ(n) time.

One way to view the process of computing the values of fi[j] and li [j] is that we are filling in table entries. Referring to Figure 15.2(b), we fill tables containing values fi[j] and li[j] from left to right (and top to bottom within each column). To fill in an entry fi[j], we need the values of f1[j - 1] and f2[j - 1] and, knowing that we have already computed and stored them, we determine these values simply by looking them up in the table.

#### Step 4: Constructing the fastest way through the factory

Having computed the values of fi[j], f*, li[j], and l*, we need to construct the sequence of stations used in the fastest way through the factory. We discussed above how to do so in the example of Figure 15.2.

The following procedure prints out the stations used, in decreasing order of station number. Exercise 15.1-1 asks you to modify it to print them in increasing order of station number.

    PRINT-STATIONS(l, n)
    1  i ← l*
    2  print "line " i ", station " n
    3  for j ← n downto 2
    4        do i ← li[j]
    5           print "line " i ", station " j - 1

In the example of Figure 15.2, PRINT-STATIONS would produce the output

line 1, station 6

line 2, station 5

line 2, station 4

line 1, station 3

line 2, station 2

line 1, station 1

Exercises 15.1-1

Show how to modify the PRINT-STATIONS procedure to print out the stations in increasing order of station number. (Hint: Use recursion.)

Exercises 15.1-2

Use equations (15.8) and (15.9) and the substitution method to show that ri(j), the number of references made to fi[j] in a recursive algorithm, equals 2n - j.

Exercises 15.1-3

Using the result of Exercise 15.1-2, show that the total number of references to all fi[j] values, or , is exactly 2n+1 - 2.

Exercises 15.1-4

Together, the tables containing fi[j] and li[j] values contain a total of 4n - 2 entries. Show how to reduce the space requirements to a total of 2n + 2 entries, while still computing f* and still being able to print all the stations on a fastest way through the factory.

Exercises 15.1-5

Professor Canty conjectures that there might exist some ei, ai,j, and ti,j values for which FASTEST-WAY produces li[j] values such that l1[j] = 2 and l2[j] = 1 for some station number j. Assuming that all transfer costs ti,j are nonnegative, show that the professor is wrong.

| < Day Day Up > |