Публикация Школы траблшутеров

Топологическая сортировка: как выстроить работы без споров и простоев

Время чтения: 8 мин 30 сек
05 ноября 2026 Просмотров: 12

Шесть месяцев отвели на ремонт клиники, а поставщики раз за разом подбивали начать монтаж оборудования раньше отделки, чтобы быстрее получить деньги за поставку и настройку. Основатель «Школы траблшутеров», экс-директор Альфа-Банка по процессам, Олег Брагинский рисует топологическую сортировку и поиск циклов в трёх нотациях.

Топологическая сортировка: как выстроить работы без споров и простоев

Рис. 1. Алгоритм Кана: работа встаёт в очередь, как только готовы все предшественники

Когда открывали пилотное отделение нового типа, хотели уложиться в 180 дней. Тщательно прорабатывали «что после чего», но единого списка не сделали, поэтому по ходу много раз спорили. С трудом, но в срок уложились, и больше таких нервов точно не хочется.

Короткий ответ: топологическая сортировка выстраивает работы так, чтобы каждая шла после всех, от которых зависит. Алгоритм Кана берёт в работу то, что уже готово, и заодно находит циклы – работы, ждущие друг друга. Если единый список связей полон, порядок находится за секунды, а споры о том, что делать раньше, заканчиваются.

Рисовать порядок работ руководителю удобнее всего сетевым графиком: стрелка показывает «после чего», и пропущенную связь видно сразу. У участников перед глазами одна картинка вместо десятка версий в головах.

Что такое топологическая сортировка?

Топологическая сортировка – способ выстроить работы в цепочку так, чтобы ни одна не стояла раньше той, от которой зависит. Исходные данные – единый список пар «что после чего», результат – порядок, по которому можно идти без споров.

Например, отделка идёт после ремонта и электрики, открытие – после монтажа и найма.

Порядков обычно несколько: независимые работы – скажем, закупку оборудования и подбор персонала – можно свободно менять местами. Порядка нет только в одном случае – когда работы ждут друг друга по замкнутому кругу.

Как устроен алгоритм Кана?

Алгоритм Кана – способ топологической сортировки, в котором у каждой работы считают число невыполненных предшественников. Работы с нулём встают в очередь готовых. Взяв работу, уменьшают счётчик у последователей, и новые нули тоже встают в очередь.

По ГОСТ 19.701 это цикл с ромбом «Очередь пуста?». Когда очередь опустела, второй ромб проверяет, все ли работы попали в порядок. Если нет, оставшиеся ждут друг друга. Метод опубликовал Артур Кан в 1962 году.

Как выглядит порядок на примере?

Сервисная компания «Кедр» запускает новую точку: восемь работ от проекта помещения до открытия. Отделка ждёт ремонта и электрики, монтаж оборудования – отделки и закупки, открытие – монтажа и найма персонала.

Сетевой график – способ нарисовать работы рамками, а зависимости – стрелками. Слева направо читается порядок, а длительность в рамке подсказывает, где ждать дольше.

image html

Рис. 2. Восемь работ и девять стрелок «после чего»

Алгоритм Кана проходит восемь шагов. Сначала в очереди проект и найм: у них нет предшественников. После проекта готовы ремонт, электрика и закупка, затем отделка.

image html

Рис. 3. Восемь шагов: очередь, взятая работа и счётчики последователей

Порядок: проект, найм, ремонт, электрика, закупка, отделка, монтаж, открытие. Найм можно поставить в любое место до открытия – такую свободу и даёт сортировка.

Почему волны медленнее?

Развёртывая сеть заправок по стране, хотели действовать системно: сначала одна группа команд и поставщиков выполняет часть работ, потом в дело вступает следующая волна.

Ближе к концу срока поняли, что не стоит играть в системность слоёв. Лучше делать всё независимо, допуская неравномерную готовность объектов, но вычисляя её в процентах.

На примере «Кедра» разница видна в неделях. Волна ждёт самую долгую работу предыдущей: отделка стартует только после четырёхнедельной закупки, хотя нужны ей лишь ремонт и электрика. Волнами выходит 14 недель, по готовности – 11, на 21% быстрее.

image html

Рис. 4. Волнами – 14 недель, без волн – 11

Алгоритм Кана не требует волн: работа встаёт в очередь, как только готовы все предшественники. Готовность объекта удобно считать долей выполненных работ общего списка.

Что бывает, если нарушить порядок?

Когда с супругой открывали клинику «вГолливуд», сделал проект в MS Project и надеялся уложиться с ремонтом за шесть месяцев. Несколько раз поставщики подбивали нарушить ход работ, чтобы быстрее получить деньги за поставку, монтаж или настройку.

В разные периоды работы начинали раньше тех, от которых они зависели. Понесли временные потери, а однажды смонтировали много дорогостоящего оборудования, которое пришлось накрывать плёнкой от строительной пыли. Всё равно по мелочам немного поцарапали.

На сетевом графике «Кедра» это стрелка «отделка – монтаж». Поставщику выгодно поставить технику сразу после закупки, а отделка ещё идёт. Нарушенная стрелка выглядит как экономия, а оборачивается пылью, укрытиями и переделками.

Как найти работы, замкнутые в круг?

Начали ИТ-трансформацию – дорогостоящую масштабную программу. Нам казалось, что ждём английских консультантов, а им казалось, что они ждут, пока мы пройдём обучение в IBM.

Потеряли пару недель драгоценного времени. Проект сдали в срок только на морально-волевых.

Алгоритм Кана ловит такую ловушку сам: у консультантов и обучения счётчики не обнуляются, очередь пустеет, а две работы остаются вне порядка. Разорвать цикл может только решение руководителя: кто-то начинает первым, не дожидаясь другой стороны.

Матрица зависимостей – способ записать связи таблицей: строки и столбцы – те же работы, точка означает «строка нуждается в столбце». Матрицу описал Дональд Стюард в 1981 году.

image html

Рис. 5. Матрица зависимостей «Кедра» и цикл из двух работ

Если работы стоят в верном порядке, все точки лежат ниже диагонали. Точка выше диагонали значит, что работа ждёт ту, что стоит позже. У ИТ-трансформации точки по обе стороны диагонали – консультанты и обучение ждали друг друга.

Сколько длится расчёт?

Алгоритм Кана просматривает каждую работу и каждую связь один раз. Для восьми работ и девяти связей «Кедра» – около двадцати действий, для 10’000 работ и 50’000 связей – доли секунды. Дольше всего – не вычисления, а сбор единого списка связей.

Когда уместна топологическая сортировка?

Там, где работ много, а связи между ними известны: открытие отделений, переезд, запуск продукта, миграция систем, ремонт. Если связи неизвестны, алгоритм не поможет – начинать надо с единого списка «что после чего».

Сортировка отвечает только на вопрос «в каком порядке», но не «к какому сроку». Срок проекта определяет самая длинная цепочка работ.

В следующей статье сборника – метод критического пути: как найти работы, задержка которых сдвигает весь проект.

Какими нотациями рисовать порядок работ?

ГОСТ 19.701 точно передаёт алгоритм Кана, но не сами работы и связи. Его ценят авторы методик планирования: схема одна на все проекты.

Сетевой график показывает работы и стрелки зависимостей. Его любят руководители проектов: нарушенную стрелку видно сразу, а длительности подсказывают, где ждать дольше.

Матрица зависимостей компактна и ловит циклы точкой выше диагонали. Ею пользуются инженеры сложных изделий: сотня работ помещается на экран, а ИИ читает её без потерь.

Какая нотация лучше?

Лучшая нотация для порядка работ – сетевой график: 20 баллов против 19 у матрицы зависимостей и 16 у ГОСТ. Руководитель за минуту видит, что после чего и где поставщик торопит. Вес вопроса о руководителе удвоен: сборник написан для него.

image html

Рис. 6. Оценка трёх нотаций: 16, 20 и 19 баллов

Матрица отстала на балл и лучше на больших проектах, где график превращается в паутину. ГОСТ остаётся для методики планирования.

Что сделать руководителю?

Хватит четырёх шагов:

  1. Соберите единый список «что после чего» до начала работ, а не по ходу.
  2. Выстройте порядок алгоритмом Кана и проверьте, все ли работы в него попали.
  3. Работы вне порядка разберите как цикл: решите, кто начинает первым.
  4. Запускайте работы по готовности предшественников, а не волнами.

Что запомнить?

  • топологическая сортировка ставит каждую работу после всех, от которых она зависит
  • алгоритм Кана берёт в работу то, что уже готово
  • работы, не попавшие в порядок, ждут друг друга по кругу
  • запуск по готовности быстрее запуска волнами
  • порядок работ лучше всего рисовать сетевым графиком.