По легенде хакатона участники должны восстановить боевую мощь Империи ситхов после разрушения Звезды Смерти. Для этого им в распоряжение предоставляется завод на окраинах галактики. Команды должны составить расписание работы предприятия, то есть рассчитать, как долго нужно работать на тех или иных станках, чтобы как можно быстрее и дешевле восстановить боевую мощь Империи.
Задача осложняется массой дополнительных условий, сообщил участник команды Университета ИТМО Виктор Хованский. Например, на заводе есть только 13 рабочих групп, некоторые из них выполняют задания быстрее, но им нужно платить больше, а другие, те же штурмовики, не требуют высокой оплаты, их много, но они работают медленно. Кроме того, необходимо было учесть особенности работы самих станков: некоторые комплектующие нельзя было начинать делать, пока не закончены другие определенные детали, например, нельзя ведь собрать Звезду Смерти без генераторов энергии. Серьезно карались и такие ситуации: в расписании стоит сборка деталей для боевого дроида, а вот металл для выплавки изделий еще не доставлен на производство. Или нельзя было допустить, чтобы две группы рабочих пришли работать на один и тот же станок или, наоборот, чтобы какое-то оборудование простаивало, ведь так производство становится дороже, а это невыгодно Империи в кризисный момент.
Необходимо было принимать и стратегические решения, например, каких роботов, как и где использовать. Так, можно было поставить роботов-сварщиков для определенной задачи либо организовать эту же самую задачу на производственной линии, которая единовременно выполняет несколько заказов одного типа. Дело в том, что за одни и те же деньги робот собирает одну деталь быстро, а производственная линия – дольше, но зато сразу 10 экземпляров.
«Составленное расписание работы завода необходимо было оптимизировать по скорости постройки Звезды Смерти и стоимости производства. То есть мы могли использовать только строго определенный объем средств, условные 10 тысяч кредитов, и ресурсов – те самые рабочие группы, а также станки, и с этим всем выстроить максимальную мощность оружия. Кроме того, нужно было хорошо презентовать результаты работы жюри, от этого зависела треть оценки», – прокомментировал другой участник команды Вячеслав Шаламов.
Расписание работы завода должно было быть представлено в виде диаграмм Ганта – это довольно популярный формат для составления планов или графиков в виде столбчатых диаграмм. С их помощью визуально можно было показать, какие группы рабочих, что и где делают в определенное время. На наличие ошибок диаграммы проверяли эксперты от организаторов хакатона – холдинга «Ленполиграфмаш». Так как в составе жюри был только один технический специалист, приоритет отдавался визуальной оценке. На начальных этапах командам было важно показать работающее решение, пускай не самое точное.
«Мы сначала старались делать все как можно более точно алгоритмически и математически, даже начали делать математическое решение для задачи, однако потом выяснилось, что для начала это не главное. Важнее было сделать решение быстро. Поэтому мы разработали эвристический алгоритм, то есть такой, который не будет точным на 100%, но решает наиболее важную сейчас задачу. При этом особенность хакатона была в том, что на отправку решения давалась всего одна попытка, поэтому мы сделали автоматический верификатор расписания, чтобы в нем не было ошибок. Также параллельно с разработкой верификатора писали юнит-тесты для проверки наших алгоритмов», – рассказал Виктор Хованский.
Одним из преимуществ команды Университета ИТМО было использование точной математики, что также отметили эксперты. По мнению жюри, магистранты представили наиболее красивую архитектуру своего алгоритма. Но самое важное то, что это решение является, по сути, универсальным. Это значит, что вместо данных по заводу для строительства Звезды Смерти можно подставить данные о сотрудниках и ресурсах другого завода, и программа автоматически сформирует наиболее эффективное расписание для рабочих, которое при этом удешевит производство.
По словам студентов Университета ИТМО, эксперты жюри конкурса были удивлены, что некоторые другие команды пытались решить задачу не программными методами, а путем обычных подстановок, сравнений, графиков. Однако и сам хакатон требует улучшений. Например, стартовые данные о заводе по строительству Звезды Смерти участникам представили не в автоматизированном виде, а на бумаге. То есть участники потратили немало времени, чтобы просто перенести информацию в компьютер. Также на будущий год организаторы пообещали сделать упор при оценке именно на алгоритмическую составляющую задания.
«Хакатон был очень полезен тем, что мы смогли очень быстро изучить теорию и практику по теории расписаний – это раздел математики, который мы не проходили в вузе», – отметил участник команды Traffox Евгений Варламов.
По итогам конкурса команда вуза, в которую также вошли Сергей Меньшов и Жавлон Исомуродов, заняла третье место. Второе место досталось команде «Исключение из правил» из Санкт-Петербургского горного университета, а первое – команде «Восточный округ» из Военно-космической академии имени А.Ф. Можайского. По мнению жюри, победители продемонстрировали корректные результаты на протяжении всего мероприятия и не ошиблись ни в одном из предложенных заданий, при этом в двух из них достигли самого оптимального результата.
