Анализ сложности и разработка алгоритмов решения задач календарного планирования и теории расписаний

• Автор: Сервах, Владимир Вицентьевич
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2009
• Место защиты: Омск
• Количество страниц: 233 с. : ил.

Оглавление
Введение -
1 Исследование многостадиных задан теории расписаний
1.1 Полиномиально разрешимый случай задачи Джонсона с тремя машинами
1.2 Алгоритм динамического программирования построения точного решения разномаршрутной задачи
1.3 Эффективные алгоритмы решения разномаршрутной задачи
с фиксированным числом деталей
1.4 Полиномиальный алгоритм для разномаршрутной задачи с двумя деталями
1.5 Полиномиально разрешимый случай задачи минимизации времени переналадки оборудования
2 Задачи оптимизации обработки партии однотипных
деталей
2.1 Задача минимизации времени цикла с ограничением на число одновременно обрабатываемых деталей
2.2 Алгоритм решения задачи при условии одновременной обработки на линии не более двух деталей
2.3 Задача минимизации цикла с запретами на простой между операциями
2.4 Минимизация общего срока завершения обработки партии однотипных деталей

3 Задачи календарного планирования проектов
3.1 Постановки задач
3.2 Задача календарного планирования при наличии частичного порядка
3.3 Сложность задач с различными критериями и ресурсными ограничениями . . ■
3.4 Алгоритм решения задачи минимизации общего срока выполнения проектов
3.5 Алгоритмы решения задачи планированиия проектов с различными критериями
3.6 Вполне полиномиальные аппроксимационные схемы для задач с ограниченной шириной частичного порядка
3.7 Гибридный алгоритм для задач календарного планирования
с единичными длительностями работ
4 Задачи максимизации прибыли при планировании проектов
4.1 Календарное планирование проектов с критерием чистой приведенной прибыли
4.2 Сложность задач максимизации прибыли
4.3 Задачи календарного планирования с кредитами и реинвестированием прибыли
4.4 Моделирование рисков при планировании проектов
4.5 Задача выбора проектов
Заключение
Литература

Введение
Теория расписаний и календарное планирование являются одними из важных и интересных направлений в области оптимизации и в настоящее время переживают период бурного развития. Это связано, прежде всего, с появлением принципиально новых видов продукции, технологий, интенсификацией производства, его непрерывным обновлением и совершенствованием. Стремительное развитие систем связи, интернета, логистики ставит перед математиками новые задачи, в том числе в области теории расписаний. На практике возникает множество разнообразных задач календарного планирования производства и сбыта продукции, эффективного использования оборудования и других ресурсов, согласования работы различных служб и так далее. Возникнув в середине 50-х годов прошлого века, теория расписаний усилиями таких ученых, как Глебов Н.И., Михалевич B.C., Танаев B.C., Шкурба В.В., Веллман Р., Бруккер П., Джонсон Д., Джонсон С., Фридман Д. и других превратилась в содержательную научную дисциплину со своей структурой, развитыми исследовательскими подходами [2, 16,26,30,38,82,85,87,89,90,106,129,145,150]. В настоящее время это направление активно развивается в работах Гимади Э.Х, Гордона B.C., Ковалева М.Я., Кононова A.B., Севастьянова С.В., Сотскова Ю.Н., Струсевича В.А., Тимковского В.Г., Войгенгера Г. и многих других российских и зарубежных ученых [12,32,81,83,84,132,134-136,158,159,161,204,205,215,220,221].
Несмотря на огромное количество исследований в этой области, потребность в них не уменьшается. Это связано как с постоянным притоком новых задач, так и с трудностью их решения. Особо актуальным является детальное исследование сложности различных постановок, на основе которого можно делать выводы о существовании или отсутствии эффек-

= bßi + тах{ад + ад+1 + Л»_ь bßl+1 + max{oft+1 + Д_ъ Д-i}} =
= max{bßt + aßi + aßt^ -f A_i, bßt + ftA+1 + ад+1 + Д-_ь bßt + Ьд+1 + Д-i} = = max{bA + ад+1 + Д-i + max{oÄ, ЬАт1}, Ьд + Ьд+1 + Д_ Д. Аналогично убеждаемся в том, что
Д+х(/?) = тах{Ьд+1 + од + Д_х + тах{ад_п Ьд}, Ьд + Ьд+1 + Д-Д.
Для доказательства (1.5) достаточно показать следующее
bß, + ад+1 + тах{ад, 6д+1} < 6д+1 + ад + тах{ад+1, Ьд}
Вычтем из обеих частей неравенства сумму од + ад+1 + bßi + 6д+1. Тогда ЬД + аА+1 + тах{ад, Ьд+1} - (ад + ад+1 + 6Д + Ьд+1) =
=тах{ад, Ьд^} - ад - 6Дт1 = тах{-Ьд+1, -ад}, а
6д+1 + ад + тах{ад+1, &д} - (ад + ад+1 + Ьд + 6д+1) = тах{-6д, -ад+1}. Полученное неравентсво тах{—ад, —Ьд+1} < шах{—ад+1, — 6Д} эквивалентно тт{ад,6д+1} > тт{ад+1,6д}, справедливость которого вытекает из условия ßi £ Y,ßi+i Е X, так как при этом ад > 6Д и ад+1 < Ьд+1. Тем самым соотношение (1.5) доказано.
Неравенство (1.6) докажем от противного. Пусть имеет место Ci+(oi) > Ci+i(ß). Распишем
сд + bßt + ад + ад+1 + Д_ 1 сД + bßt + 6д+1 + ад+1 +

CÄ + bß, + &д+1 + Д-i сД + сд+1 + 6д+1 + ад+1 + Аг_! сД + сд+1 + Ьд+1 + Вг_! сД + сд+1 + Д_х