# Review 8-1

* Hajin Ju, 2024062806

## Problem 1

Fill in the blanks in the following assembly-line scheduling example.

### Solution 1

![](/assets/R8-1_1.png)


**table $s$**

| $s$ | 1   | 2   | 3   | 4   | 5   | 6   |
| --- | --- | --- | --- | --- | --- | --- |
| 1   | 9   | 18  | 20  | 24  | 32  | 35  |
| 2   | 12  | 16  | 22  | 25  | 30  | 37  |

**table $l$**

| $l$ | 1   | 2   | 3   | 4   | 5   | 6   |
| --- | --- | --- | --- | --- | --- | --- |
| 1   | -   | 1   | 2   | 1   | 1   | 2   |
| 2   | -   | 1   | 2   | 1   | 2   | 2   |

$$\begin{align*}s^* &= 38\\l^* &= 1\end{align*}$$

## Problem 2

Fill in the blanks in the following pseudocode for assembly-line scheduling

### Solution 2

```python
FASTEST-WAY(a, t, e, x, n)
    s[1][1] = e[1] + a[1][1]
    s[2][1] = e[2] + a[2][1]
    for j = 2 to n
        do
        if s[1][j-1] + a[1][j] <= s[2][j-1] + t[2][j-1] + a[1][j]
            then s[1][j] = s[1][j-1] + a[1][j]
                l[1][j] = 1
            else s[1][j] = s[2][j-1] + t[2][j-1] + a[1][j]
                l[1][j] = 2
        
        if s[2][j-1] <= s[1][j-1] + t[1][j-1]
            then s[2][j] = s[2][j-1] + a[2][j]
                l[2][j] = 2
            else s[2][j] = s[1][j-1] + t[1][j-1] + a[2][j]
                l[2][j] = 1
    if s[1][n] + x[1] <= s[2][n] + x[2]
        then s* = s[1][n] + x[1]
            l* = 1
        else s* = s[2][n] + x[2]
            l* = 2
```