Исследование сложности задач календарного планирования с ограниченными ресурсами и разработка алгоритмов их решения

• Автор: Щербинина, Татьяна Александровна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Омск
• Количество страниц: 101 с.

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

1. Задачи календарного планирования с ограниченными ресурсами

1.1. Постановка общей задачи календарною планирования с

ограниченными ресурсами.

1.2. Частные случаи задач календарного планировании с ограниченными ресурсами

1.3. Задача календарного планирования проектов с критерием чистой приведенной прибыли

1.4. Модель целочисленного линейного программирования

2. Анализ сложности задач календарного планирования со

складируемыми ресурсами

2.1. Алгоритмическая сложность решения задач

2.2. О сложности задачи календарного планирования с критерием средневзвешенного времени выполнения работ.
2.3. Сложность задачи календарного планирования с критерием чистой приведенной прибыли
2.4. Псевдополиномиальные алгоритмы решения задач календарного планирования при независимых работах .
3. Алгоритмы нахождения точного решения некоторых задач
календарного планирования
3.1. Алгоригмы, основанные на. методе динамического программирования .
3.2. Алгоритмы ветвей и границ решения задач календарного планирования.
3.3. Гибридный алгоритм решения задач календарного планирования с ограниченными ресурсами
4. Аппроксимационные схемы для некоторых задач календарного планирования с возобновимыми ресурсами
4.1. Предварительные сведения.
4.2. Задача календарного планирования с критерием общего времени завершения работ
4.3. Задача календарного планирования с критерием среднего времени завершения всех работ
4.4. Разномаршрутная задача теории расписаний.
Заключение
Литература


К первому относятся задачи с временными критериями (общее или средневзвешенное время завершения всех работ, штраф за нарушение директивных сроков, число невыполненных в срок работ и т. Ко второму классу - задачи с критериями, связанными с эффективным использованием ресурсов или получением прибыли, в частности, задачи минимизации общего потребления ресурсов (Resource leveling problem), сглаживания потребляемых ресурсов (Resource Investment problem), максимизации чистой приведенной прибыли {Net Present Value problem) [, , ]. Ограниченные ресурсы, используемые при выполнении работ, в основном делятся на возобновимые и складируемые. Возобновимые ресурсы доступны в каждый момент времени. При этом общий расход ресурса, требуемого для выполнения всех работ в момент времени ? Представителями данного типа ресурсов являются рабочая сила, оборудование, производственные мощности и т. Складируемые ресурсы в отличие от возобновимых ресурсов доступны на протяжении всего проекта. В период времени I невостребованный объем складируемого ресурса переходит на сле;1ующий период времени. При этом в каждый момент ? Примером данного вида ресурсов могут служить материалы с длительным сроком храпения: финансы, сырье и т. Наиболее изучена задача календарного планирования с возобновимыми ресурсами и критерием общего времени завершения всех работ. Для данной задачи в [. Однако задачи такого типа с другими критериями оптимизации исследованы относительно слабо, поэтому возникает необходимость в построении как точных, так и приближенных алгоритмов решения таких задач. В связи со сложностью рассматриваемых задач значительное число исследований посвящено разработке приближенных алгоритмов с гарантированной оценкой точности. Особое значение имеют аипроксимационныс схемы, с помощью которых за полиномиальное время от длины входа можно получить решение задач с любой наперед заданной точностью. Построение аппроксимаци-опных схем решения ЛГР-трудных задач является одним из перспективных направлений дискретной оптимизации. Определенные успехи достигнуты при исследовании задачи календарного планирования со складируемыми ресурсами, в которых минимизируется общее время завершения всех работ [6,8 — ,,] Было доказано, что данная задача является полиномиально разрешимой |7| и предложен алгоритм ее решения. Поэтому актуальным является исследование сложности указанных задач с другими критериями оптимизации. Целью диссертационной работы является исследование задач календарного планирования с ограниченными ресурсами и различными критериями оптимизации, построение и анализ алгоритмов решения данных задач. Диссертация состоит из введения, четырех глав и заключения. В первой главе описываются модели задач календарного планирования с учетом ограничений на ресурсы и различными критериями оптимизации. В н. Проект состоит из множества взаимосвязанных работ, выполнение которых направлено на достижение определенной цели. Каждая работа характеризуется длительностью, некоторыми ресурсными требованиями и директивными сроками. Необходимо с учетом ограничений на ресурсы определить сроки выполнения всех работ, при которых значение целевой функции является оптимальным. Ь-ькор) [|, задача об упаковке в контейнеры [], задача с параллельными приборами []. Приводится также постановка задачи календарного планирования, в которой мощность множества независимых работ ограниченна константой. В и. Постановка данной задачи отличается от общею случая только одним видом складируемого ресурса (финансового) и наличием потока поступлений. В п. Л -релаксация данной задачи используется для построения верхней оценки (нижней оценки) значений целевой функции в третьей главе. Во второй главе исследуется сложность задач календарного планирования с различными критериями. В и. В п. АР-трудноеть в сильном смысле задачи календарного планирования со складируемыми ресурсами и критерием средневзвешенного времени завершения всех работ. К данной задаче полиномиально сводится задача о максимальной клике. Аналогичный результат получен для задачи календарного планирования проекта с критерием чистой приведенной прибыли.