The Problem

Minimizing the maximum number of open stacks.

The problem we will consider arises from industrial contexts involving a cutting process, where small pieces should be cut from larger objects. The first decision problem that appears consists of the allocation of pieces into objects. Then, once the cutting patterns have been generated, they must
be sequenced. Each pattern is composed of smaller piece types and the pieces of the
same type are stacked together. However, space around the saw is limited, hence, the
number of distinct stacks must be small. The following policy is assumed: a stack is open as
soon as a new piece type is cut and it remains open until all the pieces corresponding
to that stack are cut; at this moment the stack can be removed; when this event is verified that the stack is close. The objective we want to achieve is maintaining as small as possible the maximum number of simultaneously open stacks during the cutting process.

We are given a Boolean matrix in which the columns correspond to the item types and each row corresponds to a pattern. The entry cij = 1 if pattern i contains some quantity of product j (the quantity  is irrelevant). The objective is to find a permutation of the patterns such that the maximum number of open stacks is minimized. The stack for item type j is open at point k in the production sequence if there is an item of j that is contained in the pattern cut at or before position k in the sequence and also an item that is contained in a pattern cut at or after position k in the sequence.

File Format

Each file represents a single instance. The file generated according to the following format:
  • First line: number of patterns (n) number of item types (m)
  • Each of next n lines: m Boolean values, one for each product
  • In the matrix of Boolean values a 1 in the row corresponding to pattern i and item type j means that pattern i contains one or more items of type j.

Instance files

The instances are collected by the industrial partners of SCOOP Project.
They are provided in tarred and gzipped format and in zip file format.