Article ID: | iaor1989619 |
Country: | Netherlands |
Volume: | 8 |
Issue: | 1 |
Start Page Number: | 11 |
End Page Number: | 16 |
Publication Date: | Feb 1989 |
Journal: | Operations Research Letters |
Authors: | Bartholdi John J., Vande Vate John H., Zhang Jixian |
The shelf heuristic is an on-line algorithm to pack oriented rectangles into an open-ended bin of unbounded height. The heuristic uses space effectively by partitioning the bin into ‘shelves’ into which rectangles of nearly equal heights are packed. The authors analyze the expected performance of the shelf heuristic when the dimensions of the rectangles are identically and independently distributed according to a uniform distribution on (0,1]. In addition, they discuss how to choose the shelf sizes to optimize expected performance.