• Openstacks

Openstacks

This domain has been used first at IPC-2006. At IPC-2008 we kept the same scenario, however we produced entirely new problem sets. So, the scenario is the following (adapted from the IPC-2006 description):

The openstacks domain is based on the "minimum maximum simultaneous open stacks" combinatorial optimization problem, which can be stated as follows: A manufacturer has a number of orders, each for a combination of different products, and can only make one product at a time.

The total required quantity of each product is made at the same time (because changing from making one product to making another requires a production stop). From the time that the first product included in an order is made to the time that all products included in the order have been made, the order is said to be "open" and during this time it requires a "stack" (a temporary storage space). The problem is to order the making of the different products so that the maximum number of stacks that are in use simultaneously, or equivalently the number of orders that are in simultaneous production, is minimized (because each stack takes up space in the production area).

The problem is NP-hard and known to be equivalent to several other problems. It was recently posed as a challenge problem for the constraint programming community (see http://www.dcs.st-and.ac.uk/~ipg/challenge/).

Note that this is an optimization problem: for any instance of the problem every ordering of the making of products is a solution, which at worst uses as many simultaneously open stacks as there are orders. Thus, finding a plan is quite trivial (in the sense that there exists a domain-specific linear-time algorithm that solves the problem), but finding a plan of high quality is hard (even for a domain-specific algorithm).

The following versions of the Openstacks domain have been used at IPC-2008:

• Sequential: The goal is to minimize the total number of stacks. The number of stacks is represented using symbols. There are two versions of the domain in this track:
  • ADL: Universally quantified preconditions are used in order to ensure that all related orders have been started before making a product, or that all related products have been produced before shipping an order.
  • Semiground: Universally quantified preconditions have been replaced by multiple semiground actions.
• Time: In this case a maximum number of stacks is given and the goal is to find the plan with the least makespan, wothout violating the maximum number of stacks constraint. There are four versions of the domain in this track:
  • ADL: Similar to ADL of sequential track.
  • Semiground: Similar to semiground of sequential track.
  • ADL-numeric: Similar to ADL, but numeric fluents are used to represent the number of stacks.
  • Semiground-numeric: Similar to semiground, but numeric fluents are used to represent the number of stacks.
• Net-benefit: There is a cost associated with each additional stack used to make the products. Howeverm we can ship an order without all of its products beeing delivered with it. A product is considered "delivered" wrt a specific order, if the order includes the product, the product has been made and at the time the product has been made the order was open. A penalty is associated for each non-delivered product of order. There are two versions of the openstacks domain for this track:
  • ADL: Similar to ADL of the time track.
  • ADL-numeric: Similar to the ADL-numeric of the time track.