Том 16, номер 4, 2009 г., Стр. 61-86
УДК 519.178
А. С. Руднев
Вероятностный поиск с запретами для задачи упаковки кругов и прямоугольников в полосу
Аннотация:
Рассматривается задача двумерной упаковки кругов и прямоугольников различных размеров в полубесконечную полосу минимальной длины. Представлена математическая постановка задачи в терминах нелинейного целочисленного программирования. Предложена кодирующая схема для двухконтактных решений. На еёе основе разработан вероятностный алгоритм поиска с запретами для нахождения приближёенного решения задачи. Численные эксперименты на случайно сгенерированных примерах, а также на известных тестовых примерах для частных случаев рассматриваемой задачи показали эффективность алгоритма. Для четырёех известных примеров упаковки кругов в полосу удалось найти новые рекордные значения целевой функции.
Ил. 6, табл. 6, библиогр. 34.
Ключевые слова: упаковка в полосу, кодирующие схемы, вероятностный поиск с запретами.
Руднев Антон Сергеевич 1
1. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: anton.rudnev@gmail.com
Статья поступила 5 ноября 2008 г.
Исправленный вариант — 29 мая 2009 г.
