This problem is very similar to the last problem, but the reduction is much harder to understand.
The problem: No-Wait Flow-Shop Scheduling. This is problem SS16 in the appendix.
The description: Given an instance of Flow-Shop Scheduling, can we create a schedule that meets the deadline with the additional property that no job waits between tasks? (So, once a job completes a task, it immediately starts another task).
Example: Suppose I have 3 processors and 2 jobs:
|Job||P1 time||P2 time||P3 time|
A flow-shop schedule that allowed waiting could be:
This works because Job 2 waits for one time unit between finishing on P2 and starting on P3. In the no-wait instance, we’d have to start job 2 much later, so that there is no interference. But it turns out that we could also have a no-wait schedule putting a different order of jobs on P1 (Job 2, then Job 1, then Job 3) that is just as fast:
Since jobs can’t be interrupted, the finish time of a job is always the start time plus all the time of all of its subtasks. What we are trying to do is find a permutation of the jobs that allows each job to start at a time where all of the jobs will be finished by the deadline.
Reduction: I think this is Theorem 6 in the Lenstra, Rinooy Kan, and Brucker paper. They reduce from directed Hamiltonian Cycle, but I think the discussion beforehand talking about (directed) TSP is also useful.
The key insight is based on the permutation discussion in the example above. The TSP problem is also looking for a permutation of the vertices. We can make the problems equivalent by making the cost of each edge (i,j) the value cij: The length of the time interval between when we can start job i and job j, assuming we start j as soon as possible after i.
The problem is that this is a reduction in the wrong direction (it reduces from our problem to TSP). But since TSP is proven NP-Complete by reduction from directed HC, we can use a similar construction as we do in that proof to take an HC instance and build the correct jobs in the same fashion. The paper actually does show you how to make that construction but it’s pretty complicated.
Difficulty: 8. Not only is the conversion hard, I think the “oh, wait, this is based on a backward reduction” will confuse beginning students. For more advanced students, showing the details of this reduction may help add to a bag of tricks that can be used in similar “I have a reduction in the wrong direction” situations.