DMMP Seminar

Gerhard Post — The Manufacturer's Pallet Loading Problem

Time: Wednesday, November 24, 2010
Location: Room 101, Citadel

Given a large rectangle (the pallet) and many small rectangles (the boxes), the problem is to decide how many boxes can be placed on the pallet. Here the boxes have to be placed with the sides parallel to the sides of the pallet, but can be turned by 90 degrees; hence the height of the box is irrelevant. Remarkably it seems to be unknown whether this problem is NP-hard; even the question whether it is in NP seems to be unanswered. We will discuss some bounds, equivalences of the problem, and some heuristics that for small problems often find an optimal solution.