Метод поиска с запретами для задач упаковки в контейнеры

• Автор: Усманова, Анжелика Рашитовна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Уфа
• Количество страниц: 101 с. : ил

ОГЛАВЛЕНИЕ
Введение

Глава 1. Постановка задачи упаковки в контейнеры и обзор методов ее решения

1.1 Классификация задач раскрояупаковки

1.2 Постановка задачи, оценка сложности решения

1.3 Методы решения задачи ВРР

1.3.1 Эвристические алгоритмы полиномиальной сложности

1.3.2 Асимптотически точные и точные алгоритмы

1.3.3 Метаэвристические алгоритмы

1.4 Выводы

Глава 2. Недетерминированные алгоритмы для задачи упаковки в контейнеры

2.1 Многообразие недетерминированных подходов
2.2 Вероятностные простые эвристики
2.2.1 Алгоритм случайная перестановка с равными вероятностями
2.2.2 Алгоритм случайная перестановка с параметром
2.2.3 Алгоритм случайный контейнер с параметром
2.2.4 Общая характеристика простых вероятностных алгоритмов
2.2.5 Численный эксперимент с алгоритмами ЯРЕР, ЯРР, ЯВР
2.2.5.1 Описание тестовых задач
2.2.5.3 Определение параметров алгоритма ВР
2.2.5.2 Определение параметров алгоритма ИРР
2.2.5.4 Сравнение вероятностных алгоритмов
2.3 Алгоритм локального спуска
2.3.1 Описание алгоритма
2.3.2 Численный эксперимент с детерминированным и вероятностным алгоритмами локального спуска
2.4 Выводы
Глава З.Метод поиска с запретами
3.1 Общая схема метода
3.1.1 Классическая структура метода поиска с запретами
3.1.2 Описание алгоритма ТБ для задачи упаковки в контейнеры
3.1.2.1 Общий алгоритм решения
3.1.2.2 Конкретизация метода поиска с запретами
3.2 Окрестности соседних решений полиномиальной мощности
3.2.1 Контейнерноориентированное представление решения и операторы его преобразования
3.2.2 Рандомизированные окрестности
3.3 Оценочная функция
3.4 Список запретов
3.4.1 Различные структуры списка запретов
3.4.2 Управление длиной списка
3.5 Процедуры диверсификации и интенсификации
3.6 Численный эксперимент
3.7 Выводы Глава 4. Экспоненциальная окрестность
соседних решений
4.1 Постановка задачи о назначениях и методы ее решения
4.2 Модификация метода Т8 с использованием задачи о назначениях
4.2.1 Алгоритмы построения экспоненциальной окрестности решений
4.2.2 Улучшение начального решения
4.2.3 Процедура диверсификации
4.4 Численный эксперимент
4.5 Выводы
Заключение
Литература


Задачи Р-У представляют собой важный раздел задач дискретной оптимизации и исследования операций. В рамках решения этих задач исследуются общий проблемы, характерные для указанных областей математики. Сложность решения задач Р-У обусловлена их принадлежностью к классу ИР-трудных задач комбинаторной оптимизации. Исследуемая задача является КР-трудной в сильном смысле, так как содержит в качестве подзадачи также ИР-трудную задачу. В настоящее время не существует точных методов полиномиальной сложности для их решения. Большинство исследователей склоняется к мнению, что ЫР^Р, то есть упомянутые точные методы в принципе не могут быть разработаны. Задача упаковки в контейнеры представляет собой задачу распределения одномерного ресурса. Кроме того, она часто входит в качестве подзадачи в различные многомерные задачи упаковки и размещения геометрических объектов. Во многих случаях применение точных методов для ее решения невозможно из-за больших затрат вычислительного времени. В связи с этим важное значение приобретает разработка и исследование методов локальной оптимизации. Теоретических доказательств эффективности таких методов практически не существует, однако, на практике они очень хорошо себя зарекомендовали. Исходя из вышеизложенного проблема является актуальной. Целью работы является разработка метаэвристического метода решения задачи упаковки в контейнеры; исследование составляющих этот метод различных стратегий локального поиска и создания программной реализации указанного метода. Описание математической модели задачи упаковки в контейнеры, обоснование ее связи с задачей расписания идентичных параллельных процессоров, оценка мощности множества допустимых решений. Разработка и исследование вероятностных алгоритмов решения задачи упаковки в контейнеры, являющихся важными компонентами основного метода. Разработка метода поиска с запретами по полиномиальным окрестностям соседних решений, исследование компонент метода, анализ его параметров. Описание математической модели экспоненциальной окрестности решений, разработка метаэвристического алгоритма, сочетающего локальный поиск по различным окрестностям решений. Проведение и анализ результатов численного эксперимента на базе созданного программного обеспечения. Математические модели задачи упаковки в контейнеры, оценка мощности пространства решений. Вероятностные алгоритмы решения задачи упаковки в контейнеры. Алгоритм поиска с запретами по полиномиальным окрестностям соседних решений. Метод построения экспоненциальной окрестности решений с использованием задачи о назначениях. Вычислительный эксперимент на основе созданного программного обеспечения, его результаты и рекомендации по использованию. Результаты диссертации могут быть использованы при решении задач упаковки в контейнеры, задач раскроя одномерного материала, а также задач расписания работы параллельных процессоров. Апробация работы. Результаты работы и отдельные ее разделы докладывались и обсуждались на международной научной конференции «Проблемы оптимизации и экономические приложения» (г. Уфа); на XII Байкальской международной конференции (г. Иркутск); на первой всероссийской научно-практической конференции по вопросам решения оптимизационных задач в промышленности «Ресурсосберегающие технологии: математическое обеспечение оптимизационных задач в системах автоматизированного прокетирования» ( г. Санкт-Петербург). Глава 1. Под задачами раскроя-упаковки понимается широкий класс моделей, объединенных общей логической структурой. Приведенный перечень можно продолжить, и каждая задача из него , в свою очередь, может быть различным образом конкретизирована. Критерием, по которому какая-либо задача может быть отнесена к данному классу моделей, обычно является наличие двух групп объектов. К первой группе относятся объекты с большим значением некоторой характеристики (длина, вес, время и т. Требуется установить соответствие и порядок назначений между некоторыми объектами и элементами. Существует множество различных факторов, определяющих классы задач раскроя-упаковки [,]. Рис. Многопарам.