Is this a minimal set-cover problem?

Question

I have the following scenario (preliminary apologies for length, but I wanted to be as descriptive as possible):

I am presented with a list of "recipes" (Ri) that must be fulfilled, in the order presented, to complete a given task. Each recipe consists of a list of the parts (Pj) required to complete it. A recipe typically requires up to 3 or 4 parts, but might require as many as 16. An example recipe list might look like:

• R1 = {P1}
• R2 = {P4}
• R3 = {P2, P3, P4}
• R4 = {P1, P4}
• R5 = {P1, P2, P2} //Note that more than 1 of a given part may be needed. (Here, P2)
• R6 = {P2, P3}
• R7 = {P3, P3}
• R8 = {P1} //Note that recipes may recur within the list. (Same as R1)

The longest list might consist of a few hundred recipes, but typically contains many recurrences of some recipes, so eliminating identical recipes will generally reduce the list to fewer than 50 unique recipes.

I have a bank of machines (Mk), each of which has been pre-programmed (this happens once, before list processing has begun) to produce some (or all) of the available types of parts.

An iteration of the fulfillment process occurs as follows:

• The next recipe in the list is presented to the bank of machines.
• On each machine, one of its available programs is selected to produce one of the parts required by this recipe, or, if it is not required for this recipe, it is set "offline."
• A "crank" is turned, and each machine (that has not been "offlined") spits out one part.
• Combining the parts produced by one turn of the crank fulfills the recipe. Order is irrelevant, e.g., fulfilling recipe {P1, P2, P3} is the same as fulfilling recipe {P1, P3, P2}.

The machines operate instantaneously, in parallel, and have unlimited raw materials, so there are no resource or time/scheduling constraints. The size k of the bank of machines must be at least equal to the number of elements in the longest recipe, and thus has roughly the same range (typically 3-4, possibly up to 16) as the recipe lengths noted above. So, in the example above, k=3 (as determined by the size of R3 and R5) seems a reasonable choice.

The question at hand is how to pre-program the machines so that the bank is capable of fulfilling all of the recipes in a given list. The machine bank shares a common pool of memory, so I'm looking for an algorithm that produces a programming configuration that eliminates (entirely, or as much as possible) redundancy between machines, so as to minimize the amount of total memory load. The machine bank size k is flexible, i.e., if increasing the number of machines beyond the length of the longest recipe in a given list produces a more optimal solution for the list (but keeping a hard limit of 16), that's fine.

For now, I'm considering this a unicost problem, i.e., each program requires the same amount of memory, although I'd like the flexibility to add per-program weighting in the future. In the example above, considering all recipes, P1 occurs at most once, P2 occurs at most twice (in R5), P3 occurs at most twice (in R7), and P4 occurs at most once, so I would ideally like to achieve a configuration that matches this - only one machine configured to produce P1, two machines configured to produce P2, two machines configured to produce P3, and one machine configured to produce P4. One possible minimal configuration for the above example, using machine bank size k=3, would be:

• M1 is programmed to produce either P1 or P3
• M2 is programmed to produce either P2 or P3
• M3 is programmed to produce either P2 or P4

Since there are no job-shop-type constraints here, my intuition tells me that this should reduce to a set-cover problem - something like the minimal unate set-cover problem found in designing digital systems. But I can't seem to adapt my (admittedly limited) knowledge of those algorithms to this scenario. Can someone confirm or deny the feasibility of this approach, and, in either case, point me towards some helpful algorithms? I'm looking for something I can integrate into an existing chunk of code, as opposed to something prepackaged like Berkeley's Espresso.

Thanks!

Answer 1

This reminds me of the graph coloring problem used for register allocation in compilers.

Step 1: if the same part is repeated in a recipe, rename it; e.g., R5 = {P1, P2, P2'}

Step 2: insert all the parts into a graph with edges between parts in the same recipe

Step 3: color the graph so that no two connected nodes (parts) have the same color

The colors are the machine identities to make the parts.

This is sub-optimal because the renamed parts create false constraints in other recipes. You may be able to fix this with "coalescing." See Briggs.