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

Question

[Xymis]

Встала необходимость оптимизировать некоторые процессы на предприятии
Есть целая куча скриптов запускающихся по крону и каждый отрабатывает примерно за одно время
Разобрался с matplotlib и в итоге график будет иметь следующий вид:

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

Comments

[Сергей Соколов]

мало условий. Так-то просто выстроить их в одну линию и зациклить.

[Xymis]

Сергей Соколов, не подходит, так как каждый скрипт должен отработать 1 раз в течении суток

[Pavel Shvedov]

Xymis, выстроить в одну линию, и вызывать все 1 раз в сутки по крону

[Дмитрий Шицков]

Это учебная задача? Если нет, то почему бы не отдать исполнение этих задач какому-нибудь Airflow, ограничив в нем параллелизм для исполняемых задач.

Все скрипты можно выстроить друг за другом и выполнить 1 раз в сутки всю цепочку. Не вижу противоречий ни с одним из указанных в вопросе ограничивающих факторов. Видимо, есть все-таки еще критерии? Вроде того, что скрипт не должен стартовать позже чем N минут от назначенного времени? Что-то еще?

[Xymis]

На графике случайные данные
Суммарное время работы всех скриптов превышает 24 часа, всегда будет параллельное выполнение нескольких скриптов
Задача автоматизировать оптимизацию и прийти к результату при котором в один момент времени будет выполнятся минимум скриптов, но чтоб выполнялись они почти весь день
Сейчас собираю данные и уже вижу, что есть моменты, когда одновременно работает 15 скриптов, а есть пустые окна с простоем вплоть до часа

[Сергей Соколов]

проявляются подробности:

каждый скрипт должен отработать 1 раз в течении суток

Суммарное время работы всех скриптов превышает 24 часа, всегда будет параллельное выполнение нескольких скриптов

Суточная нагрузка постоянна, или скрипты могут в любой момент добавляться / удаляться из «пула» ?

[Xymis]

Сергей Соколов в целом постоянна
В среднем добавляем один скрипт в crontab в месяц
Так что суточная нагрузка постоянна

[Сергей Соколов]

Xymis, похоже на стандартную «задачу об упаковке» (bin packing) — требуется так расставить эти отрезки в рамках суток, чтобы высота была минимальна, т.е. они максимально плотно улеглись в минимум строк. В общем случае решается полным перебором.

[d'Ivan]

Сергей Соколов,

похоже на стандартную «задачу об упаковке» (bin packing)

У меня была ровно та же мысль.

Answer 1

[dmshar]

А в чем проблема?
1. Выбрать некоторое множество скриптов так, что-бы сумма времен их работы была максимально близка но меньше 24 часов.
2. Выбранные скрипты формируют отдельную последовательность скриптов. Выбросить выбранные скрипты из рассматриваемого пула.
3. Если пул скриптов не пуст - перейти к п.1. В противном случае - закончить.
Получаем некое количество последовательностей скриптов. Каждая такая последовательность запускается параллельно и независимо от других. Элементы в каждой из этих последовательностей можно запускать в произвольном порядке.
Количество таких последовательностей - минимально возможное. А следовательно, минимально и количество скриптов, которые будут работать параллельно.

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

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