Представлены оригинальные постановка и алгоритмы решения одной из прикладных задач теории расписаний. Рассматриваемая задача оптимального управления флотом авиакомпании заключается в таком оперативном регулировании расписаний, которое минимизирует потери авиакомпании от нарушений заданных графиков движения воздушных судов. Данная задача обладает NP-полнотой и не может быть решена точно для сколько-нибудь реальных размерностей. Предложен параметрический эффективный алгоритм ее приближенного решения, являющийся расширением подобного алгоритма оптимизации расписаний системы несвязанных параллельных приборов с задержками начала обслуживания по критерию быстродействия (Сmax). Параметр алгоритма задает число анализируемых промежуточных вариантов расписания на каждом шаге и соответственно число отсеиваемых локально наихудших вариантов. Это позволяет гибко регулировать общую трудоемкость и точность получаемых корректирующих расписаний. Приведены содержательный пример применения алгоритма и статистика его тестирования на данных порождающей задачи по критерию Сmax. В дополнение к параметрическому алгоритму предложен улучшающий обменный алгоритм, позволяющий на завершающих шагах параметрического алгоритма конструировать улучшенные по критерию Сmax расписания. Приведены результаты вычислительных экспериментов с применением обоих алгоритмов на сгенерированных примерах приближенных к реальным размерностей, которые показали высокую общую эффективность подхода.
Исследование выполнено при финансовой поддержке Министерства науки и высшего образования РФ (проект \No~2.2327.2017/PCh); НГТУ (темплан НИР НГТУ), проект
ТП-ЭИ-1_17.
Мезенцев Ю.А., Эстрайх И.В. Об одной задаче оптимального оперативного управления движением воздушных судов авиакомпании // Доклады АН ВШ РФ. – 2018. – № 3 (40). – C. 74–90. doi: 10.17212/1727-2769-2018-3-74-90
Mezentsev Yu.A., Estraykh I.V. Ob odnoi zadache optimal'nogo operativnogo upravleniya dvizheniem vozdushnykh sudov aviakompanii [An optimal fleet assignment and flight scheduling problem for an airline company]. Doklady Akademii nauk vysshei shkoly Rossiiskoi Federatsii – Proceedings of the Russian higher school Academy of sciences, 2018, no. 3 (40), pp. 74–90. doi: 10.17212/1727-2769-2018-3-74-90.