Flow-Shop Scheduling

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 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.

Leave a Reply

Your email address will not be published. Required fields are marked *