Two-Processor Flow-Shop With Bounded Buffer

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 {a1..an} and a set B with 2n integers {b1..b2n}.  Let c = the desired sum of each set.  We’re going to create 4n+1 jobs:

  • Each element ai creates a job (c/2, ai+c).
  • Each element bi creates a job (1,bi).
  • We have n+1 “K” jobs.  K0 = (0,2).  Kn = (3c/2, 0).  The intervening Ki=(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 K0 has to be scheduled first (since it jumps straight to processor 2) and Kn 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, bi and bj) on processor 1 while K0 is on processor 2.  Then, those 2 tasks move to processor 2 and will be done by time 2+bi+bj.  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.

Leave a Reply

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