Как разбить набор зависимых шагов на группы

Question

У меня есть набор шагов для выполнения, каждый со временем (в минутах).

У меня также есть набор зависимостей (т.е. шаг 7 должен появиться после шага 5).

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

Очевидно, что, если зависимости не дают линейный порядок, существуют различные способы организации этапов, легко или возможно разработать наиболее оптимальные (т. Е. Требуется наименьшее количество групп).

В настоящее время мои шаги и зависимости находятся в SQL, но я бы с удовольствием имел решение на другом языке.

Answer 1

Если нет зависимостей, это проблема с упаковкой NP-hard bin. У упаковки бина есть некоторые умные точные алгоритмы, но я не уверен, как их адаптировать, и их сложно реализовать в любом случае. Вот аналог довольно хорошего аппроксимации первого приближения (11/9 асимптотического приближения для оригинала, нет идеи, если новая версия будет хорошей).

Сначала сбросьте все задачи и их зависимости из своей базы данных. Топологически сортируйте задачи, используя вариант Kahn's algorithm, где среди всех задач, зависимости которых были выбраны ранее, выберите наиболее длинный, чтобы быть следующим. Запланируйте эту задачу в первой группе, где она подходит и не предшествует зависимости.