@Xymis

Какой алгоритм применить для решения задачи?

Встала необходимость оптимизировать некоторые процессы на предприятии
Есть целая куча скриптов запускающихся по крону и каждый отрабатывает примерно за одно время
Разобрался с matplotlib и в итоге график будет иметь следующий вид:
60eacd192b427065188137.png
На горизонтальной оси время старта и окончания работы каждого скрипта
По вертикальной, соответственно, идентификаторы скриптов
Необходимо найти алгоритм оптимизации, чтоб в каждый момент работало минимальное кол-во скриптов
Передаваться будет время запуска каждого скрипта и время его работы
На выходе ожидается предлагаемое алгоритмом время запуска каждого скрипта, чтоб пересечение их работ было минимальным
  • Вопрос задан
  • 121 просмотр
Решения вопроса 1
@dmshar
А в чем проблема?
1. Выбрать некоторое множество скриптов так, что-бы сумма времен их работы была максимально близка но меньше 24 часов.
2. Выбранные скрипты формируют отдельную последовательность скриптов. Выбросить выбранные скрипты из рассматриваемого пула.
3. Если пул скриптов не пуст - перейти к п.1. В противном случае - закончить.
Получаем некое количество последовательностей скриптов. Каждая такая последовательность запускается параллельно и независимо от других. Элементы в каждой из этих последовательностей можно запускать в произвольном порядке.
Количество таких последовательностей - минимально возможное. А следовательно, минимально и количество скриптов, которые будут работать параллельно.

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

P.S. Ни к Матстатистике ни к Python задача отношения не имеет. Да и к Аналитике - тоже. Типичная задача исследования операций.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы