Here’s the reduction using the problem from last week.

**The problem: **Two-processor Flow-Shop with Bounded Buffer. This is problem SS17 in the Appendix.

**The description: **We’re given an instance of Flow-Shop Scheduling, but we fix the number of processors to 2. We’re also given a non-negative integer buffer bound B. Can we find a flow-shop schedule that meets the deadline such that the number of jobs finished with their first task, but yet to start their second task never exceeds B?

**Example: **Suppose I have three jobs:

Job | P1 Time | P2 Time |

1 | 1 | 3 |

2 | 1 | 3 |

3 | 4 | 1 |

For ease of discussion in the reduction, we will write these 2 times as tuples. So job 1 will be written as (1,3).

One possible schedule would be:

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

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

This uses a buffer of size 1 (Job 2 finishes its first task at time 2 and starts its second task at time 5, and Job 3 finishes its first task at time 6 and starts its second task at time 8). This finishes all three tasks at time 8. If we have a buffer size of 0, this wouldn’t be allowed. The best we can do is:

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

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

..finishing everything by time 9.

**Reduction: **The paper by Papadimitriou and Kanellakis uses the Three-Way Matching of Integers problem. So we have a set A with n integers {a_{1}..a_{n}} and a set B with 2n integers {b_{1}..b_{2n}}. Let c = the desired sum of each set. We’re going to create 4n+1 jobs:

- Each element a
_{i}creates a job (c/2, a_{i}+c). - Each element b
_{i}creates a job (1,b_{i}). - We have n+1 “K” jobs. K
_{0}= (0,2). K_{n}= (3c/2, 0). The intervening K_{i}=(3c/2,2)

We have a buffer size of 1, and a deadline of n(*2c+2). Notice that this deadline is both the sum of all processor 1 tasks and the sum of all processor 2 tasks. So there can be no waiting by either processor if we want to meet the deadline. This means that K_{0} has to be scheduled first (since it jumps straight to processor 2) and K_{n} has to be scheduled last (so processor 1 is doing something while processor 2 is finishing).

If we have a feasible schedule, it has to start by scheduling 2 B tasks(say, b_{i} and b_{j}) on processor 1 while K_{0} is on processor 2. Then, those 2 tasks move to processor 2 and will be done by time 2+b_{i}+b_{j}. Meanwhile, an A process runs on process 1 and moves to processor 2 as soon as both B processes end. The A process will finish on process 2 at time c+2. We run one of the K processes on processor 1 at the same time.

What we get is this (from the paper):

Notice how everything lines up in a giant chain of corresponding A and B elements, and that we have to choose A and B elements that add up to c to not have any wasted time on a processor. The actual proof in the paper uses induction on N and is a very nicely presented argument.

If we have a matching of A and B, we can use that matching to build the above schedule.

**Difficulty: **6**. **I think the combination of coming up with the steps above and realizing you need an inductive proof to make it happen makes this a hard problem for students. Maybe this should be a 7, but I think giving them the Three-Way Matching of Integers problem (instead of Numerical 3DM, which is what G&J say in the Appendix) is a big hint.