Tag Archives: 3-Partition

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.

Protected: Flow-Shop Scheduling

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

Protected: Sequencing to Minimize Weighted Tardiness

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

Protected: Dynamic Storage Allocation

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

Protected: Bin Packing Take 2

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

Protected: Numerical 3-Dimensional Matching

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

Protected: Intersection Graph For Segments On A Grid

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

Weighted Diameter

It took over a year (the first problem strictly from the Appendix was Domatic Number, last August), but we’re finally at the end of the Graph Theory section!  And the last problem is one that’s actually good for students to solve.

The problem: Weighted Diameter.  This is problem GT65 in the appendix

The description: Given a graph G=(V,E) a collection C of  |E| not necessarily distinct, non-negative integers, and a positive integer K.  Can we find a one-to-one function f  mapping each edge in E to an element of C such that if f(e) is the length of edge e, then G has a diameter of K or less.

In other words, given a set of edge weights C, can we give each edge in E a (distinct) weight from C such that the resulting weighted graph has a path between any two vertices of length ≤ K?

Example: Suppose I have a graph:

weighted dimater3

And C= {1,2,2,2,3,5}.  I think the best was you can label this is:

weighted dimater2

The Diameter here is 7 (The length of the path from A-D).

The reduction: G&J say to use 3-Partition, so we’ll go with that.  We’re given a set A, with 3m elements, a bound B, and want to split the elements of B into sets of size 3 so that each set adds up to m.  We know several things about A, but the important thing for our purposes is that all of the elements in A add up to m*B.

We’ll also assume that |A| is at least 9.  If it’s smaller than that, we can just brute-force the answer.

What we’re going to do is build a graph that is a tree with 3m+1 vertices.  We have a root, and the root has m chains of length 3 extending from it. This gives us exactly 3*m edges.

We set K = 2*B, and set C = A

If there exists a 3-parition of A, then each of the sets of 3 elements can map onto a different chain in the graph.  This makes the longest path in the graph be between any 2 leaves.  Since the length from a leaf to a root is exactly B, the diameter of the graph is 2B.

If there exists a weighted diameter of the graph of cost 2*B, then we need to show the the cost of each chain is exactly B.  Suppose it wasn’t, and the cost from the root to some leaf v is > B, let’s say B+x.  Then , since there are least 3 chains (since |A| >= 9) and since the sum of all of the weights is m*B exactly), there must exist some leaf w, with the cost of the chain from the root to w > B-x.  The cost of the path from v to w is now > 2B, a contradiction.

If the cost from the root to some leaf is < B, then there must be some other leaf u with the cost from the root to u > B (since the cost of all of the edges add up to m*B) , and we can do the above on u.

Since each chain costs exactly B, we can use the edge weights of each chain as the sets of 3 elements that make our 3-Partition.

Difficulty: 4. G&J does say in the comments that this problem is NP-Complete even for trees, so that may have been a hint.  The proof is a little tricky (getting from “diameter ≤ K” to “set adding up to exactly K” requires some work, and there may be a more elegant way than what I did).  But I think this would make a good homework problem.

Protected: Directed Bandwidth

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

Protected: 3-Partition

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