The Openstacks Domain ===================== 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). Domain Versions =============== Note that for this domain we give (equivalent) compiled STRIPS variants. These are in the sub-directories "Strips", "Strips-Time" and "Strips- MetricTime" of the Propositional, Time and MetricTime variants, respectively. The CPU-time required to generate the compiled versions was not significant. Propositional ------------- This is simply an encoding of the original open stacks problem as a planning problem. The encoding is done in such a way that minimizing the length (sequential or parallel) of the plan also minimizes the objective function, i.e., the maximum number of simultaneously open stacks. The problems are a selection of the problems used in the constraint modelling challenge, and include a few problems that could not be solved (optimally) by any of the CSP approaches. Note: This domain uses some ADL constructs (quantified disjunctive preconditions), but these can be compiled away in linear size. Time ----- In this version of the domain, the number of stacks is fixed, and the objective is to minimize makespan. Makespan is dominated by the actions that make products. Note: This domain uses the same ADL constructs as the propositional version. MetricTime ---------- In this version, the objective function is to minimize a (linear) combination of the number of open stacks and the plan makespan. Note: This domain uses the same ADL constructs as the propositional version. Simple (Goal) Preferences ------------------------- In this version, the goal of including all required products in each order is softened, and a score is given for each product that is included in an order when it is shipped. The objective is to maximize this score. The maximum number of open stacks is fixed. Note: This domain uses a quantified conditional effect. ComplexPreferences ------------------ This version has "soft goals", like the previous version, but a variable maximum number of open stacks. The objective is to maximize a linear combination of the score (positive) and the number of open stacks (negative). Note: This domain uses a quantified conditional effect.