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|
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:
For total time 9.
But, if we schedule Job 2 instead of Job 3 on P1, we get:
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 Ej (where j runs from 1 to 3N) will take <0, aj, 0> time, where aj 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.