Алгоритмы с оценками качества для задач календарного планирования, упаковки и выбора подмножества векторов

• Автор: Рыков, Иван Александрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Новосибирск
• Количество страниц: 114 с. : ил.

Оглавление
Введение

Глава 1 Задача календарного планирования в условиях

ограниченных ресурсов

1.1 Постановка задачи

1.1.1 Классическая постановка

1.1.2 Известные обобщения

1.1.3 Возобновимые, складируемые и невозобновимые ресурсы

1.1.4 Задачи упаковки как частные случаи задачи календарного планирования

1.2 Связь задачи календарного планирования с задачей упаковки в полосу

1.2! Оценка сверху на отношение оптимальных значений

1.2.2 Пример с отношением 5/4
1.2.3 Минимальность примера
1.3 Приближенный алгоритм для мультипроектной задачи календарного планирования
1.3.1 Приближенный полиномиальный алгоритм для задачи упаковки в полосу
1.3.2 Мультипроектная постановка

1.4 Опыт применения алгоритмов для задачи планирования в
прикладных проектах
1.4.1 Коммерческая библиотека решения задач планирования ЬБЕ
1.4.2 Система планирования собраний РгееПте
1.4.3 Вероятностная модель планирования ВСНГК
Глава 2 Задача выбора подмножества векторов
2.1 Постановка задачи
2.2 Алгоритм решения задачи с целочисленными координатами векторов
2.2.1 Алгоритм решения задачи га-ПВ
с целочисленными координатами векторов
2.2.2 Алгоритм решения задачи ПВО
с целочисленными координатами векторов
2.3 Полиномиальный при фиксированном к алгоритм
2.4 Приближенный рандомизированный алгоритм и условия его асимптотической точности
Заключение
Литература
Публикации автора по теме диссертации

Введение
В двадцатом веке, в связи с радикальным усложнением возникающих задач оптимизации, возникла потребность в развитии математического аппарата, поддерживающего принятие решений. Возникла новая область математики, названная исследованием операций. Деятельность исследователя операций при поддержке принятия наилучших решений состоит из следующих этапов: анализ реальной проблемы и составление математической модели; разработка алгоритмов нахождения оптимального решения в полученной модели; корректировка модели в случае, если полученное решение оказывается практически неприемлемым.
Математическую модель реальной задачи принятия решения в общем случае можно представить в виде
/(ж) -+ min, (*)
где множество V. определяет область доступных для выбора вариантов (допустимых решений), функция / : О, —> R, называемая целевой функцией, определяет критерий, позволяющий сравнивать различные решения.
Если множество О, в задаче (*) конечно, ее называют задачей дискретной оптимизации. Любую такую задачу можно решить, рассмотрев все элементы множества Д. Однако мощность множества О может оказаться слишком большим для осуществления полного перебора в обозримое время. В частности, его размер может экспоненциально возрастать с ростом длины

В статье [19] рассматривается более сложный алгоритм UD ("Up-Down"), состоящий из нескольких этапов, сочетающих упаковку "Bottom-Left" с упорядочением по убыванию ширины прямоугольников и обобщение алгоритма "Next Fit Decreasing Height" (подробное описание всех этапов см. в [19]). Доказывается следующая теорема.
Теорема [19]. UD(L) < 1,25 * SPP*(L) + Щ1тах для всех L.
Доказательство теоремы представляет собой разбор случаев, для каждого из которых строится вспомогательная функция, играющая роль, аналогичную представленной выше функции А(Ь). Эти функции оценивают оптимум снизу и величину UD(L) сверху.
В первом из трех случаев оптимум оценивается как
SPP*(L) > Нх + Н2/2,
где Hi — суммарная длина прямоугольников, имеющих ширину меньше заданной величины, а Н2 — суммарная длина остальных прямоугольников. Заметим, что оптимум RCSP*(L) не меньше оптимума SPP*(L), где список L получен из L заменой каждой работы с параметрами (Wj,lj) на lj работ ширины Wj и единичной длины (так как любое допустимое расписание для списка L представляет упаковку списка L с дополнительным ограничением — прямоугольники единичной длины, полученные из одного и того же исходного, должны быть размещены в последовательных единичных слоях). Ввиду того, что параметр «суммарная длина прямоугольников, имеющих ширину из заданного диапазона» для списков L и L одинаков, приведенная нижняя оценка остается верной и для RCSP.