G.~Belov, G. Scheithauer
Gaps between optimal values of some packing and scheduling problems
We consider three connected resource-constrained optimization problems: 1D bin packing (BPP), resource-constrained project scheduling (PSP), and 2D strip packing without rotation (SPP).
It is easy to see that SPP can be relaxed in two different ways down to a PSP: horizontal and vertical scheduling relaxation.
In turn, PSP itself can be relaxed down to BPP, again in two different ways, horizontal and vertical 1D relaxation.
We investigate the quality of these relaxations.
(submitted April 2011)
(Preprint MATH-NM-02-2011, TU Dresden, May. 2011)