Главная » 2014 » Август » 12 » Скачать Исследование сложности задач календарного планирования с ограниченными ресурсами и разработка алгоритмов их решения. Щербинина, бесплатно
9:39 PM
Скачать Исследование сложности задач календарного планирования с ограниченными ресурсами и разработка алгоритмов их решения. Щербинина, бесплатно
Исследование сложности задач календарного планирования с ограниченными ресурсами и разработка алгоритмов их решения
Диссертация
Автор: Щербинина, Татьяна Александровна
Название: Исследование сложности задач календарного планирования с ограниченными ресурсами и разработка алгоритмов их решения
Справка: Щербинина, Татьяна Александровна. Исследование сложности задач календарного планирования с ограниченными ресурсами и разработка алгоритмов их решения : диссертация кандидата физико-математических наук : 05.13.18 / Щербинина Татьяна Александровна; [Место защиты: Ин-т вычисл. математики и мат. геофизики] - Омск, 2009 - Количество страниц: 101 с. Омск, 2009 101 c. :
Объем: 101 стр.
Информация: Омск, 2009
Содержание:
Введение
1 Задачи календарного планирования с ограниченными ресурсами
11 Постановка общей задачи календарного планирования с ограниченными ресурсами
12 Частные случаи задач календарного планирования с ограниченными ресурсами
13 Задача календарного планирования проектов с критерием чистой приведенной прибыли
14 Модель целочисленного линейного программирования
2 Анализ сложности задач календарного планирования со складируемыми ресурсами
21 Алгоритмическая сложность решения задач
22 О сложности задачи календарного планирования с критерием средневзвешенного времени выполнения работ
23 Сложность задачи календарного планирования с критерием чистой приведенной прибыли
24 Псевдополиномиальные алгоритмы решения задач календарного планирования при независимых работах
3 Алгоритмы нахождения точного решения некоторых задач календарного планирования
31 Алгоритмы, основанные на методе динамического программирования
32 Алгоритмы ветвей и границ решения задач календарного планирования
33 Гибридный алгоритм решения задач календарного планирования с ограниченными ресурсами
4 Аппроксимационные схемы для некоторых задач календарного планирования с возобновимыми ресурсами
41 Предварительные сведения
42 Задача календарного планирования с критерием общего времени завершения работ
43 Задача календарного планирования с критерием среднего времени завершения всех работ
44 Разномаршрутная задача теории расписаний
Введение:
Задачи календарного планирования возникают в различных сферах деятельности, в том числе при проектировании новых изделий и запуске их в производство, составлении расписаний движения транспорта, планировании графиков выпуска и доставки продукции, разведке и освоении месторождений и т. д. Разнообразие приложений делает это направление весьма актуальным в области математических моделей и методов оптимизации.
Научный подход к календарному планированию проектов предложен и применен в конце 50-х годов прошлого века. Были разработаны такие технологии как PERT (Project Evaluation and Review Technique) [46, 65] и CPM (Critical Path Method) [71, 75]. Характерной особенностью этих технологий является представление проекта в виде комплекса взаимосвязанных работ. Однако возможности указанных разработок были ограничены, так как в них не учитывались реальные ограничения на используемые ресурсы.
В дальнейшем, после создания теории сложности, было установлено, что большинство задач календарного планирования с учетом ограничений на ресурсы являются iVP-трудными. Эти задачи можно рассматривать, например, как обобщения разномаршрутной задачи теории расписаний (Job-shop) [47], задачи построения конвейерного расписания (Flow-shop)\58], задачи с параллельными приборами [92], задача о камнях [57] и т. д.
В настоящее время ведутся исследования структуры и вычислительной сложности указанных задач календарного планирования, выделяются полиномиально разрешимые случаи, развиваются точные и приближенные методы их решения [7,12,16,22,28,36—38,48,50,62]. Особую актуальность эти задачи приобретают при планировании крупномасштабных проектов, требующих больших затрат ресурсов [10, 8, 9, 81].
Среди подходов к получению оптимальных решений задач календарного планирования следует выделить схему динамического программирования [2], метод ветвей и границ [8 — 10,81], различные алгоритмы комбинаторного типа [11, 14, 16, 23, 36, 37, 57, 61].
Другим перспективным направлением является сведение задач построения расписаний к задачам целочисленного линейного программирования (ЦЛП). Данный подход используется, например, в [10, 81]. В ряде известных методов решения задач ЦЛП применяется приведение исходной задачи к последовательности задач непрерывной оптимизации. На таком подходе основаны алгоритмы отсечения [4, 15, 18, 39, 42], ветвей и границ [20, 42], декомпозиции [45], перебора L-классов [19| и др.
Задачи календарного планирования с ограничениями па ресурсы можно разбить два класса. К первому относятся задачи с временными критериями (общее или средневзвешенное время завершения всех работ, штраф за нарушение директивных сроков, число невыполненных в срок работ и т. д. [47,49 — 51,59,72]). Ко второму классу - задачи с критериями, связанными с эффективным использованием ресурсов или получением прибыли, в частности, задачи минимизации общего потребления ресурсов (Resource leveling problem), сглаживания потребляемых ресурсов [Resource Investment problem), максимизации чистой приведенной прибыли (Net Present Value problem) [53, 68, 72]. В диссертации рассматриваются задачи из обоих классов.
Ограниченные ресурсы, используемые при выполнении работ, в основном делятся на возобновимые и складируемые. Возобновимые ресурсы доступны в каждый момент времени. При этом общий расход ресурса, требуемого для выполнения всех работ в момент времени t, не должен превосходить имеющегося объема ресурса. Представителями данного типа ресурсов являются рабочая сила, оборудование, производственные мощности и т. п. Складируемые ресурсы в отличие от возобновимых ресурсов доступны на протяжении всего проекта. В период времени t невостребованный объем складируемого ресурса переходит на следующий период времени. При этом в каждый момент t должен сохраняться баланс между потребляемым и выделяемыми объемами ресурсов. Примером данного вида ресурсов могут служить материалы с длительным сроком хранения: финансы, сырье и т. д.
Наиболее изучена задача календарного планирования с возобновимыми ресурсами и критерием общего времени завершения всех работ. Для данной задачи в [44, 53, 68, 69, 90] предложены алгоритмы точного и приближенного решений. Однако задачи такого типа с другими критериями оптимизации исследованы относительно слабо, поэтому возникает необходимость в построении как точных, так и приближенных алгоритмов решения таких задач.
В связи со сложностью рассматриваемых задач значительное число исследований посвящено разработке приближенных алгоритмов с гарантированной оценкой точности. Особое значение имеют аппроксимационные схемы, с помощью которых за полиномиальное время от длины входа можно получить решение задач с любой наперед заданной точностью. Такой иодход использовали в [5, 67, 73] и других работах. Построение аппроксимаци-онных схем решения NP-трудных задач является одним из перспективных направлений дискретной оптимизации.
Определенные успехи достигнуты при исследовании задачи календарного планирования со складируемыми ресурсами, в которых минимизируется общее время завершения всех работ [6, 8 — 10,14,16] Было доказано, что данная задача является полиномиально разрешимой [7] и предложен алгоритм ее решения. Поэтому актуальным является исследование сложности указанных задач с другими критериями оптимизации.
Целью диссертационной работы является исследование задач календарного планирования с ограниченными ресурсами и различными критериями оптимизацрщ, построение и анализ алгоритмов решения данных задач.
Диссертация состоит из введения, четырех глав и заключения.
