Топологическая сортировка и её применение (возможное) на производстве и других процедурах предприятия от кладовщика до бухгалтера и главного инженера

Топологическая сортировка - это алгоритм упорядочивания вершин ориентированного ациклического графа (DAG) таким образом, что для каждого ориентированного ребра (u, v) вершина u идет в упорядочении раньше вершины v. Проще говоря, это способ выстроить задачи в таком порядке, чтобы каждая задача выполнялась только после того, как будут выполнены все задачи, от которых она зависит.

Представление графа:

Представим граф в виде таблицы значений, где каждая строка представляет вершину, а колонки:

• Идентификатор (Строка): Уникальный идентификатор вершины.
• Зависимости (Строка): Список идентификаторов вершин, от которых зависит данная вершина, разделенных запятыми (или другим разделителем).

Разберем процедуру топологической сортировки (где Граф - это наша таблица на форме с строковыми колонками):

 &НаСервере
Функция ТопологическаяСортировка(Граф) Экспорт

    // 1.  Создаем копию графа (чтобы не менять исходный)
    ГрафКопия = Граф.Скопировать();

    // 2.  Находим вершины без входящих ребер (источники)
    Источники = Новый Массив;
    Для Каждого СтрокаГрафа Из ГрафКопия Цикл
        Если СтрокаГрафа.Зависимости.Количество() = 0 Тогда
            Источники.Добавить(СтрокаГрафа);
        КонецЕсли;
    КонецЦикла;

    // 3.  Инициализируем результат
    Результат = Новый Массив;

    // 4.  Основной цикл
    Пока Источники.Количество() > 0 Цикл

        // 4.1.  Берем вершину из источников
        Вершина = Источники[0];
        Источники.Удалить(0);

        // 4.2.  Добавляем вершину в результат
        Результат.Добавить(Вершина.Вершина);

        // 4.3.  Удаляем вершину из зависимостей других вершин
        Для Каждого СтрокаГрафа Из ГрафКопия Цикл
            ИндексЗависимости = СтрокаГрафа.Зависимости.Найти(Вершина.Вершина);
            Если ИндексЗависимости <> Неопределено Тогда
                СтрокаГрафа.Зависимости.Удалить(ИндексЗависимости);

                // 4.4.  Если после удаления зависимостей у вершины не осталось входящих ребер,
                // добавляем ее в источники
                Если СтрокаГрафа.Зависимости.Количество() = 0 Тогда
                    Источники.Добавить(СтрокаГрафа);
                КонецЕсли;
            КонецЕсли;
        КонецЦикла;

        // 4.5. Удаляем обработанную вершину из графа
        ГрафКопия.Удалить(ГрафКопия.Найти(Вершина.Вершина, "Вершина"));


    КонецЦикла;

    // 5. Проверяем, остались ли в графе вершины. Если да, то в графе есть цикл.
	Если ГрафКопия.Количество() > 0 Тогда  
		Возврат "Ошибка: В графе обнаружен цикл!";
    КонецЕсли;

    // 6. Возвращаем результат
    Возврат Результат;

КонецФункции

Перед сортировкой "Зависимости" перегоняем в "Массив".

Как работает обработка:

1. Пользователь заполняет табличное поле "Граф".
   • В колонке "Идентификатор" указывается уникальный идентификатор вершины.
   • В колонке "Зависимости" указывается список идентификаторов вершин, от которых зависит данная вершина, разделенных запятыми (например, "B, C, D", или "3,4,5" если используем цифры вместо букв).
2. Пользователь нажимает кнопку "Выполнить сортировку".
3. Код получает данные из табличного поля, преобразует строку зависимостей в массив и вызывает функцию топологической сортировки.
4. Результат сортировки выводится в окно сообщений.

Ну а теперь практика, притянем к производству.

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

Производство велосипеда

Пусть у нас есть следующие задачи по производству велосипеда:

• A: Собрать раму велосипеда.
• B: Изготовить переднее колесо.
• C: Изготовить заднее колесо.
• D: Покрасить раму.
• E: Установить руль.
• F: Установить сиденье.
• G: Установить тормоза.
• H: Установить колеса на раму.
• I: Установить трансмиссию (цепи, звезды, переключатели).
• J: Проверить качество сборки.

Зависимости:

• A зависит от D (сначала нужно покрасить раму, потом собирать)
• B ни от чего не зависит (можно начинать сразу)
• C ни от чего не зависит (можно начинать сразу)
• D ни от чего не зависит (можно начинать сразу)
• E зависит от A (руль устанавливается на раму)
• F зависит от A (сиденье устанавливается на раму)
• G зависит от A (тормоза устанавливаются на раму)
• H зависит от A, B, C (колеса устанавливаются на раму и нужно иметь готовые колеса)
• I зависит от A (трансмиссия устанавливается на раму)
• J зависит от E, F, G, H, I (проверять качество можно только после установки всех компонентов)

Результат топологической сортировки:

B, C, D, A, E, F, G, I, H, J

Этот результат говорит нам, в каком порядке следует выполнять задачи для производства велосипеда:

1. B: Изготовить переднее колесо.
2. C: Изготовить заднее колесо.
3. D: Покрасить раму.
4. A: Собрать раму велосипеда.
5. E: Установить руль.
6. F: Установить сиденье.
7. G: Установить тормоза.
8. I: Установить трансмиссию (цепи, звезды, переключатели).
9. H: Установить колеса на раму.
10. J: Проверить качество сборки.

Этот пример демонстрирует, как топологическую сортировку можно использовать для планирования и оптимизации производственных процессов.

Топологическая сортировка в 1С:ERP может быть полезна в следующих областях:

1. Планирование производства и управление производственными заказами:

• Определение последовательности операций: Как показано в предыдущем примере, топологическая сортировка позволяет определить оптимальный порядок выполнения производственных операций, учитывая зависимости между ними. Это может быть использовано для автоматизации планирования производственных маршрутов и определения приоритетов задач.
• Разрешение конфликтов зависимостей: В сложных производственных процессах могут возникать ситуации, когда зависимости между операциями становятся неясными или противоречивыми. Топологическая сортировка может помочь выявить такие конфликты и определить, какие операции необходимо перепланировать или выполнить параллельно.
• Оптимизация использования ресурсов: Топологическая сортировка может быть интегрирована с механизмами планирования ресурсов (оборудование, персонал, материалы) для оптимизации их использования и минимизации простоев. Например, можно спланировать выполнение операций таким образом, чтобы ресурсы были доступны в нужный момент и не простаивали в ожидании завершения других задач.

2. Управление проектами и задачами:

• Планирование этапов проекта: В проекта топологическая сортировка может быть использована для определения приоритетов задач, особенно если задачи взаимосвязаны. Задачи, от которых зависят другие задачи, должны быть выполнены в первую очередь.

3. Управление бизнес-процессами:

• Анализ бизнес-процессов: Топологическая сортировка может быть использована для анализа существующих бизнес-процессов с целью выявления узких мест и оптимизации последовательности шагов.

4. Управление жизненным циклом продукции (PLM):

• Управление изменениями: При внесении изменений в конструкцию изделия необходимо пересмотреть все связанные с ним процессы. Топологическая сортировка может помочь определить, какие этапы жизненного цикла продукции (проектирование, производство, испытания, и т.д.) необходимо изменить в первую очередь, чтобы обеспечить согласованность всех процессов.

5. Интеграция с другими системами:

• Построение ETL-процессов (Extract, Transform, Load): При интеграции 1С:ERP с другими системами часто требуется выполнять преобразование данных и загрузку их в целевую систему. Топологическая сортировка может быть использована для определения последовательности выполнения задач ETL, учитывая зависимости между ними.

Топологическая сортировка в компьютерной архитектуре: планирование выполнения инструкций

В компьютерной архитектуре топологическая сортировка находит своё применение в задачах планирования выполнения инструкций, особенно в конвейерных процессорах (pipelined processors) и системах с внеочередным выполнением (out-of-order execution).

Суть применения:

1. Представление инструкций как графа: Инструкции в программе можно представить как вершины графа. Если инструкция B зависит от результата инструкции A (например, B использует значение, вычисленное A), то между A и B создаётся направленное ребро (A -> B). Такой граф называется графом зависимостей данных (data dependency graph).

2. Зависимости между инструкциями:

   • Зависимость по данным (Data Dependency): Инструкция B использует результат, вычисленный инструкцией A.
     • RAW (Read After Write): B читает данные, которые были записаны A. Это наиболее распространенный тип зависимости.
     • WAR (Write After Read): B записывает данные, которые были прочитаны A.
     • WAW (Write After Write): B записывает данные в то же место, куда записывала A.
   • Зависимость по управлению (Control Dependency): Выполнение инструкции зависит от результата условного перехода (например, if statement).
   • Зависимость по ресурсам (Resource Dependency): Две инструкции требуют один и тот же ресурс (например, арифметическое устройство, память) в один и тот же момент времени.

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

4. Планирование выполнения: Результат топологической сортировки используется планировщиком (scheduler) процессора для определения последовательности выполнения инструкций. В конвейерных процессорах это позволяет заполнить конвейер инструкциями, минимизируя простои, вызванные зависимостями. В системах с внеочередным выполнением это позволяет выполнять инструкции в порядке, отличном от программного, но с соблюдением всех зависимостей.

Преимущества использования топологической сортировки:

• Правильность: Гарантирует, что инструкции выполняются в правильном порядке с учётом всех зависимостей, обеспечивая корректный результат.
• Оптимизация: Позволяет выявить независимые инструкции, которые могут выполняться параллельно или вне очереди, повышая производительность.
• Эффективность: Алгоритмы топологической сортировки обычно имеют сложность O(V + E), где V — количество инструкций (вершин графа), а E — количество зависимостей (рёбер графа). Это делает их достаточно эффективными для практического применения.

Пример:

Рассмотрим следующий фрагмент кода (условно ассемблерный):

1.  ADD R1, R2, R3  ; R1 = R2 + R3
2.  MUL R4, R1, R5  ; R4 = R1 * R5
3.  SUB R6, R7, R8  ; R6 = R7 - R8
4.  DIV R9, R6, R10 ; R9 = R6 / R10
5.  ADD R11, R4, R9 ; R11 = R4 + R9

Граф зависимостей:

• 1 -> 2 (RAW: инструкция 2 использует результат R1, вычисленный инструкцией 1)
• 3 -> 4 (RAW: инструкция 4 использует результат R6, вычисленный инструкцией 3)
• 2 -> 5 (RAW: инструкция 5 использует результат R4, вычисленный инструкцией 2)
• 4 -> 5 (RAW: инструкция 5 использует результат R9, вычисленный инструкцией 4)

Топологическая сортировка может выдать следующий порядок:

1, 3, 2, 4, 5

В этом порядке инструкция 1 и 3 выполняются первыми (они независимы). Затем 2 и 4, и наконец 5. Такой порядок позволяет, например, начать выполнение инструкции 3, пока инструкция 1 ещё не завершилась.

Дополнительные замечания:

• В реальных процессорах планирование инструкций — гораздо более сложный процесс, чем просто топологическая сортировка. Он учитывает множество факторов, таких как доступность ресурсов, приоритеты инструкций, предсказание переходов и т. д.
• Топологическая сортировка часто используется как один из этапов в более сложных алгоритмах планирования.
• Внеочередное выполнение инструкций (out-of-order execution) позволяет процессору динамически переупорядочивать инструкции во время выполнения, чтобы максимально использовать доступные ресурсы и минимизировать простои.

Вот так математические алгоритмы применимы и в компьютерной архитектуре, и в реализации 1С задач.