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.