Packing Task
Jump to navigation
Jump to search
A Packing Task is a allocation task that requires the packing objects together into containers.
- AKA: Bin-Packing.
- Context:
- It can (often) be a Packing Optimization Task.
- Example(s):
- Counter-Example(s):
- See: Maximum Coverage Task, NP-Hard Task, Linear Programming.
References
2013
- http://en.wikipedia.org/wiki/Packing_problem
- Packing problems are a class of optimization problems in mathematics that involve attempting to pack objects together into containers. The goal is to either pack a single container as densely as possible or pack all objects using as few containers as possible. Many of these problems can be related to real life packaging, storage and transportation issues. Each packing problem has a dual covering problem, which asks how many of the same objects are required to completely cover every region of the container, where objects are allowed to overlap.
- In a packing problem, you are given:
- 'containers' (usually a single two- or three-dimensional convex region, or an infinite space)
- A set of 'objects' some or all of which must be packed into one or more containers. The set may contain different objects with their sizes specified, or a single object of a fixed dimension that can be used repeatedly.
- Usually the packing must be without overlaps between goods and other goods or the container walls. In some variants, the aim is to find the configuration that packs a single container with the maximal density. More commonly, the aim is to pack all the objects into as few containers as possible.[1] In some variants the overlapping (of objects with each other and/or with the boundary of the container) is allowed but should be minimized.
- ↑ Lodi, A., Martello, S., Monaci, M. (2002). "Two-dimensional packing problems: A survey". European Journal of Operational Research (Elsevier).