Tag Archives: Difficulty 2

Job-Shop Scheduling

Are you sick of all of these flow-shop problems where we have to split up the tasks of a job into exactly one thing on each processor, progressing through the processors in the same order?  Then today’s problem is for you!

The problem: Job-Shop Scheduling.  This is problem SS18 in the appendix.

Description: We’re given a set of m processors and a set J of jobs.  Each job j in J consists of a chain of tasks, but different jobs can have different numbers of tasks.  The subtasks need to be processed in order, and each task has a processor assignment associated with it, and it’s possible that the subtasks can be assigned to the same processor multiple times, and/or skip some processors entirely.  The only requirement is that two consecutive tasks need to be on different processors (otherwise, we can just merge those tasks together). If we’re given a deadline D, can we schedule all jobs to complete all of their tasks by time D?

Example: Suppose we have three processors and 4 jobs:

  1. Job 1: 1 time on P1, then 2 time on P2, then 3 time on P3, then 2 time on P2
  2. Job 2: 2 time on P1, then 3 time on P2, then 2 time on P1
  3. Job 3: 1 time on P1, then 2 time on P3, then 3 time on P1, then 2 time on P3.
  4. Job 4: 1 time on P4, and that’s it.

Then we can get everything done by time 8 with the following schedule:

P1 1 2 2 3 3 3 2 2
P2 3 1 1 2 2 2 1 1
P3 4 3 3 1 1 1 3 3

Reduction: Garey, Johnson, and Sethi use 3-Partition.  So we’re given a set of 3n elements A, and a bound B.  The Job-Shop instance will have 2 processors and 3n+1 jobs labeled C0 through C3n.  Job C0 has 2n tasks, alternating B time on each processor (so, B time on P1, then another B time on P2, then another B time on P1, and so on).  The rest of the tasks get 0 time on P1 and a1 time on P2.  The deadline is 2nB, which is the time it takes to schedule all of C0.  The paper leaves out the “straightforward” task of showing this reduction actually solves the problem.  I believe them that it is straightforward, let’s take a closer look:

If A has a 3-Partition, then we have a collection of N sets of 3 elements that all add up to B.  Each one of these sets can fit on P2 while C0 is running on P1 (since C0 uses P1 for exactly B time for each task on P1), so we can fit all of the C tasks into the “holes” left by C0.

If we have a schedule that meets the deadline, we know that C0 must be scheduled continually, which leaves the B-sized holes on P2.  For all of the A tasks to be scheduled by the deadline, they have to fit in those holes, which gives us a partition of A.

Difficulty: 5.  The hard part, of course, is coming up with the conversion.  3-Partition isn’t the easiest problem to work with, but the nice features of it (especially that you know that any subset of A that adds to B has exactly 3 elements) make it a good fit here.

I wonder if it’s necessary to have C0 spend B time on both processors.  I understand the need to have C0 running on P2 to separate the partition sets, but wouldn’t it also work (and to my mind, be easier) if C0 took just 1 time (instead of B) each time it ran on P2?

I also wonder if there isn’t an easier reduction that goes straight from Flow-Shop Scheduling.  The reduction can take the Flow-Shop instance, and map it directly to the Job-Shop instance (just because the Job-Shop problem allows you to reuse, reorder, or skip processors with tasks, doesn’t mean it’s required).  Unless I’m missing something, this is a difficulty 2 reduction.  I think the reason they do the 3-Partition reduction in the paper is because they want to show it’s NP-Complete in the case where there are only 2 processors, and the Flow-Shop Scheduling reduction uses 3 processors.

Preemptive Scheduling

This is one of those reductions that is easy because you remove everything that makes the problem hard.  It always feels like cheating to do this, but I guess it shows that adding extra complexity to a hard problem will never make it easier..

The problem: Preemptive Scheduling.  This is problem SS12 in the appendix.

The description: Given a set T of tasks arranged in a partial order,   each task t has a positive length l(t).  We have a set of m processors and an overall deadline D.  Can we create a preemptive schedule for T that obeys the precedence constraints and meets the overall deadline?  A preemptive schedule allows tasks to be partially run on a processor and then removed, and we can finish it at some later time.

Example: Here is a simple partial order:

The number of the task is its length.  So task a takes 3 time units, for example.

A two-processor preemptive schedule could be something like: P1: (a,a,a,b,b,d)  and P2: (d,d,d,c,c,c), getting both tasks done at time6.

If we did not allow preemption, we would not be able to fit task d along with task a, so we couldn’t do anything on P2 while P1 was running task 1.

Reduction: The paper by Ullman which we used for Precedence Constrained Scheduling has the reduction.   He basically notes that Precedence Constrained Scheduling is a special instance of Preemptive Scheduling where all lengths of all jobs are 1.  In that case, no preemption is possible.  So the reduction is basically “use the exact same problem”.

Difficulty: 2.  I usually reserve Difficulty 1 for “this is the same problem”, but here, there is a little bit of insight to convince yourself that you can interpret the problem this way.

Protected: Scheduling with Individual Deadlines

This content is password protected. To view it please enter your password below:

Protected: Hitting Set

This content is password protected. To view it please enter your password below:

Protected: Bin Packing

This content is password protected. To view it please enter your password below:

Protected: Quadratic Assignment Problem

This content is password protected. To view it please enter your password below:

Protected: DNF Non-Tautology

This content is password protected. To view it please enter your password below:

Protected: Subset Sum

This content is password protected. To view it please enter your password below:

Protected: Longest Circuit, Longest Path

This content is password protected. To view it please enter your password below:

Protected: Traveling Salesman, Bottleneck Traveling Salesman

This content is password protected. To view it please enter your password below: