Состоялся научный семинар МЛАВР НИУ ВШЭ
Докладчики: Лазарев А.А. (профессор, ведущий научный сотрудник МЛАВР НИУ ВШЭ, заведующий лабораторией ИПУ РАН) и Петров А. (стажер-исследователь МЛАВР)
Тема: Модели и алгоритмы решения задач объемно-календарного планирования подготовки экипажа МКС
Среди множества разнообразных задач, возникающих в космонавтике, особое место занимают задачи планирования. Для планирования действий космонавтов необходимы подробные расписания проводимых на МКС работ, а также расписания подготовки космонавтов. На сегодняшний день их разработка требует достаточно большого количества человеческих, временных и материальных ресурсов.
Полная подготовка космонавтов является очень длительным, дорогостоящим и технически сложным процессом. Это комплекс мероприятий, направленных на формирование и поддержание у космонавтов совокупности определенных знаний, навыков и умений, необходимых для надежного и безопасного выполнения программы космического полета и составляющих основу квалификации космонавта.
Предметом деятельности экипажа, согласно принятой в РКК «Энергия» формулировке, являются бортовые комплексы (БК): бортовые системы, научные эксперименты, полетные операции.
По каждому БК космонавт должен обладать определенной квалификацией. Квалификация отражает уровень профессиональной подготовки космонавта по данному БК. Уровню квалификации космонавта по конкретному БК соответствует однозначное подмножество задач по данному БК, которое он может выполнять, по которому он был сертифицирован в процессе подготовки. Квалификация пользователя позволяет выполнять определенный набор задач по определенному бортовому комплексу. Квалификация оператора позволяет выполнять все задачи, предназначенные для космонавта с квалификацией пользователя, а также некоторое множество дополнительных задач. Квалификация специалиста позволяет космонавту выполнять все задачи по данному БК. По разным БК у космонавта может быть разная квалификация.
Всё планирование подготовки космонавтов МКС можно логически разделить на два этапа: задача объёмного планирования и задача календарного планирования.
Исходные данные задачи объёмного планирования представляют собой известный набор БК и требуемое количество космонавтов различной квалификации для каждого БК. Задача состоит в том, чтобы распределить подготовку по квалификациям БК между космонавтами с одной из следующих целевых функций:
- максимальное общее время подготовки одного космонавта должно быть минимальным;
- минимальное общее время подготовки одного космонавта должно быть максимальным;
- разность между максимальным и минимальным общим временем подготовки одного космонавта должно быть минимальным.
Для задачи объёмного планирования были разработаны математическая модель и три алгоритма. Идея первого алгоритма состоит в разбиении всей задачи на независимые составляющие по БК и в выборе наилучшего распределения на каждой итерации алгоритма. Второй алгоритм схож с первым, его идея состоит в присвоении наиболее продолжительной подготовки космонавту с наименьшим общим временем подготовки на каждой итерации. Третий алгоритм основывается на методах решения задач целочисленного программирования.
Был проведён сравнительный анализ всех трёх алгоритмов. Наилучшей точностью обладает третий алгоритм, но все равно не гарантируется, что полученные значения являются оптимальными. Очевидные корреляции в распределении работ со средними и малыми длительностями в алгоритмах 2 и 3 не наблюдаются.
Следующим важным этапом планирования подготовки является задача календарного планирования. После того, как решена задача объёмного планирования, для каждого космонавта определен набор БК, по которым ему необходимо подготовиться, также заданы необходимые ему квалификации по этим бортовым комплексам. Необходимо составить план подготовки по времени, но при этом соблюсти ресурсные ограничения и директивные сроки подготовки всех экипажей.
Поставленная задача календарного планирования является задачей построения проекта с ограничением на ресурсы (RCPSP). Как известно, такую задачу можно поставить в виде задачи целочисленного программирования. Для решения были применены методы решения задач целочисленного программирования, пакет-решатель CPLEX.