Вероятностный анализ различных шельфовых алгоритмов упаковки прямоугольников в полосу.

Вероятностный анализ различных шельфовых алгоритмов упаковки прямоугольников в полосу.

Н.Н. Кузюрин, А.И. Поспелов.

Abstract

Рассматривается задача упаковки множества прямоугольников в вертикальную полосу (strip packing problem). Изучается важный подкласс онлайновых алгоритмов для этой задачи – так называемые шельфовые алгоритмы. Предложен общий метод вероятностного анализа шельфовых алгоритмов, позволяющий для многих шельфовых алгоритмов оценивать математическое ожидание незаполненной площади, в предположении, что высота и ширина каждого прямоугольника являются случайными величинами.

Edition

Proceedings of the Institute for System Programming, vol. 12 (in Russian), 2007, Стр. 17-26.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

For citation

Н.Н. Кузюрин, А.И. Поспелов. Вероятностный анализ различных шельфовых алгоритмов упаковки прямоугольников в полосу. . Proceedings of the Institute for System Programming, vol. 12 (in Russian), 2007, Стр. 17-26. .

Full text of the paper in pdf (in Russian) Back to the contents of the volume