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

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

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

Аннотация

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

Издание

Труды Института системного программирования РАН, том 12, 2007, стр. 17-26.

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

Для цитирования

Н.Н. Кузюрин, А.И. Поспелов. Вероятностный анализ различных шельфовых алгоритмов упаковки прямоугольников в полосу. . Труды Института системного программирования РАН, том 12, 2007, стр. 17-26. .

Полный текст статьи в формате pdf Вернуться к содержанию тома