Category Archives: Appendix: Sequencing and Scheduling

Deadlock Avoidance

I was out of town last week- sorry for the missed post.

The problem: Deadlock Avoidance.  This is problem SS22 in the appendix.

The description: (The definition in G&J is a little vague, so this comes more from the paper by Araki, Sugiyama, Kasami, and Okui).  Given a set {P1..PU} of processes (represented as directed acyclic graphs with a fixed “start node”), and set {t1..tT} of resource types, where resource type ti has ai equivalent units available.  Each process state may allocate or deallocate a resource type, with the stipulations that:

  • Each process can only deallocate a resource it has allocated
  • Each process must deallocate all allocated resources before completing (along any path through its DAG)

Given a state in this system (where each process is somewhere along its process flow), is the state of the system “safe”?  That is, for each control flow, can we find a sequence of allocations and deallocations that allows each process to finish?

Example: I had a hard time with this definition until I realized we were asking about a specific state of the system.  So here is the classic deadlock situation described in this terminology.  Suppose we have 2 processes, P1 and P2.  Each process’ start node is its name, the symbol a(X) means to allocate resource X and the symbol d(X) means to deallocate resource X.

The process flows look like:

If we set the starting state to after the second node of each graph (so P0 has R1, and P1 has R2), then we have a deadlock.  But if we set the starting state to after the first node for each graph (so, before any resources are allocated) then we would call that “safe” because we can do all of P0, followed by all of P1, and have both processes finish.

Reduction: The paper by Araki, Sugiyama, Kasami, and Okui have several reductions for several variants of the problem.  This is the first one (Theorem 2 in my paper) and uses 3SAT.  We’re given a formula with n variables and m clauses, and build a system that has 3m+2n+1 processes and 7m+3n+1 resource types (each with 1 unit of the resource each).    The resources are:

  • Bi, Xi and ~Xi for each variable
  • Cj for each clause
  • Cjk and Djk for each literal position in each clause (k goes from 1 to 3).
  • A single resource A, which will control the flow through processes.

The processes are:

  • Pxi and P~xi for each variable
  • Pjk for each literal position in each clause
  • P0, which manages everything.

Here is the flow diagram for Pxi.  “a” means allocate a resource, and “d” means deallocate a resource:

Here is the flow diagram for P~xi.  Notice that because they share Bi and A, only one of these processes can complete at a time:

The three Pjk processes for a clause are all similar.  The resource “Yj1” refers to the resource that is the first literal in clause j (so it’s really an X resource):

(You can click the images to make them larger)

It’s worth noticing that resource Cj is in common among all 3 processes, and that each process allocates two D resources in a circular fashion.

The main P0 process is:

The starting state is the second node of each process (so after each process acquires its first resource).

If the original formula was satisfiable, then we have a way of setting each variable that satisfies each clause.  Each variable has two processes: Pxi (corresponding to setting xi to true) and P~xi (corresponding to setting xi to false).  The process corresponding to the way we set each xi to satisfy the formula is the one we want to let proceed.  It will grab Bi and eventually wait on A (which is held by P0). This will release the xi (if the variable is set to true) or ~xi (if the variable is set to false) resource. This means that the Pjk process that corresponds to that literal that can run to completion (this is the literal that makes clause Cj true).  Once it’s done, we can run the other two Pjk processes to right before they each try to acquire Cj.

At this moment, none of the Cj‘s or Cjk resources are allocated, so process P0 can finish.  This releases A, so process Pxi (or P~xi) can finish.  This releases Bi, so the other of Pxi and P~xi can finish.  Then, finally, the other two Pjk in each clause can finish, in order.  Since we found an order to terminate all processes, our starting state was safe.

If the original formula was unsatisfiable, for each Bi, we need to decide whether to allocate it to Pxi or P~xi.  The one we allocate to can release it’s Xi (or ~Xi) resource.  That process is waiting to get A (currently held by P0) and the other process for that variable is waiting to get Bi (currently held by the other Xi (or ~Xi ) process).  P0 can’t release A until all Cj and Cjk resources are free, which only happens if some Pjk process completes.  But these processes can’t complete until they get a resource corresponding to a literal in a clause (currently held by a Xi/~Xi process).  Since we know the formula is unsatisfiable, no matter how we decide to allocate the Bi, there will always be at least one clause where all of the literals in that clause were not chosen to advance.  The three processes for this clause cannot complete, meaning P0 cannot advance.  Since we always get to a state where no processes can finish, we have a deadlock.

Difficulty: 8.  Tracing through the different processes is very cool, but very complicated.  I wish I could teach a course one of these years in “cool hard reductions”.  This is way to hard to fit into the last couple of weeks of an Algorithms class, but I think it is something students could sink their teeth into and learn a lot from.

Production Planning

This is one of those problems where we eliminate a lot of the parameters and are still left with a version that in NP-Complete.  I guess I would have started with the stripped-down version first, since adding extra parameters keeps the problem NP-Complete.

The problem: Production Planning.  This is problem SS21 in the appendix.

The description: Given a positive number n of time periods, and for each period i, several non-negative parameters: demand (ri), production capacity (ci), setup cost (bi), incremental production cost coefficient (pi), and inventory cost coefficient (hi).  We’re also given an overall bound B.  Can we find a positive production amount (xi)  for each period such that:

  • xi ≤ ci for all i (we never produce more than the production capacity)
  •  The inventory on hand for each period (Ii =\sum_{j=1}^i(xj -rj)  is non-negative
  • \sum_{i=1}^n(pixi+hiIi) + \sum_{x_{i}>0}bi ≤ B?

Example: There are a lot of variables here, but here’s what it’s really saying:

Suppose we have a factory that makes some product, and the factory’s schedule for making the product is split into time periods.  In each time period, we can only make a certain amount (ci) of the product, and it costs a certain amount to use the factory at all during a time period (bi) and then an additional amount to make each instance of the product (pi).   Each time period also has a demand (ri) that has to be met.  We can get ahead of the demand by producing more than we need (leaving Ii extra around at time i), but also at a cost (hi).

Suppose I have 3 time periods:

Time Period Production Capacity Demand Production Cost Inventory Cost Production Setup
1 5 3 2 1 6
2 5 3 4 3 2
3 1 2 20 20 5

Since at time period 3, we have less production capacity than demand, we will have to carry over inventory from a previous time period.  There are basically four strategies to meet the demands:

  1. Produce 4 units at time period 1, 3 at time 2, and 1 at time 3.  At time 1, this costs 6 to set up production, 4×2 to make the goods, and 1×1 to store the extra good (So 15).  At time period 2, it costs 2+3×4+1×3 = 17, and time period 3, it costs 5+1×20+0x20 = 25, for 57 total cost.
  2. Produce 3 units at time period 1, 4 at time 2, and 1 at time 3.  At time 1, this costs 6+3×2+0x1 = 12.  At time period 2, it costs 2+4×4+1×3 = 21. At time period 3, it costs 5+1×20+0x20  25.  This is a total cost of 58.
  3. Produce 5 units at time period 1, 3 at time period 2, and 0 at time period 3.  This would cost 6+5×2+2×1 = 18 at time 1, 2+3×4+2×3 =20, and 0 at time 3, for a cost of 38.
  4. Produce 3 units at time period 1, 5 at time period 2, and 0 at time period 3.  This would cost 6+3×2+0x1 =12 at time 1, 2+5×4+2×3 = 28 at time 2, and 0 at time 3, for a total time of 40.

So option 3 is the best choice.  But if we raised the inventory cost of time period 1 significantly (say, to 50), then option 3 would cost 114, and option 4 would still cost 40, and be best.

Reduction: The paper by Florian, Lenstra, and Rinnooy Kan say they use Knapsack, but by our definitions, the problem is really Sum of Subsets.    So we’re given a set of integers A= {a1 .. an} and a target B.    We will build a production planning instance with n+1 time periods numbered from 1 to n.  The demand of each period is B.  The b costs (to set up production) are 1 at all periods.   The capacity at time period 0 is n*B, and the capacity at time period i > 0 is ai.  The production cost at time period 0 is 0, the production cost at time period i is \frac{a_i -1}{a_i}.  All inventory costs are 0.   The cost bound B’ is equal to the SOS bound B + 1.

Since it costs 1 to make any amount of goods (up to our capacity limit) in time 0, we might as well make all of it that we can.  This gives us n*B goods, and will be enough to supply the demands at all of the other time periods except for the last, leaving B left over to be supplied in the last time period.  Notice that our production cost fraction is built in such a way that if in time period i, we make ai goods, we pay exactly ai cost.  If we build less than ai goods in time period i (but more than 0), we pay more than ai cost in that time period.  So the only to get a total cost of B’ while meeting the demand is to make exactly ai of the good in each time period that makes goods.  This corresponds to a subset of A that sums to exactly B.

Difficulty: 5.  If you do use this in a class, I’d give them a simpler version where you don’t even mention the inventory costs, and where the b cost is always 1, and where the demands are always equal in each time period, since that’s what the reduction does.

Staff Scheduling

This one has no reference in G&J, but I think it’s easy enough for me (or a student) to figure out.

The problem: Staff Scheduling.  This is problem SS20 in the appendix.

The description: Given a collection C of m-tuples, each tuple consisting only of 0’s and 1’s, and each tuple having the same amount (k) of 1’s.  These represent possible schedules we can give a worker.  We’re also given a “requirement” m-tuple consisting of m non-negative integers, and a number N of workers.  Can we map each c in C to a non-negative integer (representing the number of workers we assign to that schedule) such that the total number of all integers is N or less, and the requirement tuple is met?

Example: I think this is easier to explain with an example.  Suppose we had 4-tuples (corresponding to 4 “work periods”) and C is the tuples:

0 0 1 1
1 1 0 0
1 0 0 1
0 1 1 0
0 1 0 1

Our requirement tuple is:

2 1 4 3

Then one possible schedule would be:

  • 3 people with the first schedule (0,0,1,1)
  • 2 people with the third schedule (1,0,0,1)
  • 1 person with the fourth schedule (0,1,1,0)

..for a total of 6 workers. I think that’s the best you can do, since the first and third time periods have no schedules in common, and there is a total requirement of 6 workers for those time periods.

Reduction: G&J don’t give a reference, but they do suggest to use X3C.   So we’re given a set X of 3q elements, and a collection C of 3-element subsets of X.  The set C’ that we’ll build will be a set of “3q-tuples”, one position corresponding to each element in X.  There will be one tuple for each triple in C.  The tuples will have 1’s in the 3 positions corresponding to the elements in the triple in C, and 0’s everywhere else.  The R-tuple will be all 1’s, and N will be equal to q.

The Staff Scheduling instance we’ve built needs to choose q different tuples to be successful, and that set of tuples will correspond to a solution to the original X3C instance.

Difficulty: 4, assuming I didn’t miss anything.  If you’ve previously explained X3C to your students, this would be a good homework problem.

Timetable Design

We’ve now entered the “Miscellaneous” section of the Sequencing and Scheduling chapter.

The problem: Timetable Design.  This is problem SS19 in the appendix.

The description: (I’m using the description in the paper by Even, Itai, and Shamir, because I think it’s clearer than G&J’s definition): We’re given a set H (of hours to schedule), a collection of N “teachers”, each teacher is available for some subset of the H hours.  We’re also given a collection of M “Classes”, each class is available to be taught for some subset of the H hours. We’re also given an NxM matrix R of requirements:  Rij is the number of hours teacher i needs to teach class j for.   Can create a function f: TxCxH->{0,1} such that f(t,c,h) is 1 if teacher T is teaching class c at time h (and 0 otherwise)?  The function needs to respect the following rules:

  • If f(i,j,h) is 1, then h is in Ti and Cj  (we only schedule teachers and classes when they’re available)
  • The sum of f(i,j,h) over all h = Rij  (Each teacher teaches each class the number of hours they’re supposed to
  • The sum of f(i,j,h) over all i <= 1  (Each class has at most 1 teacher in each time period)
  • The sum of (i,j,h) over all i <= 1 (Each teacher can only teach 1 class per time slot).

Example:  Suppose H was {1,2,3,4,5}

We have 3 teachers:

  • T1 is available at {1,2,3}
  • T2 is available at {3,4,5}
  • T3 is available at {1,3,5}

..and 3 classes:

  • C1 is available at {2,4}
  • C2 is available at {1,5}
  • C3 is available at {2,3}

If R was:

1 1 0
1 0 1
0 1 1

(Teachers are rows, so T1 needs 1 hour of C1, 1 hour of C2, and none of C3, this won’t be satisfiable, since neither T2 nor T3 can teach C3 during hour 2, and someone has to.  If we change C3 to be available at {2,3,5}, then this becomes satisfiable:

  • T1 can only teach C1 at time 2, and C2 at time 1
  • T2 can only teach C1 at time 4, and C3 can be either time 3 or 5.  Let’s pick 5.
  • T3 can teach C2 at times 1 or 5, but time 1 is taken by T1, so we schedule it at time 5.  Similarly, C3 is available at times 2 and 3, and T3 is also available at time 3, so we can schedule that class then.

Reduction: Even, Itai, and Shamir use 3SAT.  So we’re given a set X of literals (x1 through xl, and the negation ~x1 through ~xl), and a set D of k clauses (D1 through Dk).  Define pi to be the number of times variable i (so the literal xi or the literal ~xi)  shows up in the formula.  Each variable i will get 5*pi classes denoted Ciab, where a runs from 1 to pi, and b runs from 1 to 5.  There will be 3 hours to schedule the classes.   They organize the teachers for the classes in a widget that looks like this (from the paper, p. 693):

The idea is that the diagonal lines are teachers who have to teach the 2 classes connected by the line (So, C12 and C13 for example) and the crosses are the 2 ways they can teach it (so h2 and h3).  The bottom arrows are teachers who can have 3 hours of availability and 3 classes to teach.  Each variable gets pi teachers who teach Cq3 and Cq4 (where q runs from 1 to pi) during h1 and h2.  If Cq3 is taught at time h1, the variable is treated as being set to positive, otherwise, it’s negative.

We then need to add more jobs to make sure that we make one literal true in each clause.  This is done by creating a teacher with 3 classes (one for each literal in the clause).  If the literal is the qth occurrence of literal xi, the teacher is assigned to class Ciq2 if the literal is true, and Ciq5 if the literal is false.

If there is a satisfiable solution to the SAT instance, the literal that makes each clause true will define a way to set the teacher at time h1 and h2, and that starts a chain reaction that schedules everything.

If there is a feasible timetable, we look at the Ciq3 and Ciq4 classes to see how we have allocated the teachers to those tasks, which tells us how to set the variables to make each clause true.

Difficulty: 9.  I’m having a hard time following all of the classes and teachers here.  I wonder if there is a much easier way to do this if we reduce from some other problem.

 

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.

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.

No-Wait Flow-Shop Scheduling

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
1 2 4 3
2 2 2 2
3 2 3 1

 

A flow-shop schedule that allowed waiting could be:

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

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:

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

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.

Protected: Flow-Shop Scheduling

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

Protected: Open-Shop Scheduling

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

Protected: Scheduling to Minimize Weighted Completion Time

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