Разработка программного обеспечения
Создавая действительно полезное
Есть вопросы?

Задайте их нам!

Телефон:

О самом сложном алгоритме разработки

« Назад

О самом сложном алгоритме разработки 20.08.2020 15:15

«На заре карьеры мне поручили разработать алгоритм автоматического составления графика работы машинистов метрополитена», - начал свой рассказ Василий Демченко.

Суть задачи – составить график работы поездных бригад с учетом обязательного перерыва на отдых. Если смена длилась больше 4 часов, то машинистам полагался 30-минутный обед в интервале от 2,5 часов до 4 часов с момента выхода на линию. Если же смена превышала 7 часов, то машинистов ожидал дополнительный 15-минутный отдых в интервале от 6 до 7 часов работы.
Во все предыдущие попытки разработать соответствующий алгоритм получалось распределить только половину рабочего времени. Оставшиеся «хвосты» нужно было обрабатывать вручную, поскольку алгоритм «давал» лишние бригады либо делал «неправильную» смену, по которой невозможно было работать.
Казалось бы, задача была простой: через 30 минут с начала обеда машиниста нужно было вернуть на линию. Однако вскрылась особенность работы метро: машиниста можно было вернуть только в тот же поезд, с которого он начал смену. И вот тут появилась проблема.
Из-за графика движения поездов продолжительность обеденного перерыва «плавала» от 25 до 33 минут в зависимости от времени и дня недели (час пик, будни, выходной), а также от отдельных линий метро. Помимо этого, обедать машинисты могли только на определенных станциях линии. При этом количество одновременно обедающих бригад также было ограничено, так как, пока основная бригада была на перерыве, составом управляла так называемая подменная бригада. А их было немного.
Технически все реализовывалось с помощью T-SQL в рамках хранимых процедур и функций в MS SQL Server. Нужно было взять данные расписания поездов из соответствующей таблицы, посчитать количество маршрутов, и, исходя из длины маршрута и смен, произвести расчет числа необходимых бригад.
Первая итерация алгоритма насчитывала 300 строк кода, с множеством вложенных подзапросов для определения «границ» выборки. По результатам работы первой итерации выяснилось, что по такому расписанию работать невозможно, поскольку в бригадах – люди, а не роботы.
Дальнейшая оптимизация привела к увеличению количества строк кода до 900. Появилась тройная вложенность запросов, вложенные циклы, двойные курсоры, временные таблицы и самописные SQL-функции.
В результате получилось оптимизировать автоматическое составление графика работы на 80%. Оставшиеся 20% составляли «хвосты» смен, которые не позволяли создать полноценную смену для бригады, и их надо было распределять вручную.
Ближе к концу данной работы мне дополнительно поручили задачу автоматического составления графика работ маневровых бригад (это те бригады, которые садятся на конечной или предпоследней станции метро, заводят состав в тупик и выгоняют его обратно). Проблема этих бригад, помимо обеденного перерыва, была еще в продолжительности их работы: всего 2-3 минуты. Из-за этого появлялись накладки в считанные секунды, которые при неправильной настройке выдавали лишнюю 3-5-минутную смену в утренний или вечерний час пик.
Итогом работы стал «монструозный» SQL-скрипт, который был разбит на основную процедуру из 1200 строк кода и в котором многократно вызывались три дополнительные самописные функции по 50-150 строк кода, а также скрипт маневровых бригад на 700 строк.
После окончания разработки выяснилось, что данный скрипт не вписывается в текущие процессы работы депо. В итоге наработки по данному скрипту легли в основу другого ПО, которое позволяло составлять смены в автоматизированном режиме, а не в автоматическом. В дальнейшем основной алгоритм был переделан в алгоритм автоматизированного составления смен для помощников машиниста, который стал моим дипломным проектом.
ПО для автоматизированного составления графика работы позволило сократить количество часов, требуемых на создание нового графика, с 20-30 до 5-6, поскольку ранее данную работу делали вручную с помощью карандаша и ластика на листах формата А1. ПО было полностью внедрено в трех депо и начало внедряться еще в трех. В 2011 году произошла смена директора метрополитена, и проект закрыли.

 


Наверх
Энджиар Софтлаб

Копирование для собственных нужд, с целью распространения, а также любое иное использование материалов и элементов сайта запрещено без письменного согласия ООО «Энджиар Софтлаб»

Телефон: