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.

Protected: Staff Scheduling

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

Protected: Timetable Design

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

Protected: Job-Shop Scheduling

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

Protected: Two-Processor Flow-Shop With Bounded Buffer

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

Protected: No-Wait Flow-Shop Scheduling

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

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: