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.