The first couple of problems in this section, at least, are pretty tractable for students.

**The problem: **Flow-Shop Scheduling. This is problem SS15 in the appendix.

**The description: **Exactly the same as Open-Shop scheduling, with the additional restriction that we have to schedule each job on the processors in strictly increasing order of processor number.

(Note that the description in G&J doesn’t specify that subtasks of a job are assigned to specific processors. But it’s clear that’s how it works in the paper.)

**Example: **Here is the set of jobs from last week:

Job | P1 time | P2 time | P3 time |

1 | 1 | 2 | 3 |

2 | 3 | 1 | 2 |

3 | 2 | 3 | 1 |

If we have to schedule things in order, we can only schedule one job at time 0, and it has to go on P1. The greedy choice would be to schedule Job 1 on P1 first, and then schedule it on P2 at time 1, once it’s finished. Then we can schedule the beginning of Job 3 on P1, and so on. The overall schedule looks like:

P1 | 1 | 3 | 3 | 2 | 2 | 2 | |||

P2 | 1 | 1 | 3 | 3 | 3 | 2 | |||

P3 | 1 | 1 | 1 | 3 | 2 | 2 |

For total time 9.

But, if we schedule Job 2 instead of Job 3 on P1, we get:

P1 | 1 | 2 | 2 | 2 | 3 | 3 | ||||

P2 | 1 | 1 | X | 2 | X | 3 | 3 | 3 | ||

P3 | 1 | 1 | 1 | 2 | 2 | X | 3 |

For total time 10.

**Reduction:** The paper by Garey, Johnson, and Sethi uses 3-Partition. So we’re given a set A with 3N elements, and a bound B. We’ll build a Flow-Shop problem with 3 processors. The jobs will be a set of N+1 “C” jobs and 3N “E” jobs.

Job C0 has tasks of length <0, B, 2B>, job Cn has tasks of length <2B, B, 0> and the intervening Ci tasks have length<2B, B, 2B>.

Notice that scheduling the C tasks leaves “holes” of length B on processor 2- a Ci task takes 2B time on processor P1, and when it moves to P2, it finishes there in B time, and so P2 needs to wait idly for another B time units while waiting for the next job on P1 to finish.

Job E_{j} (where j runs from 1 to 3N) will take <0, a_{j}, 0> time, where a_{j} is the corresponding element in A. The deadline is (2n+1)B.

If a 3-partition exists, then we can split A into sets of 3 elements, each of which sum exactly to B. Each of these sets of 3 elements can fit exactly into one of the length B “holes” left by the C jobs.

If a feasible schedule exists, notice that scheduling all of the C tasks as efficiently as possible gets us exactly to the deadline. So the only thing we can do with the E tasks is put them into the holes on processor 2. Which gives us a partition.

**Difficulty: **5. This is a pretty easy and straightforward application of 3-partition. But I think 3-partition is hard to understand, so it’s still not an easy reduction.